1数据结构(树与图部分)练习题一、填空题1. 不考虑顺序的3个结点可构成种不同形态的树，种不同形态的二叉树。

2. 已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数为：。

3. 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。

4.一棵具有110个结点的完全二叉树，若i ＝54，则结点i 的双亲编号是；结点i 的左孩子结点的编号是，结点i 的右孩子结点的编号是。

5. 一棵具有48个结点的完全二叉树，若i ＝20，则结点i 的双亲编号是______；结点i的左孩子结点编号是______，右孩子结点编号是______。

6. 在有n 个叶子结点的Huffman 树中，总的结点数是：______。

7. 图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限集合，E(G)是______的有限集合。

8. 遍历图的基本方法有优先搜索和优先搜索两种方法。

9. 图的遍历基本方法中是一个递归过程。

10. n 个顶点的有向图最多有条弧；n 个顶点的无向图最多有条边。

11. 在二叉树的二叉链表中，判断某指针p 所指结点是叶子结点的条件是。

12. 在无向图G 的邻接矩阵A 中，若A[i,j]等于1，则A[j,i]等于。

二、单项选择题1. 树型结构的特点是：任意一个结点：（ ） A 、可以有多个直接前趋B 、可以有多个直接后继 C 、至少有1个前趋D 、只有一个后继2. 如下图所示的4棵二叉树中，（ ）不是完全二叉树。

A B C D3. 深度为5的二叉树至多有（ ）个结点。

A 、16 B 、32 C 、31 D 、104. 64个结点的完全二叉树的深度为：（ ）。

A 、8 B 、7 C 、6 D 、55. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（ ）。

A 、98B 、99C 、50D 、486. 在一个无向图中，所有顶点的度之和等于边数的（ ）倍。

A 、1/2 B 、1 C 、2 D 、47. 设有13个值，用它们组成一棵Huffman 树，则该Huffman 树中共有()个结点。

A、13B、12C、26D、258.若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为()。

A、2,14B、2,15C、3,14D、3,159.若对一棵有20个结点的完全二叉树按层编号，则对于编号为5的结点x，它的双亲结点及左孩子结点的编号分别为()。

A、2,11B、2,10C、3,9D、3,1010.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：A、48B、49C、50D、5111.无向图的邻接矩阵是一个()。

A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵12.由64个结点构成的完全二叉树，其深度为：( )。

A、8B、7C、6D、513.若对一棵有16个结点的完全二叉树按层编号，则对于编号为7的结点x，它的双亲结点及右孩子结点的编号分别为()。

A、2,14B、2,15C、3,14D、3,1514.图示二叉树的中序遍历序列是：（）A、abcdgefB、dfebagcC、dbaefcgD、defbagc15.图示二叉树的后序遍历序列是：（）A、ABCDEFGHB、BDAFEHGCC、DBFHGECAD、HGFEDCBA16.邻接表是图的一种（）。

A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构17.给定有向图如右图所示，则该图的一个强连通分量是：（）。

A、{A,B,C,F}B、{B,C,F}C、{B,C,D,F}D、{C,D,E,F}18.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A、将邻接矩阵的第i行删除B、将邻接矩阵的第i行元素全部置为0C、将邻接矩阵的第i列删除D、将邻接矩阵的第i列元素全部置为0三、判断题1.（）非线性数据结构可以顺序存储，也可以链接存储。

2.（）非线性数据结构只能用链接方式才能表示其中数据元素的相互关系。

3.（）完全二叉树一定是满二叉树。

4.（）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。

5.（）若一棵二叉树的任意一个非叶子结点的度为2，则该二叉树为满二叉树。

6.（）度为1的有序树与度为1的二叉树是等价的。

7.（）二叉树的先序遍历序列中，任意一个结点均排列在其孩子结点的前面。

8.（）已知一棵二叉树的先序序列和后序序列，就一定能构造出该二叉树。

9.（）在霍夫曼树中，权值最小的结点离根结点最近。

10.()对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访问到该图的每个顶点。

11.（）线性数据结构可以采用顺序存储结构或链式存储结构，而非线性数据结构只能采用链式存储结构。

12.（）二叉树中的叶子结点就是二叉树没有左、右子树的结点。

13.（）如果一棵树中某结点的度为1，则该结点仅有一棵子树。

14.（）在有向图中，若存在有向边<V1,V2>,则一定存在有向边<V2，V1>。

15.（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历后，并不一定能访问到该图的每个顶点。

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

四、简答题1.什么叫有序树？什么叫无序树？有序树和二叉树的差别是什么？2.什么叫完全二叉树？什么叫满二叉树？它们之间的关系是什么？3.什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？3五、综合题1.如图所示的两棵二叉树，分别给出它们的顺序存储结构。

第1棵树第2棵树2.已知一棵二叉树的中序、后序序列分别如下：中序：D C E F B H G A K J L I M后序：D F E C H G B K L J M I A要求：⑴画出该二叉树；⑵写出该二叉树的先序序列。

3.一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。

先序：_B_F_ICEH_G中序：D_KFIA_EJC_后序：_K_FBHJ_G_A4.将下图中的树转化为二叉树，并写出转换后的二叉树的后序遍历序列。

5.将下图所示的树转换成二叉树，并写出转换后二叉树的先序、中序、后序遍历结果。

6.将下列一棵二叉树进行前序遍历、中序遍历、后序遍历，并转化为树。

7.写出下面二叉树的先序、中序、后序遍历结果，并将它转换为树。

8. 分别写出下图所示二叉树的先序、中序和后序遍历序列。

9. 写出下图中的二叉树先序和后序遍历序列。

10. 输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴ 画出该二叉排序树；⑵ 画出删除结点302后的二叉排序树。

11. 按给出的一组权值{4，5，7，8，11}，建立一个霍夫曼树，并请计算出该树的带权路径长度WPL 。

12. 以{5,9,15,18,22}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度(WPL)。

13. 以{4,7,10,15,23}作为叶子结点的权值构造一棵Huffman 树，并求出其带权路径长度。

14. 以{5,6,7,8,9,10,15,18,22}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度(WPL)。

15. 以{10,12,16,21,30}作为叶子结点的权值构造一棵Huffman 树，并计算其带权路径长度(WPL)。

16. 如右所示的有向图，请给出它的： （1） 每个顶点的入度和出度；（2）邻接矩阵；（3）邻接表；（4）强连通分量。

17.已知一棵二叉树的中序和先序序列如下，求该二叉树的后序序列，并将它转换为树。

先序结果：A,B,E,F,C,D,G,H,I中序结果：E,F,B,C,G,H,I,D,A18.已知一棵二叉树的中序和后序遍历结果如下所示，求该二叉树的先序遍历序列。

中序结果：E,F,B,C,G,H,I,D,A后序结果：F,E,I,H,G,D,C,B,A19.请给出按自左向右的顺序依次将关键字为{30，5，20，23，9，27，6，14，45，22}的记录插入到一个初始时为空的二叉排序树后所建立的二叉排序树。

20.请将序列51，17，60，32，6，10，23，3，80，40，44，7排列为二叉排序树。

21.请将序列28，55，06，33，161，81，91，11，25，56，57，02排列为二叉排序树。

22.构造插入序列为{10，18，3，8，12，2，7，13}的二叉排序树，（要求过程）。

23.请给出下面的二叉树的先序、中序和后序遍历结果。

24.请给出下面的有向图的邻接矩阵、邻接表形式的存储结构，并计算出每个顶点的入度和出度。

725.已知某无向图的邻接表存储结构如下图所示，（1）请画出此无向图，（2）给出无向图的邻接矩阵表示。