文档介绍：该【数据结构查找习题及答案 】是由【小辰GG】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【数据结构查找习题及答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第9章查找
一、单选题
()遍历,可得到结点值从小到大的排列序列。
,在平均情况下的时间复杂度大致为()。
(n)(1)(logn)(n2)
,在最坏情况下的时间复杂度为()。
(n)(1)(logn)(n2)
()。
(1)(n)(logn)(n2)
,与用其它三个序列所构造的结果不同的是()。
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)
,每个结点的平衡因子的取值范围是()。
A.-11B.-21
(56,42,50,64,48)依次插入结点生成一棵AVL树,当插入到值
为()的结点时需要进行旋转调整。
()个结点。
,其每个分支结点的平衡因子均为0,则该平衡二叉树共有()
个结点。
-1--1+-
,设最低的不平衡结点为A,并已知A的左
孩子的平衡因子为0,右孩子的平衡因子为1,则应作()型调整以使其平衡。
二、判断题
,关键字最小的结点必无左孩子,关键字最大的结点必无
右孩子。
(若存在的话)所有结点的关键字
值,且小于其右非空子树(若存在的话)所有结点的关键字值。
,将得到按照由小到大的排
列。
,则根结点一定是值最小的结点。
。
。
,小于其右孩子的值。
,则其中最小元素和最大元素一定是叶子结点。
,删除某结点后又将其插入,则所得二叉搜索树与原二叉
搜索树相同。
,则该结点一定成为叶子结点。
。
,其树上任一结点的平衡因子的绝对值不大于1。
,向某个平衡因子不为零的结点的树中插入一新结点,必引起平衡旋转。
三、填空题
,其关键字序列是一个有序表。
,构树的过造程即为对无
序序列进行排序的过程。
,每个分支结点的左子树上所有结点的值一定________该结点的值,
右子树上所有结点的值一定________该结点。
,若元素的值等于根结点的值,则表明_______,
若元素的值小于根结点的值,则继续向_______查找,若元素的值大于根结点的值,则
继续向________查找。
,若元素的值小于根结点的值,则接着向根结点的
________插入,若元素的值大于根结点的值,则接着向根结点的________插入。
。
。
,至多有个结点。
,每个结点的左子树高度与右子树高度之差的绝对值不超过________。
四、应用题
,结点的值为1~8,请标出各结点的值。
{62,68,30,61,25,14,53,47,90,84}中的元素,生成一棵二叉搜索树。画出
生成后的二叉搜索树(画出生成过程)。
{7,16,4,8,20,9,6,18,5},构造一棵二叉搜索树,并计算在等概率
情况下该二叉搜索树的平均查找长度ASL。(要求给出构造过程)
,严格按照二叉搜索树的插入算法(不进行平衡旋转),逐个插入关键
码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树,画出这棵二叉搜索树
并写出其前序、后序遍历序列。
{80,6,10,7,8,25,100,90},请画出该二
叉搜索树。
(45,80,48,40,22,78),要求构造一棵二叉搜索树并给
出构造过程。
(38,52,25,74,68,16,30,54,90,72),画出按序列中元素的次序
生成的一棵二叉搜索树,求出其平均查找长度。
(24,15,38,27,121,76,130)的各元素依次插入一棵初始为空的二叉搜索
树中,请画出最后的结并求等概率情况下查找成果功的平均查找长度。
{40,28,6,72,100,3,54,1,80,91,38},建立一棵二叉搜索树,然后
删除结点72,分别画出该二叉树及删除结点72后的二叉树。
,可构成多种形态的二叉搜索树。请画出4棵含1,2,3,
4四个元素且以1为根、深度为3的二叉搜索树。
。
20
1140
62450
35
384560
28
(25,16,34,39,28,56),
1)画出按此序列生成的二叉搜索树。
2)计算等概率下查找成功时的平均查找长度。
(53,17,12,66,58,70,87,25,56,60),试完成下列各题。
(1)按次序构造一棵二叉搜索树BS。
(2)依此二叉搜索树,如何得到一个从大到小的有序序列?
(3)假定每个元素的查找概率相等,试计算该二叉搜索树的平均查找长度
(4)画出在此二叉搜索树中删除“66”后的树结构。
,并画出一棵这样的树。
,1,4,6,9,8,5,7时每一插入后AVL树的形
态。若做了某种旋转,说明旋转的类型。
,5,7,2,1,3,6,生成一棵AVL树,画出构造过程。
,5,7,2,1,3,6,分别生成二叉搜索树和AVL树,并用二叉搜索树和
AVL树两种方法查找,给出查找6的查找次数及查找成功的平均查找长度。
{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO},假
定关键词比较按英文字典序,试画出从一棵空树始,依开上述顺序(从左到右)输入关
键词,用AVL树的插入算法生成一棵AVL树的过程,并说明生成过程中采用了何种转
动方式进行平衡调整,标出树中各结点的平衡因子。
参考答案
一、
1--
二、
1-5.√√√√×6-10.××××√11-13.√√×
三、
,大于
,左子树,右子树
,右子树
(n2)
,15
四、
1.
2.
3.
ASL=(1+2*2+3*3+4*3)/9=26/9=
4.
前序:181057368272541325199
后序:5102532514**********
5.
6.
,平均查找长度等于32/10。
=1+2×2+3×2+4×2=19/7。
9.
二叉搜索树删除72后的二叉搜索树
10.
11.
或
12.(1)
(2)(1+2*2+3*2+4*1)/6=
13.(1)构造的二叉搜索树为:(4)删除结点66后
(2)对于一个二叉搜索树,想得到一个从大到小的序列只要先读右子树再读根结点,最
后读左子树的遍历这颗二叉树就可以了。如果是要从小到大的序列,则只需中序遍历这
颗二叉树即可。
(3)该二叉树的平均查找长度为:ASL=(1*1+2*2+3*4+4*3)/10=
15.
16.
从二叉搜索树查找6需4次,平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/7≈。
从平衡二叉树查找6需2次,平均查找长度ASL=(1+2+2+3+3+3+3)=17/7≈。
18.
单向左旋
先右旋后左旋