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

...wd......wd......wd...数据构造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，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．9B.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.5B.6C.7D.88.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为(C)。A.n，eB.2n，eC.n，2eD.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.bacedfD.beafdc填空题数据元素之间的逻辑构造有四种基本类型，分别是集合、线性、树形构造和网状构造。数据元素之间的存储构造有两种基本类型，分别是顺序存储构造和链式存储构造。3.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是n-i+1。4.设入栈序列为7、3、4、8，则通过栈的作用后可以得到的出栈序列为8、4、3、7。5.深度为k的二叉树中最少有k个结点，最多有2k-1个结点。6.二叉树的第i层最多有2i-1个结点。7.树中的一个节点拥有的子树数称为该节点的度。一棵树的度是指该树中节点的度的最大值，度为零的节点称为叶结点，度不为零的节点称为分支结点。8.设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开场顺序编号，则第i个结点的双亲结点编号为i/2，左孩子结点的编号为2i。9、哈夫曼树是其树的带权路径长度最短的二叉树。10、树内各结点度的度的最大值称为树的度。11.一有向图的邻接表存储构造如下：从顶点2出发，DFS(深度优先)遍历的输出序列是21345，BFS(广度优先)遍历的输出序列是21345。22341512.设某无向图中顶点数和边数分别为e和n，所有顶点的度数之和为b，则n=b/2。三、综合题1.以以下列图所示的树：(1)求树的先根序列和后根序列；(2)将此树换为相应的二叉树；AABCDEFIHGJAABCDEFGHIJ解：(1)树的先根序列为：ABEJFCGDHI树的后根序列为：JEFBGCHIDA(3)将此树转换为相应的二叉树如以以下列图所示：ABDCEFGHABDCEFGHIJ解：〔1〕这棵二叉树如以以下列图所示：(2)这棵树后序遍历序列为：CBEHJIGFDA2951140608020435161922101215863295114060802043516192210121586解：〔1〕构造的Huffman树如以以下列图所示：(2)带权外部路径为：(16+19)*2+(15+10+12)*3+8*4+(4+2)*5=2434.请画出以以下列图的邻接矩阵和邻接表。解：(1)邻接矩阵如下：0110110011100110110111110(2)邻接表如以以下列图所示：011212412030342303034341212445321032105.一个图的顶点集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〕用普里姆算法构造最小生成树的过程如下所示：949416372163721163(3)(1)(2)(3)(1)(2)2072071254694163721254694163724469416372(6)(5)(4)(6)(5)(4)依次得到的各条边为：(1,3)6,(2,3)7,(1,4)9,(4,6)4,(2,5)12,(4,7)20〔2〕用克鲁斯卡尔算法构造最小生成树的过程如下所示：754754642136754642136775