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

1、-考试-学资学习网-押题- 数据结构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，3 3.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是( C ) 。 A. N0=N1+1 B. N0=Nl+N2 C. N0=N2+1 D. N0=2N1+l 4.设某棵

2、二叉树中有1000个结点，则该二叉树的最小高度为( B )。 A9 B. 10 C. 11 D. 12 5、在一棵具有4层的满二叉树中结点总数为（ A ）。 A. 15 B. 16 C. 17 D. 32 6、设一棵二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树先序遍历序列为（ D ）。 A. adbce B. decab C. debac D. abcde 7.设有8个结点的无向图，该图至少应有( C )条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 8.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( C )。 A.

3、 n，e B. 2n，e C. n，2e D. e，n 9.设无向图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. 树形结构 数据元素之间的逻辑结构有四种基本类型，分别是集合、线性、 。网状结构 和 2.数据元素之间的存储结构有两种基本类型，分别是 顺序存储结构 。 和 链式存储结构 3.设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输

4、出元素是 n-i+1 。 4.设入栈序列为7、3、4、8，则通过栈的作用后可以得到的出栈序列为 8、4、3、7 。 k-1 2 个结点。 k 个结点，最多有 的二叉树中最少有5.深度为k i-1 2 个结点。 6.二叉树的第i层最多有 7.树中的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的 度的最大值 ，度为零的节点称为 叶结点 ，度不为零的节点称为 分支结点 。 8.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为 i/2 ，左孩子结点的编号为 2i 。 哈夫曼树是其树的带权路径长度 最短 的二叉树。 、910、树内各结点

5、度的 度的最大值 称为树的度。 11.已知一有向图的邻接表存储结构如下：从顶点2出发，DFS(深度优先)遍历的输出序列是 21345 ，BFS(广度优先)遍历的输出序列是 21345 。 1 2 3 4 5 n= ，则，所有顶点的度数之和为和设某无向图中顶点数和边数分别为12.enb b/2 。 三、综合题 1.下图所示的树： (1) 求树的先根序列和后根序列； (2) 将此树换为相应的二叉树； A D C B F E G H I J ABEJFCGDHI (1) 树的先根序列为：解：A JEFBGCHIDA 树的后根序列为：B (3) 将此树转换为相应的二叉树如下图所示： C E D G J

6、 F H I ，中序遍历序列是，已知二叉树的前序遍历序列是2.ABCDEFGHIJBCAEDFHGIJ 试画这棵二叉树，并给出这棵树后序遍历的结果。A 1）这棵二叉树如下图所示：（解：D B F E C G H I J CBEHJIGFDA 这棵树后序遍历序列为：(2) 树，并计算它的Huffman给定权值集合12,04,15,02,08,10,16,19，构造相应的3. 带权外部路径长度。86 树如下图所示：解：（1）构造的Huffman51 35 19 16 29 22 14 15 10 12 08 06 04 02 (16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2

7、43 (2)带权外部路径为： 4.请画出下图的邻接矩阵和邻接表。 (1)邻接矩阵如下：解： 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 邻接表如下图所示：(2)1 01242 1340 23340 342415 4 1 0 2 3 5.已知一个图的顶点集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出发)和

8、克鲁斯卡尔(Kruskal)算法得到最小生成树，写出在最小生成树中依次得到的各条边。 解：（1）用普里姆算法构造最小生成树的过程如下所示： 1 1 6 6 1 9 6 3 3 4 7 7 3 2 2 (2) (3) (1) 1 1 1 6 6 6 9 9 9 3 3 3 4 4 7 20 7 4 4 4 7 7 4 2 2 6 6 12 12 2 6 5 5 (6) (4) (5) 依次得到的各条边为：(1,3)6, (2,3)7,(1,4)9,(4,6)4,(2,5)12, (4,7)20 ）用克鲁斯卡尔算法构造最小生成树的过程如下所示：2（ 1116 6 333 4 4 4 7 7 7 7 4 4 4 2 2 6 6 2 6 5 5 5 (3) (2) (1) 1 1 1 6 6 6 9 9