发布时间 : 星期日 文章数据结构习题更新完毕开始阅读144210a7195f312b3169a5d5
if (P) { ; ; }
;
else {
printf(\ }
3.我们可以借助队列对二叉树进行层次遍历，请补充下列算法。typedef struct BiTNode{ //二叉链表的定义
TElemType data;Struct BiTNode *lchild,*rchild;}BiTNode, *BiTree; typedef BiTNode* ElemType; typedef struct{ QElemType *base; void LevelOrderTraverse(BiTree T) { BiTree p; SqQueue Q; InitQueue(Q); if (T)
{ Q.base[Q.rear]=T;
; while ( ) { p=Q.base[Q.front]; printf(\ ; if ( )
{ Q.base[Q.rear]=p->lchild;
Q.rear=(Q.rear+1)%MAXQSIZE;
int front,rear;}SqQueue;
}
}
if ( )
{ Q.base[Q.rear]=p->rchild;
Q.rear=(Q.rear+1)%MAXQSIZE;
} } } }
4．分别设计出先序、中序和后序遍历二叉树的非递归算法。
37
5．分别讨论先序、中序和后序线索化二叉树中前驱和后继的求解。 6．设计一个遍历先序线索二叉树的非递归算法，要求不许用栈。
7．设计算法将值为x的结点作为右子树的（后序序列的）第一个结点的左孩子插入到后序线索二叉树中。 8．分别设计出先序、中序和后序线索化算法。
9．设计算法以实现将以二叉链表形式存储的树（森林）转换为对应的双亲表示形式。
10．已知树（森林）的高度为4，所对应的二叉树的先序序列为ABCDE，请构造出所有满足这一条件的树或森林。
11．设计算法按先序次序输出森林中每个结点的值及其对应的层次数。 12．设计算法以求解森林的高度。
13．设计算法以输出森林中的所有叶子结点的值。 14．设计算法逐层输出森林中的所有结点的值。
15．设计算法以产生哈夫曼树中各叶子结点的哈夫曼编码。
六、简答题
2.说明一棵度为2的树与一棵二叉树之间的区别。
3.试分别画出具有3个结点的树和具有3个结点的二叉树的所有结构图。
38
第七章 图
一、单项选择题
1.n 个顶点的连通图至少有（ ）条边。
A.n-1 B.n C.n+1 D.0 2. 图的广度优先搜索类似于树的（ ）次序遍历。 A. 先根
B. 中根
C. 后根
D. 层次
3．设有向图G的顶点个数为n，则该图最多有（ ）条弧。若G是强连通图，其弧的个数至少为（ ） A.n(n+1)/2 B.n(n-1) C.n(n-1)/2 D.n 4．设有无向图G的顶点个数为n，则该图最多有（ ）条边。 A.n(n+1)/2 B.n(n-1) C.n(n-1)/2 D. n-1 5.若n个顶点的无向图G是连通图，其边的个数至少为（ ） A.n(n+1)/2 B.n(n-1) C.n(n-1)/2 D. n-1 6. 具有n个顶点的有向无环图最多可包含( )条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)
7.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。 A．O（nlog2e） B．O（n+e） C．O(ne) D．O(n2) 8.在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A．3 B．2 C．1 D．1/2
9.在有向图中每个顶点的度等于该顶点的（ ）。 A. 入度 B. 出度 C. 入度与出度之和 10.对下图，不能得到的拓扑序列是( )
D. 入度与出度之差
A.l,2,3,4,5,6,7,8 B.1,5,2,6,3,7,4,8 C.1,2,5,6,3,4,7,8 D.1,2,3,4,8,7,6,5 11．关键路径指AOE网中（ ）
A．从开始结点到完成结点的最长路径 B．最长的回路 C．从开始结点到完成结点的最短路径 D．最短的回路
12．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )
A．e B．2e C．n－e D．n－2e 13．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )
39
2
2
A．O(n) B．O(e) C．O(n+e) D．O(n*e) 14．连通分量是（ ）极大连通子图。 A. 无向图 B. 有向图 C 树 D 图 15．强连通分量是（ ）极大连通子图。 A. 无向图 B. 有向图 C. 树 D. 图
16．有 n 个顶点的无向图的邻接矩阵是用（ ）组存储。 A.n 行 n 列 B. 一维 C. 任意行 n 列 D.n 行任意列 ]
17．有 n 条边的无向图的邻接表存储法中，链边中结点的个数是（ ）个。 A.n B.2n C.n/2 D.n*n
18．一个加权的无向连通图的最小生成树（ ）。
A. 有一棵或多棵 . B. 只有一棵 C. 一定有多棵 D. 可能不存在 19．下列有关图遍历的说法中不正确的是（ ）。 A. 连通图的深度优先搜索是个递增过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法
D. 图 D. 图的遍历要求每个顶点仅被访问一次 20．无向图的邻接矩阵是一个（ ）。
A. 对称矩阵 B 零矩阵 C. 上三角矩阵 D. 对角矩阵 21．下列说法中正确的是（ ）。
A. 一个具有 n 个顶点的无向完全图的边数为 n(n-1) B. 连通图的生成树是该图的一个极大连通子图 C. 图的广度优先搜索是一个递归过程
D. 在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量 22．如果从无向的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。 A. 完全图 B. 连通图 C. 有回路 D. 一棵树
二、填空题
1. n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。
2.具有n个结点的无向图中，有 条边的无向图称为完全图；对于具有n个结点有向图，有 条弧的有向图称为有向完全图。
3.图的遍历的两种搜索方法分别是 和 。
40