数据结构第8章自测卷答案.doc

第8章 查找 自测卷答案 姓名 班级 A 题号 一 二 三 四 五 总分 题分 10 27 16 24 23 100 得分 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O（log2n）5次（25）。但具体是多少次，则不应当按照公式 来计算（即（21×log221）/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（nm）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查找次数 ≤n-1) 二、单项选择题（每小题1分，共27分） （ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为 Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２; Ｃ. ＡＳＬ＝＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ （ A ）2．【计研题2001】折半查找有序表（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．【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A．3 B．4 C．5 D． 6 （ A ）4. 链表适用于 查找 A．顺序 B．二分法 C．顺序，也能二分法 D．随机 （ C ）5. 折半有哪些信誉好的足球投注网站与二叉有哪些信誉好的足球投注网站树的时间性能 A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n） 6．【91程P3】从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。 要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。 某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案： A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储 ⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好 D，E： ① 25000 ② 30000 ③ 45000 ④ 90000 答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④ 7. （96初程P73）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。 数据结构反映了数据元素之间的结构