《数据结构习题-5》由会员分享，可在线阅读，更多相关《数据结构习题-5（8页珍藏版）》请在金锄头文库上搜索。
1、第8章 查找8.1选择题1顺序查找法适合于存储结构为（）的线性表。 A）散列存储 B）顺序存储或链接存储 C）压缩存储 D）索引存储2下面哪些操作不属于静态查找表（）A）查询某个特定元素是否在表中B）检索某个特定元素的属性C）插入一个数据元素D）建立一个查找表3下面描述不正确的是（）A）顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。B）静态查找表中关键字有序时，可用二分查找。C）分块查找也是一种静态查找表。D）经常进行插入和删除操作时可以采用二分查找。4散列查找时，解决冲突的方法有（）A）除留余数法B）数字分析法 C）直接定址法 D）链地址法5若表中的记录顺序存放在一个一维数组中，
2、在等概率情况下顺序查找的平均查找长度为（）A）O（1）B）O(log2n) C）O(n) D）O(n2)6对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为（）A）11/8 B）7/4 C）9/4 D）11/47静态查找表与动态查找表二者的根本差别在于（）A）它们的逻辑结构不一样 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样8若查找表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下二分法查找的平均检索长度是（）A）O(n)B）O(l
3、og2n)C）O(nlog2n) D）O(log2n)2)9对有14个数据元素的有序表R14（假设下标从1开始）进行二分查找，搜索到R4的关键码等于给定值，此时元素比较顺序依次为（）。A）R1，R2，R3，R4 B）R1，R13，R2，R3C）R7，R3，R5，R4 D）R7，R4，R2，R310设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（）次。A）9B）8C）7D）6 11请指出在顺序表2,5,7,10,14,15,18,23,35,41,52中，用二分法查找关键码12需做（）次关键码比较。A）2B）3 C）4 D）512从具有 n 个结点的二叉排序树中查
4、找一个元素时，在最坏情况下的时间复杂度为 ( ) 。 A )O (n) B） O（1） C） O (log 2 n) D）O (n 2 ) 13分块查找时确定块的查找可以用顺序查找，也可以用（ ），而在块中只能是（ ）A）静态查找，顺序查找B）二分查找，顺序查找 C）二分查找，二分查找D）散列查找，顺序查找14采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。A）10B）25 C）6 D）62515采用分块查找法（块长为s，以二分查找确定块）查找长度为n的线性表时，每个元素的平均查找长度为（ ）A）s+n B）l
5、og2ns/2 C）log2 (n/s+1)+s/2 D）(n+s)/2 16对一棵二叉排序树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是（）A）小于 B）大于C）等于D）不小于17若二叉排序树中关键字互不相同，则下面命题中不正确的是（ ）A）最小元和最大元一定是叶子B）最大元必无右孩子C）最小元必无左孩子D）新结点总是作为叶结点插入二叉排序树 18设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列（）不可能是在二叉排序树上查找到的序列? A）2,252,401,398,330, 344,397,363B）924, 220, 911,
6、 244, 898, 258, 362, 363C）2, 399, 387, 219, 266, 382, 381, 278, 363 D）925, 202, 911, 240, 912, 245, 36319在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 0:6 ，采用线性再散列法处理冲突。插入后的散列表应该如（）所示。 A）0 1 2 3 4 5 6 THU TUE WED FRI SUN SAT MON B） 0 1 2 3 4 5 6 T
7、UE THU WED FRI SUN SAT MON C） 0 1 2 3 4 5 6 TUE THU WED FRI SAT SUN MON D） 0 1 2 3 4 5 6 TUE THU WED SUN SAT FRI MON20若根据查找表建立长度为 m 的散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则下一次的散列地址为 ( ) 。 A） d B） (d+1)%m C） (d+1)/m D） d+121若根据查找表建立长度为 m 的散列表，采用二次探测法处理冲突，假定对一个元素第一次计算的散列地址为 d ，则第四次计算的散列地址为 ( ) 。 A )(d
8、+1)%m B） (d-1)%m C） (d+4)%m D） (d-4)%m 22下面有关散列查找的说法中正确的是（ ）A）直接定址法所得地址集合和关键字集合的大小不一定相同。B）除留余数法构造的哈希函数H(key)=key MOD p，其中P必须选择素数。C）构造哈希函数时不需要考虑记录的查找频率。D）数字分析法适用于对哈希表中出现的关键字事先知道的情况。23下面有关散列冲突解决的说法中不正确的是（ ）A）处理冲突即当某关键字得到的哈希地址已经存在时，为其寻找另一个空地址。B）使用链地址法在链表中插入元素的位置随意，即可以是表头表尾，也可以在中间。C）二次探测能够保证只要哈希表未填满，总能找
9、到一个不冲突的地址。D）线性探测能够保证只要哈希表未填满，总能找到一个不冲突的地址。24设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7其余地址为空，如用二次探测处理冲突，关键字为49的结点的地址是（）A）8B）3C）5D）98.2填空题1在散列函数H(key)=key%p中，p应取_。2采用分块查找法（块长为s，以顺序查找确定块）查找长度为n的线性表时的平均查找长度为_。3己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当二分查找值为29
10、和90的元素时，分别需要_次和_次比较才能查找成功；若采用顺序查找时，分别需要_次和_次比较才能查找成功。4从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明 _ ，若元素的值小于根结点的值，则继续向 _查找，若元素的值大于根结点的值，则继续向 _ 查找。5二分查找的存储结构仅限于 _，且是_。6假设在有序线性表A1.20上进行二分查找，则比较一次查找成功的结点数为 _个 ，比较二次查找成功的结点数为_ ，比较三次查找成功的结点数为_ ，比较四次查找成功的结点数为_ ，比较五次查找成功的结点数为_，平均查找长度为_ 。7在对有20个元素的递增有序表作二分查找时，查找长度为5的元
11、素的下标从小到大依次为_。（设下标从1开始）8对于线性表（70,34,55,23,65,41,20,100）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有_个，散列地址为7的元素有_ 个。9索引顺序表上的查找分两个阶段：_、_。10分块查找中，要得到最好的平均查找长度，应对256个元素的线性查找表分成_块，每块的最佳长度是_。若每块的长度为8，则等概率下平均查找长度为_。11_是一棵二叉树，如果不为空，则它必须满足下面的条件：A）若左子树不空，则左子树上所有结点的值均小于根的值。B）若右子树不空，则右子树上所有结点的值均大于根的值。C）其左右子树均为二叉排序树。13
12、假定有k个关键字互为同义词，若用线性探测法把这些同义词存入散列表中，至少要进行_次探测。8.3应用题1设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)，请分别画出对给定值a, g和n进行折半查找的过程。2已知一棵二叉排序树如下： （1）假如删除关键字28，画出新二叉树。（2）若查找56，需和哪些关键字比较。3已知散列表的地址区间为011，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。4设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。5假定一个待散列存储
