A.O(1)B.O(log2n)C.O(log2n2)D.O(nlog2n)E.O(n)

Question

A．O(1)

B．O(log2n)

C．O(log2n2)

D．O(nlog2n)

E．O(n)

Answer 1

正确答案：B
解析：顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等，，则查找成功；若扫描结束后，仍未找到关键字等于k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。成功的顺序查找的平均查找长度如下：ASL=pici＝(n-i+1)＝np1+(n-1)p2+…+2pn-1+pn在等概率情况下，pi=1/n(1≤i≤n)，平均查找长度为(n+…+2+1)/n＝(n+1)/2，即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则需进行n+1次比较之后才能确定查找失败。查找时间复杂度为O(n)。若事先知道表中各结点的查找概率不相等，以及它们的分布情况，则应将表中结点按查找概率由小到大的顺序存放，以便提高顺序查找的效率。顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。二分法查找的基本思想是(设R[low，…，high]是当前的查找区间)：(1)确定该区间的中点位置：mid=[(low+high)/2]。(2)将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下：.若R[mid].key＞k，则由表的有序性可知R[mid，…，n].key均大于A，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low，…，mid-1]中。因此，新的查找区间是左子表R[low，…，high]，其中high=mid-1。.若R[mid].keyk，则要查找的k必在mid的右子表R[mid+1，…，high]中，即新的查找区间是右子表R[low，…，high]，其中low=mid+1。.若R[mid].key=k，则查找成功，算法结束。(3)下一次查找针对新的查找区间进行，重复步骤(1)和(2)。(4)在查找过程中，low逐步增加，而high逐步减少。如果highlow，则查找失败，算法结束。因此，从初始的查找区间R[1，…，n]开始，每经过一次与当前查找区间中点位置上结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。重复这一过程，直至找到关键字为k的结点，或者直至当前的查找区间为空(即查找失败)时为止。查找的时间复杂度为O(log2n)。在二叉排序树上查找，和二分法查找类似，也是一个逐步缩小查找范围的过程。在二叉排序树上进行查找时，若查找成功，则是从根结点出发，走了一条从根到待查结点的路径。若查找不成功，则是从根结点出发，走了一条从根到某个叶子的路径。与二分法查找类似，这种方法中和关键字比较的次数不超过树的深度。二分查找法查找长度为n的有序表，其判定树是唯一的。含有n个结点的二叉排序树却不唯一。对于含有同样一组结点的表，由于结点插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同，这与在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关。(1)在最坏的情况下，二叉排序树是通过把一个有序表的n个结点依次插入而生成的，此时所得的二叉排序树退化为一棵深度为n的单支树，它的平均查找长度和单链表上的顺序查找相同，也是(n+1)/2。(2)在最好的情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分法查找的判定树相似的二叉排序树，此时它的平均查找长度大约是log2n。对于平衡的二叉排序树查找，平衡二叉排序树中的每个结点的左、右子树高度差不大于1，n个结点的平衡树的深度和log2n是同数量级的。对二叉排序树来说，它的查找时间与树的深度成正比。因此，平衡二叉排序树的平均查找时间为O(log2n)。在平衡树上删除或插入结点往往会破坏树的平衡。通过旋转又可使其重新成为一棵平衡树。在最坏情况下，从叶子开始一直调整到根为止，需进行的旋转次数与树的深度一致，等于O(log2n)次。