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

《数据结构》习题汇编 08 第八章 查找 试题(12 页)Good is good, but better carries it.精益求精，善益求善。数据结构课程（本科）第七章试题一、单项选择题1.若搜索每一个元素的概率相等，则在长度为 n 的顺序表上搜索到表中任一元素的平均搜索长度为（ ）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/22.对长度为 10 的顺序表进行搜索，若搜索前面 5 个元素的概率相同，均为 1/8，搜索后面5 个元素的概率相同，均为 3/40，则搜索到表中任一元素的平均搜索长度为（ ）。 A. 5.5 B. 5 C. 39/8 D. 19/43.对长度为 3 的顺序表进行搜索，若搜索第一个元素的概率为 1/2，搜索第二个元素的概率为 1/3，搜索第三个元素的概率为 1/6，则搜索到表中任一元素的平均搜索长度为（ ）。 A. 5/3 B. 2 C. 7/3 D. 4/34.对长度为 n 的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（ ）。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/45.对于长度为 n 的有序顺序表，若采纳折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/26.对于长度为 n 的有序顺序表，若采纳折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向下取整加一。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/27.对于长度为 9 的有序顺序表，若采纳折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以 9。 A. 20 B. 18 C. 25 D. 228.对于长度为 18 的有序顺序表，若采纳折半搜索，则搜索第 15 个元素的搜索长度为（ ）。 A. 3 B. 4 C. 5 D. 69.对具有 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+111. 从具有 n 个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为（ ）。A. O(n) B. O(1) C. O(log2n) D. O(n2)12. 从具有 n 个结点的二叉搜索树中搜索一个元素时，在最坏情况下进行成功搜索的时间复杂度为（ ）。 A. O(n) B. O(1) C. O(log2n) D. O(n2)13. 向具有 n 个结点的二叉搜索树中插入一个元素...