发布时间 : 星期一 文章南邮通达2015数据结构B刷题试题及答案更新完毕开始阅读58edaf846c85ec3a86c2c560
三、算法设计题(22分)
1． 设计在链式存储结构上合并排序的算法。 设计在链式存储结构上合并排序的算法。
void mergelklist(lklist *ha,lklist *hb,lklist *&hc) {
lklist *s=hc=0;
while(ha!=0 && hb!=0)
if(ha->data
else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; }
2． 设计在二叉排序树上查找结点X的算法。 设计在二叉排序树上查找结点X的算法。
bitree *bstsearch1(bitree *t, int key) {
bitree *p=t;
while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild;
return(0); }
3． 设关键字序列(k1，k2，?，kn-1)是堆，设计算法将关键字序列(k1，k2，?，
kn-1，x)调整为堆。
设关键字序列(k1，k2，?，kn-1)是堆，设计算法将关键字序列(k1，k2，?，kn-1，x)调整为堆。
void adjustheap(int r[ ],int n) {
int j=n,i=j/2,temp=r[j-1];
while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp; }
37
数据结构试卷（一）参考答案
一、 选择题（每题2分，共20分）
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 二、填空题（每空1分，共26分）
1. 正确性 易读性 强壮性 高效率 2. O(n)
3. 9 3 3
38
10.A
4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路
8. n(n-1)/2 n(n-1)
9. （12，40） （ ） （74） （23,55，63） 10. 增加1 11. O(log2n) O(nlog2n) 12. 归并
三、计算题（每题6分，共24分）
1. 线性表为：（78，50，40，60，34，90）
?01110??10101????11011???10101????2. 邻接矩阵：?01110? 邻接表如图11所示：
图11
3. 用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 见图12 2 4 4 2 2 2 2 图12 4 4 5 4 5 4 5 8 8 3
2
3 5
4 8 四、 读算法（每题7分，共14分） 1. （1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 2. 递归地后序遍历链式存储的二叉树。
39
五、 法填空（每空2分，共8 分） true BST->left BST->right 六、 编写算法（8分）
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)
{ if (P->data==x) i++; p=p->next;
}//while, 出循环时i中的值即为x结点个数 return i; }//CountX
数据结构试卷（二）参考答案
一、选择题 1.D
2.B
3.C
4.A
5.A
6.C
7.B
8.C
二、填空题
1. 构造一个好的HASH函数，确定解决冲突的方法 2. stack.top++，stack.s[stack.top]=x 3. 有序
4. O(n2)，O(nlog2n) 5. N0-1，2N0+N1 6. d/2
7. (31，38，54，56，75，80，55，63) 8. (1，3，4，5，2)，(1，3，2，4，5)
三、应用题
1. (22，40，45，48，80，78)，(40，45，48，80，22，78) 2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9
40