数据结构过程考核试卷2（提交版）

合肥学院20 13 至20 14 学年第 2 学期

数据结构 课程过程考核试卷（2）

计科 系 级 专业 学号 姓名

题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 总 分

得分 一、选择题：（2分×15=30分）

1.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。 A.98 B.99 C.50 D.48

2.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是________。 A 8 B 3 C 5 D 9

3.在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为________。 A.e B.2e C.n2-e D.n2-2e

4.图的深度优先遍历类似于二叉树的_______。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 5.堆的形状是一棵_______。

A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树

6．二叉树中第5层上的结点个数最多为________。 A.8 B.15 C.16 D.32

7．对于哈希函数H(key)=key，被称为同义词的关键字是_______ A．35和41 B.23和39 C.15和44 D.25和51

8. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。 A、 24 B、 48 C、 72 D、 53

9、设有6个结点的无向图，该图至少应有______条边才能确保是一个连通图。 A、5 B、6 C、7 D、8

10. 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为______。

A、 BADC B、 BCDA C、 CDAB D、CBDA

11．设某完全无向图中有n个顶点，则该完全无向图中有______条边。 A、 n(n-1)/2 B、 n(n-1) C、 n2 D、 n2-1

12．设某棵二叉树中有2000个结点，则该二叉树的最小高度为______。 A、 9 B、 10 C、 11 D、 12

13．设某有向图中有n个顶点，则该有向图对应的邻接表中有______个表头结点。 A、 n-1 B、 n C、n+1 D、2n-1

14．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为______。 A、 abedfc B、 acfebd C、 aebdfc D、 aedfcb

15. 设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6；r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是______。

A、 8 B 、3 C、 5 D 、9 二、填空题：（1分×20=20分）

1、稀疏矩阵可用_________进行压缩存储，存储时需存储非零元的________、________、________。

2、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为__________。 3、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个___________。 4、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是_____________。

5、高度为k的二叉树具有的结点数目，最少为_____,最多为_____。 6、在含100个结点的完全二叉树，叶子结点的个数为_______。

7、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用________遍历法。

8、设有10个值，构成哈夫曼树，则该哈夫曼树共有______个结点。

9、从树中一个结点到另一个结点之间的分支构成这两个结点之间的____________。 10、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________。 11、有一个n个顶点的有向完全图的弧数_____________。

12、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____ _______。

13、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的____________遍历。 14、若图的邻接矩阵是对称矩阵，则该图一定是________________。

15、结点关键字转换为该结点存储单元地址的函数H称为_____________或叫__________。 答案：36、三元组，行号，列号，值

37、三对角矩阵48、线索 49、k，2k-1 51、50

63、中序 65、19 66、路径71、对称矩阵72、n(n-1) 77、连通 78、层次 79、无向图 86、哈希函数，散列函数 三、判断题：（1分×20=20分）

1、对一个堆按层次遍历，不一定能得到一个有序序列。（ ） 2、哈夫曼树一定是满二叉树。（ ）

3、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（ ） 4、非空二叉排序树的任意一棵子树也是二叉排序树。（ ）

5、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（ ）

6、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（ ）

7、若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（ ）

8、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（ ） 9、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（ ） 10、在n个结点的元向图中,若边数在于n-1,则该图必是连通图。（ ） 11、在完全二叉树中,若某结点无左孩子,则它必是叶结点。（ ）

12、若一个有向图的邻接矩阵中,对角线以下元素均为0,则该图的拓扑有序序列必定存在。（ ）√

13、树的带权路径长度最小的二叉树中必定没有度为1的结点。（ ） 14、二叉树可以用0≤度≤2的有序树来表示。（ ） 15、一组权值，可以唯一构造出一棵哈夫曼树。( ) 16、101，88，46，70，34，39，45，58，66，10）是堆；（ ） 17、将一棵树转换成二叉树后，根结点没有左子树；（ ） 18、用树的前序遍历和中序遍历可以导出树的后序遍历；（ ）

19、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（ ）

20、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（ ） 四、应用题：（5分×4=20分）

1．已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

2.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。

3．下图所示的森林：

(1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； 3）将此森林转换为相应的二叉树；

ABDCEFIGHJ(b)K(a)

4、依次输入表(30，15，28，20，24，10，12，68，35，50，46)中的元素，构造一棵二叉排序树，试

画出其构造过程。

五、算法设计题：（5分×2 =10分）

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

2. 设计判断两个二叉树是否相同的算法。