数据结构C语言版复习

1、据结构C语言版复习资料2数据结构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的结点数为N1,度数为2的结点数为N2,则下列等式成立的是（C）oA.NO=Nl+1B.NO=N1+N2C.NO=N2+1D.NO=2N1+14 .设某棵二叉树中有1000个结点，则该二叉树的最小高度为（B）。A.9B

2、.10C.11D.125、在一棵具有4层的满二叉树中结点总数为（AA.15B.16C.17D.326、设一棵二叉树的中序遍历序列：badce,后序遍历序列：bdeca,则二叉树先序遍历序列为（D）。A.adbceB.decabC.debacD.abcde7 .设有8个结点的无向图，该图至少应有（C）条边才能确保是一个连通图。A.5B.6C.7D.88 .设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（C）。A.n,eB2n,eC.n,2eD.e,n9 .设无向图G中的边的集合E=(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c),

3、则从顶点b出发进行深度优先遍历可以得到的一种顶点序列为(A)。A.bacfdeB.beefadC.bacedfD.beafde二、填空题1 .数据元素之间的逻辑结构有四种基本类型，分别是集合、线性、树形结构和网状结构O2 .数据元素之间的存储结构有两种基本类型，分别是顺序存储结构和链式存储结构。3 .设输入序列是1、2、3、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是n-1+l34 .设入栈序列为7、3、4、8,则通过栈的作用后可以得到的出栈序列为上4、3、7o5 .深度为k的二叉树中最少有k个结点,最多有2匚1个结点。6 .二叉树的第i层最多有2个结点。7 .树中

4、的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的度的最大值，度为零的节点称为叶结点，度不为零的节点称为分支结点。8 .设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始L顺序编号，则第i个结点的双亲结点编号为i/2,左孩子结点的编号为2io9、哈夫曼树是其树的带权路径长度最短的二叉树。10、树内各结点度的度的最大值称为树的度。11 .已知一有向图的邻接表存储结构如下：从顶点2出发，DFS(深度优先)遍历的输出序列是21345，BFS(广度优先)遍历的输出序列是21345图的邻接表存楮结构12 .设某无向图中顶点数和边数分别为e和n,所有顶点的度数之和为b,则n=b/

5、2三、综合题1 .下图所示的树：(1)求树的先根序列和后根序列;(2)将此树换为相应的二叉树；解：(1)树的先根序列为：ABEJFCGDHI树的后根序列为：JEFBGCHIDA(3)将此树转换为相应的二义树如下图所示:2 .已知二叉树的前序遍历序列是ABCDEFGHIJ,中序遍历序列是BCAEDFHGIJ,试画这棵二叉树，并给出这棵树后十二的结果。解：(1)这棵二叉树如下图所示：(2)这棵树后序遍历序列为：CBEHJIGFDA3 .给定权值集合12,04,15,02,08,10,16,19,构造相应的Huffman树,并计算它的带权外部路径长度。(7解：(1)构造的Huffman树如下图所示：

6、/一(2)带权外部路径为：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2434 .请画出下图的邻接矩阵和邻接表。解：(1)邻接矩阵如下：飞1101一10011100110110111110邻接表如下图所示: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出发）和克鲁斯卡尔（Kruskal）算法得到最小生成树，写出在最小生成树中依次得到的各条边。解：（1）用普里姆算法构造最小生成树的过程如下所示:依次得到的各条边为：(1,3