中国石油大学《数据结构》复习题及答案

A?0B??1C?0?D?0E?1?F??000100?01000??00111??00000? 10100??10010??其中顶点A的入度为2，出度为1；

其中顶点B的入度为2，出度为2； 其中顶点C的入度为1，出度为3； 36. 终点 b c d e f vj S 37.

答案： (1) 4

(2)算法功能：统计单词的个数。 38.

答案：

（1） e，d，c，b，a

（2） 将队列里的值反转 39.

答案：

（1）第一趟（pass = 0）19 15 18 16 17 12 13 10 （2）第二趟（pass = 1）19 15 16 18 12 17 10 13 40.

答案：

（1）NULL （2）p->next=H[j] p=q 41.

答案: 最短路径求解过程 6 (a,b) 3 (a,c) ? ? ? c {a,c} 5 (a,c,b) 6 (a,c,d) 7 (a,c,e) ? b {a,c,b} 6 (a,c,d) 7 (a,c,e) ? d {a,c,d} 7 (a,c,e) 9 (a,c,d,f) e {a,c,e} 9 (a,c,d,f) f {a,c,d,f} 答案：

21

（1）pre->next=pb （2）pre->next=pa （3）pre->next=pb 42.

43.

答案：

（1）(i==k) return; （2）i+1 （3）i-1 44.

答案：

(1)a[i]=t (2)(i=2;i<=n;i+=2) (3)flag

四、算法设计题（本大题共2小题，每小题10分，共20分） 8. 参考答案：

void invent(Lnode *head) {

Lnode *p,*q;

if(!head->next) return ERROR;

p=head->next; q=p->next; p->next =NULL; while(q)

{p=q; q=q->next; p->next=head->next; head->next=p;} }

9. 参考答案：

void Inverse(ElemType arr[],int n) {

SeqStack *s; int i;

InitStack(&s);

for(i=0;i

for(i=0;i

int twochild(Btree *b) { int num1,num2;

if (b==NULL) return 0; else

{ num1=twochild1(b->left);

答案：

(1）top==-1 （2）top=graph[j].count （3）graph[k].count==0

22

num2=twochild1(b->right);

if ( b->left!=NULL&&b->right!=NULL) return (num1+num2+1); else return (num1+num2); }

}

11. 参考答案：

（1）分两种情况讨论 ①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直到找到一个没有左孩子的节点为止，则该结点为*px在中序序列中的后继； ②当*px的右孩子为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点为*px在中序序列中的后继。 （2）BinTree f34(BinTree px) { BinTree q=px->rchild; if(q!=NULL){//沿左孩子往下查找 px=q; while(px->lchild!=NULL) px=px->lchild;

}

else{//沿双亲指针链向上查找 while(px!=NULL && px->rchild==q){ q=px; px=px->parent;

} }

return px;//返回所找到的中序序列后继结点的指针 //或者无后继结点时返回空指针 }

12. 参考答案：

void AllSPdfs(AdjList g,vertype u,vertype v)

{ //求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v)

int top=0,s[];

s[++top]=u; visited[u]=1; while (top>0 || p) {

p=g[s[top]].firstarc; //第一个邻接点。

while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。 if (p==null) top--; //退栈。 else {

i=p->adjvex; //取邻接点（编号）。

if (i==v) //找到从u到v的一条简单路径，输出。 {

23

for (k=1;k<=top;k++)

printf( \

else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else

}//while

}// AllSPdfs

13. 参考答案：

int outdegree(adjlist adj,int v) { int degree=0; edgenode *p; p=adj[v].link; while(p!=NULL) { degree++; p=p->next; }

return degree; }

14. 参考答案：

//二叉树的二叉链表表示 typedef struct BINTREENODE { ElemType data;

struct BINTREENODE *lchild, rchild; } BinNode,*BinTree //答对给2分 int BsBtr(BinTree t, BinTree pre, int flag) { //判别给定的二叉树是否为二叉排序树

pre =NULL; flag=TRUE; if (t && flag)

{ BSBtr(t->lchild, pre, flag);

if (pre = = NULL) { flag=TRUE；pre=t; } else

if(pre->key < t->key) //比较t 与中序直接前驱pre的大小

{ flag=TRUE; pre=t;} //pre与t有序

else flag=FALSE; //pre与t无序

}//if

BSBtr(t->rchild,pre,flag);

24

}//BSBtr

25