计算机二级
设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是（）A.堆排序B.有序链表查找C.希尔排D.循环链表中寻找最大项
题目
设表的长度为n。在下列结构所对应的算法中，最坏情况下时间复杂度最低的是（）
A.堆排序
B.有序链表查找
C.希尔排
D.循环链表中寻找最大项
参考答案和解析
相似问题和答案
第1题：
（ 1 ）下列叙述中正确的是
A ） 对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 n
B ） 对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n /2 ）
C ） 对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为 （ log 2 n ）
D ） 对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为 （ n log 2 n ）
第2题：
下列叙述中正确的是（ ）。
A.对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为n／2
C.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为log2n
D.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为n log2 n
C。【解析】二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较l0g2n次。
第3题：
下列叙述中正确的是( )。
A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)
C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
第4题：
下列叙述中正确的是
A．对长度为n的有序链表进行查找，最坏情况下需要比较的次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为n/2
C．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为log2n
D．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为nlog2n
解析：有序链表中定位元素需要通过指针逐个查找，所以对分查找的意义不大。选项A正确。
第5题：
下列叙述中正确的是
A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n／2)
C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
解析：对长度为n的有序链表进行查找，最坏情况是从最小值开始查找最大值(或从最大值开始查找最小值)，这个过程需要比较的次数为n，故选项A正确。对分查找只能针对随机存取的有序表进行，而有序链表只能进行顺序存取，不能进行随机仔取，在有序链表上不能进行对分查找，故B、c、D选项都错误。
第6题：
下列叙述中，正确的是
A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n／2）
C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）
D．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nlog2n）
解析：对长度为n的有序链表进行查找，最坏情况是从最小值开始查找最大值(或从最大值开始查找最小值)，这个过程需要比较的次数为n，故选项A正确。对分查找只能针对随机存取的有序表进行，而有序链表只能进行顺序存取，不能进行随机存取，在有序链表上不能进行对分查找，故B、C、D选项都错误。
第7题：
（ 1 ）下列叙述中正确的是
A ）对长度为 n 的有序链表进行查找，最坏清况下需要的比较次数为 n
B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）
C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）
D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ nlog 2 n ）
第8题：
下列叙述中正确的是( )。
A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n／2)
C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2(下标)n)
D．对长度为n的有序链表进行对分查找，最坏情况—卜需要的比较次数为(nlog2(下标)n)
解析：二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。
第9题：
（ 1 ）下列叙述中，正确的是
A ）对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 n
B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）
C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）
D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n log 2 n ）
