手机版

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

发布时间:2021-06-07   来源:未知    
字号:

数据结构课件

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. 如果关键码按值排序,而后用二分法依次检索这些关键码,并把检索中遇到的在二叉树

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

数据结构第九章 查找 习题及答案(2).doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
×
二维码
× 游客快捷下载通道(下载后可以自由复制和排版)
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
注:下载文档有可能出现无法下载或内容有问题,请联系客服协助您处理。
× 常见问题(客服时间:周一到周五 9:30-18:00)