数据结构与算法分析—期末复习题及答案

}

10. 10.???? 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语

句。

struct record{int key; int others;};

int bisearch(struct record r[ ], int k)

{

int low=0,mid,high=n-1;

while(low<=high)

{

________________________________;

if(r[mid].key==k) return(mid+1); else if(____________) high=mid-1;else low=mid+1;

}

return(0);

}

三、应用题(24分)

1. 1.?????? 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序

列为ABDEC，要求给出该二叉树的的后序遍历序列。

2. 2.?????? 设无向图G（如右图所示），给出该图的最小生成树

上边的集合并计算最小生成树各边上的权值之和。

3. 3.?????? 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求

计算出成功查找时的平均查找长度。

4. 4.?????? 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列

为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

四、算法设计题(16分)

1． 1．?? 设计判断两个二叉树是否相同的算法。

2． 2．?? 设计两个有序单链表的合并排序算法。

数据结构试卷（五）参考答案

一、选择题

1．A 2．B 3．A 4．A 5．D

6．B 7．B 8．B 9．C 10．C

二、填空题

1. 1.???????? top1+1=top2

2. 2.???????? 可以随机访问到任一个顶点的简单链表

3. 3.???????? i(i+1)/2+j-1

4. 4.???????? FILO，FIFO

5. 5.???????? ABDECF，DBEAFC，DEBFCA

6. 6.???????? 8，64

7. 7.???????? 出度，入度

8. 8.???????? ki<=k2i && ki<=k2i+1

9. 9.???????? n-i，r[j+1]=r[j]

10. 10.???? mid=(low+high)/2，r[mid].key>k

三、应用题

1. 1.???????? DEBCA

2. 2.???????? E={(1,5),(5,2),(5,3),(3,4)},W=10

3. 3.???????? ASL=(1*1+2*2+3*4)/7=17/7

4. 4.???????? ASL1=7/6，ASL2=4/3

四、算法设计题

1. 1.???????? 设计判断两个二叉树是否相同的算法。

typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;

int judgebitree(bitree *bt1,bitree *bt2)

{

if (bt1==0 && bt2==0) return(1);

else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0);

else

return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));

}

2. 2.???????? 设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc)

{