数据结构第8章 查找 答案

第8章查找测试题及答案一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。 2. 线性有序表（a，a，a，…，a)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相123256等的元素，在

查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次

数是7。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；

比较两次查找成功的结点数为 2；比较四次查找成功的结点数为 8；平均查找长度为 3.7。

5解：显然，平均查找长度＝O（logn）<5次（2）。但具体是多少次，则不应当按照公式2m来计算（即

（21×log21）/20＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下22n推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！4．【计研

题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，

它将依次与表中元素 28，6，12，20比较大小。 5. 在各种查找方法中，平均查找长度与结

点个数n无关的查找方法是散列查找。 6. 散列法存储的基本思想是由关键字的值决定数

据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探

测的总次数是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素查找次数≤n-1) 二、单项选择题（B）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝

（ｎ＋１）／２; nＣ. ＡＳＬ＝＋１; Ｄ. ＡＳＬ≈ｌｏｇ（ｎ＋１）－１２（A）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次

与表中比较大小，查找结果是失败。A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 （C）3．对22个记录的有序表作折半查找，当查找失败时，至

少需要比较次关键字。A．3 B．4 C．5 D． 6 （A）4. 链表适用于查找A．顺序 B．二分法 C．顺序，也能二分法 D．随机（C ）5. 折半搜索与二叉搜索

树的时间性能 A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（logn） 2 6．从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。 1

要进行线性查找，则线性表 A ；要进行二分查找，则线性表B ；要进行散列查找，则线性表 C 。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为D ，最大比较次数为 E 。供选择的答案： A~C：① 必须以顺序方式存储② 必须以链表方式存储③ 必须以散列方式存储④ 既可以以顺序方式，也可以以链表方式存储⑤ 必

须以顺序方式存储且数据元素已按值递增或递减的次序排好⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E：① 25000 ② 30000 ③ 45000 ④ 90000 答案：A= ④ B= ⑤ C= ③ D＝③ E＝④7.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。供选择的答案：A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表 B：① 不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针C：① 顺序查找②循环查找③条件查找④二分法查找D：① 顺序查找②随机查找③二分法查找④分块查找 E：① 效率较低的线性查找②效率较低的非线性查找③ 效率较高的非线性查找④效率较高的线性查找答案：A＝④ B＝② C＝④ D＝① E＝③ 8. 从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。在二叉排序树中，每个结点的关键码值 A ， B 一棵二

叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C 。供选择的答案 A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大③比左右子树的所有结点的关键码值都大④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系B: ①前序遍历② 中序（对称）遍历③ 后序遍历④ 层次遍历 C：① 除最下二层可以不满外，其余都是充满的②除最下一层可以不满外，其余都是充满的③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边答案：A＝① B＝② C＝② 9. 从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。供选择的答案 A，B：①存储地址② 元素的符号③ 元素个数④ 关键码值⑤ 非码属性⑥ 平均检索长度⑦ 负载因子⑧ 散列表空间 2

C: ①两个元素具有相同序号② 两个元素的关键码值不同，而非码属性相同③ 不同关键码值对应到相同的存储地址④ 负载因子过大⑤ 数据元素过多 D：① 线性探查法和双

散列函数法② 建溢出区法和不建溢出区法③ 除余法和

折叠法④ 拉链法和开地址法答案：A＝④ B＝

① C＝③ D＝④ 10.考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结

点的值。并小于等于其右子树上的一切结点的值。现把9个数1，2，3，…，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值10是 B ，

n9的值是 C 。现欲把放入此树并使该树保持前述性质，增

加的一个结点可以放在 D 或 E 。供选择的答案 A～C：

①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9 D～E：① n7下面② n8下面③ n9下面

④ n6下面⑤ n1与n2之间⑥ n2与n4之间⑦ n6

与n9之间⑧ n3与n6之间答案：A＝⑦ B＝④ C

＝⑥ D＝② E＝⑥ 三、简答题1.对

分（折半）查找适不适合链表结构的序列，为什么？用二分查

找的查找速度必然比线性查找的速度快，这种说法对吗？答：

不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指

针开始逐步搜索，故不能进行折半查找。二分查找的速度在一

般情况下是快些，但在特殊情况下未必快。例如所查数据位于

首位时，则线性查找快；而二分查找则慢得多。 2.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行

折半查找，试回答下列问题：（1）画出描述折半查找过程的

判定树；（2）若查找元素54，需依次与哪些元素比较？（3）若查找元素90，需依次与哪些元素比较？（4）假定每个元素

的查找概率相等，求查找成功时的平均查找长度。 3

解：（1）先画出判定树如下（注：）：30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；（4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共

查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能

用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.08 3.用

比较两个元素大小的方法在一个给定的序列中查找某个元素的

时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么

方法？此方法的时间复杂度是多少? 答：查找某个元素的时间

复杂度下限，如果理解为最短查找时间，则当关键字值与表头

元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。4.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（1）画出哈

希表的示意图；（2）若查找关键字63，需要依次与哪些关键

字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：（1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55 四、分析题 4

1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：判定树应当描述每次查找的位置： ASL＝1/10（1＋2×2＋3×4＋4×3） 5 ＝1/10（1＋4＋12＋12）2 8 1 3 6 9 ＝29/10=

2.9 4 7 10 2.在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。答：12 7 17 2 11 16 21 4 9 13 验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21

3.已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May,

June, July, Aug, Sep, Oct, Nov, Dec） (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 (3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解： 5

4. 选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。解：由题意知，m=11(刚好为素数) 则(22*3)%11=6……0 链接指针地址值(41*3)%11=11……2 0 22 1 1 66 (53*3)%11=14……5 2 41 3 (08*3)%11=2……2 3 08 4,7 (46*3)%11=12……6 4 30 (30*3)%11=8……2 5 53 (01*3)%11=0……3 6 46 7 01 (31*3)%11=8……5 8 31 (66*3)%11=9……0 9 10 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1 3 4，7 五、算法设计题 1. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算法程序，查找关键字为key的数据元素(建议上机调试)。解：折半查找的C程序有很多参考资料，注意此题要求是整型量。 6

折半查找的一个递归算法如下，形式非常简洁！int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半

查找的递归算法 { if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2; if(ST.elem[mid].key= =key) return mid; else

if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); } }//Search_Bin_Recursive 2.试写一个判别给定二叉

树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结

构。且树中结点的关键字均不同。解：注意仔细研究二叉排序

树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非

空的二叉树其左、右子树均为二叉排序树，且左子树的根的值

小于根结点的值，又根结点的值不大于右子树的根的值，则是

二叉排序树” （注：即不能只判断左右孩子的情况，还要判断

左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。

若要采用递归算法，建议您采用如下的函数首部：bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结

点的前驱的指针。（或者直接存储前驱的数值，随时与当前根

结点比较）一个漂亮的算法设计如下：int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比

前驱大就行。 int Is_BSTree(Bitree T) //判断二叉树T是否二

叉排序树，是则返回1，否则返回0 { if(T->lchild&&flag)

Is_BSTree(T->lchild); if(T->data

相比较, flag=0表示当前结点比直接前驱小，则立即返回

last=T->data; if(T->rchild&&flag) Is_BSTree(T->rchild); return

flag; }//Is_BSTree 3. 已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。解：设计哈希表的步骤为：a) 根据所选择的处理冲突的方法求出装载因子a的上界； b) 由a值设计哈希表的长度m； c) 根据关键字的特性和表长m选定合适的哈希函数。刘注：要求ASL≤3，则m必然要尽量长，以减少冲突； 4.已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。 7

解：注意此题给出的条件：装载因子a〈1, 则哈希表未填满。由此可写出下列形式简明的算法：void PrintWord(Hash Table ht) {//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。for(i=1; i<=26; i++){ j=i; While(ht.elem[j].key){ if(Hash(ht.elem[j].key==i)printf(ht.elem[j] .key); j=(j+1)%m; } } }//PrintWord 8

《数据结构》习题汇编08_第八章_查找_试题

数据结构课程（本科）第七章试题 一、单项选择题 1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为 （）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概 率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。 A. 5.5 B. 5 C. 39/8 D. 19/4 3.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索 第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（）。 A. 5/3 B. 2 C. 7/3 D. 4/3 4.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度 为（）。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 5.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 6.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向下取整加一。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（） 的值除以9。 A. 20 B. 18 C. 25 D. 22 8.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。 A. 3 B. 4 C. 5 D. 6 9.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。 A. n B. log2n C. (h+1)/2 D. h+1 11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为 （）。 A. O(n) B. O(1) C. O(log2n) D. O(n2)

数据结构第八章习题及答案

习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个

数据结构C语言版第八章 查找

第八章查找 重点难点 要求理解"查找表"的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 典型例题 1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度： (1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。 【解】查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。 查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。 2.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 【解】 等概率情况下，查找成功的平均查找长度为： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 3.为什么有序的单链表不能进行折半查找?

【解】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 4.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。 新结点总是作为叶子插入在二叉排序树中的。 5.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字? 【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。 若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。6.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答： (1)拉链法如下图： T[0..10] ┌──┐ 0││→ 33 → 22 →∧ ├──┤ 1││→ 1 → 12 →34→ ∧ ├──┤ 2││→ 13 →∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤ 5││→ 38 → 27 →∧ ├──┤ 6│ ∧ │ ├──┤ 7│∧ │

数据结构练习第八章-查找

数据结构练习第八章查找 1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A. O(1) B. O(log 2 n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(log 2 n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 A. log 2n+1 B. log 2 n-1 C. log 2 n D. log 2 (n+1) 5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。A. O(n) B. O(n2) C. O(n1/2) D. O(1og 2 n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 A. O(n) B. O(n2) C. O(nlog 2n) D. O(1og 2 n) 8．（）二叉排序树可以得到一个从小到大的有序序列。 A. 先序遍历 B.中序遍历 C. 后序遍历 D. 层次遍历9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 A. 1 B. 2 C. 3 D. 4 10．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 A. 99 B. 97 C. 91 D. 93 11．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 A. O(n) B. O(1og 2n) C. O(nlog 2 n) D. O(n2) 12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4] 13．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 A. 小于等于m的最大奇数 B.小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4

数据结构 第八章 查找自测题

第9章查找自测卷姓名班级 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结 点数为；比较四次查找成功的结点数为；平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

数据结构第8章 查找 答案

第8章 查找 测试题 及答案 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n

数据结构练习8

第八章查找 习题 9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。( ) (2)查找成功与否的关键在于是否按主关键字查找。( ) (3)顺序文件必须用一片地址连续的存储空间来存放。( ) (4)只有在顺序存储结构上才能采用顺序查找方法。( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( ) (8)建立稠密索引的优点是节省存储空间。( ) (9)分块查找的效率与文件中的记录被分成多少块有关。( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。( ) (11)B-树和B十树都是用来实现动态索引的。( ) (12)在B-树上可以进行顺序查找。( 1 (13)在B+树上可以进行顺序查找。／ 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。( ) (15)在散列文件中进行查找不涉及关键字的比较。( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。( ) (19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。( ) 9．2单项选择题。 (1)衡量查找算法性能好坏的主要标准是。 A．参加比较的关键字值的多少 B．被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D．关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是—。· A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找 C.适合链接顺序文件的查找D．查找时间效率高 (3)对线性表采用折半查找，该线性表必须。 A．元素按值有序排列B．采用顺序结构 C．元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链式存储结构 (4)下面的说法中，不正确的是——。 A．折半查找方法不适用于按值有序链接的链表的查找 B．折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D．折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。

数据结构第8章 查找 答案

第8章查找测试题及答案一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。 2. 线性有序表（a，a，a，…，a)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相123256等的元素，在 查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次 数是7。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1； 比较两次查找成功的结点数为 2；比较四次查找成功的结点数为 8；平均查找长度为 3.7。 5解：显然，平均查找长度＝O（logn）<5次（2）。但具体是多少次，则不应当按照公式2m来计算（即 （21×log21）/20＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下22n推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！4．【计研 题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20， 它将依次与表中元素 28，6，12，20比较大小。 5. 在各种查找方法中，平均查找长度与结 点个数n无关的查找方法是散列查找。 6. 散列法存储的基本思想是由关键字的值决定数 据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

数据结构第8章查找练习题

一、单选题 1．下列查找方法中，不属于动态的查找方法是( )。 A ．二叉排序树法 B ．平衡树法 C ．散列法 D ．二分查找法 2．适用于静态的查找方法为( )。 A ．二分查找、二叉排序树查找 B ．二分查找、索引顺序表查找 C ．二叉排序树查找、索引顺序表查找 D ．二叉排序树查找、散列法查找 3．静态查找表与动态查找表二者的根本差别在于( )。 A ．它们的逻辑结构不一样 B ．施加在其上的操作不同 C ．所包含的数据元素的类型不一样 D ．存储实现不一样 4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。 A ．5.5 B ．5 C ．39/8 D ．19/4 5．( )存储方式适用于折半查找。 A ．键值有序的单链表 B ．键值有序的顺序表 C ．键值有序的双链表 D ．键值无序的顺序表 6．对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B ．以链接方式存储 C ．顺序存储，且结点按关键字有序排序 D ．链式存储，且结点按关键字有序排序 7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。 A ．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B ．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C ．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D ．用二分查找法确定元素所在块，再用二分查找法在相应块中查找 8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A ．13 B ．24 C ．12 D ．79 9．由同一关键字集合构造的各棵二叉排序树( )。 A ．形态和平均查找长度都不一定相同 B ．形态不一定相同，但平均查找长度相同 C ．形态和平均查找长度都相同 D ．形态相同，但平均查找长度不一定相同 10．对二叉排序树进行( )，可以得到各结点键值的递增序列。 A ．先根遍历 B ．中根遍历 C ．层次遍历 D ．后根遍历 11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？ A ．2，25，40，39，53，34，35 B ．25，39，2，40，53，34，35 C ．53，40，2，25，34，39，35 D ．39，25，40，53，34，2，35 12．在A VL 树中，每个结点的平衡因子的取值范围是( )。 A ．-1~1 B ．-2~2 C ．1~2 D ．0~1 13．在AVL 树中，任一结点的( )。 A ．左、右子树的高度均相同 B ．左、右子树高度差的绝对值不超过1 C ．左、右子树的结点数均相同 D ．左、右子树结点数差的绝对值不超过1 14．下面关于B 树和B +树的叙述中，不正确的是 A ．都是平衡的多叉树 B ．都是可用于文件的索引结构 C ．都能有效地支持顺序检索 D ．都能有效地支持随机检索 15．右图是一棵( )。 2822221915100528 2610