套数据结构试题及答案 

四、算法设计题

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

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

if(bt!=0)

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

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 [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．对 四、算法设计题

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

(nlog2n)，O(n2) ，2 (m-1)+1 >next

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

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

node *rchild，bt=0，createbitree(bt->lchild) ，q=p

6．D 12．D

三、算法设计题

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