第頁(yè)中級(jí)軟件設(shè)計(jì)師復(fù)習(xí)測(cè)試卷1.在__（34）__存儲(chǔ)結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系。A、順序（Sequence）B、鏈表（Link）C、索引（Index）D、散列（Hash）【正確答案】：D2.在二叉樹的順序存儲(chǔ)中，每個(gè)節(jié)點(diǎn)的存儲(chǔ)位置與其父節(jié)點(diǎn)、左右子樹節(jié)點(diǎn)的位置都存在一個(gè)

簡(jiǎn)單的映射關(guān)系，因此可與三叉鏈表對(duì)應(yīng)。若某二叉樹共有n個(gè)節(jié)點(diǎn)，采用三叉鏈表存儲(chǔ)時(shí)，每個(gè)節(jié)

點(diǎn)的數(shù)據(jù)域需要d個(gè)字節(jié)，每個(gè)指針域占用4個(gè)字節(jié)，若采用順序存儲(chǔ)，則最后一個(gè)節(jié)點(diǎn)下標(biāo)為k（起

始下標(biāo)為1），那么__（19）__時(shí)采用順序存儲(chǔ)更節(jié)省空間。A、B、C、D、【正確答案】：A3.若一個(gè)問(wèn)題既可以用迭代方式也可以用遞歸方式求解，則__（68）__方法具有更高的時(shí)空效率。A、迭代B、遞歸C、先遞歸后迭代D、先迭代后遞歸【正確答案】：A4.下面C程序段中count++語(yǔ)句執(zhí)行的次數(shù)為__(118)__。

For(inti=1；i<=11；i*=2)

For(intj=1；j<=i；j++)

Count++；A、15B、16C、31D、32【正確答案】：A5.下面關(guān)于哈夫曼樹的敘述中，正確的是__（115）__A、哈夫曼樹一定是完全二叉樹B、哈夫曼樹一定是平衡二叉樹C、哈夫曼樹中權(quán)值最小的兩個(gè)結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)D、哈夫曼樹中左孩子結(jié)點(diǎn)小于父結(jié)點(diǎn)、右孩子結(jié)點(diǎn)大于父結(jié)點(diǎn)【正確答案】：C6.關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，__（67）__是正確的。A、算法的實(shí)現(xiàn)依賴于數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)B、算法的效率與數(shù)據(jù)結(jié)構(gòu)無(wú)關(guān)C、數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，算法的效率越高D、數(shù)據(jù)結(jié)構(gòu)越簡(jiǎn)單，算法的效率越高【正確答案】：A7.下面關(guān)于圖（網(wǎng)）的敘述，正確的是__（90）__.A、連通無(wú)向網(wǎng)的最小生成樹中，頂點(diǎn)數(shù)恰好比邊數(shù)多1B、若有向圖是強(qiáng)連通的，則其邊數(shù)至少是頂點(diǎn)數(shù)的2倍C、可以采用AOV網(wǎng)估算工程的工期D、關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)至匯點(diǎn)的最短路徑【正確答案】：A8.用插入排序和歸并排序算法對(duì)數(shù)組<3,1,4,1,5,9,6,5>進(jìn)行從小到大排序，則分別需要進(jìn)行_（128）__次數(shù)組元素之間的比較。A、12,14B、10,14C、12,16D、10,16【正確答案】：A9.一個(gè)具有n（n＞0）個(gè)頂點(diǎn)的連通A、n+1B、nC、n/2D、n-1【正確答案】：D10.下面關(guān)于二叉排序樹的敘述，錯(cuò)誤的是__（91）__.A、對(duì)二叉排序樹進(jìn)行中序遍歷，必定得到結(jié)點(diǎn)關(guān)鍵字的有序序列B、依據(jù)關(guān)鍵字無(wú)序的序列建立二叉排序樹，也可能構(gòu)造出單支樹C、若構(gòu)造二叉排序樹時(shí)進(jìn)行平衡化處理，則根結(jié)點(diǎn)的左子樹結(jié)點(diǎn)數(shù)與右子樹結(jié)點(diǎn)數(shù)的差值一定不超過(guò)1D、若構(gòu)造二叉排序樹時(shí)進(jìn)行平衡化處理，則根結(jié)點(diǎn)的左子樹高度與右子樹高度的

差值一定不超過(guò)1【正確答案】：C11.在11個(gè)元素的有序表A[111]中進(jìn)行折半查找（），查找元素A[11]時(shí)，被比較的元素的下標(biāo)依

次是__（22）__.A、6,8,10,11B、6,9,10,11C、6,7,9,11D、6,8,9,11【正確答案】：B12.利用逐點(diǎn)插入法建立序列（50，72，43，85，75，20，35，45，65，30）對(duì)應(yīng)的二叉排序

樹以后，查找元素30要進(jìn)行__(5)__次元素間的比較。A、4B、5C、6D、7【正確答案】：B13.若總是以待排序列的第一個(gè)元素作為基準(zhǔn)元素進(jìn)行快速排序，那么最好情況下的時(shí)間復(fù)雜度為__（78）__.A、B、C、D、【正確答案】：C14.拓?fù)湫蛄惺菬o(wú)環(huán)有向圖中所有頂點(diǎn)的一個(gè)線性序列，圖中任意路徑中的各個(gè)頂點(diǎn)在該圖的拓

撲序列中保持先后關(guān)系，__（30）__為圖1-2所示有向圖的一個(gè)拓?fù)湫蛄小?/p>

A、1234567B、1526374C、5126347D、5123764【正確答案】：B15.若對(duì)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則采用僅設(shè)尾指針的單向循環(huán)鏈表（不含頭結(jié)點(diǎn)）時(shí)，__（113）__.A、插入和刪除操作的時(shí)間復(fù)雜度都為O（1）B、插入和刪除操作的時(shí)間復(fù)雜度都為O（n）C、插入操作的時(shí)間復(fù)雜度為O（1），刪除操作的時(shí)間復(fù)雜度為O（n）D、插入操作的時(shí)間復(fù)雜度為O（n），刪除操作的時(shí)間復(fù)雜度為O（1）【正確答案】：C16.設(shè)下三角矩陣（上三角部分的元素值都為0）A[0n,0n]如下所示，將該三角矩陣的所有非零元

素（即行下標(biāo)不小于列下標(biāo)的元素）按行優(yōu)先壓縮存儲(chǔ)在容量足夠大的數(shù)組M[]中（下標(biāo)從1開

始），則元素A[i,j]（O≤i≤n,j≤i）存儲(chǔ)在數(shù)組M的__（120）__中。

A、B、C、D、【正確答案】：A17.對(duì)于n（n≥0）個(gè)元素構(gòu)成的線性序列L,在__（63）__時(shí)適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。A、需要頻繁修改L中元素的值B、需要頻繁地對(duì)L進(jìn)行隨機(jī)查找C、需要頻繁地對(duì)L進(jìn)行刪除和插入操作D、要求L存儲(chǔ)密度高【正確答案】：C18.表達(dá)式a*（b+c）-d的后綴表達(dá)式為__（2）__.A、abcd*+-B、abc+*d-C、abc*+d-D、-+*abcd【正確答案】：B19.對(duì)n個(gè)元素的數(shù)組進(jìn)行__（56）__,其平均時(shí)間復(fù)雜度和最壞情況下的時(shí)間復(fù)雜度都是O（nlogn）。A、希爾排序B、快速排序C、堆排序D、選擇排序【正確答案】：C20.在如圖1-7所示平衡二叉樹（樹中任一結(jié)點(diǎn)的左右子樹高度之差不超過(guò)1）中，結(jié)點(diǎn)A的右子樹AR高度為

H,結(jié)點(diǎn)B的左子樹BL高度為

H,結(jié)點(diǎn)C的左子樹CL、右子樹CR高度都為h-1.若在

CR中插入一個(gè)結(jié)點(diǎn)并使得CR的高度增加1,則該二叉樹__（54）__.

A、以B為根的子二叉樹變?yōu)椴黄胶釨、以C為根的子二叉樹變?yōu)椴黄胶釩、以A為根的子二叉樹變?yōu)椴黄胶釪、仍然是平衡二叉樹【正確答案】：C21.表達(dá)式（a-b）*（c+5）的后綴式是__（79）__.A、abc5+*-B、ab–c+5*C、abc-*5+D、ab-c5+*【正確答案】：D22.若將某有序樹T轉(zhuǎn)換為二叉樹T1,則T中結(jié)點(diǎn)的后（根）序序列就是T1中結(jié)點(diǎn)的__（72）__

遍歷序列。例如，圖1-8（a）所示的有序樹轉(zhuǎn)化為二叉樹后如圖（b）所示。

A、先序B、中序C、后序D、層序【正確答案】：B23.己知一棵度為3的樹（一個(gè)結(jié)點(diǎn)的度是指其子樹的數(shù)目，樹的度是指該樹中所有結(jié)點(diǎn)的度的最大值）中有5個(gè)度為1的結(jié)點(diǎn)，4個(gè)度為2的結(jié)點(diǎn)，2個(gè)度為3的結(jié)點(diǎn)，那么，該樹中的葉子結(jié)點(diǎn)數(shù)目為__（117）__.A、10B、9C、8D、7【正確答案】：B24.鄰接矩陣和鄰接表是圖（網(wǎng)）的兩種基本存儲(chǔ)結(jié)構(gòu)，對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，__（99）__.A、進(jìn)行深度優(yōu)先遍歷運(yùn)算所消耗的時(shí)間與采用哪一種存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B、進(jìn)行廣度優(yōu)先遍歷運(yùn)算所消耗的時(shí)間與采用哪一種存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)C、采用鄰接表表示圖時(shí)，查找所有頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O（n*e）D、采用鄰接矩陣表示圖時(shí)，查找所有頂點(diǎn)的鄰接頂點(diǎn)的時(shí)間復(fù)雜度為O（n^2）【正確答案】：D25.用關(guān)鍵字序列10、20、30、40、50構(gòu)造的二叉排序樹（二叉查找樹）為__（111）__.A、B、C、D、【正確答案】：C26.以下的算法設(shè)計(jì)方法中，__（95）__以獲取問(wèn)題最優(yōu)解為目標(biāo)。A、回溯方法B、分治法C、動(dòng)態(tài)規(guī)劃D、遞推【正確答案】：C27.對(duì)于哈希表，如果將裝填因子定義為表中裝入的記錄數(shù)與表的長(zhǎng)度之比，那么向表中加入新記錄時(shí)，__（110）__.A、的值隨沖突次數(shù)的增加而遞減B、越大發(fā)生沖突的可能性就越大C、等于1時(shí)不會(huì)再發(fā)生沖突D、低于0.5時(shí)不會(huì)發(fā)生沖突【正確答案】：B28.給定-個(gè)有n個(gè)元素的有序線性表。若采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率前提下，刪除其中的一

個(gè)元素平均需要移動(dòng)__（32）__個(gè)元素。A、（n+1）/2B、n/2C、（n-1）/2D、1【正確答案】：C29.輸入受限的雙端隊(duì)列是指元素只能從隊(duì)列的一端輸入、但可以從隊(duì)列的兩端輸出，如圖1-5所

示。若有8、1、4、2依次進(jìn)入輸入受限的雙端隊(duì)列，則得不到輸出序列__（50）__.

A、2、8、1、4B、1、4、8、2C、4、2、1、8D、2、1、4、8【正確答案】：D30.A、B、C、D、【正確答案】：A31.__（38）__在其最好情況下的算法時(shí)間復(fù)雜度為O（n）。A、插入排序B、歸并排序C、快速排序D、堆排序【正確答案】：A32.某一維數(shù)組中依次存放了數(shù)據(jù)元素15,23,38,47,55,62,88,95,102,123,采用折半（二分）法查找元素95時(shí)，依次與__（116）__進(jìn)行了比較。A、62,88,95B、62,95C、55,88,95D、55,95【正確答案】：D33.設(shè)商店有10元、5元、2元和1元的零幣，每種零幣的數(shù)量充足。售貨員給顧客找零錢時(shí)，

零幣的數(shù)量越少越好。例如給顧客找零29元：先選2張10元幣，然后選擇1張5元幣，再選擇兩

張2元幣。以上的找零錢方法采用了__（55）__策略。A、分治B、貪心C、動(dòng)態(tài)規(guī)劃D、回溯【正確答案】：B34.一個(gè)算法是對(duì)某類給定問(wèn)題求解過(guò)程的精確描述，算法中描述的操作都可以通過(guò)將已經(jīng)實(shí)現(xiàn)

的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)，這句話說(shuō)明算法具有__（75）__特性。A、有窮性B、可行性C、確定性D、健壯性【正確答案】：B35.設(shè)L為廣義表，將head（L）定義為取非空廣義表的第一個(gè)元素，tail（L）定義為取非空廣義表除第一個(gè)元素外剩余元素構(gòu)成的廣義表。若廣義表L=（（x,y,z），a,（u,t,w）），則從L中取出原子項(xiàng)y的運(yùn)算是__（94）__.A、head（tail（tail（L）））B、tail（head（head（L）））C、head（tail（head（L）））D、tail（tail（head（L）））【正確答案】：C36.某算法的時(shí)間復(fù)雜度表達(dá)式為T（n）=an^2+bnlgn+cn+d,其中，n為問(wèn)題的規(guī)模，a、b、c和d為常數(shù)，用O表示其漸近時(shí)間復(fù)雜度為__（103）__.A、O（n^2）B、O（n）C、O（nlgn）D、O（1）【正確答案】：A37.某雙向鏈表中的節(jié)點(diǎn)如圖1-4所示，刪除t所指節(jié)點(diǎn)的操作為__（42）__.

A、t->prior->next=t->next;t->next->prior=t->prior;B、t->prior->prior=t->prior;t->next->next=t->next;C、t->prior->next=t->prior;t->next->prior=t->next;D、t->prior->prior=t->next;t->next->prior=t->prior;【正確答案】：A38.由權(quán)值為9,2,5,7的4個(gè)葉子節(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為__（8）__.A、23B、37C、44D、46【正確答案】：C39.A、B、C、D、【正確答案】：A40.為了便于存儲(chǔ)和處理一般樹結(jié)構(gòu)形式的信息，常采用孩子-兄弟表示法將其轉(zhuǎn)換成二叉樹（左

子關(guān)系表示父子，右子關(guān)系表示兄弟），與圖1-3所示的樹對(duì)應(yīng)的二叉樹是__（31）__.

A、B、C、D、【正確答案】：A41.棧是一種按"后進(jìn)先出"原則進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)，因此，__（108）__必須用棧。A、實(shí)現(xiàn)函數(shù)或過(guò)程的遞歸調(diào)用及返回處理時(shí)B、將一個(gè)元素序列進(jìn)行逆置C、鏈表結(jié)點(diǎn)的申請(qǐng)和釋放D、可執(zhí)行程序的裝入和卸載【正確答案】：A42.表達(dá)式"（a+b）*（c-d）"的后綴表示為__（49）__.A、ab+cd-*B、abcd+-*C、ab+*cd-D、abcd*+-【正確答案】：A43.對(duì)于關(guān)鍵字序列（26,25,72,38,8,18,59），采用散列函數(shù)H（Key）=Keymod13構(gòu)造散列表（哈希表）。若采用線性探測(cè)的開放定址法解決沖突（順序地探查可用存儲(chǔ)單元），則關(guān)鍵字59所在散列表中的地址為__（124）__.A、6B、7C、8D、9【正確答案】：D44.若用n個(gè)權(quán)值構(gòu)造一棵最優(yōu)二叉樹（哈夫曼樹），則該二叉樹的結(jié)點(diǎn)總數(shù)為__（107）__.A、2nB、2n-1C、2n+1D、2n+2【正確答案】：B45.具有n個(gè)頂點(diǎn)、e條邊的圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷運(yùn)算的時(shí)間復(fù)雜度均為__（86）__.A、O（n^2）B、O（e^2）C、O（n*e）D、O（n+e）【正確答案】：D46.在平衡二叉樹中，__（33）__.A、任意節(jié)點(diǎn)的左、右子樹節(jié)點(diǎn)數(shù)目相同B、任意節(jié)點(diǎn)的左、右子樹高度相同C、任意節(jié)點(diǎn)的左、右子樹高度之差的絕對(duì)值不大于1D、不存在度為1的節(jié)點(diǎn)【正確答案】：C47.廣義表中的元素可以是原子，也可以是表，因此廣義表的適用存儲(chǔ)結(jié)構(gòu)是__（84）__A、鏈表B、靜態(tài)數(shù)組C、動(dòng)態(tài)數(shù)組D、散列表【正確答案】：A48.下面關(guān)于棧和隊(duì)列的敘述，錯(cuò)誤的是__（92）__.A、棧和隊(duì)列都是操作受限的線性表B、隊(duì)列采用單循環(huán)鏈表存儲(chǔ)時(shí)，只需設(shè)置隊(duì)尾指針就可使入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度都為O（1）C、若隊(duì)列的數(shù)據(jù)規(guī)模n可以確定，則采用順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)效率更高D、利用兩個(gè)?？梢阅M一個(gè)隊(duì)列的操作，反之亦可【正確答案】：D49.對(duì)n個(gè)元素的有序表A[1n]進(jìn)行順序查找，其成功查找的平均查找長(zhǎng)度（即在查找表中找到指定關(guān)鍵碼的元素時(shí)，所進(jìn)行比較的表中元素個(gè)數(shù)的期望值）為__（121）__.A、nB、（n+1）/2C、log2nD、n^2【正確答案】：B50.下面關(guān)于查找運(yùn)算及查找表的敘述，錯(cuò)誤的是__（89）__.A、哈希表可以動(dòng)態(tài)創(chuàng)建B、二叉排序樹屬于動(dòng)態(tài)查找表C、二分查找要求查找表采用順序存儲(chǔ)結(jié)構(gòu)或循環(huán)鏈表結(jié)構(gòu)D、順序查找方法既適用于順序存儲(chǔ)結(jié)構(gòu)，也適用于鏈表結(jié)構(gòu)【正確答案】：C51.求單源點(diǎn)最短路徑的迪杰斯特拉（Dijkstra）算法是按__（45）__的順序求源點(diǎn)到各頂點(diǎn)的最

短路徑的。A、路徑長(zhǎng)度遞減B、路徑長(zhǎng)度遞增C、頂點(diǎn)編號(hào)遞減D、頂點(diǎn)編號(hào)遞增【正確答案】：B52.A、（4,10,15,72,39,23,18）B、（58,27,36,12,8,23,9）C、（4,10,18,72,39,23,15）D、（58,36,27,12,8,23,9）【正確答案】：C53.將一個(gè)無(wú)序序列中的元素依次插入到一棵__（83）__,并進(jìn)行中序遍歷，可得到一個(gè)有序序列。A、完全二叉樹B、最小生成樹C、二叉排序樹D、最優(yōu)二叉樹【正確答案】：C54.若某算法在問(wèn)題規(guī)模為n時(shí)，其基本操作的重復(fù)次數(shù)可由下式表示，則該算法的時(shí)間復(fù)雜度為__（112）__.

A、O（n）B、O（n^2）C、O（logn）D、O（nlogn）【正確答案】：B55.拓?fù)渑判蚴侵赣邢驁D中的所有頂點(diǎn)排成一個(gè)線性序列的過(guò)程，若在有向圖中從頂點(diǎn)vi到vj有一

條路徑，則在該線性序列中，頂點(diǎn)vi必然在頂點(diǎn)vj之前。因此，若不能得到全部頂點(diǎn)的拓?fù)渑判蛐?/p>

列，則說(shuō)明該有向圖一定__（60）__.A、包含回路B、是強(qiáng)連通圖C、是完全圖D、是有向樹【正確答案】：A56.下面關(guān)于二叉樹的敘述，正確的是__（93）__.A、完全二叉樹的高度h與其結(jié)點(diǎn)數(shù)n之間存在確定的關(guān)系B、在二叉樹的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，完全二叉樹更適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C、完全二叉樹中一定不存在度為1的結(jié)點(diǎn)D、完全二叉樹中必定有偶數(shù)個(gè)葉子結(jié)點(diǎn)【正確答案】：A57.由元素序列（27,16,75,38,51）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插

入節(jié)點(diǎn)最近且平衡因子的絕對(duì)值為2的節(jié)點(diǎn)）為__（23）__.A、27B、38C、51D、75【正確答案】：D58.從E開始的活動(dòng)啟動(dòng)的最早時(shí)間是__（17）__.A、10B、12C、13D、15【正確答案】：C59.某一維數(shù)組中依次存放了數(shù)據(jù)元素12,23,30,38,41,52,54,76,85,在用折半（二分）查找方法（向上取整）查找元素54時(shí)，所經(jīng)歷"比較"運(yùn)算的數(shù)據(jù)元素依次為__（85）__.A、41,52,54B、41,76,54C、41,76,52,54D、41,30,76,54【正確答案】：B60.無(wú)向圖中一個(gè)頂點(diǎn)的度是指圖中__(4)__。A、通過(guò)該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B、通過(guò)該頂點(diǎn)的回路數(shù)C、與該頂點(diǎn)相鄰的頂點(diǎn)數(shù)D、與該頂點(diǎn)連通的頂點(diǎn)數(shù)【正確答案】：C61.__（46）__算法策略與遞歸技術(shù)的聯(lián)系最弱。A、動(dòng)態(tài)規(guī)劃B、貪心C、回溯D、分治【正確答案】：B62.要在8*8的棋盤上擺放8個(gè)"皇后",要求"皇后"之間不能發(fā)生沖突，即任何兩個(gè)"皇后"不能在同一行、同一列和相同的對(duì)角線上，則一般采用__（125）__來(lái)實(shí)現(xiàn)。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法【正確答案】：D63.在常用的描述二叉排序樹的存儲(chǔ)結(jié)構(gòu)中，關(guān)鍵字值最大的節(jié)點(diǎn)__(6)__。A、左指針一定為空B、右指針一定為空C、左、右指針均為空D、左、右指針均不為空【正確答案】：B64.設(shè)某算法的計(jì)算時(shí)間表示為遞推關(guān)系式T（n）=T（n-1）+n（n>0）及T（0）=1,則該算法的時(shí)間復(fù)雜度為__（88）__.A、O（lgn）B、O（nlgn）C、O（n）D、O（n^2）【正確答案】：D65.循環(huán)鏈表的主要優(yōu)點(diǎn)是__（1）__.A、不再需要頭指針了B、已知某個(gè)節(jié)點(diǎn)的位置后，能很容易找到它的直接前驅(qū)節(jié)點(diǎn)C、在進(jìn)行刪除操作后，能保證鏈表不斷開D、從表中任一節(jié)點(diǎn)出發(fā)都能遍歷整個(gè)鏈表【正確答案】：D66.給定一組長(zhǎng)度為n的無(wú)序序列，將其存儲(chǔ)在一維數(shù)組a[0..n-1]中。現(xiàn)采用如下方法找出其中的最大元素和最小元素：比較a[0]和a[n-1],若a[0]較大，則將二者的值進(jìn)行交換；再比較a[1]和a[n-2],若a[1]較大，則交換二者的值；然后依次比較a[2]和a[n-3]、a[3]和a[n-4]、…，使得每一對(duì)元素中的較小者被交換到低下標(biāo)端。重復(fù)上述方法，在數(shù)組的前n/2個(gè)元素中查找最小元素，在后n/2個(gè)元素查找最大元素，從而得到整個(gè)序列的最小元素和最大元素。上述方法采用的算法設(shè)計(jì)策略是__（87）__.A、動(dòng)態(tài)規(guī)劃法B、貪心法C、分治法D、回溯法【正確答案】：C67.歸并排序采用的算法設(shè)計(jì)方法屬于__（96）__.A、歸納法B、分治法C、貪心法D、回溯方法【正確答案】：B68.迪杰斯特拉（Dijkstra）算法按照路徑長(zhǎng)度遞增的方式求解單源點(diǎn)最短路徑問(wèn)題，該算法運(yùn)用了__（66）__算法策略。A、貪心B、分而治之C、動(dòng)態(tài)規(guī)劃D、試探+回溯【正確答案】：A69.對(duì)于長(zhǎng)度為m（m>1）的指定序列，通過(guò)初始為空的一個(gè)棧、一個(gè)隊(duì)列后，錯(cuò)誤的敘述是__（101）__.A、若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可能相同B、若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可以互為逆序C、入隊(duì)序列與出隊(duì)序列關(guān)系為1:1,而入棧序列與出棧序列關(guān)系是l:n（n≥1）D、入棧序列與出棧序列關(guān)系為1:1,而入隊(duì)序列與出隊(duì)序列關(guān)系是l:n（n≥1）【正確答案】：D70.對(duì)以下四個(gè)序列用直接插入排序方法由小到大進(jìn)行排序時(shí)，元素比較次數(shù)最少的是__（109）__.A、89,27,35,78,41,15B、27,35,41,16,89,70C、15,27,46,40,64,85D、90,80,45,38,30,25【正確答案】：C71.已知一個(gè)線性表（38,25,74,63,52,48），假定采用散列函數(shù)h（key）=key%7計(jì)算散列地

址，并散列存儲(chǔ)在散列表A[0,…，6]中，若采用線性探測(cè)方法解決沖突，則在該散列表上進(jìn)行等概率

成功查找的平均查找長(zhǎng)度為__（10）__.A、1.5B、1.7C、2.0D、2.3【正確答案】：C72.●表達(dá)式"X=A+B（C-D）/E"的后綴表示形式可以為__（59）__（運(yùn)算符優(yōu)先級(jí)相同時(shí)，遵循左結(jié)合的原則）。A、B、C、D、【正確答案】：C73.對(duì)n個(gè)元素的有序表A[1n]進(jìn)行二分（折半）查找（除2取商時(shí)向下取整），查找元素A[i]（1≤i≤n）時(shí)，最多與A中的__（106）__個(gè)元素進(jìn)行比較。A、B、C、D、【正確答案】：D74.在最好和最壞情況下的時(shí)間復(fù)雜度均為O（nlog2n）且穩(wěn)定的排序方法是__（9）__.A、基數(shù)排序B、快速排序C、堆排序D、歸并排序【正確答案】：D75.分治算法設(shè)計(jì)技術(shù)__（126）__.A、一般由三個(gè)步驟組成：?jiǎn)栴}劃分、遞歸求解、合并解B、一定是用遞歸技術(shù)來(lái)實(shí)現(xiàn)C、將問(wèn)題劃分為k個(gè)規(guī)模相等的子問(wèn)題D、劃分代價(jià)很小而合并代價(jià)很大【正確答案】：A76.__（119）__不能保證求得0-1背包問(wèn)題的最優(yōu)解。A、分支限界法B、貪心算法C、回溯法D、動(dòng)態(tài)規(guī)劃策略【正確答案】：B77.●設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式T（n）=2T（n/2）+n表示，則該算法的時(shí)間復(fù)雜度為

__（37）__.A、O（lgn）B、O（nlgn）C、O（n）D、O（n^2）【正確答案】：B78.與逆波蘭式ab+-c*d-對(duì)應(yīng)的中綴表達(dá)式是__（29）__.A、a-b-c*dB、-（a+b）*c-dC、-a+b*c-dD、（a+b）*（-c-d）【正確答案】：B79.若二叉樹的先序遍歷序列為ABDECF,中序遍歷序列為DBEAFC,則其后序遍歷序列為__（3）__.A、DEBAFCB、DEFBCAC、DEBCFADEBFCA【正確答案】：D80.設(shè)一個(gè)包含N個(gè)頂點(diǎn)、E條邊的簡(jiǎn)單無(wú)向圖采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)（矩陣元素A[i][j]等于1/0分別表示頂點(diǎn)i與頂點(diǎn)j之間有/無(wú)邊），則該矩陣中的非零元素?cái)?shù)目為__（123）__.A、NB、EC、2ED、N+E【正確答案】：C81.在__（122）__中，任意一個(gè)結(jié)點(diǎn)的左、右子樹的高度之差的絕對(duì)值不超過(guò)1.A、完全二叉樹B、二叉排序樹C、線索二叉樹D、最優(yōu)二叉樹【正確答案】：A82.若有數(shù)組聲明a[0..3,0..2,1..4],設(shè)編譯時(shí)為a分配的存儲(chǔ)空間首地址為base_a,且每個(gè)數(shù)組元素

占據(jù)一個(gè)存儲(chǔ)單元。當(dāng)元素以行為序存放（即按a[0,0,1],a[0,0,2],a[0,0,3],a[0,0,4],a[0,1,1],a[0,1,2],

…，a[3,2,4]順序存儲(chǔ)），則數(shù)組元素a[2,2,2]在其存儲(chǔ)空間中相對(duì)base_a的偏移量是__（69）__.A、8B、12C、33D、48【正確答案】：C83.對(duì)于二維數(shù)組a[0..4,1..5],設(shè)每個(gè)元素占1個(gè)存儲(chǔ)單元，且以列為主序存儲(chǔ)，則元素a[2,2]相對(duì)

于數(shù)組空間起始地址的偏移量是__（43）__.A、5B、7C、10D、15【正確答案】：B84.已知某二叉樹的中序、層序序列分別為DBAFCE、FDEBCA,則該二叉樹的后序序列為

__（18）__.A、BCDEAFB、ABDCEFC、DBACEFDABECF【正確答案】：B85.__（82）__的鄰接矩陣是一個(gè)對(duì)稱矩陣。A、無(wú)向圖B、AOV網(wǎng)C、AOE網(wǎng)D、有向圖【正確答案】：A86.利用動(dòng)態(tài)規(guī)劃方法求解每對(duì)節(jié)點(diǎn)之間的最短路徑問(wèn)題（allpairsshortestpathproblem）

時(shí)，設(shè)有向圖G=<V,E>共有n個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)1~n,設(shè)C是G的成本鄰接矩陣，Dk（i,j）即為圖G中

節(jié)點(diǎn)i到j(luò)并且不經(jīng)過(guò)編號(hào)比k還大的節(jié)點(diǎn)的最短路徑的長(zhǎng)度（Dn（i,j）即為圖G中節(jié)點(diǎn)i到j(luò)的最短路徑

長(zhǎng)度），則求解該問(wèn)題的遞推關(guān)系式為__（14）__.A、Dk（i,j）=Dk-1（i,j）+C（i,j）B、Dk（i,j）=min{Dk-1（i,j），Dk-1（i,j）+C（i,j）}C、Dk（i,j）=Dk-1（i,k）+Dk-1（k,j）Dk（i,j）=min{Dk-1（i,j），Dk-1（i,k）+Dk-1（k,j）}【正確答案】：D87.以比較為基礎(chǔ)的排序算法在最壞情況下的計(jì)算時(shí)間下界為__（13）__.A、O（n）B、O（n2）C、O（log2n）D、O（nlog2n）【正確答案】：D88.字符串采用鏈表存儲(chǔ)方式時(shí)，每個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符有助于提高存儲(chǔ)密度。若采用結(jié)點(diǎn)大小

相同的鏈表存儲(chǔ)串，則串比較、求子串、串連接、串替換等串的基本運(yùn)算中，__（102）__.A、進(jìn)行串的比較運(yùn)算最不方便B、進(jìn)行求子串運(yùn)算最不方便C、進(jìn)行串連接最不方便D、進(jìn)行串替換最不方便【正確答案】：D89.若排序前后關(guān)鍵字相同的兩個(gè)元素相對(duì)位置不變，則稱該排序方法是穩(wěn)定的。__（24）__排序

是穩(wěn)定的。A、歸并B、快速C、希爾D、堆?！菊_答案】：A90.單向鏈表中往往含有一個(gè)頭結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，一般令鏈表的頭指針指向該結(jié)點(diǎn)，而該結(jié)點(diǎn)指針域的值為第一個(gè)元素結(jié)點(diǎn)的指針。以下關(guān)于單鏈表頭結(jié)點(diǎn)的敘述中，錯(cuò)誤的是

__（100）__.A、若在頭結(jié)點(diǎn)中存入鏈表長(zhǎng)度值，則求鏈表長(zhǎng)度運(yùn)算的時(shí)間復(fù)雜度為O（1）B、在鏈表的任何一個(gè)元素前后進(jìn)行插入和刪除操作可用一致的方式進(jìn)行處理C、加入頭結(jié)點(diǎn)后，代表鏈表的頭指針不因?yàn)殒湵頌榭斩淖僁、加入頭結(jié)點(diǎn)后，在鏈表中進(jìn)行查找運(yùn)算的時(shí)間復(fù)雜度為O（1）【正確答案】：D91.設(shè)循環(huán)隊(duì)列Q的定義中有rear和len兩個(gè)域變量，其中rear表示隊(duì)尾元素的指針，len表示隊(duì)列的長(zhǎng)度，如下圖所示（隊(duì)列長(zhǎng)度為3,隊(duì)頭元素為e）。設(shè)隊(duì)列的存儲(chǔ)空間容量為M,則隊(duì)頭元素的指針為__（114）__.

A、（Q.rear+Q.len-1）B、（Q.rear+Q.len-1+M）%MC、（Q.rear-Q.len+1）D、（Q.rear-Q.len+1+M）%M【正確答案】：D92.已知某二叉樹的中序序列為CBDAEFI、先序序列為ABCDEFI,則該二叉樹的高度為__（51）A、2B、3C、4D、5【正確答案】：C1.一個(gè)具有m個(gè)結(jié)點(diǎn)的二叉樹，其二叉鏈表結(jié)點(diǎn)（左、右孩子指針分別用left和right表示）中的空指針總數(shù)必定為__（80）__個(gè)。為形成中序（先序、后序）線索二叉樹，現(xiàn)對(duì)該二叉鏈表所有結(jié)點(diǎn)進(jìn)行如下操作：若結(jié)點(diǎn)p的左孩子指針為空，則將該左指針改為指向p在中序（先序、后序）遍歷序列的前驅(qū)結(jié)點(diǎn)；若p的右孩子指針為空，則將該右指針改為指向p在中序（先序、后序）遍歷序列的后繼結(jié)點(diǎn)。假設(shè)指針s指向中序（先序、后序）線索二叉樹中的某結(jié)點(diǎn)，則__（81）__.A、m+2B、m+1C、mD、m-E、s->right指向的結(jié)點(diǎn)一定是s所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)F、s->left指向的結(jié)點(diǎn)一定是s所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)G、從s所指結(jié)點(diǎn)出發(fā)的right鏈可能構(gòu)成環(huán)H、s所指結(jié)點(diǎn)的left和right指針一定指向不同的結(jié)點(diǎn)【正確答案】：BG2.對(duì)于求取兩個(gè)長(zhǎng)度為n的字符串的最長(zhǎng)公共子序列（LCS）問(wèn)題，利用__（35）__策略可以有

效地避免子串最長(zhǎng)公共子序列的重復(fù)計(jì)算，得到時(shí)間復(fù)雜度為O（n2）的正確算法。串

<1,0,0,1,0,1,0,1>和<0,1,0,1,1,0,1,1>的最長(zhǎng)公共子序列的長(zhǎng)度為__（36）__.A、分治B、貪心C、動(dòng)態(tài)規(guī)劃D、分支一限界E、3F、4G、5H、6【正確答案】：CD3.已知一個(gè)線性表（16,25,35,43,51,62,87,93），采用散列函數(shù)H（Key）=Keymod7將

元素散列到表長(zhǎng)為9的散列表中。若采用線性探測(cè)的開放定址法解決沖突（順序地探查可用存儲(chǔ)單

元），則構(gòu)造的哈希表為__（70）__,在該散列表上進(jìn)行等概率成功查找的平均查找長(zhǎng)度為__（71）

__（為確定記錄在查找表中的位置，需和給定關(guān)鍵字值進(jìn)行比較的次數(shù)的期望值稱為查找算法在查找

成功時(shí)的平均查找長(zhǎng)度）。A、B、C、D、E、（5*1+2+3+6）/8F、（5*1+2+3+6）/9G、（8*1）/8H、（8*1）/9【正確答案】：CE4.利用貪心法求解0/1背包問(wèn)題時(shí)，__（27）__能夠確保獲得最優(yōu)解。用動(dòng)態(tài)規(guī)劃方法求解0/1

背包問(wèn)題時(shí)，將"用前i個(gè)物品來(lái)裝容量是X的背包"的0/1背包問(wèn)題記為KNAP（1,i,X），設(shè)fi（X）是

KNAP（1,i,X）最優(yōu)解的效益值，第j個(gè)物品的重量和放入背包后取得效益值分別為Wj和

Pj（j=1~n）。則依次求解f0（X）、f1（X）、…、fn（X）的過(guò)程中使用的遞推關(guān)系式為__（28）

__.A、優(yōu)先選取重量最小的物品B、優(yōu)先選取效益最大的物品C、優(yōu)先選取單位重量效益最大的物品D、沒有任何準(zhǔn)則E、fi（X）=min{fi-1（X），fi-1（X）+pi}F、fi（X）=max{fi-1（X），fi-1（X-Wi）+pi}G、fi（X）=min{fi-1（X-Wi），fi-1（X-Wi）+pi}H、fi（X）=max{fi-1（X-Wi），fi-1（X）+pi}【正確答案】：DF5.斐波那契（Fibonacci）數(shù)列可以遞歸地定義為：

用遞歸算法求解F（5）時(shí)需要執(zhí)行__（76）__次"+"運(yùn)算，該方法采用的算法策略是__（77）A、5B、6C、7D、8E、動(dòng)態(tài)規(guī)劃F、分治G、回溯H、分支限界【正確答案】：BC6.某工程計(jì)劃如圖1-6所示，各個(gè)作業(yè)所需的天數(shù)如下表所示，設(shè)該工程從第0天開工，則該工

程的最短工期是__（52）__天，作業(yè)J最遲應(yīng)在第__（53）__天開工。A、17B、18C、19D、20E、11F、13G、14H、16【正確答案】：DF7.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素按照a、b、c、d、e的次序進(jìn)入棧S,當(dāng)一個(gè)元素從棧中

出來(lái)后立即進(jìn)入隊(duì)列Q.若隊(duì)列的輸出元素序列是c、d、b、a、e,則元素的出棧順序是__（61）__,棧S

的容量至少為__（62）__.A、a、b、c、d、eB、e、d、c、b、aC、c、d、b、a、eD、e、a、b、d、cE、2F、3G、4H、5【正確答案】：CF8.以下關(guān)于快速排序算法的描述中，錯(cuò)誤的是__（104）__.在快速排序過(guò)程中，需要設(shè)立基準(zhǔn)元素并劃分序列來(lái)進(jìn)行排序。若序列由元素{12,25,30,45,52,67,85}構(gòu)成，則初始排列為__（105）__時(shí)，排序效率最高（令序列的第一個(gè)元素為基準(zhǔn)元素）。A、快速排序算法是不穩(wěn)定的排序算法B、快速排序算法在最壞情況下的時(shí)間復(fù)雜度為O（nlgn）C、快速排序算法是一種分治算法D、當(dāng)輸入數(shù)據(jù)基本有序時(shí)，快速排序算法具有最壞情況下的時(shí)間復(fù)雜度E、45,12,30,25,67,52,85F、85,67,52,45,30,25,12G、12,25,30,45,52,67,85H、45,12,25,30,85,67,52【正確答案】：AB9.為在狀態(tài)空間樹中__（11）__,可以利用LC-檢索（LeastCostSearch）快速找到一個(gè)答案節(jié)

點(diǎn)。在進(jìn)行LC-檢索時(shí)，為避免算法過(guò)分偏向于縱深檢查，應(yīng)該__（12）__.A、找出任一個(gè)答案節(jié)點(diǎn)B、找出所有的答案節(jié)點(diǎn)C、找出最優(yōu)的答案節(jié)點(diǎn)D、進(jìn)行遍歷E、使用精確的成本函數(shù)c來(lái)做LC-檢索F、使用廣度優(yōu)先檢索G、使用深度優(yōu)先檢索H、在成本估計(jì)函數(shù)ê中考慮根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的成本（距離）【正確答案】：CH10.在活動(dòng)圖中，節(jié)點(diǎn)表示項(xiàng)目中各個(gè)工作階段的里程碑，連接各個(gè)節(jié)點(diǎn)的邊表示活動(dòng)，邊上的

數(shù)字表示活動(dòng)持續(xù)的時(shí)間。在下面的活動(dòng)圖中，從A到J的關(guān)鍵路徑是__（15）__,關(guān)鍵路徑長(zhǎng)度是

__（16）__,

圖1-1活動(dòng)圖ABEGJB、ADFHJC、ACFGJD、ADFIJE、22F、49G、19H、35【正確答案】：BF11.設(shè)一個(gè)包含N個(gè)頂點(diǎn)、E條