数据结构手册面作业练习题（含答案）6-9

习 题 六 树 和 二 叉 树

6.1 单项选择题

1. 如图8.7所示的4棵二叉树，_C___不是完全二叉树。

（A）（B）（C）（D）图8.7 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 （A）（B）（C）（D）图8.8 4棵二叉树

3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__。 A. t—＞left=NULL B. t—＞ltag=1 C. t—＞ltag=1且t—＞left=NULL D. 以上都不对

4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B__。 A. 正确 B. 错误

5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。 A. 正确 B. 错误

6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。 A. 正确 B. 错误

7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__B__。

A. 2h B. 2h-1 C. 2h+1 D. h+1 a

8. 如图8.9所示二叉树的中序遍历序列___B_。

A. abcdgef B. dfebagc C. dbaefcg D. defbagc

abcdgef图8.9 一棵二叉树

9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是D____。

A. acbed B. decab C. deabc D. cedba

10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。

A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙

11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。B

A．15 B．16 C．17 D．47

12.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是D___ _。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca

13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__B__。 A. 正确 B. 错误

14. 按照二叉树的定义，具有3个结点的二叉树有__C__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为__B__。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh abcdefg图8.10 一棵二叉树h

16. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论___A_是正确的。

A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对

17. 深度为5的二叉树至多有___C_个结点。 A. 16 B. 32 C. 31 D. 10

18. 在一非空二叉树的中序遍历序列中，根结点的右边_A___。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点

19. 树最适合用来表示__C__。

A. 有序数据元素 B. 无序数据元素

C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

20. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A___。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 21. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用__C__存储结构。 A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构 22. 对一个满二叉树，m个树叶，n个结点，深度为h，则__D__ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1 23. 如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为_C___。 A. uwvts B. vwuts C. wuvts D. wutsv 24.具有五层结点的二叉平衡树至少有___B_个结点。F(n)=F(n-1)+F(n-2)+1, 1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量 A. 10 B. 12 C. 15 D. 17

25. 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__C__。 A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孙

6.2 填空题（将正确的答案填在相应的空中）

1. 有一棵树如图8.12所示，回答下面的问题：

⑴ 这棵树的根结点是___K1_；

⑵ 这棵树的叶子结点是___K2,K5,K7,K4_； ⑶ 结点k3的度是_2___； ⑷ 这棵树的度是___3_； ⑸ 这棵树的深度是_4___；

⑹ 结点k3的子女是__K5,K6__； ⑺ 结点k3的父结点是__K1__；

k1k2k3k4k5k6k7图8.12 一棵树 2. 指出树和二叉树的三个主要差别_树的结点个数至少为1，而二叉树的结点个数可以为0； 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 树的结点无左、右之分，而二叉树的结点有左、右之分。 3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_利用二叉树的已有算法解决树的有关问题___。

4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图8.13所示，则该二叉

树的链接表示形式为_ 1 2 3 4 5 6 e a f d

___。

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 g c j l h b 图8.13 一棵二叉树的顺序存储数组t

5. 深度为k的完全二叉树至少有__2k-1__个结点。至多有__2k-1__个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_2k-2+1___。 6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=_n2+1___。

7. 一棵二叉树的第i（i≥1）层最多有_2i-1___个结点；一棵有n（n>0）个结点的满二叉树共有__ 2[log2n+1]-1__个叶子和___2[log2n+1]-1_个非终端结点。

8. 结点最少的树为__只有一个结点的树__，结点最少的二叉树为_空二叉树___。

9. 现有按中序遍历二叉树的结果为abc，问有__5__种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。

10. 根据二叉树的定义，具有三个结点的二叉树有___5_种不同的形态，它们分别是__参照楼上__。 11. 由如图8.17所示的二叉树，回答以下问题： ⑴ 其中序遍历序列为_dgbaechif__； ⑵ 其前序遍历序列为___ abdgcefhi_； ⑶ 其后序遍历序列为_gdbeihfca___； ⑷ 该二叉树的中序线索二叉树为___

_；

⑸ 该二叉树的后序线索二叉树为____； ⑹ 该二叉树对应的森林是____。

a

bcdefg图8.20 一棵树

12. 已知一棵树如图8.20所示，转化为一棵二叉树，表示为_abcdefghi图8.17 一棵二叉树

___。

13. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为

____，其带权路径长度为__165__。 6.3 算法设计题: 1．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。 2. 一棵度为2的树与一棵二叉树有何区别? 3. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少? 4. 证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系: n0=(k-1)n1+1 5. 请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。

A

B C

D F E

GH

6. 画出和下列已知序列对应的树T：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBFG。

7. 假设用于通讯的电文仅有八个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 8. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。 9. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。

习 题 七 图

7.1 单项选择题 1. 在一个图中，所有顶点的度数之和等于所有边数的_A___倍。 A. 1/2 B. 1 C. 2 D. 4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__B__倍。 A. 1/2 B. 1 C. 2 D. 4 3. 一个有n个顶点的无向图最多有__C__条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 4. 具有4个顶点的无向完全图有__A__条边。 A. 6 B. 12 C. 16 D. 20 5. 具有6个顶点的无向图至少应有__A__条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8

6. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要___C_条边。 A. n B. n+1 C. n-1 D. n/2

7. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是__D__。 A. n B. (n-1)2 C. n-1 D. n2

8. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①A___；所有邻接表中的接点总数是_②C___。

① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e

9. 已知一个图如图9.5所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__D①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。 ① A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b ② A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D. a,c,f,d,e,b

abced图 9.5 一个无向图f10. 已知一有向图的邻接表存储结构如图9.6所示。 1 3 2 ^ 2 ^ 3 4 5 4 ^ 5 2 4 图9.6 一个有向图的邻接表存储结构

⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是__C__。 A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2

⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是__B__。 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2

11. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的__A__。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 12. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的_D___。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

13. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用___D_。 A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法

7.2 填空题（将正确的答案填在相应饿空中） 1. n个顶点的连通图至少_n-1___条边。 2. 在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于__1__，否则等于___0_。

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

4. 已知图G的邻接表如图9.7所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。 V1 V2 V5 V4 ^ v2 v3 V5 ^ v3 V6 ^ v4 ^ v5 V4 V6 V3 ^ v6 ^ 图9.7 图G的邻接表 5. 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 6.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。 7.3

1．已知如图所示的有向图，请给出该图的:

1 5 （1）每个顶点的入/出度；

（2）邻接距阵； （3）邻接表； （4）逆邻接表； 6（5）强连通分量。 2

3 4

2．请用克鲁斯卡尔普里姆两种算法分别构造最小生成树：

（1） a b d f 16 11 15 15 c 15 13 16 14 12 e 21 （2） 12 1 6 4 7 2 9 12 3 5 3. 试列出下图中全部的拓扑排序序列。 15 20 6 16 4 132 5 10

53 1 2

4 5

4. 请用图示说明从顶点a到其余各顶点之间的最短路径。

4

b d 11 6

3 8a f 9c e 2

7.4已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：

(1)请画出该AOE图。

(2)计算完成整个计划需要的时间。 (3)求出该AOE网的关键路径。 V1 V2 V3 V4 V5 V6 V7 V8 V9 V1 6 4 5 ∝ ∝ ∝ ∝ ∝ ∝ V2 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ V3 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ V4 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ V5 9 7 ∝ ∝ ∝ ∝ ∝ ∝ ∝ V6 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ V7 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ V8 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ V9 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 习 题 八 查 找 8.1 单项选择题 1. 顺序查找法适合于存储结构为_B___的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储 2. 对线性表进行二分查找时，要求线性表必须__C__。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序

3. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_C___. A. n B. n/2 C. (n+1)/2 D. (n-1)/2

4. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为__D__。 A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n)

5. 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，___C_次比较后查找成功。 A. 1 B. 2 C. 4 D. 8

6. 设哈希表长m=14，哈希函数H(key)=key。表中已有4个结点： H (15)=4; H (38)=5; H (61)=6; H (84)=7

如用二次探测再散列处理冲突，关键字为49的结点的地址是__D__。 A. 8 B. 3 C. 5 D. 9

7. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为__B__。

A. 35/12 B. 37/12 C. 39/12 D. 43/12

8.2 填空题（将正确的答案填在相应的空中）

1. 顺序查找法的平均查找长度为_ ___；二分查找法的平均查找长度为__ __；分块查找法（以二分查找确定块）的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。 2. 二分查找的存储结构仅限于__顺序存储__，且是___有序的_。 3. 在散列函数H(key)=key%p中，p应取__小于表长的最大素数__。 4. 假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为_1___，则比较二次查找成功的结点数为_2___，则比较三次查找成功的结点数为__4__，则比较四次查找成功的结点数为__8__，则比较五次查找成功的结点数为__5__，平均查找长度为_3.7___。 5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为_ O（n）___；若采用二分法查找，则时间复杂度为__ O（log2n）__；

6. 在散列存储中，装填因子

a

的值越大，则__存取元素时发生冲突的可能性越大__；的

值越小，则____。

8.3 综合练习题:

选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（i=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。

习 题 九 排 序

9.1 单项选择题

1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是___D_。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是___A_。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

4. 一组记录的关键字为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为____。

A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84， C. 84，79，56，46，40，38 D. 84，56，79，40，46，38 5. 一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为___C_。 A. 38，40，46，56，79，84 B. 40，38，46，79，56，84 C. 40，38，46，56，79，84 D. 40，38，46，84，56，79 6. 一组记录的关键字为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为___A_。 A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72 C. 16，25，48，35，79，82，23，36，40，72 D. 16，25，35，48，79，23，36，40，72，82 7. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__C__。

A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

8. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为_D___。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序

9. 用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：

⑴ 25，84，21，47，15，27，68，35，20

⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是__D_。

A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序

10. 下述几种排序方法中，平均查找长度最小的是_C___。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

11. 下述几种排序方法中，要求内存量最大的是___D_。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

12. 快速排序方法在_C___情况下最不利于发挥其长处。

A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 9.2 填空题 （将正确的答案填在相应的空中） 1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较__3次__。 2. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取__堆__方法，其次选取__快速__方法，最后选取___归并_方法；若只从排序结果的稳定性考虑，则应选取__归并__方法；若只从平均情况下排序最快考虑，则应选取__快速__方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取___堆_方法。 3. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用_堆排序___，若原始记录无序，则最好选用__快速__。 4. 对n个元素的序列进行起泡排序时，最少的比较次数是_n-1___。

9.3 综合题

1. 以关键字序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态： （1） 直接插入排序；

（2） 希尔排序（增量d[1]=5）； （3） 快速排序； （4） 堆排序； （5） 归并排序；

2. 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。

（1）(100,86,48,73,35,39,42,57,66,21); (2)(12,70,33,65,24,56,48,92,86,33)

(3)(103,97,56,38,66,23,42,12,30,52,06,20) (4)(05,56,20,23,40,38,29,61,35,76,28,100).

|'

本文来源：https://www.bwwdw.com/article/9to2.html