北航计算机研究生入学考试数据结构 - CSDN文库

5星 · 超过95%的资源需积分: 20 189 浏览量更新于2023-03-16 评论 1 收藏 26KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

2005 年北航硕士研究生入学考试"数据结构"试题与答案

一、（本题 10 分）

 若散列函数为 H(key)=i MOD 7，其中，i 为关键字 key 的第一个字母在英文字母表中

的序号，并采用线性探测再散列法处理冲突。请画出在一个初始状态为空、地址域为[0‥

6]的散列表中依次插入下列关键字值 MON,TUE,WED,THU,FRI,SAT,SUN 以后的散列表。

二、算法设计（本题 10 分）

所谓二叉树等价，是指它们不仅具有相同的拓扑结构，而且对应结点中包含相同的数据

信息。假设二叉树采用二叉链表存储结构，链结点构造为（lchild data rchild），请写一

递归算法，判断根结点指针分别为 T1 与 T2 的两棵二叉树是否等价。若它们等价，算法返

回 1，否则返回 0。（说明:写成非递归算法不得分）

三、算法设计（本题 10 分）

已知一具有 n 个顶点的有向图 G=(V,E)采用邻接表存储方法，请写一算法，检查任意给

定序列 v1,v2,…,vn(vi∈V,1≤i≤n)是否为该有向图的一个拓扑序列。若是，算法给出信

息 1，否则，给出信息 0。

答案:

一、

 01 2 3 4 5 6

 TUE THUWED FRI SUN SAT MON

二、

int EQUAL(BTREE T1,BTREE T2)

{

 if(!T1 && !T2)

 return 1;    /* 两棵二叉树均为空 */

 if(T1 && T2

 && T1->data==T2->data   /* 对应结点的数据相同 */

 && EQUAL(T1->lchild,T2->lchild)  /* 并且左子树等价 */

 && EQUAL(T1->rchild,T2->rchild))/* 并且右子树等价 */

  return 1;

return 0;     /* 二叉树不等价 */

}

三、

int TOPOTEST(TOPOVLink G[],vertype V[],int n)

{

Elink *p;

int i,k;

for(i=0;i<n;i++){

  for(k=0;k<n;k++){

  if(G[k].vertex==V[i]){ /* 若顶点 V[i]是 G 中的顶点 */

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论1

zuozhong2007

2013-01-03

对于考北航的同学，非常有帮助，非常感谢！

duanlianvip

粉丝: 179
资源: 3

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈