1、数据结构导论自考题模拟 12 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.树形结构中，度为 0 的结点称为_（分数：2.00）A.树根B.叶子C.路径D.二叉树2.具有 n 个结点的完全二叉树的深度是_ A B C D （分数：2.00）A.B.C.D.3.深度为 9 的二叉树最多拥有的结点数目是_（分数：2.00）A.255B.512C.256D.5114.若一棵度为 8 的树有 9 个度为 1 的结点，有 8 个度为 2 的结点，有 7 个度为 3 的结点，有 6 个度为 4 的结点，有 5 个度为 5 的结点，有 4 个度为
2、6 的结点，有 3 个度为 7 的结点，有 2 个度为 8 的结点，该树一共有多少个叶子结点_（分数：2.00）A.44B.58C.113D.1155.在一个二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序_（分数：2.00）A.完全相同B.先序序列和中序序列相同，而与后序序列不同C.都不相同D.中序序列和后序序列相同，而与先序序列不同6.若一颗二叉树有 2013 个结点，且无度为 1 的结点，则叶子结点的个数为_（分数：2.00）A.1005B.1007C.1004D.10067.已知二叉树的先序遍历序列为 ABCFHIDGJE，中序遍历序列为 AHIFCJGDEB，则其后
3、序遍历序列为_（分数：2.00）A.IHFJGEDBCAB.IHFCBJGEDAC.IHFJGEDCBAD.HIFJGEDCBA8.对于给出的一组权值 W=10，15，16，22，31，通过哈夫曼算法求出的哈夫曼树的 WPL 为_（分数：2.00）A.200B.220C.213D.2109.设 n 0 为哈夫曼树的叶子结点数目，则该哈夫曼树共有多少个结点_（分数：2.00）A.n0+1B.2n0+1C.2n0D.2n0-110.图的广度优先搜索使用的数据结构是_（分数：2.00）A.队列B树C栈D.集合11.设有 7 个结点的无向图，该图至少应有几个边才能保证是一个连通图_（分数：2.00）A
4、.5B.6C.7D.812.无向图中，所有顶点的度数之和是所有边数的_（分数：2.00）A.0.5 倍B.1 倍C.2 倍D.4 倍13.下图所示的无向图中，从顶点 1 出发按照 DFS 规则遍历得到的序列为_ （分数：2.00）A.ABCDEFHIGB.ABGEFCHDIC.ABGEFCHDID.ABEGCFDHI14.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的_（分数：2.00）A.按层次遍历B.中序遍历C.后序遍历D.先序遍历15.对于一个具有 n 个顶点和 e 条边的有向图，在邻接表表示图时，拓扑排序算法时间复杂度为_ A.O(n) B.O(n+e) C.O(n2) D
5、.O(n*e)（分数：2.00）A.B.C.D.二、填空题(总题数：13，分数：26.00)16.二叉树有不同的链式存储结构，其中最常用的是 1 和 2。 （分数：2.00）17.结点的层次是从 1 开始算起的，根的层次是 2。 （分数：2.00）18.深度为 k(k1)且有 2 k -1 个结点的二叉树称为 1。 （分数：2.00）19.一棵树上的任何结点(不包括根本身)称为根的 1。若 B 是 A 的子孙，则称 A 是 B 的 2。 （分数：2.00）20.已知完全二叉树的第 7 层有 20 个结点，则整个完全二叉树的叶子结点数是 1。 （分数：2.00）21.若二叉树的一个叶子是某子树的
6、先序遍历序列中的第一个结点，则它必是孩子树的后序遍历序列中的 1 个结点。 （分数：2.00）22.满二叉树 1 是完全二叉树，完全二叉树 2 是满二叉树。 （分数：2.00）23.由 1 转换成二叉树时，其根结点的右子树总是空的，其与二叉树可相互转换。 （分数：2.00）24.设 a，b 是图 G 中的两个顶点，则(a，b)与(b，a)被认为是 1，但是a，b和b，a是 2 的两条弧。 （分数：2.00）25.若无向图 G 中有 n 个顶点 m 条边，采用邻接矩阵存储，则该矩阵中非零元素的个数为 1。 （分数：2.00）26.对含有 n 个结点，e 条边的无向连通图，利用 Prim 算法生成
7、最小生成树的时间复杂度为 1。 （分数：2.00）27.一个连通图的生成树是含有连通图的全部顶点的一个 1。 （分数：2.00）28.一个有向图 G 中若有弧a，b，b，c，a，c，则在图 G 的拓扑序列中，顶点 a，b 和 c 的先后关系为 1。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.画出 3 个结点的二叉树的所有不同形态。 （分数：6.00）30.分别画出下图所示二叉树的二叉链表、三叉链表。 （分数：6.00）31.已知无向图 G 的邻接矩阵如下图所示，假设对其元素的访问必须从左至右，写出从 v 0 开始的深度优先搜索序列。 （分数：6.00）32.求下图的最小
8、生成树。 （分数：6.00）33.根据图 G 的邻接矩阵，求从顶点 v 0 到其余各顶点的最短路径及长度(给出求解过程)。 （分数：6.00）四、算法设计题(总题数：2，分数：14.00)34.试分别写出二叉树的先序遍历和中序遍历的递归算法。 （分数：7.00）_35.以二叉链表作为存储结构，编写求二叉树叶子数的算法。 （分数：7.00）_数据结构导论自考题模拟 12 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.树形结构中，度为 0 的结点称为_（分数：2.00）A.树根B.叶子 C.路径D.二叉树解析：考点 叶子的定义 解析 度为
9、0 的结点称为叶子或者终端结点。2.具有 n 个结点的完全二叉树的深度是_ A B C D （分数：2.00）A.B.C. D.解析：考点 完全二叉树的深度 解析 具有 n 个结点的完全二叉树的深度是(log 2 n)+1。3.深度为 9 的二叉树最多拥有的结点数目是_（分数：2.00）A.255B.512C.256D.511 解析：考点 二叉树的性质 解析 深度为 k(k1)的二叉树至多有 2 k -1 个结点。4.若一棵度为 8 的树有 9 个度为 1 的结点，有 8 个度为 2 的结点，有 7 个度为 3 的结点，有 6 个度为 4 的结点，有 5 个度为 5 的结点，有 4 个度为 6
10、 的结点，有 3 个度为 7 的结点，有 2 个度为 8 的结点，该树一共有多少个叶子结点_（分数：2.00）A.44B.58C.113 D.115解析：考点 树的性质 解析 任意一棵树的结点个数等于所有结点的出度之和加一，所以叶子结点个数=(1*9+2*8+3*7+4*6+5*5+6*4+7*3+8*2)-(9+8+7+6+5+4+3+2)+1=113。5.在一个二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序_（分数：2.00）A.完全相同 B.先序序列和中序序列相同，而与后序序列不同C.都不相同D.中序序列和后序序列相同，而与先序序列不同解析：考点 二叉树在遍历过程中对
11、叶子结点的访问顺序 解析 无论哪种访问顺序，对叶子结点的访问顺序都是先左子树后右子树，先序、中序、后序遍历指的是访问根的顺序。6.若一颗二叉树有 2013 个结点，且无度为 1 的结点，则叶子结点的个数为_（分数：2.00）A.1005B.1007 C.1004D.1006解析：考点 二叉树的性质 3 解析 由二叉树的性质 3 可知，对任意一棵二叉树，若度为零的结点个数为 n 0 ，度为 2 的结点个数为n 2 ，则 n 0 =n 2 +1，所以有 n 2 =n 0 -1；由于没有度为 1 的结点，所以 n 0 +(n 0 -1)=2013，n 0 =1007。7.已知二叉树的先序遍历序列为
12、ABCFHIDGJE，中序遍历序列为 AHIFCJGDEB，则其后序遍历序列为_（分数：2.00）A.IHFJGEDBCAB.IHFCBJGEDAC.IHFJGEDCBAD.HIFJGEDCBA 解析：考点 由先序遍历序列和中序遍历序列推算后序遍历序列 解析 由先序遍历序列和中序遍历序列推算出二叉树如下图所示，进而进行后序遍历，得出后序遍历序列为 HIFJGEDCBA。 8.对于给出的一组权值 W=10，15，16，22，31，通过哈夫曼算法求出的哈夫曼树的 WPL 为_（分数：2.00）A.200B.220C.213 D.210解析：考点 哈夫曼树和哈夫曼算法 解析 根据一组权值得到哈夫曼树
13、如下图所示，其 WPL=(16+22)2+(10+15)3+312=213。 9.设 n 0 为哈夫曼树的叶子结点数目，则该哈夫曼树共有多少个结点_（分数：2.00）A.n0+1B.2n0+1C.2n0D.2n0-1 解析：考点 哈夫曼树 解析 哈夫曼树虽然带有权值，但是其构形仍然是一个普通的二叉树，且只有度为 2 和度为 0 的结点，所以由二叉树的性质 3 可知，哈夫曼树结点个数 n=2n 0 -1。10.图的广度优先搜索使用的数据结构是_（分数：2.00）A.队列 B树C栈D.集合解析：考点 图的广度优先搜索 解析 图的广度优先搜索使用的数据结构是队列。11.设有 7 个结点的无向图，该图
14、至少应有几个边才能保证是一个连通图_（分数：2.00）A.5B.6 C.7D.8解析：考点 连通图 解析 n 个结点的无向连通图至少有 n-1 条边。12.无向图中，所有顶点的度数之和是所有边数的_（分数：2.00）A.0.5 倍B.1 倍C.2 倍 D.4 倍解析：考点 无向图顶点的度数 解析 无向图顶点的度数就是该顶点相关联的边的数目。即每条边都连接两个结点，一条边对应两个度，故本题答案为 C。13.下图所示的无向图中，从顶点 1 出发按照 DFS 规则遍历得到的序列为_ （分数：2.00）A.ABCDEFHIGB.ABGEFCHDIC.ABGEFCHDID.ABEGCFDHI 解析：考点
15、 图的深度优先搜索 解析 根据 DFS 规则可知，其深度优先遍历序列如下图所示： 14.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的_（分数：2.00）A.按层次遍历 B.中序遍历C.后序遍历D.先序遍历解析：考点 广度优先搜索 解析 广度优先搜索的基本思想是：从图中某个顶点出发，在访问该结点后，依次访问该结点的所有邻接点，然后从这些邻接点按广度优先搜索遍历其他顶点，所以类似于二叉树按层次(同一层，从左到右)的遍历算法。15.对于一个具有 n 个顶点和 e 条边的有向图，在邻接表表示图时，拓扑排序算法时间复杂度为_ A.O(n) B.O(n+e) C.O(n2) D.O(n*e)
16、（分数：2.00）A.B. C.D.解析：考点 图的拓扑排序时间复杂度 解析 对于含有 n 个顶点，e 条弧的有向图 G，在邻接表表示图时，其进行拓扑排序算法的时间复杂度为O(n+e)。二、填空题(总题数：13，分数：26.00)16.二叉树有不同的链式存储结构，其中最常用的是 1 和 2。 （分数：2.00）解析：二叉链表 三叉链表 考点 二叉树的链式存储结构 解析 二叉树有不同的链式存储结构，其中最常用的是二叉链表和三叉链表。17.结点的层次是从 1 开始算起的，根的层次是 2。 （分数：2.00）解析：根 1 考点 结点的层次的定义 解析 结点的层次是从根开始算起的，根的层次是 1。18
17、.深度为 k(k1)且有 2 k -1 个结点的二叉树称为 1。 （分数：2.00）解析：满二叉树 考点 满二叉树的定义 解析 深度为 k(k1)且有 2 k-1 个结点的二叉树称为满二叉树。19.一棵树上的任何结点(不包括根本身)称为根的 1。若 B 是 A 的子孙，则称 A 是 B 的 2。 （分数：2.00）解析：子孙 祖先 考点 树的基本概念 解析 一棵树上的任何结点(不包括根本身)称为根的子孙。若 B 是 A 的子孙，则称 A 是 B 的祖先。20.已知完全二叉树的第 7 层有 20 个结点，则整个完全二叉树的叶子结点数是 1。 （分数：2.00）解析：83 考点 二叉树的性质及完全
18、二叉树的定义 解析 二叉树的性质 1：二叉树第 i 层(i1)上至多有 2 i-1 个结点，第 7 层上最多有 64 个结点，2064，所以此完全二叉树共 7 层，前六层是满二叉树；从满二叉树定义可知前 6 层共有 2 6 -1=63 个结点，所以共有 63+20=83 个结点。21.若二叉树的一个叶子是某子树的先序遍历序列中的第一个结点，则它必是孩子树的后序遍历序列中的 1 个结点。 （分数：2.00）解析：最后一 考点 二叉树的先序遍历和后序遍历算法 解析 二叉树先序遍历的第一个结点，是其后序遍历的最后一个结点。22.满二叉树 1 是完全二叉树，完全二叉树 2 是满二叉树。 （分数：2.0
19、0）解析：一定 不一定 考点 完全二叉树与满二叉树的关系 解析 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。23.由 1 转换成二叉树时，其根结点的右子树总是空的，其与二叉树可相互转换。 （分数：2.00）解析：树 考点 树与二叉树的转换 解析 由树转换成二叉树时，其根结点的右子树总是空的。24.设 a，b 是图 G 中的两个顶点，则(a，b)与(b，a)被认为是 1，但是a，b和b，a是 2 的两条弧。 （分数：2.00）解析：同一条边 不同 考点 有向图与无向图的边 解析 设 a，b 是图 G 中的两个顶点，则(a，b)与(b，a)被认为是同一条边，但是a，b和b，a是不同的两条
20、弧。25.若无向图 G 中有 n 个顶点 m 条边，采用邻接矩阵存储，则该矩阵中非零元素的个数为 1。 （分数：2.00）解析：2m 考点 无向图的邻接矩阵对称性 解析 根据无向图的邻接矩阵对称性，图有 m 条边，则矩阵中非零元素的个数为 2m。26.对含有 n 个结点，e 条边的无向连通图，利用 Prim 算法生成最小生成树的时间复杂度为 1。 （分数：2.00）解析：O(n 2 ) 考点 Prim 算法 解析 对含有 n 个结点，e 条边的无向连通图，利用 Prim 算法生成最小生成树的时间复杂度为 O(n 2 )。27.一个连通图的生成树是含有连通图的全部顶点的一个 1。 （分数：2.0
21、0）解析：极小连通子图 考点 极小连通子图 解析 一个连通图的生成树是含有连通图的全部顶点的一个极小连通子图。28.一个有向图 G 中若有弧a，b，b，c，a，c，则在图 G 的拓扑序列中，顶点 a，b 和 c 的先后关系为 1。 （分数：2.00）解析：abc 考点 图的拓扑排序 解析 由题可知有向图 G 如下： 拓扑排序过程如下： 三、应用题(总题数：5，分数：30.00)29.画出 3 个结点的二叉树的所有不同形态。 （分数：6.00）解析：含有 3 个结点的二叉树的所有不同形态： 30.分别画出下图所示二叉树的二叉链表、三叉链表。 （分数：6.00）解析：二叉链表示意图三叉链表示意图3
22、1.已知无向图 G 的邻接矩阵如下图所示，假设对其元素的访问必须从左至右，写出从 v 0 开始的深度优先搜索序列。 （分数：6.00）解析：v 0 ，v 1 ，v 3 ，v 2 考点 图的深度优先搜索32.求下图的最小生成树。 （分数：6.00）解析：最小生成树如下： 33.根据图 G 的邻接矩阵，求从顶点 v 0 到其余各顶点的最短路径及长度(给出求解过程)。 （分数：6.00）解析：求解过程如下： 步骤 S u dist1 dist2 dist3 dist4 dist5 第 1 步 v 0 6 3 Max_int Max_int Max_int 第 2 步 v 0 ，v 2 v 2 5 3
23、 6 7 Max_int 第 3 步 v 0 ，v 2 ，v 1 v 1 5 3 6 7 Max_int 第 4 步 v 0 ，v 2 ，v 1 ，v 3 v 3 5 3 6 7 9 第 5 步 v 0 ，v 2 ，v 1 ，v 3 ，v 4 v 4 5 3 6 7 9 第 6 步 v 0 ，v 2 ，v 1 ，v 3 ，v 4 ，v 5 v 5 5 3 6 7 9 考点 Dijkstra 算法求最短路径四、算法设计题(总题数：2，分数：14.00)34.试分别写出二叉树的先序遍历和中序遍历的递归算法。 （分数：7.00）_正确答案：()解析：先序遍历递归算法： Void preorder(b
24、itreptr r) if(r!=NULL) visit(r); preorder(r-lchild); preorder(r-rchild); 中序遍历递归算法： Void in order(bitreptr r) if(! -NULL) inorder(r-lchild); visit(r); inoder(r-rchild); 35.以二叉链表作为存储结构，编写求二叉树叶子数的算法。 （分数：7.00）_正确答案：()解析：算法思想：先求左子树的叶子数，再求右子树的叶子数，两者相加就是根结点的叶子数，也就是对应二叉树的叶子数。具体算法如下： int leafcount(BinTree T) if(T=NULL)leaf=0; else if(T-lchild=NULL) elseL=leafcount(T-lchild); R=leafcount(T-rchild); leaf=L+R; return(leaf)
