點(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[單選題]在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找,最壞情況下需要較的次數(shù)是( )。
參考答案:C
參考解析:對(duì)于長(zhǎng)度為n的線性表進(jìn)行順序查找,平均要進(jìn)行n/2次比較,在最壞情況下要進(jìn)行n次比較;對(duì)于長(zhǎng)度為n的線性表進(jìn)行二分查找,在最壞情況下要進(jìn)行l(wèi)092n次比較(但二分查找要求線性表是順序存儲(chǔ)的有序表)。因此本題的正確答案是C。
3[單選題]對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找,在最壞情況下所需要的比較次數(shù)為( )
A.log2 nB.n/2C.nD.n+l
參考答案:C
參考解析:對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找,在最壞情況下所需要的比較次數(shù)為n,平均比較次數(shù)為n/2、對(duì)長(zhǎng)度為n的線性表進(jìn)行二分法查找,在最壞情況下所需要的比較次數(shù)為logan。因此選項(xiàng)C正確。
4[單選題]下列數(shù)據(jù)結(jié)構(gòu)中,能用二分法進(jìn)行查找的是( )。
參考答案:A
參考解析:
5[單選題]在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找,最壞情況下需要比較的次數(shù)是( )!究键c(diǎn)7查找】
A.0(n)B.0(n2)C.O(1092n)D.O(n l092n)
參考答案:C
參考解析:對(duì)于長(zhǎng)度為n的有序線性表,在最壞情況下,二分法查找只需比較l092n次,而順序查找需要比較n次。
6[單選題]對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找,在最壞情況下所需要的比較次數(shù)為( )。
參考答案:C
參考解析:對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找,在最壞情況下所需要的比較次數(shù)為n,平均比較次數(shù)為n/2、對(duì)長(zhǎng)度為n的線性表進(jìn)行二分法查找,在最壞情況下所需要的比較次數(shù)為logan。因此選項(xiàng)C正確。
7[單選題]在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找,最壞情況下需要較的次數(shù)是( )
A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)
參考答案:C
參考解析:對(duì)于長(zhǎng)度為n的線性表進(jìn)行順序查找,平均要進(jìn)行n/2次比較,在最壞情況下要進(jìn)行n次比較;對(duì)于長(zhǎng)度為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ò)程直到查找元素或是序列為空.
相關(guān)推薦:
2015年9月計(jì)算機(jī)等級(jí)考試成績(jī)查詢時(shí)間通知
北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |