點擊查看：2015年計算機二級公共基礎知識考點測試題匯總

　　查找技術(shù)

　　1[單選題]下列關(guān)于棧的敘述正確的是(　　)。

　　A.棧按“先進先出”組織數(shù)據(jù)

　　B.棧按“先進后出”組織數(shù)據(jù)

　　C.只能在棧底插入數(shù)據(jù)

　　D.不能刪除數(shù)據(jù)

　　參考答案：B

　　參考解析：棧是限定在一端進行插入和刪除的線性表，允許進行插入和刪除元素的一端稱為棧頂，另一端稱為棧底。棧是按照“先進后出”的原則組織數(shù)據(jù)的。

　　2[單選題]在長度為n的有序線性表中進行二分查找，最壞情況下需要較的次數(shù)是(　　)。

　　參考答案：C

　　參考解析：對于長度為n的線性表進行順序查找，平均要進行n/2次比較，在最壞情況下要進行n次比較;對于長度為n的線性表進行二分查找，在最壞情況下要進行l(wèi)092n次比較(但二分查找要求線性表是順序存儲的有序表)。因此本題的正確答案是C。

　　3[單選題]對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為(　　)

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

　　參考答案：C

　　參考解析：對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為n，平均比較次數(shù)為n/2、對長度為n的線性表進行二分法查找，在最壞情況下所需要的比較次數(shù)為logan。因此選項C正確。

　　4[單選題]下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進行查找的是(　　)。

　　參考答案：A

　　參考解析：

 　　5[單選題]在長度為n的有序線性表中進行二分查找，最壞情況下需要比較的次數(shù)是(　　)。【考點7查找】

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

　　參考答案：C

　　參考解析：對于長度為n的有序線性表，在最壞情況下，二分法查找只需比較l092n次，而順序查找需要比較n次。

　　6[單選題]對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為(　　)。

　　參考答案：C

　　參考解析：對長度為n的線性表進行順序查找，在最壞情況下所需要的比較次數(shù)為n，平均比較次數(shù)為n/2、對長度為n的線性表進行二分法查找，在最壞情況下所需要的比較次數(shù)為logan。因此選項C正確。

　　7[單選題]在長度為n的有序線性表中進行二分查找，最壞情況下需要較的次數(shù)是(　　)

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

　　參考答案：C

　　參考解析：對于長度為n的線性表進行順序查找，平均要進行n/2次比較，在最壞情況下要進行n次比較;對于長度為n的線性表進行二分查找，在最壞情況下要進行l(wèi)092n次比較(但二分查找要求線性表是順序存儲的有序表)。因此本題的正確答案是C。

　　8[單選題]在一個n×m的二維線性表中順序查找一個數(shù)據(jù)元素的算法時間復雜度是(　　)。

　　參考答案：B

　　參考解析：

　　9[填空題]請寫出用二分查找法在有序順序表(1，2，3，4，6，8，9，11)中查找3的比較序列(　　)。

　　參考解析：4，2，3

　　【分析】可采用擦去法做這類二分法查找序列的題：每次從序列中找出中間元素，剛開始時是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列(1，2，3)，在重復以上過程直到查找元素或是序列為空.

　　相關(guān)推薦：

　　2015年9月計算機等級考試成績查詢時間通知

　　2015計算機二級公共基礎知識考前沖刺練試題匯總

　　2015計算機二級《公共基礎知識》精選選擇題90道