[查找题.ppt

填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 。 2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。设有100个结点，用二分法查找时，最大比较次数是 。 填空题 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较三次查找成功的结点数为4；比较四次查找成功的结点数为8；平均查找长度为 。 解：显然，平均查找长度＝O（log2n）5次（25）。但具体是多少次，则不应当按照公式来计算，应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！ 填空题 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 。 6. 哈希法存储的基本思想是由 决定数据的存储地址。 填空题 8. 一个无序序列可以通过构造一棵( )树而变 成一个有序序列,构造树的过程即为对无序序列进行排序的过程. 9. ( )法构造的哈希函数肯定不会发生冲突. 10. 在顺序表上施行的三个查找算法,就平均查找长度来看,( )最小,( )最大. 填空题 11．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____次。 12. 在n个记录的有序顺序表中进行折半查找，最大的比较次数是_______。 13.对于二叉排序树的查找，若根结点元素的健值大于被查元素，则应该在二叉树的_______上继续查找。 单项选择题 1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ） Ａ. ＡＳＬ＝ Ｂ. ＡＳＬ＝（ｎ＋１）／２; Ｃ. ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ 2.下面关于二叉排序树论述中，错误的是 A 当所有结点的权值都相等时，用这些节点构造的二叉排序树除根节点外只有右子树 B 中序遍历二叉排序树的结点就可以得到排好序的结点序列 C 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 D 对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历得到的序列是一样的 单项选择题 3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。（ ） A．3 B．4 C．5 D． 6 4. 链表适用于 查找 （ ） A．顺序 B．二分法 C．顺序，也能二分法 D．随机 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. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。 现把9个数1，2，3，…，8，9填入后图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B