数据结构 第六章 考试题目

习题6.1选择题1、假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，则叶子结点数为（ B ）。

A、15B、16C、17D、472、设n，m为一棵树上的两个结点，在中根遍历时，n在m前的条件是（C）。

A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙3、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D ）。

A、23B、37C、46D、444、如果F是由树T转换而来的二叉树，则T中结点的前根就是F中结点的（ B ）。

A、中根遍历B、先根遍历C、后根遍历D、按层遍历5、某二叉树的先根遍历结点序列和后根遍历结点序列刚好相反，则该二叉树一定是（D）。

A、空树或只有一个根结点B、完全二叉树C、二叉排序树D、高度等于其结点数6.2填空题1、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（后继）结点，其余结点的后继结点可以（任意多个）。

2、在具有n个结点的二叉树中，有（n+1）个空指针。

3、深度为k的完全二叉树至少有（2k-1）个结点，至多有（2k-1）个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是（n/2+1 ）。

4、由a，b，c三个结点构成的二叉树，共有（5）种不同形态。

5、树所对应的二叉树其根结点的（右）子树一定为空。

6.3应用题1、给定的树如图6-24（a）所示，回答以下问题：（1）哪个是根结点，哪些是叶子结点？答：根结点是A，叶子结点是B，K，L，M，G，D，H，I，J。

（2）哪个是结点F的双亲结点，哪些是结点F 的祖先结点，哪些是结点F的孩子结点？答：结点F的双亲结点是C，祖先结点是A，C，孩子结点是K，L，M。

（3）哪些是结点C的子孙结点，哪些是结点C的兄弟结点？答：结点C的子孙结点是F，G，K，L，M，结点C的兄弟结点是B，D，E。

（4）给定树的层数是多少，结点I所在的层数是多少？答：树的层数为4，结点I在第三屋。

第6章图一、填空题1、用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（AOV-网）。

2、有n(n-1)/2条边的无向图称为_无向完全图__；有n(n-1)条边的有向图称为_有向完全图。

3、一个含n个结点的完全无向图中，其最大边数为__ n(n-1)/2_。

4、顶点表示事件，弧表示活动，权表示活动持续时间的有向图称为AOE-网。

二、判断题1、任何无向图都存在生成树。

（）2、连通分量是无向图中的极小连通子图。

（）3、强连通分量是有向图中的极大强连通子图。

（）4、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

（）5、邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

（）6、求最小生成树的Prim算法在边较少、结点较多时效率较高。

（）7、图的最小生成树的形状可能不唯一。

（）8、一个AOV网的拓扑序列一定是唯一的。

（）9、若AOV网中存在环，则不能求它的拓扑排序序列。

（）10、若AOV网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

（）11、缩短关键路径上活动的工期一定能够缩短整个工程的工期。

（）12、AOE网中一定只有一条关键路径。

（）三、单项选择题1、在一个图中，所有顶点的度数之和等于图的边数的（C）倍。

A．1/2 B．1 C．2 D．42、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。

A．1/2 B．1 C．2 D．4解释：有向图所有顶点入度之和等于所有顶点出度之和。

3、具有n个顶点的有向图最多有（B）条边。

A．n B．n(n-1) C．n(n+1) D．n2解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。

4、n个顶点的连通图用邻接距阵表示时，该距阵至少有（B）个非零元素。

A．n B．2(n-1) C．n/2 D．n25、G是一个非连通无向图，共有28条边，则该图至少有（C）个顶点。

数据结构习题第6章树（1）2007-06-03 14:33:26| 分类：数据结构习题 | 标签：数据结构练习题|字号订阅第6章树6.1选择题1．一棵具有 n个结点的完全二叉树的树高度（深度）是（）A）?log2n?+1 B）log2n +1 C）? log2n ? D）log2n-1【答案】A2．有关二叉树下列说法正确的是（）A）二叉树的度为2 B）一棵二叉树的度可以小于2C）二叉树中至少有一个结点的度为2 D）二叉树中任何一个结点的度都为2【答案】B3．二叉树的第I层上最多含有结点数为（）A）2I B）2I-1-1 C）2I-1 D）2I-1【答案】C4．具有10个叶结点的二叉树中有（）个度为2的结点A）8 B）9 C）10 D）11【答案】B5．在下述结论中，正确的是（）①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A）①②③ B）②③④ C）②④ D）①④【答案】D6．由3 个结点可以构造出多少种不同的二叉树？（）A）2 B）3 C）4 D）5【答案】D7．引入二叉线索树的目的是（）A）加快查找结点的前驱或后继的速度B）为了能在二叉树中方便的进行插入与删除C）为了能方便的找到双亲D）使二叉树的遍历结果惟一【答案】A8．有n个叶子的哈夫曼树的结点总数为（）A）不确定 B）2n C）2n+1 D）2n-1【答案】D9．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A）所有的结点均无左孩子 B）所有的结点均无右孩子C）只有一个叶子结点 D）是任意一棵二叉树【答案】C【解析】先序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，单支树的特点是只有一个叶子结点或高度等于其结点数，故选C。

10．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A）250 B）500 C）505 D）以上答案都不对【答案】D【解析】若每个结点均已经编号，则最大的编号为1001，其父亲结点的编号为500，那么从501到1001均为叶子结点。

第6章树和二叉树一、选择题1．不含任何结点的空树（）。

A. 是一棵树B. 是一棵二叉树C. 是一棵树也是一棵二叉树;D. 既不是树也不是二叉树2. 一棵有n个结点的树的所有结点的度数之和为（）。

A. n-1B. nC. n+1D. 2n3. 在二叉树中某一个结点的深度为3，高度为4，则该树的高度是（）。

A. 5B. 6C. 7D. 84. 设高度为h的二叉树中只有度为0和度为2的结点，则该树的结点数至多为（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h+15. 设高度为h的二叉树中只有度为0和度为2的结点，则该树的结点数至少为（）。

A. 2h-1B. 2h+1C. 2h-1D. 2h+16. 高度为h的满二叉树中有n个结点，其中有m个叶结点，则正确的等式是（）。

A. h+m=nB. h+m=2nC. m=h-1D. n=2h-17．二叉树是非线性数据结构，所以（）。

A. 它不能用顺序存储结构存储B. 它不能用链式存储结构存储C. 顺序存储结构和链式存储结构都能存储D. 顺序存储结构和链式存储结构都不能使用8. 一棵完全二叉树有25个叶结点，则该树最少有（）个结点。

A. 48B. 49C. 50D. 519. 假设一个三叉树的结点数为36，则该树的最小高度为（）。

A. 2B. 3C. 4D. 510. 设二叉树有n个结点，则二叉链表中非空指针数为（）。

A. n-1B. nC. n+1D. 2n11. 先序序列和中序序列正好相反的二叉树是（）。

A. 完全二叉树B. 满二叉树C. 左单枝树D. 右单枝树12. 后序序列和中序序列正好相反的二叉树是（）。

A. 完全二叉树B. 满二叉树C. 左单枝树D. 右单枝树13．把一棵树转换为二叉树后，这棵二叉树的形态是（）。

A. 唯一的B. 有多种C. 有多种，但根结点都没有左孩子D. 有多种，但根结点都没有右孩子14. 将一棵树T转换为孩子—兄弟链表表示的二叉树H，则T的后根序遍历是H 的（）。