南邮通达2015数据结构B刷题试题及答案

三、算法设计题(22分)

1． 设计在链式存储结构上合并排序的算法。 设计在链式存储结构上合并排序的算法。

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

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0) hc=s=ha; else {s->next=ha; s=ha;};ha=ha->next;}

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