严蔚敏版数据结构习题及参考答案1

{ root=s->data[s->top]*2+1; s->top--;

} }

}

2. 解答：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。 levelorder (BiTree *t) //按层次遍历二叉树t { BiTree *que[maxnum];

int rear,front; if (t!=NULL)

{ front=0; //置空队列 rear=1; que[1]=t; do

{ front=front%maxsize+1; //出队 t=que[front]; printf(t->data);

if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1;

que[rear]=t->lchild;

}

if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild;

}

}while (rear= =front); //队列为空时结束 }

}

3. 解答：设该线索二叉树类型为bithptr，包含5个域：lchild，ltag，data，rchild，rtag。 insert(p, s) //将s结点作为p的右子树插入 BiThrNode *p,*s; { BiThrNode *q;

if (p->rtag= =1) //无右子树，则有右线索 { s->rchild=p->rchild; s->rtag=1; p->rchild=s;

p->rtag=0; } else

{ q=p->rchild;

while(q->ltag= =0) //查找p所指结点中序后继，即为其右子树中最左下的结点

q=q->lchild;

q->lchild=p->rchild; s->rtag=0; p->rchild=s; }

s->lchild=p; //将s结点的左线索指向p结点 s->ltag=1;

}

4. 解答：利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。 parentjudge(t,n) BiTree *t; int n;

{ BiTree *que[maxnum];

int front,rear; BiTree *parent; parent=NULL; if (t)

if (t->data= =n)

printf(“no parent!”); //n是根结点，无双亲 else

{ front=0; //初始化队列

rear=1;

que[1]=t; //根结点进队 do

{ front=front%maxsize+1; t=que[front];

if((t->lchild->data= =n)|| (t->rchild->data= =n)) //结点n有双亲 { parent=t; front=rear;

printf(“parent”,t->data);

}

else

{ if (t->lchild!=NULL) //左子树的根结点入队

{ rear=rear%maxsize+1; }

}while(rear= =front); //队空时结束 }

if (parent = =NULL) printf(“结点不存在”);

}

if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; }

que[rear]=t->lchild;

}

习题6

一、单项选择题

1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为( )。

A. s A. s A. n A. n

B. s-1 B. s-1 B. e

C. s+1 C. s+1

D. n D. 2s

2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( )。 3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( )。

C. n+e

D. 2e D. n(n+1)/2

4. 在一个具有n个顶点的无向完全图中，所含的边数为( )。

B. n(n-1)

C. n(n-1)/2

5. 在一个具有n个顶点的有向完全图中，所含的边数为( )。

A. n A. k A. 0

B. n(n-1)

C. n(n-1)/2 D. n(n+1)/2

6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。

B. k+1 C. k+2 D. 2k B. 1 C. n D. n+1

7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。

8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。

A. k

B. 1 C. k-1 D. k+1

9. 若要把n个顶点连接为一个连通图，则至少需要( )条边。

A. n

个数为( )。

A. n A. n A. n

为( )。

A. n A. 1

数为( )。

A. k1

点数为( )。

A. k1

B. n+1 C. n-1 D. 2n

10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的

B. n?e C. e D. 2?e B. n?e C. e D. 2?e B. n?e

C. e D. 2?e

11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。 12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。

13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少

B. 2n

C. e D. 2e

14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。

B. 2 C. 3 D. 4

15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点

B. k2 C. k1-k2 D. k1+k2

16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结

B. k2 C. k1-k2 D. k1+k2

17. 对于一个无向图，下面( )种说法是正确的。

A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和 C. 每个顶点的入度为0 A. 出边数 B. 入边数

索，得到的顶点序列可能为( )。

A. A,B,C,F,D,E B. A,C,F,D,E,B C. A,B,D,C,F,E D. A,B,D,F,E,C

20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为( )。

A. A,B,C,D,E,F B. A,B,C,F,D,E C. A,B,D,C,E,F D. A,C,B,F,D,E

21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为( )。

A. 1,2,5,4,3 B. 1,2,3,4,5 C. 1,2,5,3,4 D. 1,4,3,2,5

22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为( )。

D. 每个顶点的出度为0 C. 度数

D. 度数减1

18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。

19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜