数据结构C语言版复习资料2.doc

.数据结构C语言版复习资料2一、选择题1.以下数据结构中哪一个是非线性结构？( B ) A. 队列 B. 二叉树 C. 栈 D. 线性表2.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( B )。 A. 5，6，3，4，1，2 C. 3，1，2，6，5，4 B. 3，2，5，6，4，1 D. 1，5，4，6，2，33.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是( C ) 。 A. N0=N1+1 B. N0=Nl+N2 C. N0=N2+1 D. N0=2N1+l4.设某棵二叉树中有1000个结点，则该二叉树的最小高度为( B )。 A9 B. 10 C. 11 D. 125、在一棵具有4层的满二叉树中结点总数为（ A ）。A. 15 B. 16 C. 17 D. 326、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（ D ）。A. adbce B. decab C. debac D. abcde7.设有8个结点的无向图，该图至少应有( C )条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 88.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( C )。 A. n，e B. 2n，e C. n，2e D. e，n9.设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点b出发进行深度优先遍历可以得到的一种顶点序列为( A ) 。 A. bacfde B. becfad C. bacedf D. beafdc2、 填空题1. 数据元素之间的逻辑结构有四种基本类型，分别是集合、线性、 树形结构 和 网状结构 。2. 数据元素之间的存储结构有两种基本类型，分别是 顺序存储结构 和 链式存储结构 。3.设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是 n-i+1 。4.设入栈序列为7、3、4、8，则通过栈的作用后可以得到的出栈序列为 8、4、3、7 。5.深度为k的二叉树中最少有 k 个结点，最多有 2k-1 个结点。6.二叉树的第i层最多有 2i-1 个结点。7.树中的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的 度的最大值 ，度为零的节点称为 叶结点 ，度不为零的节点称为 分支结点 。8.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为 i/2 ，左孩子结点的编号为 2i 。9、哈夫曼树是其树的带权路径长度 最短 的二叉树。10、树内各结点度的 度的最大值 称为树的度。11.已知一有向图的邻接表存储结构如下：从顶点2出发，DFS(深度优先)遍历的输出序列是 21345 ，BFS(广度优先)遍历的输出序列是 21345 。 23415 12.设某无向图中顶点数和边数分别为e和n，所有顶点的度数之和为b，则n= b/2 。三、综合题1.下图所示的树： (1) 求树的先根序列和后根序列； (2) 将此树换为相应的二叉树；ABCDEFIHGJABCDEFGHIJ解：(1) 树的先根序列为：ABEJFCGDHI树的后根序列为：JEFBGCHIDA(3) 将此树转换为相应的二叉树如下图所示：ABDCEFGHIJ2.已知二叉树的前序遍历序列是ABCDEFGHIJ，中序遍历序列是BCAEDFHGIJ，试画这棵二叉树，并给出这棵树后序遍历的结果。解：（1）这棵二叉树如下图所示：(2) 这棵树后序遍历序列为：CBEHJIGFDA2951140608020435161922101215863.给定权值集合12,04,15,02,08,10,16,19，构造相应的Huffman树，并计算它的带权外部路径长度。解：（1）构造的Huffman树如下图所示：(2)带权外部路径为：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2434.请画出下图的邻接矩阵和邻接表。解：(1)邻接矩阵如下：0110110011100110110111110(2)邻接表如下图所示：011241203423034341244532105.已知一个图的顶点集V和边集E分别为：V=1,2,3,4,5,6,7;E=(1,2)13,(1,3)6,(1,4)9,(2,5)12,(2,3)7,(3,4)15,(3,5)14,(3,6)10,(4,6)4,(4,7)20,(5,6)18,(6,7)26;分别画出用普里姆(Prim)算法(从顶点1出发)和克鲁斯卡尔(Kruskal)算法得到最小生成树，写出在最小生成树中依次得到的各条边。解：（1）用普里姆算法构造最小生成树的过程如下所示：941637216372163(3)(1)(2)207125469416372125469416372469416372(6)(5)(4)依次得到的各条边为：(1,3)6, (2,3)7, (1,4)9, (4,6)4, (2,5)12, (4,7)20（2）用克鲁斯卡尔算法构造最小生成树的过程如下所示：754642136754642136775464213(3