第頁中級軟件設計師復習測試卷1.在__（34）__存儲結構中，數據結構中元素的存儲地址與其關鍵字之間存在某種映射關系。A、順序（Sequence）B、鏈表（Link）C、索引（Index）D、散列（Hash）【正確答案】：D2.在二叉樹的順序存儲中，每個節點的存儲位置與其父節點、左右子樹節點的位置都存在一個

簡單的映射關系，因此可與三叉鏈表對應。若某二叉樹共有n個節點，采用三叉鏈表存儲時，每個節

點的數據域需要d個字節，每個指針域占用4個字節，若采用順序存儲，則最后一個節點下標為k（起

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

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

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

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

差值一定不超過1【正確答案】：C11.在11個元素的有序表A[111]中進行折半查找（），查找元素A[11]時，被比較的元素的下標依

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

樹以后，查找元素30要進行__(5)__次元素間的比較。A、4B、5C、6D、7【正確答案】：B13.若總是以待排序列的第一個元素作為基準元素進行快速排序，那么最好情況下的時間復雜度為__（78）__.A、B、C、D、【正確答案】：C14.拓撲序列是無環有向圖中所有頂點的一個線性序列，圖中任意路徑中的各個頂點在該圖的拓

撲序列中保持先后關系，__（30）__為圖1-2所示有向圖的一個拓撲序列。

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

素（即行下標不小于列下標的元素）按行優先壓縮存儲在容量足夠大的數組M[]中（下標從1開

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

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

H,結點B的左子樹BL高度為

H,結點C的左子樹CL、右子樹CR高度都為h-1.若在

CR中插入一個結點并使得CR的高度增加1,則該二叉樹__（54）__.

A、以B為根的子二叉樹變為不平衡B、以C為根的子二叉樹變為不平衡C、以A為根的子二叉樹變為不平衡D、仍然是平衡二叉樹【正確答案】：C21.表達式（a-b）*（c+5）的后綴式是__（79）__.A、abc5+*-B、ab–c+5*C、abc-*5+D、ab-c5+*【正確答案】：D22.若將某有序樹T轉換為二叉樹T1,則T中結點的后（根）序序列就是T1中結點的__（72）__

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

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

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

示。若有8、1、4、2依次進入輸入受限的雙端隊列，則得不到輸出序列__（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）__在其最好情況下的算法時間復雜度為O（n）。A、插入排序B、歸并排序C、快速排序D、堆排序【正確答案】：A32.某一維數組中依次存放了數據元素15,23,38,47,55,62,88,95,102,123,采用折半（二分）法查找元素95時，依次與__（116）__進行了比較。A、62,88,95B、62,95C、55,88,95D、55,95【正確答案】：D33.設商店有10元、5元、2元和1元的零幣，每種零幣的數量充足。售貨員給顧客找零錢時，

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

張2元幣。以上的找零錢方法采用了__（55）__策略。A、分治B、貪心C、動態規劃D、回溯【正確答案】：B34.一個算法是對某類給定問題求解過程的精確描述，算法中描述的操作都可以通過將已經實現

的基本操作執行有限次來實現，這句話說明算法具有__（75）__特性。A、有窮性B、可行性C、確定性D、健壯性【正確答案】：B35.設L為廣義表，將head（L）定義為取非空廣義表的第一個元素，tail（L）定義為取非空廣義表除第一個元素外剩余元素構成的廣義表。若廣義表L=（（x,y,z），a,（u,t,w）），則從L中取出原子項y的運算是__（94）__.A、head（tail（tail（L）））B、tail（head（head（L）））C、head（tail（head（L）））D、tail（tail（head（L）））【正確答案】：C36.某算法的時間復雜度表達式為T（n）=an^2+bnlgn+cn+d,其中，n為問題的規模，a、b、c和d為常數，用O表示其漸近時間復雜度為__（103）__.A、O（n^2）B、O（n）C、O（nlgn）D、O（1）【正確答案】：A37.某雙向鏈表中的節點如圖1-4所示，刪除t所指節點的操作為__（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.由權值為9,2,5,7的4個葉子節點構造一棵哈夫曼樹，該樹的帶權路徑長度為__（8）__.A、23B、37C、44D、46【正確答案】：C39.A、B、C、D、【正確答案】：A40.為了便于存儲和處理一般樹結構形式的信息，常采用孩子-兄弟表示法將其轉換成二叉樹（左

子關系表示父子，右子關系表示兄弟），與圖1-3所示的樹對應的二叉樹是__（31）__.

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

短路徑的。A、路徑長度遞減B、路徑長度遞增C、頂點編號遞減D、頂點編號遞增【正確答案】：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.將一個無序序列中的元素依次插入到一棵__（83）__,并進行中序遍歷，可得到一個有序序列。A、完全二叉樹B、最小生成樹C、二叉排序樹D、最優二叉樹【正確答案】：C54.若某算法在問題規模為n時，其基本操作的重復次數可由下式表示，則該算法的時間復雜度為__（112）__.

A、O（n）B、O（n^2）C、O（logn）D、O（nlogn）【正確答案】：B55.拓撲排序是指有向圖中的所有頂點排成一個線性序列的過程，若在有向圖中從頂點vi到vj有一

條路徑，則在該線性序列中，頂點vi必然在頂點vj之前。因此，若不能得到全部頂點的拓撲排序序

列，則說明該有向圖一定__（60）__.A、包含回路B、是強連通圖C、是完全圖D、是有向樹【正確答案】：A56.下面關于二叉樹的敘述，正確的是__（93）__.A、完全二叉樹的高度h與其結點數n之間存在確定的關系B、在二叉樹的順序存儲和鏈式存儲結構中，完全二叉樹更適合采用鏈式存儲結構C、完全二叉樹中一定不存在度為1的結點D、完全二叉樹中必定有偶數個葉子結點【正確答案】：A57.由元素序列（27,16,75,38,51）構造平衡二叉樹，則首次出現的最小不平衡子樹的根（即離插

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

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

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

__（37）__.A、O（lgn）B、O（nlgn）C、O（n）D、O（n^2）【正確答案】：B78.與逆波蘭式ab+-c*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.設一個包含N個頂點、E條邊的簡單無向圖采用鄰接矩陣存儲結構（矩陣元素A[i][j]等于1/0分別表示頂點i與頂點j之間有/無邊），則該矩陣中的非零元素數目為__（123）__.A、NB、EC、2ED、N+E【正確答案】：C81.在__（122）__中，任意一個結點的左、右子樹的高度之差的絕對值不超過1.A、完全二叉樹B、二叉排序樹C、線索二叉樹D、最優二叉樹【正確答案】：A82.若有數組聲明a[0..3,0..2,1..4],設編譯時為a分配的存儲空間首地址為base_a,且每個數組元素

占據一個存儲單元。當元素以行為序存放（即按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]順序存儲），則數組元素a[2,2,2]在其存儲空間中相對base_a的偏移量是__（69）__.A、8B、12C、33D、48【正確答案】：C83.對于二維數組a[0..4,1..5],設每個元素占1個存儲單元，且以列為主序存儲，則元素a[2,2]相對

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

__（18）__.A、BCDEAFB、ABDCEFC、DBACEFDABECF【正確答案】：B85.__（82）__的鄰接矩陣是一個對稱矩陣。A、無向圖B、AOV網C、AOE網D、有向圖【正確答案】：A86.利用動態規劃方法求解每對節點之間的最短路徑問題（allpairsshortestpathproblem）

時，設有向圖G=<V,E>共有n個節點，節點編號1~n,設C是G的成本鄰接矩陣，Dk（i,j）即為圖G中

節點i到j并且不經過編號比k還大的節點的最短路徑的長度（Dn（i,j）即為圖G中節點i到j的最短路徑

長度），則求解該問題的遞推關系式為__（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.以比較為基礎的排序算法在最壞情況下的計算時間下界為__（13）__.A、O（n）B、O（n2）C、O（log2n）D、O（nlog2n）【正確答案】：D88.字符串采用鏈表存儲方式時，每個結點存儲多個字符有助于提高存儲密度。若采用結點大小

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

是穩定的。A、歸并B、快速C、希爾D、堆。【正確答案】：A90.單向鏈表中往往含有一個頭結點，該結點不存儲數據元素，一般令鏈表的頭指針指向該結點，而該結點指針域的值為第一個元素結點的指針。以下關于單鏈表頭結點的敘述中，錯誤的是

__（100）__.A、若在頭結點中存入鏈表長度值，則求鏈表長度運算的時間復雜度為O（1）B、在鏈表的任何一個元素前后進行插入和刪除操作可用一致的方式進行處理C、加入頭結點后，代表鏈表的頭指針不因為鏈表為空而改變D、加入頭結點后，在鏈表中進行查找運算的時間復雜度為O（1）【正確答案】：D91.設循環隊列Q的定義中有rear和len兩個域變量，其中rear表示隊尾元素的指針，len表示隊列的長度，如下圖所示（隊列長度為3,隊頭元素為e）。設隊列的存儲空間容量為M,則隊頭元素的指針為__（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.一個具有m個結點的二叉樹，其二叉鏈表結點（左、右孩子指針分別用left和right表示）中的空指針總數必定為__（80）__個。為形成中序（先序、后序）線索二叉樹，現對該二叉鏈表所有結點進行如下操作：若結點p的左孩子指針為空，則將該左指針改為指向p在中序（先序、后序）遍歷序列的前驅結點；若p的右孩子指針為空，則將該右指針改為指向p在中序（先序、后序）遍歷序列的后繼結點。假設指針s指向中序（先序、后序）線索二叉樹中的某結點，則__（81）__.A、m+2B、m+1C、mD、m-E、s->right指向的結點一定是s所指結點的直接后繼結點F、s->left指向的結點一定是s所指結點的直接前驅結點G、從s所指結點出發的right鏈可能構成環H、s所指結點的left和right指針一定指向不同的結點【正確答案】：BG2.對于求取兩個長度為n的字符串的最長公共子序列（LCS）問題，利用__（35）__策略可以有

效地避免子串最長公共子序列的重復計算，得到時間復雜度為O（n2）的正確算法。串

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

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

元），則構造的哈希表為__（70）__,在該散列表上進行等概率成功查找的平均查找長度為__（71）

__（為確定記錄在查找表中的位置，需和給定關鍵字值進行比較的次數的期望值稱為查找算法在查找

成功時的平均查找長度）。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背包問題時，__（27）__能夠確保獲得最優解。用動態規劃方法求解0/1

背包問題時，將"用前i個物品來裝容量是X的背包"的0/1背包問題記為KNAP（1,i,X），設fi（X）是

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

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

__.A、優先選取重量最小的物品B、優先選取效益最大的物品C、優先選取單位重量效益最大的物品D、沒有任何準則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）數列可以遞歸地定義為：

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

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

出來后立即進入隊列Q.若隊列的輸出元素序列是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.以下關于快速排序算法的描述中，錯誤的是__（104）__.在快速排序過程中，需要設立基準元素并劃分序列來進行排序。若序列由元素{12,25,30,45,52,67,85}構成，則初始排列為__（105）__時，排序效率最高（令序列的第一個元素為基準元素）。A、快速排序算法是不穩定的排序算法B、快速排序算法在最壞情況下的時間復雜度為O（nlgn）C、快速排序算法是一種分治算法D、當輸入數據基本有序時，快速排序算法具有最壞情況下的時間復雜度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.為在狀態空間樹中__（11）__,可以利用LC-檢索（LeastCostSearch）快速找到一個答案節

點。在進行LC-檢索時，為避免算法過分偏向于縱深檢查，應該__（12）__.A、找出任一個答案節點B、找出所有的答案節點C、找出最優的答案節點D、進行遍歷E、使用精確的成本函數c來做LC-檢索F、使用廣度優先檢索G、使用深度優先檢索H、在成本估計函數ê中考慮根節點到當前節點的成本（距離）【正確答案】：CH10.在活動圖中，節點表示項目中各個工作階段的里程碑，連接各個節點的邊表示活動，邊上的

數字表示活動持續的時間。在下面的活動圖中，從A到J的關鍵路徑是__（15）__,關鍵路徑長度是

__（16）__,

圖1-1活動圖ABEGJB、ADFHJC、ACFGJD、ADFIJE、22F、49G、19H、35【正確答案】：BF11.設一個包含N個頂點、E條