第8章自测卷空题--数据结构课件(吴伟民-严蔚敏编著).doc

第8章查找自测卷姓名班级
题号
一
二
三
四
五
总分
题分
10
27
16
24
23
100
得分
一、填空题(每空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<m)个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同,则探测的总次数是。
二、单项选择题(每小题1分,共27分)
( ),它的平均查找长度为
A. ASL=n; B. ASL=(n+1)/2;
C. ASL=+1; D. ASL≈log2(n+1)-1
( )2. 折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中比较大小,查找结果是失败。
,70,30,50 ,88,70,50 ,50 ,88,50
( )3. 对22个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字。
D. 6
( )4. 链表适用于查找
,也能二分法
( )5. 折半搜索与二叉搜索树的时间性能
A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O(log2n)
6. 要进行线性查找,则线性表 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 是一种对顺序和链式存储结构均适用的方法。