十套数据结构试题及答案

else { for(i=start-1,j=0; i

}

3. 设计求结点在二叉排序树中层次的算法。

int lev=0;

typedef struct node{int key; struct node *lchild,*rchild;}bitree; void level(bitree *bt,int x) {

if (bt!=0)

{lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);} }

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

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

二、判断题

1．对 2．错 3．对 4．错 5．错 6．对 7．对 8．对 9．对 10．对

三、填空题

1. (49，13，27，50，76，38，65，97)

2. t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k) 3. p->next=s

4. head->rlink，p->llink 5. CABD 6. 1，16 7. 0

8. (13，27，38，50，76，49，65，97) 9. n-1 10. 50

四、算法设计题

1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

void countnode(bitree *bt,int &count) {

if(bt!=0)

{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);}

37

}

2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix;

typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) {

int i,j; glinklistnode *p;

for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) {

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p;

p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; }

}

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

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

二、填空题

1. p->next，s->data 2. 50 3. m-1 4. 6，8 5. 快速，堆 6. 19/7 7. CBDA 8. 6

9. (24，65，33，80，70，56，48) 10. 8

三、判断题

1．错 2．对 3．对 4．对 5．错 6．错 7．对 8．对 9．错 10．对

38

四、算法设计题

1． 设计计算二叉树中所有结点值之和的算法。 void sum(bitree *bt,int &s) {

if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} }

2． 设计将所有奇数移到所有偶数之前的算法。 void quickpass(int r[], int s, int t) {

int i=s,j=t,x=r[s]; while(i

while (i

r[i]=x; }

3． 设计判断单链表中元素是否是递增的算法。 int isriselk(lklist *head) {

if(head==0||head->next==0) return(1);else

for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1);

}

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

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

二、填空题 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)

6．D 12．D

39

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

40