点击查看：2015年计算机二级公共基础知识考点测试题汇总

　　查找技术

　　1[单选题]下列关于栈的叙述正确的是(　　)。

　　A.栈按“先进先出”组织数据

　　B.栈按“先进后出”组织数据

　　C.只能在栈底插入数据

　　D.不能删除数据

　　参考答案：B

　　参考解析：栈是限定在一端进行插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。

　　2[单选题]在长度为n的有序线性表中进行二分查找，最坏情况下需要较的次数是(　　)。

　　参考答案：C

　　参考解析：对于长度为n的线性表进行顺序查找，平均要进行n/2次比较，在最坏情况下要进行n次比较;对于长度为n的线性表进行二分查找，在最坏情况下要进行l092n次比较(但二分查找要求线性表是顺序存储的有序表)。因此本题的正确答案是C。

　　3[单选题]对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为(　　)

　　A.log2 nB.n/2C.nD.n+l

　　参考答案：C

　　参考解析：对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为n，平均比较次数为n/2、对长度为n的线性表进行二分法查找，在最坏情况下所需要的比较次数为logan。因此选项C正确。

　　4[单选题]下列数据结构中，能用二分法进行查找的是(　　)。

　　参考答案：A

　　参考解析：

 　　5[单选题]在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是(　　)。【考点7查找】

　　A.0(n)B.0(n2)C.O(1092n)D.O(n l092n)

　　参考答案：C

　　参考解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较l092n次，而顺序查找需要比较n次。

　　6[单选题]对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为(　　)。

　　参考答案：C

　　参考解析：对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为n，平均比较次数为n/2、对长度为n的线性表进行二分法查找，在最坏情况下所需要的比较次数为logan。因此选项C正确。

　　7[单选题]在长度为n的有序线性表中进行二分查找，最坏情况下需要较的次数是(　　)

　　A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)

　　参考答案：C

　　参考解析：对于长度为n的线性表进行顺序查找，平均要进行n/2次比较，在最坏情况下要进行n次比较;对于长度为n的线性表进行二分查找，在最坏情况下要进行l092n次比较(但二分查找要求线性表是顺序存储的有序表)。因此本题的正确答案是C。

　　8[单选题]在一个n×m的二维线性表中顺序查找一个数据元素的算法时间复杂度是(　　)。

　　参考答案：B

　　参考解析：

　　9[填空题]请写出用二分查找法在有序顺序表(1，2，3，4，6，8，9，11)中查找3的比较序列(　　)。

　　参考解析：4，2，3

　　【分析】可采用擦去法做这类二分法查找序列的题：每次从序列中找出中间元素，刚开始时是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列(1，2，3)，在重复以上过程直到查找元素或是序列为空.

　　相关推荐：

　　2015年9月计算机等级考试成绩查询时间通知

　　2015计算机二级公共基础知识考前冲刺练试题汇总

　　2015计算机二级《公共基础知识》精选选择题90道