1、数据结构自考题-14 及答案解析(总分：85.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.树(A(B(E，(F(J，K)，C(G)，D(H，I)的度和深度分别是_ A.3；3 B.2；4 C.3；4 D.4；4（分数：2.00）A.B.C.D.2.深度为 k的二叉树，其第 k层最少有_个结点。 A.1 B.2 C.0 D.不确定 2k-1（分数：2.00）A.B.C.D.3.对于二叉树 T，其度数为 1的结点数为 4，终端结点数为 5，那么该二叉树共有_个结点。 A.9 B.12 C.13 D.14（分数：2.00）A.B.C.D.4.对于二叉树 T，
2、其前序遍历为 ABCDE，中序遍历为 ACBDE，那么其后序遍历为_ A.CEDBA B.ABDEC C.BCDEA D.EDBAC（分数：2.00）A.B.C.D.5.对于二叉树 T，如果采用二叉链表的存储结构，如果此二叉树有 10个结点，那么空链域的个数为_ A.19 B.11 C.91 D.21（分数：2.00）A.B.C.D.6.给出权值为 2，4，5，7，9 的五个叶子结点，将其作为某二叉树的叶子，那么在构成的所有树中，带权路径长度最小为_ A.60 B.27 C.62 D.61（分数：2.00）A.B.C.D.7.下图所示的二叉树 T是一棵哈夫曼树，则元素 C、D 的哈夫曼编码分别
3、是_（分数：2.00）A.B.C.D.8.在图形结构中，结点之间的关系是_ A.一对一 B.多对一 C.一对多 D.任意的（分数：2.00）A.B.C.D.9.下图中 C元素的度为_（分数：2.00）A.B.C.D.10.已知图 G共有 4个结点，其各个顶点的度分别为 2、4、3、1，那么该图的边数为_ A.3 B.6 C.4 D.5（分数：2.00）A.B.C.D.11.无向图的边数的取值范围为_ A0n(n-1) B0n(n+1) C D （分数：2.00）A.B.C.D.12.已知图 G(如下图所示)，采用邻接矩阵表示法存储该图，则图 G的邻接矩阵为_ A B C D （分数：2.00）
4、A.B.C.D.13.在邻接表表示图结构时，边表中结点的个数等于邻接矩阵的一行(或一列)中_ A.元素的个数 B.非零元素的个数 C.零元素的个数 D.元素的和（分数：2.00）A.B.C.D.14.对于一个有向图(有 n个顶点)，假设用邻接矩阵表示，那么该邻接矩阵的大小是_ A.n2 B.n C.n(n-1) D.(n-1)2（分数：2.00）A.B.C.D.15.给出某有向图 G的邻接表，如下图所示，则元素 V3的出度和入度分别是_（分数：2.00）A.B.C.D.二、B填空题/B(总题数：10，分数：20.00)16.具有 16个结点的完全二叉树，其深度为_。（分数：2.00）填空项 1
5、:_17.深度为 5的二叉树最多可以有_个结点。（分数：2.00）填空项 1:_18.如下表所示是用双亲表示法表示的一棵树，元素 F的双亲是_。 0 A -11 B 02 C 03 D 04 E 15 F 16 G 57 H 58 I 3（分数：2.00）填空项 1:_19.在树中，一个结点拥有的子树的个数称为该结点的_。（分数：2.00）填空项 1:_20.对任何一棵二叉树，若其终端结点数为 m0，度数为 2的结点数为 m2，那么 m0和 m2之间的关系是_。（分数：2.00）填空项 1:_21.有向完全图有_条边。(其中图有 n个结点)（分数：2.00）填空项 1:_22.对图采用邻接矩阵
6、表示法，那么无向图的邻接矩阵是一个_矩阵。（分数：2.00）填空项 1:_23.图的遍历方法有很多，但主要常用的是深度优先遍历和_。（分数：2.00）填空项 1:_24.将一个有向无环图 G中的所有顶点排成一个线性序列，使得图中任意一对顶点 u和 v，若u，vE(G)，则 u在线性序列中出现在 v之前，这样的线性序列称为_。（分数：2.00）填空项 1:_25.树和图都是_结构。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.树的孩子兄弟表示法又称为二叉链表表示法，请画出下图树 T的二叉链表。 （分数：5.00）_27.将下图的树 T转换成二叉树。 （分数
7、：5.00）_28.假设对图采用邻接矩阵表示法，给出如下矩阵 A，请画出该矩阵对应的图。 （分数：5.00）_29.利用 Prim算法，求规划图所示图 G1的最小生成树。（分数：5.00）_四、B程序阅读题/B(总题数：1，分数：5.00)(1).简述函数 f的功能 int f32(MGraph *G, int i) int d=0, j; for(j=0; jG-n; j+) if(G-edgesij)d+; if(G-edgesji)d+; return d; （分数：2.50）_(2).对于下列图 G的邻接矩阵，写出函数调用 f( for(j=0; jG-n; j+) if(G-edgesij)d+; if(G-edgesji)d+; return d; （分数：2.50）_正确答案：(求有向图顶点 vi的出度和入度的和，也就是顶点 vi的度。)解析：(2).对于下列图 G的邻接矩阵，写出函数调用 f( if(q-ltag=1) return q-lchild; else p=q-lchild; while(p-rtag=0) p=p-rchild; return p; )解析：考点 以中序线索二叉链表作为存储结构，查找某结点的中序前驱结点的算法
