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

数据结构 C语言版复习资料 2数据结构 C语言版复习资料 2一、选择题1.以下数据结构中哪一个是非线性结构？ ( B )A.队列 B.二叉树 C.栈 D.线性表设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( B )。A.5，6，3，4，1，2 C.3，1，2，6，5，4B.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 )。A．9 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.8设无向图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.beafdc二、填空题1.数据元素之间的逻辑结构有四种基本类型，分别是集合、线性、 树形结构和 网状结构 。1/6数据结构 C语言版复习资料 22.数据元素之间的存储结构有两种基本类型，分别是 顺序存储结构和 链式存储结构 。3.设输入序列是1、2、3、⋯⋯、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是n-i+1。4.设入栈序列为7、3、4、8，则通过栈的作用后可以得到的出栈序列为8、4、3、7。5.深度为k的二叉树中最少有k个结点，最多有k个结点。2-16.二叉树的第i层最多有2i-1个结点。7.树中的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的度的最大值，度为零的节点称为叶结点，度不为零的节点称为 分支结点 。8.设有n个结点的完全二叉树， 如果按照从自上到下、 从左到右从 1开始顺序编号，则第 i 个结点的双亲结点编号为 i/2 ，左孩子结点的编号为2i 。9、哈夫曼树是其树的带权路径长度 最短 的二叉树。10、树内各结点度的 度的最大值 称为树的度。11.已知一有向图的邻接表存储结构如下： 从顶点 2出发，DFS(深度优先)遍历的输出序列是 21345 ，BFS(广度优先 )遍历的输出序列是21345 。1234512.设某无向图中顶点数和边数分别为 e和n，所有顶点的度数之和为 b，则n=b/2 。三、综合题2/6数据结构 C语言版复习资料 2下图所示的树：求树的先根序列和后根序列；将此树换为相应的二叉树；AB CE F GJ解：(1)树的先根序列为： ABEJFCGDHI树的后根序列为： JEFBGCHIDA将此树转换为相应的二叉树如下图所示：2.已知二叉树的前序遍历序列是 ABCDEFGHIJ

DH IABE CDJ F GHI，中序遍历序列是 BCAEDFHGIJ，试画这棵二叉树，并给出这棵树后序遍历的结果。A解：（1）这棵二叉树如下图所示：B DC E FGH I3/6J数据结构 C语言版复习资料 2(2)这棵树后序遍历序列为： CBEHJIGFDA3.给定权值集合 {12,04,15,02,08,10,16,19}，构造相应的 Huffman树，并计算它的带权外部路径长度。86解：（1）构造的 Huffman树如下图所示：513516 1929 2215 14 10 1206 0802 04(2)带权外部路径为： (16+19)*2+(15+10+12)*3+8*4+(4+2)*5=243请画出下图的邻接矩阵和邻接表。解：(1)邻接矩阵如下：0 1 1 0 11 0 0 1 11 0 0 1 10 1 1 0 11 1 1 1 04/6数据结构 C语言版复习资料 2邻接表如下图所示：12345

1 2 40 3 40 3 41 2 40 1 2 35.已知一个图的顶点集 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）用普里姆算法构造最小生成树的过程如下所示：116661933374722(1)(2)(3)111666999333747420744447262126212655(4)(5)(6)依次得到的各条边为：(1,3)6,(2,3)7,(1,4)9,(4,6)4,(2,5)12,(4,7)205/6数据结构 C语言版复习资料 2（2）用克鲁斯卡尔算法构造最小生成树的过程如下所示：16161333444