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

C习资料2wword下载即可编辑！！PAGE2PAGE2做一 、选择题

数据结构C语言版复习资料2以下数据结构中哪一个是非线性结构？ (B)A.队列 B.二叉树 C.栈 D.线性表 设输入序列为 1、 2、 3、 4、 5、 6，则通过栈的作用后可以得到的输出序列为 ( B。.5， 6， 3， 4， 1， 2 .3， 1， 2， 6， 5， 4.， 2， 5， 6， 4， 1 .1， 5， 4， 6， 2， 3设某二叉树中度数为 0的结点数为 0，度数为 1的结点数为 l，度数为 2结点数为 2，则下列等式成立的是 (C)。A.N0=N1+1 B.N0=Nl+N2 C.N0=N2+1 D.N0=2N1+l设某棵二叉树中有 1000个结点，则该二叉树的最小高度为 (B )。A． 9 .0 .1 .5、在一棵具有 4层的满二叉树中结点总数为（ A ）。 A.15 B.16 C.17 D.326、设一棵二叉树的中序遍历序列： ，后序遍历序列： a，则二叉树先 序遍历序列为（ D）。 A.adbce B.decab C.debac D.abcde设有 8个结点的无向图，该图至少应有 (C )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8设无向图 G中有 n个顶点 e条边，则其对应的邻接表中的表头结点和表结点 的个数分别为 (C )。A.， e .n， e .n， e .e， n9设无向图 G中的边的集合 ， b， ， )， ， ， b， ， ， ， ， ， ，则从顶点 b出发进行深度优先遍历可以得到的一种顶点序列为 (A)。A.bacfde B.becfad C.bacedf D.beafdc1234512345数据元素之间的逻辑结构有四种基本类型，分别是集合、 结构和 结构 。数据元素之间的结构有种基本类型，分别是 结构和结构 。是 1、2、3、……、n，的的元素是n，第i元素是 n。设入栈序列为7、3、4、8则通过栈作后以得到出栈序列为 8、4、3、7 。深度为k的二叉树中最少有k个结点，最多有-1个结点。二叉树的第i层最多有个结点。树中的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的度的最大值 ，度为零的节点称为叶结点，度不为零的节点称为分支结点。设有n个结点完全叉树如果按照从自上到、从左到右从1开始顺序号则第i个结点双亲结点号为i/2 左孩子结点号为2i 。9、哈夫曼树是其树的带权路径长度最短的二叉树。10、树内各结点度的度的最大值称为树的度。已知一有向图的邻接表存储结构如下：从出发，DFS(深度优先)遍历的输出序列是21345 ，BFS(广度优先)遍历的输出序列是21345 。wword下载即可编辑！！设某无向图中顶点数和边数分别为 e和 n，所有顶点的度数之和为 b，则 nb/2 。三 、综合题下图所示的树： 求树的先根序列和后根序列； 将此树换为相应的二叉树； ABCDE FJGHI解： (1)树的先根序列为： ABEJFCGDHI A树的后根序列为： JEFBGCHIDA B(3)将此树转换为相应的二叉树如下图所示： E CJ F G DHI已知二叉树的前序遍历序列是 ABCDEFGHIJ，中序遍历序列是 J，试画这棵二叉树，并给出这棵树后序 遍 历的结果。 解：（ 1）这棵二叉树如下图所示： 4

B DC E FGPAGE5PAGE5做8853221111110000(2)这棵树后序遍历序列为：CBEHJIGFDA3给定权值集合12,04,15,02,08,10,16,19，构造相应的 n树，并计算它的带权外部路径长度。解：（1）构造的 Huffman树如下图所示：(2)带权外部路径为：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=243请画出下图的邻接矩阵和邻接表。解：(1)邻接矩阵如下：011011011001110011011011 1 1 1 0(2)邻接表如下图所示：1231234512403403412401231234已知一个图的顶点集 V和边集 E分别为：(6,7)26};分别画出用普里姆(Prim)算法(从顶点 1出发)和克鲁斯卡尔(Kruskal)算法得到最小生成树，写出在最小生成树中依次得到的各条边。解：（1）用普里姆算法构造最小生成树的过程如下所示：6613613761372(2)6193742(3)619374420721265619619374426619374421265(4)

(5)

(6)依次得到的各条边为： 136,237,149,464,2512,47201（2）用克鲁斯卡尔算法构造最小生成树的过程如：1