《数据结构与算法》第九章-查找习题.docx

《《数据结构与算法》第九章-查找习题.docx》由会员分享，可在线阅读，更多相关《《数据结构与算法》第九章-查找习题.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法第二部分习题精选一、填空题I.在数据的存放无规律而言的线性表中进行检索的最佳方法是 O2 .线性有序表(ai，a2, a3,，a.)是从小到大排列的,对一个给定的值k,用二分法检索 表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。设有100个结点，用二分法查找时，最大比较次数是。3 .假设在有序线性表a20上进行折半查找，则比较一次查找成功的结点数为1；比较两次 查找成功的结点数为;比较四次查找成功的结点数为:平均查找长度 为 O.折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表中元素20,它 将依次与表中元素 比

2、较大小。4 .在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 o.散列法存储的基本思想是由 决定数据的存储地址。5 .有一个表长为m的散列表，初始状态为空，现将n(nm)个不同的关键码插入到散列表 中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总 次数是。二、单项选择题()1.在表长为n的链表中进行线性查找，它的平均查找长度为 A.ASL = n;B.ASL=(n+l)/2;C. A S L = yfn + 1; D. ASLl og2 (n+1) 1()2.折半查找有序表(4, 6, 10, 12, 20, 30, 50, 70, 88, 100)。

3、若查找表中元素58,则它将依次与表中 比较大小，查找结果是失败。A. 20, 70, 30, 50 B. 30, 88, 70, 50 C. 20, 50 D. 30, 88, 50()3.对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A. 3B. 4C. 5D. 6()4.链表适用于查找A.顺序 B.二分法 C.顺序，也能二分法 D.随机()5.折半搜索与二叉搜索树的时间性能A.相同 氏 完全不同C.有时不相同D.数量级都是O(log2n)三、简答题1 .对分(折半)查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性 查找的速度快，这种说法对吗？2

4、.假定对有序表：(3, 4, 5, 7, 24, 30, 42, 54, 63, 72, 87, 95)进行折半查找，试回答 下列问题：(1) 画出描述折半查找过程的判定树；(2) 若查找元素54,需依次与哪些元素比较？(3) 若查找元素9(),需依次与哪些元素比较？ (4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。3 .用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么？ 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少？4 .设哈希(Hash)表的地址范围为0-17,哈希函数为：H (K) =K MOD 16。K为关键字，用线性探测法

5、再散列法处理冲突，输入关键字序列：(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)造出Hash表，试回答下列问题:(1) 画出哈希表的示意图；(2)若查找关键字63,需要依次与哪些关键字进行比较？(3)若查找关键字60,需要依次与哪些关键字比较？(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 四、分析题.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查 找长度。1 .在一棵空的二叉查找树中依次插入关键字序列为12, 7, 17, 11, 16, 2, 13, 9, 21, 4, 请画出所得到的二叉查找树。2

6、 .已知如下所示长度为12的表：(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec)(i)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排 序树，并求其在等概率的情况下杳找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时 查找成功的平均查找长度。(3)按表中元素顺序构造一棵平衡二又排序树，并求其在等概率的情况下查找成功的平均查 找长度。3 .选取散列函数H (key) = (3*key) %11,用线性探测法处理冲突，对下列关键码序列构 造一

7、个散列地址空间为010,表长为11的散列表，22, 41, 53, 08, 46, 30, 01, 31, 66 a五、算法设计题1 .已知II个元素的有序表为(05 13 19 21 37 56 64 75 80 88 92),请写 出折半查找的算法程序，查找关键字为key的数据元素(建议上机调试)。2 .试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不同。习题答案、1.顺序查找(线性查找)2. 8 73.2 8 3.7 4. 28, 6, 12, 205.散列查找6.关键字的值7.n(n-l)/2= ( I+2 + -+n-l)二、1.

8、 (B) 2. (A) 3. (C) 4. (A) 5. (C)三、简答题.答：不适合！虽然有序的单链表的结点是按从小到大(或从大到小)顺序排列，但因其 存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时, 则线性查找快；而二分查找则慢得多。1 .解：(1)先画出判定树如下(注：mid=L(l + l2)/2j=6)：(2)查找元素54,需依次与3(), 63, 42. 54等元素比较；(3)查找元素90,需依次与30. 63,87,95, 72等元素比较；(4)求ASL之前，需要统计每个元素

9、的查找次数。判定树的前3层共查找1+2X2+4X 3=17 次；但最后一层未满，不能用8义4,只能用5义4=20次，所以 ASL=1/12 (17+20) =37/123.08.答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头 元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内 每个元素的比较次数都是0 (1)。4解:(1)画表如下：012345678910111213141516173217634924401030314647(2)查找63,首先要与H(63)=63%16=15号单元内容比较,即63 vs 31 ,no;然后顺移，与

10、46,47, 32,17,63相比,一共比较了 6次!(3)查找60.首先要与H(6O)=6O%I6=I2号单元内容比较，但因为12号单元为空(应当有 空标记)，所以应当只比较这一次即可。(4)对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同,要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要 2次，“46”需要3次，“47”需要3次，所以 ASL=1/U (6+2+3X3) =17/11=1.54545454541.55四、分析题1.解：判定树应当描述每次查找的位置:ASL=1/1() (1+2X2+3X4+4X3) = 1/1() (1+4+12+12) =29/

11、10=2.9.答：/八 八?/16214913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17, 211)求得的二又排序蚓如下图所示在等微率情况F套找成功的平均杳找长度为AS L=3(1 X 14-2X2 + 3X34-4X3 + 5X24-6Xl) = vi14123.解:(2)经排序后的表及在贮处时找到表中元素所经比较的次数对照如下：Apr Aug Dec Feb Jan July June Mar May Nov Oct Sept342341342434等概率情况下筐找成功时的平均查找长度为ASI2 - 75high) return 0;查找不到时返回 0

12、mid=(low+high)/2;if(ST.elemmid.key= =key) return mid;else if(ST.elemmid.keykey)return Search_Bin_Recursive(ST, key, low, mid-1);else return Search_Bin_Recursive(ST, key, mid+1, high);/Search_Bin_Recursive2 .解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵 非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结 点的值不大于右子树的根的值

13、，则是二叉排序树” 若要采用递归算法，建议您采用如下的函数首部：bool BisortTree(BiTreeT, BiTree&PRE),其中PRE为指向当前访问结点的前驱的指针。(或者直接存储前驱的数值，随时与当前根结点比较)一个漂亮的算法设计如下：int last=O, flag=l;/ last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。int Is_BSTree(Bitree T)判断二又树T是否二叉排序树，是则返回1,否则返回0if(T-lchild&flag) Is_BSTree(T-lchild);if(T-datadata;if(T-rchild&flag) Is_BSTrcc(T-rchild);relurn flag;/Is_BSTree3 .解：设计哈希表的步骤为：a)根据所选择的处理冲突的方法求出装载因子a的上界；b)由a值设计哈希表的长度m；c)根据关键字的特性和表长m选定合适的哈希函数.