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