點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)考點(diǎn)測(cè)試題匯總
查找技術(shù)
1[單選題]下列關(guān)于棧的敘述正確的是( )。
A.棧按“先進(jìn)先出”組織數(shù)據(jù)
B.棧按“先進(jìn)后出”組織數(shù)據(jù)
C.只能在棧底插入數(shù)據(jù)
D.不能刪除數(shù)據(jù)
參考答案：B
參考解析：棧是限定在一端進(jìn)行插入和刪除的線性表，允許進(jìn)行插入和刪除元素的一端稱為棧頂，另一端稱為棧底。棧是按照“先進(jìn)后出”的原則組織數(shù)據(jù)的。
2[單選題]在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要較的次數(shù)是( )。
參考答案：C
參考解析：對(duì)于長度為n的線性表進(jìn)行順序查找，平均要進(jìn)行n/2次比較，在最壞情況下要進(jìn)行n次比較;對(duì)于長度為n的線性表進(jìn)行二分查找，在最壞情況下要進(jìn)行l(wèi)092n次比較(但二分查找要求線性表是順序存儲(chǔ)的有序表)。因此本題的正確答案是C。
3[單選題]對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為( )
A.log2 nB.n/2C.nD.n+l
參考答案：C
參考解析：對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為n，平均比較次數(shù)為n/2、對(duì)長度為n的線性表進(jìn)行二分法查找，在最壞情況下所需要的比較次數(shù)為logan。因此選項(xiàng)C正確。
4[單選題]下列數(shù)據(jù)結(jié)構(gòu)中，能用二分法進(jìn)行查找的是( )。
參考答案：A
參考解析：
5[單選題]在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是( )�！究键c(diǎn)7查找】
A.0(n)B.0(n2)C.O(1092n)D.O(n l092n)
參考答案：C
參考解析：對(duì)于長度為n的有序線性表，在最壞情況下，二分法查找只需比較l092n次，而順序查找需要比較n次。
6[單選題]對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為( )。
參考答案：C
參考解析：對(duì)長度為n的線性表進(jìn)行順序查找，在最壞情況下所需要的比較次數(shù)為n，平均比較次數(shù)為n/2、對(duì)長度為n的線性表進(jìn)行二分法查找，在最壞情況下所需要的比較次數(shù)為logan。因此選項(xiàng)C正確。
7[單選題]在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要較的次數(shù)是( )
A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)
參考答案：C
參考解析：對(duì)于長度為n的線性表進(jìn)行順序查找，平均要進(jìn)行n/2次比較，在最壞情況下要進(jìn)行n次比較;對(duì)于長度為n的線性表進(jìn)行二分查找，在最壞情況下要進(jìn)行l(wèi)092n次比較(但二分查找要求線性表是順序存儲(chǔ)的有序表)。因此本題的正確答案是C。
8[單選題]在一個(gè)n×m的二維線性表中順序查找一個(gè)數(shù)據(jù)元素的算法時(shí)間復(fù)雜度是( )。
參考答案：B
參考解析：
9[填空題]請(qǐng)寫出用二分查找法在有序順序表(1，2，3，4，6，8，9，11)中查找3的比較序列( )。
參考解析：4，2，3
【分析】可采用擦去法做這類二分法查找序列的題：每次從序列中找出中間元素，剛開始時(shí)是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列(1，2，3)，在重復(fù)以上過程直到查找元素或是序列為空.
相關(guān)推薦：
2015年9月計(jì)算機(jī)等級(jí)考試成績查詢時(shí)間通知
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
