过程考核2

软外学院 过程考核二

科目：数据结构 命题教师：宫明明 时间：2014年12月 试卷类型：开卷 专业：软件技术

姓名： 学号： 成绩：

一、单选题：从供选择的答案中选出正确的答案，将其编号填入括号中。（2'*20）

1．关于二叉树的下列说法正确的是 (1)。

A．二叉树的度为2 B．二叉树的度可以小于2 C．每一个结点的度都为2 D．至少有一个结点的度为2

2．设深度为h(h>0)的二叉树中只有度为0和度为2的结点，则此二叉树中所含的结点总数至少为 （2）。 A．2h B．2h-1 C．2h+1 D．h+1 3．在树中，若结点A有4个兄弟，而且B是A的双亲，则B的度为 (3) 。 A．3 B．4 C．5 D．6 4．若一棵完全二叉树中某结点无左孩子，则该结点一定是 (4) 。

A.度为1的结点 B．度为2的结点 C．分支结点 D．叶子结点 5．深度为k的完全二叉树至多有 C(5) 个结点，至少有 B(6) 个结点。

k-1k-1 kk

A．2-1 B．2 C．2-1 D．2 6．前序序列为ABC的不同二叉树有 (7) 种不同形态。 A．3 B．4 C．5 D．6

7. 将一棵树转换成二叉树，树的前根序列与其对应的二叉树的 A(8) 相等。树的后根序列与其对应的二叉树的 (9)B 相同。

A．前序序列 B．中序序列 C．后序序列 D．层次序列 8.下面关于图的存储结构的叙述中正确的是 (10) 。

A．用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关 B．用邻接矩阵存储图占用空间大小只与图中边数有关，而与顶点数无关 C．用邻接表存储图占用空间大小只与图中顶点数有关，而与边数无关 D．用邻接表存储图占用空大小只与图中边数有关，而与顶点数无关 9．下面关于对图的操作的说法不正确的是 (11) 。 A．寻找关键路径是关于带权有向图的操作 B．寻找关键路径是关于带权无向图的操作 C．连通图的生成树不一定是惟一的

D．带权无向图的最小生成树不一定是惟一的

10．下面的各种图中，哪个图的邻接矩阵一定是对称的 (12) 。 A．AOE网 B．AOV网 C．无向图 D．有向图 11．在AOE网中关于关键路径叙述正确的是 (13) 。

A．从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间 B．从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最短时间 C．从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最长时间 D．从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所需的最长时间

1

12．一个具有n个顶点e条边的有向图中，所有顶点的度数之和等于 （14） 。

A．n B．2n C．e D．2e

13．具有8个顶点的无向图最多有 (15) 条边。

A．8 B．28 C．56 D．72

14．具有8个顶点的有向图最多有 (16) 条边。

A．8 B．28 C．56 D．78

15．深度优先遍历类似于二叉树的 (17) 。

A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 16．广度优先遍历类似于二叉树的 (18) 。

A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 17．下列关于连通图的BFS和DFS生成树高度论述正确的是 （19）。

A．BFS生成树高度DFS生成树的高度 D．BFS生成树高度≥DFS生成树的高度

18．G是一个非连通无向图，共有28条，则该图至少有解 (20) 个顶点。 A．7 B．8 C．9 D.10

二、综合题

1．已知二叉树的层次遍历序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树。（10分） 2．假定用于通信的电文仅由8个字母a，b，c，d，e, f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，13，36，4。试画出哈夫曼树，为这8个字母设计不等长哈夫曼编码，并输出该电文的总码数。（10分） 3．试将森林 F={ T1,T2,T3,T4 }转换为一棵二叉树。（10分）

T1 T2 T3 T4

4．用prim算法找出下图网络的最小生成树。（10分）

5. 已知带权有向图如右图所示，要求：（20分）

(1)给出图G的邻接矩阵； (2)给出图的邻接表

(3)求从顶点a出发到其余各顶点的最短路径。

2