数据结构试题(8)

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

一、选择题 1．A 2．D 3．B 4．B 5．B 6．D 7．A 8．D 9．D 10．C 11．B 12．D

二、填空题 1. 4，10

2. O(nlog2n)，O(n2) 3. n 4. 1，2 5. n(m-1)+1 6. q->next

7. 线性结构，树型结构，图型结构 8. O(n2)， O(n+e) 9. 8/3

10. (38，13，27，10，65，76，97) 11. (10，13，27，76，65，97，38) 12. 124653

13. struct node *rchild，bt=0，createbitree(bt->lchild) 14. lklist，q=p

三、算法设计题

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的算法。

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)调整为堆。

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; }

36