《数据结构》习题集:第9章 - 查找

更新时间:2024-01-02 00:02:01 阅读量: 教育文库 文档下载

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

第九章 查找

1.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为( ) A. 1,2,3 B. 9,5,2,3 C. 9,5,3 D. 9,4,2,3

2.设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为( )。

2

A. O(1) B. O(log2n) C. O(n) D. O(n) 5.设有序表中有1000个元素,则用二分查找查找元素X最多需要比较( )次。 A. 25 B. 10 C. 7 D. 1

6.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为( )。 A. O(n) B. O(n2) C. O(n1/2) D. O(1og2n) 8.( )二叉排序树可以得到一个从小到大的有序序列。

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 9.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为( )。 A. 1 B. 2 C. 3 D. 4 10.设某散列表的长度为100,散列函数H(k)=k % P,则P通常情况下最好选择( )。

A. 99 B. 97 C. 91 D. 93 11.在二叉排序树中插入一个关键字值的平均时间复杂度为( )。

A. O(n) B. O(1og2n) C. O(nlog2n) D. O(n2)

12.设一个顺序有序表A[1:14]中有14个元素,则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1],A[2],A[3],A[4] B.A[1],A[14],A[7],A[4] C.A[7],A[3],A[5],A[4] D. A[7],A[5] ,A[3],A[4] 13.设散列表中有m个存储单元,散列函数H(key)= key % p,则p最好选择( )。 A. 小于等于m的最大奇数 B. 小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 14.设顺序表的长度为n,则顺序查找的平均比较次数为( )。

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

15.设有序表中的元素为(13,18,24,35,47,50,62),则在其中利用二分法查找值为24的元素需要经过( )次比较。

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

17.设有一组初始记录关键字序列为(34,76,45,18,26,54,92),则由这组记录关键字生成的二叉排序树的深度为( )。

A. 4 B. 5 C. 6 D. 7 18.二叉排序树中左子树上所有结点的值均( )根结点的值。 A. < B. > C. = D. !=

26.对一棵二叉排序树采用中根遍历进行输出的数据一定是( ) A.递增或递减序列 B.递减序列 C.无序序列 D.递增

序列

27.一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当

1

二分查找值为82的结点时,查找成功时的比较次数为( ) A.1 B.2 C.4 D.8 28.若构造一棵具有n个结点的二叉排序树,最坏的情况下其深度不超过( )

nA.

2B. n

n?1 C. D. n+1

230.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 B.动态查找表

C.静态查找表与动态查找表 D.静态查找表或动态查找表

31.设一组记录的关键字key值为{62,50,14,28,19,35,47,56,83},散列函数为H(key)=key mod 13,则它的开散列表中散列地址为1的链中的结点个数是( )

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

32.已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134),当二分检索值为90的元素时,检索成功需比较的次数是( ) A.1 B.2 C.3 D.4

36.设有100个元素,用二分法查找时,最大比较次数是( )。

A.25 B.7 C.10 D.1 37.设有1000个元素,用二分法查找时,最小比较次数为( ) A.0 B.1 C.10 D.500 40.在一个有N个元素的有序单链表中查找具有给定关键字的结点,平均情况下的时间复杂性为( B )

A.O(1) B.O(N) C.0(N2) D.O(NlogN) 41.对线性表进行二分查找时,要求线性表必须( )

A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 42.下列二叉排序树中查找效率最高的是( ) A.平衡二叉树 B.二叉查找树

C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 44.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )

A.(100,80,90,60,120,110,130) B.(100,120,110,130,80,60,90) C.(100,60,80,90, 20,110,130) D.(100,80,60,90,120,130,110)

50.设哈希表长M=14,哈希函数H(KEY)=KEY MOD 11。表中已有4个结点:ADDR(15)=4, ADDR(38)=5,ADDR(61)=6,ADDR(84)=7,其余地址为空,如用二次探测再散列处理冲突,关键字为49的结点的地址是( )。

A. 8 B. 3 C. 5 D. 9 52.将10个元素散列到100000个单元的哈希表中,则( )产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 55.二叉查找树的查找效率与二叉树的树型有关, 在 ( )时其查找效率最低。 A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 64. 对于长度为 18 的顺序存储的有序表,若采用二分查找,则查找第 15 个元素的查找长度为 ( ) 。

2

A. 3 B. 4 C. 5 D. 6

二、填空题

7.根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为____________。

12.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较_________次。

13.设散列表的长度为8,散列函数H(k)=k % 7,用线性探测法解决冲突,则根据一组初始关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是________。

16.解决散列表冲突的两种方法是________________和__________________。 18.从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明_______,若元素的值小于根结点的值,则继续向________查找,若元素的大于根结点的值,则继续向________查找。

20.二叉搜索树的中序遍历得到的结点序列为____ ____。

27.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。 28.实现二分查找的存储结构仅限于顺序存储结构,且其中元素排列必须是____的。

31.一棵平衡二叉树中任一结点的平衡因子只可能是__________。 32.二分查找的时间复杂度为_________。

41.在线性表的________存储中,对每一个元素只能采用顺序查找。

48.对于二分查找所对应的判定树,它既是一棵_______,又是一棵________。 64. 平衡二叉树又称_________,其定义是________。 69. 在含有n个结点的二叉排序树中查找一个关键字,进行关键字比较次数最大值是 。

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

83. 在一棵二叉排序树中,每个分支结点的左子树上所有结点的值一定 ________ 该结点的值,右子树上所有结点的值一定 ________ 该结点的值。 86. 向一棵二叉排序树中插入一个元素时,若元素的值小于根结点的值,则接着向根结点的 ________ 插入,若元素的值大于根结点的值,则接着向根结点的 ________ 插入。

89. 在一棵平衡二叉排序树中,每个结点的左子树高度与右子树高度之差的绝对值不超过 ________ 。 四、简答题

6.对长度为20的有序表进行二分查找,试画出它的一棵判定树

3

8.一个线性表为B=(12,23,45,57,20,03,78,31,15,36),设散列表为HT[0..12],散列函数为H(key)= key % 13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。

21.一棵二叉排序树结构如下,各结点的值从小到大依次为1-9,请标出各结点的值。

22. 在查找和排序算法中,监视哨的作用是什么?

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

(1)按次序构造一棵二叉排序树BS。(2) 依此二叉排序树,如何得到一个从大到小的有序序列?

(2)画出在此二叉排序树中删除“66”后的树结构。

4

五、应用题 3.已知待散列的线性表为(36,15,40,63,22),散列用的一维地址空间为[0..6],假定选用的散列函数是H(K)= K mod 7,若发生冲突采用线性探查法处理,试: (1)计算出每一个元素的散列地址并在下图中填写出散列表: ` 0 1 2 3 4 5 6 (2)求出在查找每一个元素概率相等情况下的平均查找长度。

11.依次输入表{ 30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55 }中的元素,生成一棵二叉搜索树。

①试画出生成之后的二叉搜索树;

②对该二叉搜索树进行中序遍历,试写出遍历序列。

③假定每个元素的查找概率相等,试计算该二叉搜索树的平均查找长度。

18.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探查法处理冲突,试求出每一元素的散列地址,画出最后得到的散列表,求出平均查找长度。

5

19.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[11],若采用除留余数法构造散列函数和链接法处理冲突,试求出每一元素的散列地址,画出最后得到的散列表,求出平均查找长度。

六、程序填空题(或算法阅读题) 1.二叉搜索树的查找——递归算法:

bool Find(BTreeNode* BST,ElemType& item)

{

if (BST==NULL)

return false; //查找失败 else {

if (item==BST->data){

item=BST->data;//查找成功 return ___________;} else if(itemdata)

return Find(______________,item); else return Find(_______________,item); }//if }

七、算法设计题

1. 设有一组初始记录关键字序列(K1,K2,?,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。

3.设计在顺序有序表中实现二分查找的算法。

6.设计在二叉排序树上查找结点X的算法。

6

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

Top