作业-查找.doc

第七节 查找一、选择题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的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为( )。 *An+l B1 Cn Dn-16用顺序查找法对具有n个结点的线性表查找的时间复杂度量级为( )。 AO(n2) BO (nlog2n) *CO(n) DO (log2n)7用折半查找法对具有n个结点的线性表查找的时间复杂度量级为( )。 AO(n2) BO(nlog2n) CO(n) *DO(log 2n)8设哈希函数为H(key)=key7，一组关键字为(37，21，9，20，30，19，46)，哈希表T的地址空间为0.6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为( )。 A 0 1 2 3 4 5 6 21 20 37 9 46 30 19 *B 0 1 2 3 4 5 6 21 46 37 9 30 19 20 C 0 1 2 3 4 5 6 21 19 9 37 30 46 20 D0 1 2 3 4 5 6 20 37 30 21 46 19 99设有一个用线性探测法解决冲突得到的哈希表： 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14哈希函数为H(key)=key11，若要查找元素14，探测的次数是( )。 A3 *B6 C7 D910在哈希函数H(key)=keym中，一般来讲，m应取( )。 A奇数 B偶数 *C素数 D充分大的数11在具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为( )。 *AO(n) BO(1) CO(log2n) DO(n2)12有数据(49,32,40,6,45,12,56)，从空二叉树开始依次插入数据形成二叉排序树，若希望高度最小，则应选择下列( )输入序列。 A45，12，49，6，40，56，32 *B40，12，6，32，49，45，56 C6，12，32，13，45，49，56 D32，12，6，40，45，56，4914在一棵深度为h的具有n个元素的二叉排序树中，查找所有元素的最长查找长度为( )。 An Blog2n C(h+1)2 *Dh二、判断题1分块查找方法的平均查找长度低于顺序查找，高于折半查找。2前序遍历二叉排序树的结点就可以得到排好序的结点序列。3虽然关键字序列的顺序不一样，但依次生成的二叉排序树却是一样的。4对两棵具有相同关键字集合的形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。5在二叉排序树上插入新的结点时，不必移动其他结点，仅需要改动某个结点的指针，由空变为非空即可。6在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。三、填空题1二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值_大_于其左孩子(及其子孙)的键值且_小_于其右孩子(及其子孙)的键值。2在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值_大_的结点，只需通过结点x的右指针到它的右子树中去找。3中序遍历一棵二叉排序树所得到的结点访问序列是键值的_递增_序列。4二叉排序树上的查找长度不仅与_元素个数_有关，也与二叉排序树的_输入序列_有关。5二叉排序的查找效率与树的形态有关。当二叉排序树退化为一棵单支树时，查找算法退化为_顺序_查找，平均查找长度上升为_（n+1）/2_。6_散列_查找法的平均查找长度与元素个数n无关。7折半查找方法仅适用于这样的表：表中的记录必须_有序_，其存储结构必须是_顺序存储_。8考虑具有如下性质的二叉树：除叶结点外，每个结点的值都大于其左子树上的一切结点的值，并小于或等于其右子树上的一切结点的值。现把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)0123456789101189341416529413265121121112(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的散列地址空间中对该关键字序列构造哈希函数，并求查找成功的平均查找长度。答：01234567891011121314276805194521207024111011112136124查找成功ASL=（1+1+1+1+2+1+3+6+1+2+4）/11=23/113线性表的关键字集合(47，26，1