数据结构查找习题及答案.doc

(完整版)数据结构查找习题及答案
第9章 查找
一、单选题
1. 对一棵二叉搜索树按()遍历，可得到结点值从小到大的排列序列.
A。 先序　 B。 中序 C. 后序 D。 层次
2. 从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。
A. O（n) B。 O（1） C。 O（logn） D. O(n2)
3. 从具有n个结点的二叉搜索树中查找一个元素时,在最坏情况下的时间复杂度为（）。
A。 O（n） B。 O（1) C. O(logn) D。 O（n2)
4. 在二叉搜索树中插入一个结点的时间复杂度为（）.
A。 O（1) B。 O(n) C。 O(logn) D。 O(n2）
5. 分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是(）。
A．（100,80， 90， 60， 120，110,130）
B。（100，120,110，130，80, 60， 90)
C.（100，60， 80， 90， 120，110,130）
D.（100，80， 60， 90， 120，130，110)
6. 在一棵AVL树中,每个结点的平衡因子的取值范围是().
A. —1~1 B。 -2~2 C. 1~2 D. 0～1
7. 根据一组关键字(56，42,50,64，48）依次插入结点生成一棵AVL树，当插入到值为（)的结点时需要进行旋转调整。
A. 42 B. 50 C。 64 D. 48
8. 深度为4的AVL树至少有（）个结点.
A．9 B. 8 C。 7 D。 6
9. 一棵深度为k的AVL树，其每个分支结点的平衡因子均为0,则该平衡二叉树共有（）个结点。
A。2k—1-1 B.2k—1+1 C.2k—1 D。2k
10. 在AVL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ） 型调整以使其平衡。
A. LL B. LR C。 RL D. RR
二、判断题
1. 二叉搜索树的任意一棵子树中,关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。
2. 二叉搜索树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。
3. 二叉搜索树按照中序遍历将各结点打印出将各结点打印出来,将得到按照由小到大的排列。
4. 若二叉搜索树的根结点没有左儿子，则根结点一定是值最小的结点.
5. 二叉搜索树一定是满二叉树。
6. 从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点.
7. 二叉搜索树的充要条件是任一结点的值均大于其左孩子的值,小于其右孩子的值.
8. 若二叉搜索树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点.
9. 在任意一棵非空二叉搜索树中，删除某结点后又将其插入，则所得二叉搜索树与原二叉搜索树相同。
10. 当向二叉搜索树中插入一个结点,则该结点一定成为叶子结点。
11. AVL树是指左右子树的高度差的绝对值不大于1的二叉树。
12. AVL是一棵二叉树，其树上任一结点的平衡因子的绝对值不大于1。
13. 在AVL树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转.
三、填空题
1. 在一棵二叉搜索树上实施 遍历后，其关键字序列是一个有序表。
2. 一个无序序列可以通过构造一棵_______而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
3. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点。
4. 从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向_______查找,若元素的值大于根结点的值,则继续向________查找。
5. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。
6. 根据n个元素建立一棵二叉搜索树的时间复杂度大致为________。
7. 二叉树中某一结点左子树的深度减去右子树的深度称为该结点的_______.
8. 深度为4的平衡二叉树中至少有 个结点，至多有 个结点.
9. 在一棵AVL树中,每个结点的左子树高度与右子树高度之差的绝对值不超过________。
四、应用题
1. 一棵二叉搜索树的结构如下图所示，结点的值为1～8，请标出各结点的值.

2. 若依次输入序列｛62,68,30,61，25,14，53，47，90，84｝中的元素，生成一棵二叉搜索树.画出生成后的二叉搜索树(画出生成过程)。
3. 依次读入给定的整数序列{7,16，4,8,20，9，6，18,5}，构造一棵二叉搜索树，并计算在等概率情况下该二叉搜索树的平均查找长度ASL.（要求给出构造过程）
4. 从空二叉树开始，严格按照二叉搜索树的插入算法（不进行平衡旋转），逐个插入关键码｛18， 73, 10， 5， 68, 99， 27, 41， 51， 32， 25｝构造出一棵二叉搜索树，画出这棵二叉搜索树并写出其前序、后序遍历序列。
5. 若一棵二叉搜索树的关键字输入序列为｛80,6，10，7，8,25，100，90｝,请画出该二叉搜索树.
6. 设有一组初始记录关键字为（45，80，48，40，22，78），要求构造一棵二叉搜索树并给出构造过程。
7. 假定一个关键字序列为（38， 52, 25, 74， 68, 16, 30, 54, 90， 72)，画出按序列中元素的次序生成的一棵二叉搜索树，求出其平均查找长度。
8. 将数列（24，15,38，27，121，76,130)的各元素依次插入一棵初始为空的二叉搜索树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。
9. 输入一个正整数序列{40, 28, 6， 72， 100, 3, 54, 1, 80， 91， 38｝，建立一棵二叉搜索树,然后删除结点72,分别画出该二叉树及删除结点72后的二叉树。
10. 根据元素插入的先后次序不同，可构成多种形态的二叉搜索树。请画出4棵含1，2,3,4四个元素且以1为根、深度为3的二叉搜索树。
11. 请画出从下面的二叉搜索树中删除关键码40后的结果。

12. 对关键字序列（25, 16， 34, 39， 28， 56），
1)画出按此序列生成的二叉搜索树。
2）计算等概率下查找成功时的平均查找长度.
13. 输入一个正整数序列（53， 17， 12， 66， 58, 70, 87， 25， 56, 60），试完成下列各题。
(1）按次序构造一棵二叉搜索树BS。
（2）依此二叉搜索树，如何得到一个从大到小的有序序列?
（3)假定每个元素的查找概率相等，试计算该二叉搜索树的平均查找长度
（4）画出在此二叉搜索树中删除“66”后的树结构。
14. 试推导深度为5的平衡二叉树最少包含多少个结点,并画出一棵这样的树。
15. 画出在一个初始为空的AVL树中依次插入3， 1, 4, 6, 9， 8， 5, 7时每一插入后AVL树的形态.若做了某种旋转,说明旋转的类型.
16. 给定一个关键字序列4, 5， 7， 2， 1, 3， 6，生成一棵AVL树,画出构造过程.
17. 给定关键字序列4， 5， 7， 2, 1, 3, 6，分别生成二叉搜索树和AVL树，并用二叉搜索树和AVL树两种方法查找，给出查找6的查找次数及查找成功的平均查找长度。
18. 给定关键词输入序列{CAP， AQU, PIS， ARI， TAU, GEM, CAN， LIB, VIR, LEO， SCO｝，假定关键词比较按英文字典序，试画出从一棵空树开始，依上述顺序（从左到右)输入关键词,用AVL树的插入算法生成一棵AVL树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡因子.
参考答案
一、
1-5. BCABC 6—10。 ABCCC
二、
1-5. √√√√× 6-10。 ××××√ 11-13. √√×
三、
1. 中序
2. 二叉搜索树
3. 小于，大于
4. 查找成功，左子树，右子树
5. 左子树,右子树
6. O(n2)
7. 平衡因子
8. 7, 15
9. 1
四、
1.

2.

3.

ASL= (1+2＊2+3*3+4*3)/9 = 26/9 = 2.89
4.

前序：18 10 5 73 68 27 25 41 32 51 99
后序：5 10 25 32 51 41 27 68 99 73 18
5.

6.

7. 二叉搜索树如图所示,平均查找长度等于32/10。

8. 平均查找长度=1+2×2+3×2+4×2=19/7。

9.
二叉搜索树 删除72后的二叉搜索树

10.

11.
或
12. (1)

（2)（1+2＊2+3*2+4*1）/6 = 2.5

13. （1）构造的二叉搜索树为： （4)删除结点66后

（2） 对于一个二叉搜索树，想得到一个从大到小的序列只要先读右子树再读根结点，最后读左子树的遍历这颗二叉树就可以了。如果是要从小到大的序列，则只需中序遍历这颗二叉树即可。
(3）该二叉树的平均查找长度为：ASL=（1*1+2＊2+3＊4+4*3）/10=2。9
14. 略
15.

16.

17. 二叉搜索树 AVL树

从二叉搜索树查找6需4次，平均查找长度ASL=（1+2+2+3+3+3+4）/7=18/7≈2。57。
从平衡二叉树查找6需2次,平均查找长度ASL=（1+2+2+3+3+3+3）=17/7≈2.43。
18.