數(shù)據(jù)結(jié)構(gòu)與算法模擬測(cè)試題附答案

數(shù)據(jù)結(jié)構(gòu)與算法模擬測(cè)試卷附答案1.散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=Kmod17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。則元素59存放在散列表中的地址是()。A:9B:11(正確答案)C:10D:82.二叉排序樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為5個(gè)，則度為2的結(jié)點(diǎn)的數(shù)目是()。A:6B:5C:4(正確答案)D:33.N個(gè)記錄采用直接插入排序的最好的情況是記錄完全有序，只要比較()次，不需要插入就可以排序完成。A:NB:N-1(正確答案)C:N-2D:N(N-1)/24.就性能而言，希爾排序的時(shí)間復(fù)雜度是()。A:O(nn)B:O(nlog2n)C:O(n)D:O(n3/2)(正確答案)5.改進(jìn)的冒泡排序的任一趟排序過(guò)程中，如果沒(méi)有發(fā)生()，則說(shuō)明已經(jīng)有序；排序完畢。A:數(shù)據(jù)交換(正確答案)B:數(shù)據(jù)刪除C:數(shù)據(jù)增加D:數(shù)據(jù)修改6.從算法的時(shí)間復(fù)雜度來(lái)看，O(nlog2n)是哪種排序的時(shí)間復(fù)雜度()。A:快速排序(正確答案)B:直接插入排序C:簡(jiǎn)單選擇排序D:冒泡排序7.N個(gè)記錄，采用簡(jiǎn)單選擇排序，每趟最多進(jìn)行()次交換。A:1(正確答案)B:2C:N-2D:N-18.希爾排序是根據(jù)增量，將所有記錄分為若干個(gè)組，每組采用()排序進(jìn)行排序。A:直接插入排序(正確答案)B:冒泡排序C:快速排序D:簡(jiǎn)單選擇排序9.程序調(diào)用自身的編程技巧，稱為()。A:數(shù)組B:函數(shù)C:遞歸(正確答案)D:排序10.青蛙過(guò)河案例中，如果河中沒(méi)有石柱，有y片荷葉的話，那么從左岸到右岸可以過(guò)去()只青蛙。A:y+1只(正確答案)B:y+2只C:y+3只D:y+4只11.關(guān)于素?cái)?shù)描述正確的是()。A:素?cái)?shù)就是合數(shù)B:素?cái)?shù)不能被本身整除C:素?cái)?shù)又稱為質(zhì)數(shù)只能被1和它本省整除(正確答案)D:素?cái)?shù)不僅能被1和它本身整除，還能被其它數(shù)整除12.下列關(guān)于break語(yǔ)句描述錯(cuò)誤的是()。A:當(dāng)break用于單層循環(huán)中時(shí)，可以終止循環(huán).B:break用于switch語(yǔ)句中與case搭檔，跳出switch語(yǔ)句C:if(i%2==0)break;執(zhí)行語(yǔ)句后如果i的值是6則結(jié)果條件判斷.(正確答案)D:for(i=1;i<=10;i++)if(i%2==0)break;如果i的值是2則退出循環(huán)13.已知do…while結(jié)構(gòu)的基本語(yǔ)法如下

do

{

語(yǔ)句

}while(表達(dá)式);

下面對(duì)于do…while的敘述正確的是()。A:{}里面的語(yǔ)句只能放一條語(yǔ)句。B:while后面小括號(hào)里的表達(dá)式只能放關(guān)系表達(dá)式。C:while小括號(hào)后面的分號(hào)可以省略D:while小括號(hào)后面的分號(hào)不可以省略(正確答案)14.雞兔同籠是一個(gè)歷史悠久的問(wèn)題，早在中國(guó)的數(shù)學(xué)典籍()中就有記載：“今有雉(雞)兔同籠，上有三十五頭，下有九十四足。問(wèn)雉兔各幾何。A:孫子算經(jīng)(正確答案)B:孫子兵法C:九章算術(shù)D:九章算經(jīng)15.一個(gè)大人一餐吃2個(gè)面包，兩個(gè)小孩一餐吃1個(gè)面包，現(xiàn)在有大人和小孩共99人，一餐剛好吃了99個(gè)面包，大人、小孩各有多少人()。A:大人33人，小孩66人(正確答案)B:大人66人，小孩33人C:大人22人，小孩77人D:大人44人，小孩55人16.一根繩子有320米長(zhǎng)，每天截取12米，問(wèn)多少天后繩子長(zhǎng)度不足40米？其代碼編寫(xiě)如下：voidmain()

{

intcount=0,len=320;

while(len>=40)

{

（填空）;

printf("%d\t",len);

count++;

}

printf("\n總計(jì)需要%d天后繩子的長(zhǎng)度不足40米\n",count);

}則填空處應(yīng)該填寫(xiě)的語(yǔ)句序列是()。A:len=len-12;(正確答案)B:len=len+12;C:len=12;D:len-1217.以下是漢諾塔問(wèn)題算法：#include"stdio.h"

intstep=1;

voidmove(intm,charp,charq,charr)

{

if(m==1)//如果m為1，則為直接可解結(jié)點(diǎn)

{

printf("第%d步move1#from%cto%c\n",step,p,r);

step++;

}

else

{

move(m-1,p,r,q);

printf("第%d步move%d#from%cto%c\n",step,m,p,r);

step++;

(填空);

}

}則填空處應(yīng)填寫(xiě)的語(yǔ)句是()。A:move(m-1,q,p,r)(正確答案)B:move(m-1,p,r,q)C:move(m,p,r,q)D:move(m,q,p,r)18.關(guān)于回文字符串，描述正確的是()。A:回文字符串的長(zhǎng)度一定是奇數(shù)B:回文字符串的長(zhǎng)度一定是偶數(shù)C:回文字符串的長(zhǎng)度可以是奇數(shù)也可以是偶數(shù)(正確答案)D:回文字符串只要求首尾字母是一樣的。19.荷蘭國(guó)旗算法的時(shí)間復(fù)雜度是()。A:O(1)B:O(n)(正確答案)C:O(nlog2n)D:O(nn)20.小明的煩惱算法的時(shí)間復(fù)雜度是()。A:O(1)B:O(n)C:O(nlog2n)D:O(nn)(正確答案)21.已知一棵樹(shù)是二叉排序樹(shù)，則該樹(shù)具有()的特點(diǎn)。A:若左子樹(shù)不為空，則左子樹(shù)上的所有結(jié)點(diǎn)的值(關(guān)鍵字)都小于根節(jié)點(diǎn)的值；(正確答案)B:若右子樹(shù)不為空，則右子樹(shù)上的所有結(jié)點(diǎn)的值(關(guān)鍵字)都大于根節(jié)點(diǎn)的值；(正確答案)C:左、右子樹(shù)都分別為二叉排序樹(shù)。(正確答案)D:其中序序列是一個(gè)非遞減有序序列。(正確答案)22.O(n)是以下哪種算法的復(fù)雜度()。A:順序查找(正確答案)B:順序表刪除元素(正確答案)C:順序表插入元素(正確答案)D:單鏈表查找第i個(gè)元素(正確答案)23.裝填因子的計(jì)算方法是()。A:1-(表中未填入記錄的數(shù)目/哈希表的總長(zhǎng)度)(正確答案)B:表中未填入記錄的數(shù)目/哈希表的總長(zhǎng)度C:(表中未填入的記錄數(shù)-1)/哈希表的總長(zhǎng)度D:表中填入的記錄數(shù)/哈希表的總長(zhǎng)(正確答案)24.哈希表的平均查找長(zhǎng)度與哪些()因素有關(guān)。A:處理沖突的方法(正確答案)B:哈希函數(shù)(正確答案)C:裝填因子(正確答案)D:待存記錄的大小25.按照待排記錄是否全部在內(nèi)存中，排序可分為()。A:外部排序(正確答案)B:內(nèi)部排序(正確答案)C:歸并排序D:基數(shù)排序26.關(guān)于希爾排序描述正確的是()。A:希爾排序是不穩(wěn)定排序(正確答案)B:希爾排序是屬于插入排序(正確答案)C:希爾排序的時(shí)間復(fù)雜度是O(n3/2)(正確答案)D:希爾排序又稱為縮小增量排序(正確答案)27.從排序大類上看，屬于選擇排序的是()。A:簡(jiǎn)單選擇排序(正確答案)B:堆排序(正確答案)C:快速排序D:冒泡排序28.下列排序中屬于不穩(wěn)定排序的有()。A:快速排序(正確答案)B:直接插入排序C:簡(jiǎn)單選擇排序(正確答案)D:希爾排序(正確答案)29.快速排序的特性描述正確的是()。A:快速排序是穩(wěn)定排序B:快速排序不穩(wěn)定排序(正確答案)C:快速排序的時(shí)間復(fù)雜度是O(nlog2n)(正確答案)D:快速排序的時(shí)間復(fù)雜度是O(nn)30.以下不是漢諾塔問(wèn)題的時(shí)間復(fù)雜度的是()。A:O(1)(正確答案)B:O(n)(正確答案)C:O(nn)(正確答案)D:O(2的n次冪)31.若哈希表的裝填因子α<1，則可避免沖突的產(chǎn)生。對(duì)錯(cuò)(正確答案)32.二叉排序樹(shù)的充要條件：二叉排序樹(shù)的任意結(jié)點(diǎn)的關(guān)鍵字都大于其左孩子的關(guān)鍵字，且小于其右孩子的關(guān)鍵字。對(duì)錯(cuò)(正確答案)33.直接插入排序必須需要使用return語(yǔ)句才能實(shí)現(xiàn)。對(duì)錯(cuò)(正確答案)34.希爾排序是不穩(wěn)定排序是因?yàn)榇嬖诓幌噜彽脑刂g的交換。對(duì)(正確答案)錯(cuò)35.冒泡排序需要比較不相鄰元素之間的大小，以便交換。對(duì)錯(cuò)(正確答案)36.快速排序在