数据结构第九章 查找 习题及答案

更新时间:2023-06-03 19:44:01 阅读量: 实用文档 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

数据结构课件

第九章 查找

一、 选择题

1.若查找每个记录的概率均等,则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。

A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( )

A. 表必须有序,表可以顺序方式存储,也可以链表方式存储 C. 表必须有序,而且只能从小到大排列

B. 表必须有序且表中数据必须是整型,实型或字符型 D. 表必须有序,且表只能以顺序方式存储

3. 用二分(对半)查找表的元素的速度比用顺序法( )

A.必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有12个关键字的有序表,折半查找的平均查找长度( ) A. 3.1 B. 4 C. 2.5 D. 5 5.当采用分块查找时,数据的组织方式为 ( )

A.数据分成若干块,每块内数据有序

B.数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块

C. 数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块 D. 数据分成若干块,每块(除最后一块外)中数据个数需相同

6. 二叉查找树的查找效率与二叉树的( (1))有关, 在 ((2))时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失

败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案:

A. 相同的 B.不同的

9.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )

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) 10. 在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。

A. LL B. LR C. RL D. RR 11. 下面关于m阶B-树说法正确的是( )

①每个结点至少有两棵非空子树; ②树中每个结点至多有m一1个关键字;

③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后,树长高一层。

A. ①②③ B. ②③ C. ②③④ D. ③

12. m阶B-树是一棵( ) A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 15. 设有一组记录的关键字为{19,14,23,1,68,20,84,27,55,11,10,79},用链 地址法构造散列表,散列函数为H(key)=key MOD 13,散列地址为1的链中有( ) 个记录。

A.1 B. 2 C. 3 D. 4 16. 关于哈希查找说法不正确的有几个( )

(1)采用链地址法解决冲突时,查找一个元素的时间是相同的

(2)采用链地址法解决冲突时,若插入规定总是在链首,则插入任一个元素的时间是

相同的

(3)用链地址法解决冲突易引起聚集现象 (4)再哈希法不易产生聚集

数据结构课件

A. 1 B. 2 C. 3 D. 4

17. 设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,

84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是( )

A.8 B.3 C.5 D.9 18. 假定哈希查找中k个关键字具有同一哈希值,若用线性探测法把这k个关键字存入散列表中,至少要进行多少次探测?( )

A.k-1次 B. k次 C. k+1次 D. k(k+1)/2次

19. 好的哈希函数有一个共同的性质,即函数值应当以( )取其值域的每个值。

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 20. 将10个元素散列到100000个单元的哈希表中,则( )产生冲突。

A. 一定会 B. 一定不会 C. 仍可能会

二、 判断题

1.采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找。( ) 2.在散列检索中,“比较”操作一般也是不可避免的。( ) 3.Hash表的平均查找长度与处理冲突的方法无关。 ( ) 4. 散列法的平均检索长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大。( )

5. 在索引顺序表中,实现分块查找,在等概率查找情况下,其平均查找长度不仅与表中元素个数有关,而且与每块中元素个数有关。( )

6. 就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。( ) 7. 最佳二叉树是AVL树(平衡二叉树)。( )

8.在查找树(二叉树排序树)中插入一个新结点,总是插入到叶结点下面。 ( ) 9.二叉树中除叶结点外, 任一结点X,其左子树根结点的值小于该结点(X)的值;其右子树根结点的值≥该结点(X)的值,则此二叉树一定是二叉排序树。( )

10.有n个数存放在一维数组A[1..n]中,在进行顺序查找时,这n个数的排列有序或无序其平均查找长度不同。( )

11. N个结点的二叉排序树有多种,其中树高最小的二叉排序树是最佳的。 ( ) 12. 在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二排序叉树与原二排序叉树相同。( )

13. B-树中所有结点的平衡因子都为零。 ( ) 14. 在平衡二叉树中,向某个平衡因子不为零的结点的树中插入一新结点,必引起平衡旋转。( )

三、填空题

1. 顺序查找n个元素的顺序表,若查找成功,则比较关键字的次数最多为__ __次;当使用监视哨时,若查找失败,则比较关键字的次数为__ __。

2.在有序表A[1..12]中,采用二分查找算法查等于A[12]的元素,所比较的元素下标依次为__________。

3. 在有序表A[1..20]中,按二分查找方法进行查找,查找长度为5的元素个数是__________ 4. 高度为4(含叶子结点层)的3阶b-树中,最多有__________个关键字。

5. 在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。

6. 在哈希函数H(key)=key%p中,p值最好取__________。

8. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中,则对这样的二叉排序 树检索时,平均比较次数为__________。

9. 如果关键码按值排序,而后用二分法依次检索这些关键码,并把检索中遇到的在二叉树

中没有出现的关键码依次插入到二叉排序树中,则对这样的二叉排序树检索时,平均比

数据结构课件

较次数为__________。(提示:此时二叉排序树与折半查找的二叉判定树一样了) 10. 平衡因子的定义是______ ____ 11. 查找是非数值程序设计的一个重要技术问题,__(1)__查找,__(2)__查找和

__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。

12. 具有N个关键字的B树的查找路径长度不会大于__________。在一棵有N 个结点的非平衡二叉树中进行查找,平均时间复杂度的上限(即最坏情况平均时间复杂度)为________ 13. 高度为5(除叶子层之外)的三阶B-树至少有__________个结点。 14. 可以唯一的标识一个记录的关键字称为__________。

15. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算,而后者不包含这两种运算。

16. 已知N元整型数组a存放N个学生的成绩,已按由大到小排序,以下算法是用对分(折半)查找方法统计成绩大于或等于X分的学生人数,请填空使之完善。( 提示:这时需要找的是最后一个大于等于X的下标,若查找成功其下标若为m,则有m个学生成绩大于或等于X,若查找不成功,若这时low所指向的值小于X,则有low-1个学生成绩大于或等于X,注意这时表中可能不止一个数值为X的值,这时我们要查找的是下标最大的) #define N /*学生人数*/

int uprx(int a[N],int x ) /*函数返回大于等于X分的学生人数*/ { int low=1,mid,high=N; do {mid=(low+high)/2;

if(x<=a[mid]) __(1)__ else __(2)__; }while(__(3)__);

if (a[low]<x) return low-1; return low; }

四、应用题 1. 名词解释:

哈希表

叙述B-树定义,主要用途是什么? 平衡二叉树(AVL树) 平衡因子

平均查找长度(ASL)

3. 设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key mod 7 ,表长为10,用开放地址法的二次探测再散列方法解决冲突Hi=(H(key)+di) mod

222

10(di=1,2,3, ,)。要求:对该关键字序列构造哈希表,并确定其装填因子,查找成功所需的平均探查次数。

4. 设一组数据为{1,14,27,29,55,68,10,11,23},现采用的哈希函数是H(key)=key MOD 13, 即关键字对13取模,冲突用链地址法解决,设哈希表的大小为13(0..12),试画出插入上述数据后的哈希表。

7. 设有一棵空的3阶B-树,依次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99,请画出该树。

9. 已知2棵2-3 B-树如下(省略外结点):

(1)对树(a),请分别画出先后插入26,85两个新结点后的树形; (2

数据结构课件

10. 输入一个正整数序列(53,17,12,66,58,70,87,25,56,60),试完成下列各题。

(1) 按次序构造一棵二叉排序树BS。

(2) 依此二叉排序树,如何得到一个从大到小的有序序列?

(3) 假定每个元素的查找概率相等,试计算该二叉排序树的平均查找长度 (4) 画出在此二叉排序树中删除“66”后的树结构。

11. 给定关键词输入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO},假定关键词

比较按英文字典序,试画出从一棵空树开始,依上述顺序(从左到右)输入关键词,用平衡树的查找和插入算法生成一棵平衡树的过程,并说明生成过程中采用了何种转动方式进行平衡调整,标出树中各结点的平衡系数。 12. 假定对有序表:(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题:

(1).画出描述折半查找过程的判定树;

(2).若查找元素54,需依次与那些元素比较? (3).若查找元素90,需依次与那些元素比较?

(4).假定每个元素的查找概率相等,求查找成功时的平均查找长度。

第9章 查找

一.选择题

三.填空题

1.n n+1 2.6,9,11,12 3.5

4.26(第4层是叶子结点,每个结点两个关键字) 5.m-1,「m/2 -1 9.2,4,3

6.小于等于表长的最大素数或不包含小于20的质因子的合数

8.(n+1)/2 9.(n+1)/n*log2(n+1)-1 10.结点的左子树的高度减去结点的右子树的高度 11.(1)静态查找表(2)动态查找树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区

数据结构课件

n 1

12.log m/2 (

2

)+1 ,(n+1)/2(最坏情况是每个结点只要一个孩子结点的情况,这时的

平均时间复杂度为(n+1)/2,而log (5(n 1)) 2是通常情况下的ASL) 13.31 14.主关键字 15.插入 删除

16(1)low=mid+1 (2)high=mid-1 (3)high>=low

四.应用题

1.概念是基本知识的主要部分,要牢固掌握。这里只列出一部分,目的是引起重视,解答略。 3.

查找成功平均查找长度:ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8

以关键字27为例:H(27)=27%7=6(冲突) H1=(6+1)%10=7(冲突)

23

H2=(6+2)%10=0(冲突) H3=(6+3)%10=5 所以比较了4次。

注意:计算查找失败时的平均查找长度,必须计算不在表中的关键字,当其哈希地址为i(0≤i≤m-1)时的查找次数。如下例中m=10。对于关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8,哈希函数为H(key)=key % 7采用线性探测再散列方法解决冲突,

4.

unsuccASL查找成功=18/13 7.如下图: 9.(1)当插入26后的树形为:

数据结构课件

插入85后树形为:

(2)删除53后为:

数据结构课件

删除37后:

10.

(1)构造的二叉排序树为: (4)删除结点66后;

(2)对于一个二叉排序树,想得到一个从大到小的序列只要先读右子树再读根结点,最后读左子树的遍历这颗二叉树就可以了。如果是要从小到大的序列,则只需中序遍历这颗二叉树就可。

(3)该二叉树的平均查找长度为: ASL=(1*1+2*2+3*4+4*3)/10=2.9

11.

数据结构课件

bd336x280();257-0-1000-257.jpg" alt="数据结构第九章 查找 习题及答案" />

12.(1)二叉判定树为

数据结构课件

(2)若要查找54,则需要查找:30,63,42,54 (3)若要查找90,则需查找:30,63,87,95,空

(4)假定每个元素的查找概率相等,则查找成功时的平均查找长度为: ASL=(1*1+2*2+4*3+5*4)/12=37/12

本文来源:https://www.bwwdw.com/article/kpk1.html

Top