发布时间 : 星期六 文章十套数据结构试题及答案更新完毕开始阅读
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->data 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