1、第七节 查找一、选择题1顺序查找法适合于( )存储结构的查找表。A压缩 B散列 C索引 *D顺序或链式2对采用折半查找法进行查找操作的查找表，要求按( )方式进行存储。A顺序存储 B链式存储 *C顺序存储且结点按关键字有序 D链式存储且结点按关键字有序3设顺序表的长为 n，用顺序查找法, 则其每个元素的平均查找长度是( )。*A(n+1)2 B(n-1)2 Cn2 Dn4设有序表的关键字序列为(1，4，6 ， 10，18，35，42 ，53，67，71，78，84，92，99)，当用折半查找法查找键值为 35 67 的结点时，经( )次比较后查找成功。A2 B3 *C4 D65在表长为 n 的
2、顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为( )。*An+l B1 Cn Dn-16用顺序查找法对具有 n 个结点的线性表查找的时间复杂度量级为( )。AO(n 2) BO (nlog 2n) *CO(n) DO (log 2n)7用折半查找法对具有 n 个结点的线性表查找的时间复杂度量级为( )。AO(n 2) BO(nlog 2n) CO(n) *DO(log 2n)8设哈希函数为 H(key)=key7 ，一组关键字为(37，21 ，9，20，30 ，19 ，46)，哈希表 T 的地址空间为 0.6，用线性探测法解决冲突，依次将这组关键字插入 T 中，得到的哈希表为(
3、)。A 0 1 2 3 4 5 621 20 37 9 46 30 19*B 0 1 2 3 4 5 621 46 37 9 30 19 20C 0 1 2 3 4 5 621 19 9 37 30 46 20D0 1 2 3 4 5 620 37 30 21 46 19 99设有一个用线性探测法解决冲突得到的哈希表：0 1 2 3 4 5 6 7 8 9 1013 25 80 16 17 6 14哈希函数为 H(key)=key11，若要查找元素 14，探测的次数是( )。A3 *B6 C7 D910在哈希函数 H(key)=keym 中，一般来讲，m 应取( )。A奇数 B偶数 *C素数
4、D充分大的数11在具有 n 个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为( )。*AO(n) BO(1) CO(log 2n) DO(n 2)12有数据(49,32,40,6,45,12,56) ，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列( )输入序列。A45，12 ，49 ，6，40，56 ，32 *B 40，12 ，6，32，49，45 ，56 C6，12，32，13 ，45，49，56 D32，12，6，40，45，56 ，4914在一棵深度为 h 的具有 n 个元素的二叉排序树中，查找所有元素的最长查找长度为( )。An Blog 2n C
5、(h+1)2 *Dh二、判断题1分块查找方法的平均查找长度低于顺序查找，高于折半查找。2前序遍历二叉排序树的结点就可以得到排好序的结点序列。3虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。4对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。5在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。6在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。三、填空题1二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值_大_于其左孩子(及其子孙) 的键
6、值且_小_于其右孩子(及其子孙) 的键值。2在表示一棵二叉排序树的二叉链表上，要找键值比某结点 X 的键值_大_的结点，只需通过结点 x 的右指针到它的右子树中去找。3中序遍历一棵二叉排序树所得到的结点访问序列是键值的_递增_序列。4二叉排序树上的查找长度不仅与_元素个数 _有关，也与二叉排序树的_输入序列_有关。5二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为_顺序_查找，平均查找长度上升为_（n+1）/2_。6_散列_查找法的平均查找长度与元素个数 n 无关。7折半查找方法仅适用于这样的表：表中的记录必须_有序_，其存储结构必须是_顺序存储_。8考虑具有如
7、下性质的二叉树：除叶结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把 9 个数 1，2，3 ，4，5，6 ，7，8 ，9 填入如图 9-1 所示的二叉树中，并使之满足上述性质(圆圈旁边的数字表示插入结点的序号)。四、应用题1已知有长度为 9 的表(16,29,32,5,89,41,14,65,34)，它们存储在一个0-11 的哈希表中，哈希函 H(key)=key%11，利用线性探测再散列法 (1)将数据填入到哈希表中。 (2)计算查找成功时的平均查找长度。答： (1)0 1 2 3 4 5 6 7 8 9 10 1189 34 14 16 5 2
8、9 41 32 651 2 1 1 2 1 1 1 2(4)ASL=(1+2+1+1+2+1+1+1+2)/9=12/9=4/32设有一组关键字(19，05，21，24，45 ，20 ，68，27，70 ，11，10)，用哈希函数 H(key)=key13，采用线性探测再散列方法解决冲突，试在 014 的散列地址空间中对该关键字序列构造哈希函数，并求查找成功的平均查找长度。答：0 1 2 3 4 5 6 7 8 9 10 11 12 13 1427 68 05 19 45 21 20 70 24 11 101 1 1 1 2 1 3 6 1 2 4查找成功 ASL=（1+1+1+1+2+1+3+6+1+2+4）/11=23/113线性表的关键字集合(47，26 ，120，08 ，39，68，96，23，70 ，63，57)，已知散列函数为H(key)=key13 ，采用链地址法处理冲突。设计出这种链表结构，并计算该表的查找成功平均查找长度。答：图略。查找成功 ASL=(1*6+2*4+3*1)/11=17/11
