数据结构试卷（七）参考答案
一、选择题 1．B 2．B 6．A 7．C
二、判断题
3．C 8．C
4．B 9．B
5．B 10．D
1．对 2．对 6．对 7．对
三、填空题
1. s->left=p，p->right 2. 3. 4. 5. 6.
3．对 8．错 4．对 9．错 5．对 10．错
n(n-1)，n(n-1)/2 n/2
开放定址法，链地址法 14
2h-1，2h-1
7. (12，24，35，27，18，26) 8. (12，18，24，27，35，26) 9. 5
10. i 四、算法设计题 1. 设计在链式结构上实现简单选择排序算法。 void simpleselectsorlklist(lklist *&head) { lklist *p,*q,*s; int min,t; if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) { min=q->data; s=q; for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } } 2. 设计在顺序存储结构上实现求子串算法。 void substring(char s[ ], long start, long count, char t[ ]) { long i,j,length=strlen(s); if (start<1 || start>length) printf(\ else if (start+count-1>length) printf(\ 36 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 8．C 4．B 9．A 5．B 10．A 6．C 7．B 二、判断题 1．对 2．错 6．对 7．对 3．对 8．对 4．错 9．对 5．错 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 6．D 7．C 11．C 12．C 二、填空题 1. p->next，s->data 2. 3. 4. 5. 50 m-1 6，8 快速，堆 3．A 8．B 13．D 4．C 9．C 14．A 5．D 10．A 15．A 6. 19/7 7. CBDA 8. 6 9. (24，65，33，80，70，56，48) 10. 8 三、判断题 1．错 6．错 2．对 7．对 3．对 8．对 4．对 9．错 5．错 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 7．A 2．D 8．D 3．B 9．D 4．B 10．C 5．B 11．B 6．D 12．D 二、填空题 1. 4，10 2. 3. 4. 5. O(nlog2n)，O(n2) n 1，2 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) 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
十套数据结构试题及答案
