《数据结构》习题集：第9章 查找(第1次更新2012-5).docxVIP

第9章 查找选择题顺序查找一个共有n个元素的线性表，其时间复杂度为（ ），折半查找一个具有n个元素的有序表，其时间复杂度为（ ）。【＊，★】O(n) B. O(log2n) C. O(n2) D. O(nlog2n)在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（ ）。【＊，★】n B. C. D. 采用顺序查找方式查找长度为n的线性表时，平均查找长度为（ ）。【＊】n B. n/2 C. (n+1)/2 D. (n-1)/2采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（ ）对应判定树的高度（设高度大于等于2）。【＊＊】小于 B. 大于 C. 等于 D. 大于等于已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的比较次数为（ ）。【＊】1 B. 2 C. 3 D. 4对线性表进行折半查找时，要求线性表必须（ ）。【＊】以顺序方式存储 B. 以链接方式存储以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序顺序查找法适合于存储结构为（ ）的查找表。【＊】散列存储 B. 顺序或链接存储 C. 压缩存储 D. 索引存储采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（ ）个结点最佳。【＊＊】10 B. 25 C. 6 D. 625从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l，建立二叉排序树，则其先序遍历序列为（ ），中序遍历序列为（ ）。【＊＊，★】 abcloprstu B. alcpobsrut C. trbaoclpsu D. trubsaocpl折半查找和二叉排序树的时间性能（ ）。【＊】相同 B. 不相同一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。2k-1-1 B. 2k-1 C. 2k-1+1 D. 2k-1利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要进行（ ）元素间的比较。4次 B. 5次 C. 7次 D. 10次设Hash地址空间为0到m-1，哈希函数为h(k)=k%p，为了减少发生冲突的可能性，一般取p为（ ）。小于m的最大奇数 B. 小于m的最大素数 C. 小于m的最大偶数 D. 小于m的最大合数长度为10的按关键字有序的查找表采用顺序组织方式。若采用折半查找方法，则在等概率情况下，查找失败时的ASL值是（ ）。24/10 B. 24/11 C. 39/10 D. 39/11在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ）n+1 B. 1 C. n D. n-1设哈希函数为H(key)=key%7，一组关键字为（37，21，9，20，30，19，46），哈希表T的地址空间为0…6，用线性探测法解决冲突，依次将这组关键字插入T中，得到的哈希表为（ ）。【＊，★】设有一个用线性探测法解决冲突得到的哈希表：哈希函数为H(key)=key%11，若要查找元素14，探测的次数是（ ）3 B. 6 C. 7 D. 9在哈希函数H(key)=key%m中，一般来讲，m应取（ ）。奇数 B. 偶数 C. 素数 D. 充分大的数分块查找的时间性能（ ）。低于二分查找B. 高于顺序查找而低于二分查找高于顺序查找D. 低于顺序查找高于二分查找以下说法错误的是（ ）。哈希法存储的基本思想是由关键字的值决定数据的存储地址哈希表的结点中只包含数据元素自身的信息，不