軟件設計師考試試題分類精解(第3版)

軟件設計師考試試題分類精解(第3版)

第1章數(shù)據結構與算法

1.1試題精解

l.i.i例題1

例題1(2004年5月試題4)

的特點是數(shù)據結構中元素的存儲地址與其關鍵字之間存在某種映射關系。

A.樹形存儲結構B.鏈式存儲結構

C.索引存儲結構D.散列存儲結構

試題分析

很顯然，這是散列存儲結構。散列存儲結構將節(jié)點按其關鍵字的散列地址存儲到散列表

中。常用的散列函數(shù)有除余法、基數(shù)轉換法、平方取中法、折疊法、移位法和隨機數(shù)法等。

試題答案

D

1.1.2例題2

例題2(2004年5月試題5)

若循環(huán)隊列以數(shù)組Q[0，…，m-1]作為其存儲結構，變量rear表示循環(huán)隊列中隊尾元素

的實際位置，其移動按rear=(rear+1)modm進行，變量length表示當前循環(huán)隊列中

的元素個數(shù)，則循環(huán)隊列的隊首元素的實際位置是______

A.rear-lengthB.(rear-length+m)modm

C.(1+rear+m-length)modmD.m-length

試題分析

其實這種題目在考場上最好的解題方法是找一個實際的例子，往里面一套便知道了。下

面解釋一下原理。因為rear表示的是隊列尾元素的實際位置(注意：不是隊尾指針)。而

且題中有"移動按rear=(rear+1)modm進行”，這說明：隊列存放元素的順序為：

Q[1],Q[2]，…，所以在理想情況下rear-length+1能算出隊首元素的位置，即

當m=8,rear=5,length=2時，rear-length+l=4,4就是正確的隊首元素實際位置。但

rear-length+1有一種情況無法處理，即當m=8,rear=l,length=5時，無法算出。

所以我們在rear+1-length的基礎上加上m再與m求模，以此方法來計算。

試題答案

C

1.1.3例題3

例題3(2004年5月試題6)

一個含有n個頂點和e條邊的簡單無向圖，在其鄰接矩陣存儲結構中共有_____個零元

素。

A.eB.2eC.n2-eD.n2-2e

試題分析

鄰接矩陣反映頂點間鄰接關系，設G=(V,E)是具有n(n?l)個頂點的圖，G的鄰接

矩陣M是一個n行n列的矩陣，并有若(i,j)或<i,j>WE,則M皿j]=l;否則，M[i][j]=O.

由鄰接矩陣的定義可知，無向圖的鄰接矩陣是對稱的，即圖中的一條邊對應鄰接矩陣中

的兩個非零元素。因此，在一個含有n個頂點和e條邊的簡單無向圖的鄰接矩陣中共有

n2-2e個零元素。

試題答案

D

1.1.4例題4

例題4（2004年5月試題7）

若一棵哈夫曼樹共有9個頂點，則其葉子節(jié)點的個數(shù)為.

A.4B.5C.6D.7

試題分析

哈夫曼首先給出了對于給定的葉子數(shù)目及其權值構造最優(yōu)二叉樹的方法,根據這種方法

構造出來的二叉樹稱為哈夫曼樹。具體過程如下所述。

假設有n個權值，則構造出的哈夫曼樹有n個葉子節(jié)點。n個權值分別設為wl,w2，…，

wn,則哈夫曼樹的構造規(guī)則為：

（1）將wl,w2，…，wn看成是有n棵樹的森林（每棵樹僅有一個節(jié)點）.

（2）在森林中選出兩個根節(jié)點的權值最小的樹，作為一棵新樹的左、右子樹，且新樹

的根節(jié)點權值為其左、右子樹根節(jié)點權值之和。

（3）從森林中刪除選取的兩棵樹，并將新樹加入森林。

（4）重復第（2）步和第（3）步，直到森林中只剩一棵樹為止，該樹即為所求的哈夫

曼樹。

從以上構造過程可知，哈夫曼樹是嚴格的二叉樹，沒有度數(shù)為1的分支節(jié)點。設二叉

樹的0度節(jié)點（即葉子節(jié)點）個數(shù)為n0,2度節(jié)點個數(shù)為n2,則樹的總節(jié)點數(shù)n=n0+n2.又

因為二叉樹有性質：對任何一棵二叉樹，如果其葉子節(jié)點數(shù)為n0,度為2的節(jié)點數(shù)為n2廁

n0=n2+l.所以n=n2+l+n2.即9=n2+l+n2,n2=4,n0=5.

試題答案

B

1.1.5例題5

例題5（2004年5月試題8）

若采用鄰接矩陣來存儲簡單有向圖，則其某一個頂點i的入度等于該矩陣。

A.第i行中值為1的元素個數(shù)B.所有值為1的元素總數(shù)

C.第i行及第i列中為1的元素總個數(shù)D.第i列中值為1的元素個數(shù)

試題分析

由鄰接矩陣的定義可知，對于無向圖，其鄰接矩陣第i行元素的和，即頂點i的度。對

于有向圖，其鄰接矩陣的第i行元素之和為頂點i的出度，而鄰接矩陣的第j列元素之和為

頂點j的入度。

試題答案

D

1.1.6例題6

例題6（2004年5月試題9）

在一棵度為3的樹中，有2個度為3的節(jié)點，有1個度為2的節(jié)點，則有_____個度

為0的節(jié)點。

A.4B.5C.6D.7

試題分析

對于彳壬一棵樹，它的總度數(shù)等于節(jié)點數(shù)減1.所以我們可以設此樹的節(jié)點個數(shù)為n,其中

度為3的節(jié)點有n3個，度為2的節(jié)點有n2個，度為1的節(jié)點有nl個，度為0的節(jié)點有

n0個，并設總度數(shù)為k.此時我們可以得到兩個等量關系，一個關于節(jié)點數(shù)量，另一個關于

總度數(shù)：

n=n0+nl+n2+n3=>n=n0+nl+l+2①

k=n0x0+nlxl+n2x2+n3x3=>n-l=nlxl+n2x2+n3x3=>n-l=nl+2+6②

把上面兩式相減得：n0=6

試題答案

C

1.1.7例題7

例題7（2004年5月試題10）

設節(jié)點x和y是二叉樹中任意的兩個節(jié)點，在該二叉樹的先根遍歷序列中x在y之前,

而在其后根遍歷序列中x在y之后,則x和y的關系是o

A.x是y的左兄弟B.x是y的右兄弟

C.x是y的祖先D.x是y的后裔

試題分析

二叉樹的遍歷方法主要有3種。

（1）前序遍歷（先根遍歷，先序遍歷）：首先訪問根節(jié)點，然后按前序遍歷根節(jié)點的

左子樹，再按前序遍歷根節(jié)點的右子樹。

（2）中序遍歷（中根遍歷）：首先按中序遍歷根節(jié)點的左子樹，然后訪問根節(jié)點，再

按中序遍歷根節(jié)點的右子樹。

（3）后序遍歷（后根遍歷，后序遍歷）：首先按后序遍歷根節(jié)點的左子樹，然后按后

序遍歷根節(jié)點的右子樹，再訪問根節(jié)點。

已知在該二叉樹的先根遍歷序列中，x在y之前，則說明x可能是y的父節(jié)點（祖先）

或是y的父節(jié)點的左子樹里的某個節(jié)點。又知在其后根遍歷序列中，x在y之后，則說明x

可能是y的父節(jié)點或是y的父節(jié)點的右子樹里的某個節(jié)點。因此，x只能是y的父節(jié)點。

試題答案

C

1.1.8例題8

例題8(2004年5月試題11)

設順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表

采用I順序查找方法來確定子塊，且在確定的子塊中也采用順序查找方法，則在等概率的情況

下，分塊查找的平均查找長度為。

A.21B.23C.41D.62

試題分析

分塊查找又稱索引順序查找。它是一種性能介于順序查找和二分查找之間的查找方法。

二分查找表由分塊有序的線性表和索引表組成。表R[1，…，川均分為b塊，前bl塊中節(jié)點

個數(shù)為s[n/b],第b塊的節(jié)點數(shù)允許小于等于s;每一塊中的關鍵字不一定有序，但前一塊中

的最大關鍵字必須小于后一塊中的最小關鍵字，即表是分塊有序的。

抽取各塊中的最大關鍵字及其起始位置構成一個索引表ID[I，…，b],ID[i](lib)中存放

第i塊的最大關鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是

一個遞增有序表。

分塊查找的基本思想是：索引表是有序表，可采用二分查找或順序查找，以確定待查的

節(jié)點在哪一塊。

由于塊內無序，只能用M頁序查找。分塊查找是兩次查找過程。整個查找過程的平均查找

長度是兩次查找的平均查找長度之和。如果以二分查找來確定塊，則分塊查找成功時的平均

查找長度為ASLIIog2(bl)1(si)/2?log2(n/sl)s/2;如果以順序查找確定塊,

分塊查找成功時的平均查找長度為ASL2(bl)/2(si)/2(s22sn)/(2s)。

在本題中，nl23,b3,s41,因此平均查找長度為(4141241123)/(241)23。

試題答案

B

1.1.9例題9

例題9（2004年5月試題14）

已知有一維數(shù)組A[0，…，m=n-l],若要對應為m行、n列的矩陣，則下面的對應關系

可將元素A[k]（0=k<m=n）表示成矩陣的第i行、第j列的元素（0=i<m,0=j<n）。

A.i=k/n,j=k%mB.i=k/m,j=k%m

C.i=k/n,j=k%nD.i=k/m,j=k%n

試題分析

本題其實就是求一個一維數(shù)組A[m?n]向二維數(shù)組的轉化問題，最原始的方法

就是把A數(shù)組的前n個元素放到B數(shù)組的第一行中，A數(shù)組的第n個元素放到B數(shù)組的第

二行中，依次類推，A數(shù)組的最后n個元素放到B數(shù)組的最后一行中。

要求A[k]在B數(shù)組中的位置，首先確定A[k]處在哪一行，根據上面的存放方法，顯然,

應該是k/n行。然后再確定處在k/n行的哪一列，顯然是k%n（"％”表示模運算）。

試題答案

C

1.1.10例題10

例題10（2004年5月試題64,65）

類比二分搜索算法，設計k分搜索（k為大于2的整數(shù)）如下：首先檢查n/k處（n為

被搜索集合的元素個數(shù)）的元素是否等于要搜索的值，然后檢查2n/k處的元素，……依次

類推，或者找到要搜索的元素，或者把集合縮小到原來的1/k;如果未找到要搜索的元素，

則繼續(xù)在得到的集合上進行k分搜索；如此進行，直至找到要搜索的元素或搜索失敗。此k

分搜索算法在最壞情況下搜索成功的時間復雜度為（64），在最好情況下搜索失敗的時間

復雜度為（65）.

(64)A.O(logn)B.O(nlogn)C.O(logkn)D.O(nlogkn)

(65)A.O(logn)B.O(nlogn)C.O(logkn)D.O(nlogkn)

試題分析

與二分法查找類似，k分查找法可用k叉樹來描述。k分查找法在查找成功時進行比較

的關鍵字個數(shù)最多不超過樹的深度，而具有n個節(jié)點的k叉樹的深度為[logk雙卜-1)」+1

所以，k分查找法在查找成功時和給定值進行比較的關鍵字個數(shù)至多為口咤仃(卜-1)」+1，，

即時間復雜度為0(logkn).同時，k分查找法在查找不成功時，和給定值進行比較的關

鍵字個數(shù)也至多為]1咤5(卜-1)」+1：,即時間復雜度為。(logkn)。

試題答案

(64)C(65)C

1.1.11例題U

例題11(2004年11月試題33)

在一棵完全二叉樹中其根的序號為1____可判定序號為p和q的兩個節(jié)點是否在同

一層。

A[10g2^J=[10g29JB.l°g2P=10g29

c[Iog2/?J+1=[log2q\D[log2^J=[log2q\+l

試題分析

完全二叉樹的性質是，具有n個節(jié)點的完全二叉樹的深度為U°g2封+1.判定序號為p

和q的兩個接點是否在同一層，即求U°g2句+『L10g2+1是否成立。所以A為所求的結

果。

試題答案

A

1.1.12例題12

例題12(2004年11月試題34)

堆是一種數(shù)據結構______是堆。

A.(10,50,80,30,60,20,15,18)

B.(10,18,15,20,50,80,30,60)

C.(10,15,18,50,80,30,60,20)

D.(10,30,60,20,15,18,50,80)

試題分析

堆排序定義如下：n個元素的序列｛kl,k2，…，kn｝當且僅當滿足以下關系時，稱之為堆。

產”了(小頂堆)或者卜金(大頂堆)

隰”?2i+l［收..也加

在本題中，我們可以將對應的一維數(shù)組看作一棵完全二叉樹，如

(10,18,15,20,50,80,30,60)轉換為二叉樹,如圖1-1所示。

圖1-1序列轉換后的二叉樹

我們發(fā)現(xiàn)該序列滿足堆的含義，即完全二叉樹中所有^終端節(jié)點的值均不大于(或者不

小于)其左、右孩子節(jié)點的值。其他序列不滿足此定義。

試題答案

B

1.1.13例題13

例題13（2004年11月試題35）

從二叉樹的任一節(jié)點出發(fā)到根的路徑上，所經過的節(jié)點序列必須按其關鍵字降序排列。

A.二叉排序樹B.大頂堆C.小頂堆D.平衡二叉樹

試題分析

當為小頂堆時，任意一棵子樹的根點比其左、右子節(jié)點要小，所以從任一節(jié)點出發(fā)到根

的路徑上，所經過的節(jié)點序列必須按其關鍵字降序排列。

試題答案

C

1.1.14例題14

例題14（2004年11月試題36）

若廣義表L=（（1,2,3）），則L的長度和深度分別為.

A.1和1B.1和2C.1和3D.2和2

試題分析

廣義表記做LS=（al,a2，…，an）其中LS是廣義表名，n是它的長度。在廣義表中，

嵌套括號的層數(shù)為其深度，所以L深度為2.

試題答案

B

1.1.15例題15

例題15（2004年11月試題37）

若對27個元素只進行三趟多路歸并排序，則選取的歸并路數(shù)為

A.2B.3C.4D.5

試題分析

歸并就是將兩個或兩個以上的有序表組合成一個新的有序表。本題有三趟歸并，每次歸

并X個有序表,第一趟27個元素歸并后，剩余27/x個表，歸并2次后剩余27/(x2)個

表，歸并3次后剩余27/(x3)個表。這時候27/(x3)=1,求得x=3。

試題答案

B

1.1.16例題16

例題16(2004年11月試題52)

采用動態(tài)規(guī)劃策略求解問題的顯著特征是滿足最優(yōu)性原理，其含義是_____。

A.當前所出的決策不會影響后面的決策

B.原問題的最優(yōu)解包含其子問題的最優(yōu)解

C.問題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解

D.每次決策必須是當前看來的最優(yōu)決策才可以找到最優(yōu)解

試題分析

動態(tài)規(guī)劃(DynamicProgramming):運籌學的一個分支，是求解決策過程(Decision

Process)最優(yōu)化的數(shù)學方法。美國數(shù)學家R.E.Bellman等人在研究多階段決策過程

(MultistepDecisionProcess)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(Principleof

Optimality)，把多階段過程轉化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)

化問題的新方法一動態(tài)規(guī)劃。

最優(yōu)性原理：動態(tài)規(guī)劃的理論基礎是最優(yōu)性原理，它認為整個過程的最優(yōu)策略有這樣的

特點，即無論過去的狀態(tài)和決策如何。對于前面的決策所形成的狀態(tài)而言，余下的諸決策必

定構成最優(yōu)策略。這就是說，任何一個完整的最優(yōu)策略的子策略總是最優(yōu)的。

設計動態(tài)規(guī)劃法的步驟：

（1）找出最優(yōu)解的性質，并刻畫其結構特征。

（2）遞歸地定義最優(yōu)值（寫出動態(tài)規(guī)劃方程）。

（3）以自底向上的方式計算出最優(yōu)值。

（4）根據計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。

步驟（1）~（3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）

可以省略，步驟（3）中記錄的信息也較少；若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步

驟（4）,步驟（3）中記錄的信息必須足夠多，以便構造最優(yōu)解。

動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質。

最優(yōu)子結構：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結構性

質。

重疊子問題：在用遞歸算法自頂向下解問題時,每次產生的子問題并不總是新問題,有

些子問題被反復計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質，對每一個子問

題只解一次，而后將其解保存在一個表格中，以后盡可能多地利用這些子問題的解。

試題答案

B

1.1.17例題17

例題17（2004年11月試題54）

下面的程序段違反了算法的原則。

voidsam（）

（

intn=2

while(!odd(n))n+=2;

printf(n);

)

A.有窮性B確定性C.可行性D.健壯性

試題分析

由于n的初始值為2,語句"while(!odd(n))n+=21無論循環(huán)多少步,n都不能

為奇數(shù)，所以循環(huán)無法終止，違背了算法的有窮性。

試題答案

A

1.1.18例題18

例題18(2004年11月試題55)

拉斯維加斯(LasVegas)算法是一種常用的_____算法。

A.確定性B.近似C.概率D加密

試題分析

此題主要考查基本概率算法，我們來了解一下到底什么樣的算法是概率算法。

概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得

到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。

(因此特征，我們就可以非除哈夫曼編碼算法，因為哈夫曼編碼是一種確定的方法。)一般

情況下，可將概率算法大致分為4類：數(shù)值概率算法、蒙特卡羅(MonteCarlo)算法、拉

斯維加斯(LasVegas)算法和舍伍德(Sherwood)算法。

數(shù)值概率算法常用于數(shù)值問題的求解。這類算法所得到的往往是近似解，而且近似解的

精度隨計算時間的增加不斷提高。在許多情況下，要計算出問題的精確解是不可能或沒有必

要的，因此用數(shù)值概率算法可得到相當滿意的解。

蒙特卡羅算法用于求問題的準確解。對于許多問題來說，近彳以解毫無意義。例如，一個

判定問題其解為"是“或"否"，二者必居其一，不存在任何近似解答。又如，我們要求一個整數(shù)

的因子時所給出的解答必須是準確的，一個整數(shù)的近似因子沒有任何意義。用蒙特卡羅算法

能求得問題的一個解，但這個解未必是正確的。求得正確解的概率依賴于算法所用的時間。

算法所用的時間越多，得到正確解的概率就越高。蒙特卡羅算法的主要缺點就在于此。一般

情況下，無法有效判斷得到的解是否肯定正確。

拉斯維加斯算法不會得到不正確的解，一旦用拉斯維加斯算法找到一個解，那么這個解

肯定是正確的。但是有時候用拉斯維加斯算法可能找不到解。與蒙特卡羅算法類似。拉斯維

加斯算法得到正確解的概率隨著它用的計算時間的增加而提高。對于所求解問題的任一實

例，用同一拉斯維加斯算法反復對該實例求解足夠多次，可使求解失效的概率任意小。

舍伍德算法總能求得問題的一個解，且所求得的解總是正確的。當一個確定性算法在最

壞情況下的計算復雜性與其在平均情況下的計算復雜性有較大差別時，可以在這個確定算法

中引入隨機性將它改造成一個舍伍德算法，消除或減少問題的好壞實例間的這種差別。舍伍

德算法精髓不是避免算法的最壞情況行為，而是設法消除這種最壞行為與特定實例之間的關

聯(lián)性。

試題答案

C

1.1.19例題19

例題19（2004年11月試題56）

在分支-界限算法設計策略中，通常采用_____搜索問題的解空間。

A.深度優(yōu)先B.廣度優(yōu)先C啟底向上D.拓撲排序

試題分析

在分支-界限算法設計策略中，通常采用廣度優(yōu)先搜索問題的解空間。

試題答案

B

1.1.20例題20

例題20(2004年11月試題57,58)

在下列算法設計方法中，(57)在求解問題的過程中并不從整體最優(yōu)上加以考慮，

而是做出在當前看來是最好的選擇。利用該設計方法可以解決(58)問題。

(57)A.分治法B.貪心法C動態(tài)規(guī)劃法D.回溯法

(58)A.排序B.檢索C.背包_____D.0/1背包

試題分析

貪心法是這樣的一種解題方法：逐步給出解的各部分，在每一步“貪婪地”選擇最好的部

分解，但不顧及這樣選擇對整體的影響，因此一般地得到的不是最好的解。

解決背包問題：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物

品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。

較高效率地解決背包問題一般用遞歸和貪心算法，而背包問題規(guī)模不是很大時，也可采

用窮舉法。

試題答案

(57)B(58)C

1.1.21例題21

例題21(2004年11月試題59,60)

以關鍵字比較為基礎的排序算法在最壞情況下的計算時間下界為O(nlog2n)。在下

面的排序算法中，最壞情況下計算時間可以達到0(nlog2n)的是(59),該算法采用的

設計方法是(60)。

(59)A.歸并算法B.插入算法C.隨算法D.冒泡算法

(60)A.分治法B.貪心法C.動態(tài)規(guī)劃法D.回溯法

試題分析

對照表1-3,我們可知歸并算法在最壞情況下的計算時間可達到。(nlog2n)。設歸并

排序的當前區(qū)間是R[low,...,high],分治法的三個步驟是：

(1)分解。將當前區(qū)間一分為二，即求分裂點。

(2)求解。遞歸地對兩個子區(qū)間R[low,...,mid]和R[mid+1，…，high]進行歸并排序。

(3)組合。將已排序的兩個子區(qū)間R[low,...,mid]和R[mid+1，…，high]歸并為一個

有序的區(qū)間R[low,...,high].

遞歸的終結條件：子區(qū)間長度為1(一個記錄自然有序)。

試題答案

(59)A(60)A

1.1.22例題22

例題22(2005年5月試題38)

循環(huán)鏈表的主要優(yōu)點是____?

A.不再需要頭指針了

B.已知某個節(jié)點的位置后，能很容易找到它的直接前驅節(jié)點

C.在進行刪除操作后，能保證鏈表不斷開

D.從表中任一節(jié)點出發(fā)都能遍歷整個鏈表

試題分析

此題考查循環(huán)鏈表的基礎知識，所以我們來了解一下什么是循環(huán)鏈表，一個帶頭節(jié)點的

線性鏈表如圖1-2所示。

X-T"1T~~1-|—II-HdlA.

圖1-2帶頭節(jié)點的線性鏈表

若將此鏈表的最后一個節(jié)點d的next域指向頭，則產生了循環(huán)鏈表，如圖1-3所示。

-

M1d—-|-4~I-1-*--4~_I~\

圖1-3循環(huán)鏈表

實現(xiàn)循環(huán)鏈表的類型定義與線性鏈表完全相同，它的所有操作也都與線性鏈表類似。只

是判斷鏈表結束的條件有所不同。對照圖1-6,我們現(xiàn)在來分析題目的備選答案。選項A"不

再需要頭指針了"，言下之意就是線性鏈表一定需要頭指針，但實際上不管是線性鏈表還是循

環(huán)鏈表，頭指針都是可要可不要的，所以選項A錯誤。再來看B選項，■已知某個節(jié)點的位

置后，能很容易找到它的直接前驅節(jié)點”，題目中只說是循環(huán)鏈表，沒有說是雙向的循環(huán)鏈表。

在單向循環(huán)鏈表中，已知某個節(jié)點的位置很難得到它的直接前驅節(jié)點，所以不對。接著看C

選項，"在進行刪除操作后，能保證鏈表不斷開"，在線性鏈表中也能滿足這個要求，所以不

能算作循環(huán)鏈表的主要優(yōu)點，也不正確。其實到這里我們已經可以知道答案為D了，但我

們還是看看D到底對不對。D選項是這樣的："從表中任一節(jié)點出發(fā)都能遍歷整個鏈表”.我

們首先看看在線性鏈表中，是否能滿足這個要求。以線性鏈表中c為例，c只能往向走到

d,然后d的next域為空，無路可走，所以線性鏈表無法滿足這個要求。再看循環(huán)鏈表，無

論從哪一點出發(fā)，都可以到達任一節(jié)點，因為所有的節(jié)點圍成了一個圈。所以此題的正確答

案為D.

試題答案

D

1.1.23例題23

例題23(2005年5月試題39)

表達式a*(b+c)-d的后綴表達式為.

A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd

試題分析

題目要求根據已知的表達式寫對應的后綴表達式。解這種題,如果你知道前綴、中綴、

后綴表達式有何關聯(lián)，有什么特點,解題就非常輕松。其實前綴、中綴、后綴的得名是從二

叉樹來的，也就是把一個表達式轉化為一棵二叉樹后，對二叉樹進行前序遍歷得到前綴表達

式，對二叉樹進行中序遍歷得到中序表達式(也就是一般形式的表達式)，對二叉樹進行后

序遍歷得到后綴表達式。所以這里我們只要把表達式轉成樹的形式，再對二叉樹進行后序遍

歷，即可得到正確答案。但現(xiàn)在最主要的問題是如何構造這棵樹。構造的規(guī)則是這樣的：所

有的操作數(shù)只能在葉子節(jié)點上，操作符是它們的根節(jié)點，括號不構造到二叉樹當中去，構造

樹的順序要遵循運算的順序。在表達式a*(b+c)-d中最先計算b+c,所以先構造圖1-4的

部分。

然后把b+c的結果與a進行運算，有如圖1-5所示的結果。

圖1-4第一步圖1-5第二步

接著把運算結果和d相減，最終得到的二叉樹如圖1-6所示。

圖1-6最終得到的二叉樹

對此樹進行后序遍歷得到序列：abc+*d-,所以正確答案是B.

試題答案

B

1.1.24例題24

例題24（2005年5月試題40）

若二叉樹的先序遍歷序列為ABDECF,中序遍歷序列為DBEAFC則其后序遍歷序列為

A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA

試題分析

此題要求根據二叉樹的先序遍歷和中序遍歷求后序遍歷。我們可以根據這棵二叉樹的先

序和中序遍歷畫出這棵二叉樹。

根據先序和中序來構造二叉樹的規(guī)則是這樣的：首先看先序，先序遍歷中第一個訪問的

節(jié)點是A,這說明A是二叉樹的根節(jié)點（因為先序遍歷順序是：根、左、右）。然后看中序,

中序中A前面有節(jié)點D,B,E,后面有節(jié)點F,C.這說明D,B,E是A的左子樹,F,C是A的右子樹。

我們再回到先序遍歷中看D,B,E的排列［II頁序（此時可以不看其他節(jié)點），我們發(fā)現(xiàn)在先序中

B排在最前，所以B是A左子樹的根節(jié)點。接下來又回到了中序，中序中D在B前面，E

在B后面，所以D是B的左子樹，E是B的右子樹。依此規(guī)則可構造二叉樹，如圖1-7所

示。然后對這棵二叉樹進行后序遍歷得到DEBFCA.

試題答案

D

1.1.25例題25

例題25(2005年5月試題41)

無向圖中一個頂點的度是指圖中.

A.通過該頂點的簡單路徑數(shù)B.通過該頂點的回路數(shù)

C.與該頂點相鄰的頂點數(shù)D.與該頂點連通的頂點數(shù)

試題分析

此題是純概念題。

(1)無向圖中頂點V的度(Degree)。

無向圖中頂點V的度是關聯(lián)于該頂點的邊的數(shù)目，也可以說是直接與該頂點相鄰的頂

點個數(shù)，記為D(V)。

例如，在圖1-8中，VI的度為LV2的度為2,V3的度為3,V4的度為2.

(2)有向圖頂點V的入度(InDegree)。

有向圖中，以頂點V為終點的邊的數(shù)目稱為V的入度，記為ID(V)。

0?

圖1-8無向圖示例圖1-9有向圖示例1

例如，在圖1-9中,VI的入度為LV2的入度為2,V3的入度為1,V4的入度為0.

(3)有向圖頂點V的出度(OutDegree)

有向圖中，以頂點V為始點的邊的數(shù)目，稱為V的出度，記為0D(V)。

例如，在圖1-10中，VI的出度為0,V2的出度為0,V3的出度為2,V4的出度也_____

為2.

試題答案

C

1.1.26例題26

例題26(2005年5月試題42)

利用逐點插入法建立序列(50,72,43,85,75,20,35,45,65,30)對應的二叉排序樹以后，

查找元素30要進行次元素間的b匕較。

A.4B.5C.6D.7

試題分析

首先，我們對給出的節(jié)點建立排序二叉樹，如圖1-11所示。

50

4372

?

圖1-11排序二叉樹

圖1-11中我們可以看出，30首先要與50比較，30<50,所以進入節(jié)點50的左子樹；

接著與43比較，結果30<43,所以進入節(jié)點43的左子樹；然后與20比較，30>20,所以進

入節(jié)點20的右子樹；再和35比較，30<35,所以進入節(jié)點35的左子樹；最后與30上徽,

結果相等，查找結束。所以此查找過程要進行5次比較。

試題答案

B

1.1.27例題27

例題27(2005年5月試題48)

在常用的描述二叉排序樹的存儲結構中，關鍵字值最大的節(jié)點.

A.左指針一定為空B.右指針一定為空

C.左、右指針均為空D.左、右指針均不為空

試題分析

我們來分析一下二叉排序樹關鍵字值最大的節(jié)點的存儲位置有何特點。以序列

(50,72,43,85,75,20,35,45,65,30)為例，最大節(jié)點85的位置有兩種情形,分別如圖1-12

和圖1-13所示。

圖1-12情形之一圖1-13情形之二

在這兩種情形中，85都沒有右子樹，因為只有比85更大的節(jié)點，才能成為它的右子

樹，而85是這里最大的節(jié)點，不可能有右子樹，所以85的右指針一定為空。

試題答案

B

1.1.28例題28

例題28(2005年5月試題49)

一個具有n(n>0)個頂點的連通無向圖至少有條邊。

2

A.n+1B.nC.D.n-1

試題分析

在無向圖中如果任意兩點是可達的，則我們稱其為連通無向圖。要把這n個頂點連通,

我們可以讓一個頂點向其他所有頂點連一條邊，這樣需要n-1條邊，如圖1-14所示。

圖1-14一個頂點向其他所有頂點連一條邊

此外，我們還可以讓這n個頂點首尾相接，這樣也需要n-1條邊，如圖1-15所示。

??~~?-------0

圖1-15n個頂點首尾相接

所以至少需要n-1條邊。

試題答案

D

1.1.29例題29

例題29(2005年5月試題50)

由權值為9,2,5,7的4個葉子節(jié)點構造一棵哈夫曼樹，該樹的帶權路徑長度為

A.23B.37C.44D.46

試題分析

首先構造這棵哈夫曼樹，如圖1-16所示。

圖1-16哈夫曼樹

帶權路徑長度為：9+7x2+(2+5)x3=44.

試題答案

C

1.1.30例題30

例題30(2005年5月試題51)

在最好和最壞情況下的時間復雜度均為O(nlog2n)且穩(wěn)定的排序方法是.

A.基數(shù)排序B.快速排序C.堆排序D.歸押￡序

試題分析

此題考查對^序算法時間復雜度的掌握程度，以及對穩(wěn)定排序概念的理解。排序算法的

時間復雜度要靠理解和記憶，穩(wěn)定排序算法是指在排序過程中兩個排序關鍵字相同的元素,

在排序的過程中位置不發(fā)生變化，即對數(shù)列62,42,12,36,4,12,67進行排序時，第—12

在排序完畢以后要排在第二個12的前面，這就是穩(wěn)定的排序。有些人可能會發(fā)出疑問：既

然都是12,為什么一定要保證它的順序呢？舉一個簡單的例子如果組織一次有獎答題活動,

選手在電腦上答完題后直接提交數(shù)據，最后按答題得分獎勵前100名參賽選手。這樣會出

現(xiàn)一個問題，即如果同時有10個人并列第100名，而我們只能給一個人發(fā)獎，到底給誰發(fā)

呢？最合理的判斷標準是給先提交答案的人發(fā)獎，這樣穩(wěn)定排序就可以用上了。

下面用排除法來解答此題。題目給出的4個選項中快速排序和堆排序都是不穩(wěn)定的排

序算法，所以排除。再看基數(shù)排序，我們知道基數(shù)排序的最壞時間復雜度為。(d(n+rd))

所以正確答案應是答案D,歸并排序。

試題答案

D

1.1.31例題31

例題31(2005年5月試題50)

已知一個線性表(38,25,74,63,52,48)，假定采用散列函數(shù)h(key)=key%7計

算散列地址，并散列存儲在散列表A[0，…，6]中，若采用線性探測方法解決沖突，則在該散

列表上進行等概率成功查找的平均查找長度為.

A.1.5B.1.7C,2.0D.2.3

試題分析

要計算散列表上的平均查找長度，我們首先必須知道在建立這個散列表時，每個數(shù)據存

儲時進行了幾次散列。這樣就知道哪一個元素的查找長度是多少。散列表的填表過程如下：

首先存入第1個元素38,由于h(38)=38%7=3,又因為3號單元現(xiàn)在沒有數(shù)據，所

以把38存入3號單元，如圖1-17所示。

0123456

38

圖1-17第1步

接著存入第2個元素25,由于h(25)=25%7=4,又因為4號單元現(xiàn)在沒有數(shù)據，所

以把25存入4號單元，如圖1-18所示。

0123456

3825

圖1-18第2步

接著存入第3個元素74,由于h(74)=74%7=4,此時的4號單元已經被25占據，

所以進行線性再散列，線性再散列的公式為：Hi=(H(key)+di)%m,其中的di=l,2,3,4，……

所以Hl=(4+1)%7=5,此時的單元5沒有存數(shù)據，所以把74存入到5號單元。如圖

1-19所示。

0123456

382574

圖1-19第3步

接著存入第4個元素63,由于h(63)=63%7=0,此時的0號單元沒有數(shù)據，所以把

63存入0號單元，如圖1-20所示。

0123456

63382574

圖1-20第4步

接著存入第5個元素52,由于h(52)=52%7=3,此時的3號單元已被38占據，所

以進行線性再散列：Hl=(3+1)%7=4,但4號單元也被占據了，所以再次散列：H2=

(3+2)%7=5,但5號單元也被占據了，所以再次散列：H3=(3+3)%7=6,6號單元為

空，所以把52存入6號單元，如圖1-21所示。

0123456

6338257452

圖1-21第5步

最后存入第6個元素48,由于h(48)=48%7=6,此時的6號單元已被占據，所以進

行線性再散列：H1=(6+1)%7=0,但0號單元也被占據了，所以再次散列：H2=(6+2)%

7=1,1號單元為空，所以把48存入1號單元，如圖1-22所示。

圖1-22第6步

如果T元素存入時，進行了N次散歹(J,相應的查找次數(shù)也是N,所以38,25,63這三

個元素的查找長度為L74的查找長度為2,48的查找長度為3,52的查找長度為4.平均查找

長度為：(1+1+1+2+3+4)/6=2。

試題答案

C

1.1.32例題32

例題32(2005年5月試題53,54)

為在狀態(tài)空間樹中(53)可以利用LC-檢索(LeastCostSearch)快速找到f答

案節(jié)點。在進行LC-檢索時，為避免算法過分偏向于縱深檢查，應該(54).

(53)A.找出任■/答案節(jié)點B.找出所有的答案節(jié)點

C.找出最優(yōu)的答案節(jié)點D.進行遍歷

(54)A.使用精確的成本函數(shù)c(x)來做LC-檢索

B.使用廣度優(yōu)先檢索

C.使用深度優(yōu)先檢索

D.在成本估計函數(shù)6(x)中考慮根節(jié)點到當前節(jié)點的成本(距離)

試題分析

LC-檢索是分支限界法中的一種檢索方法。分支限界法類似于回溯法，是在問題的解空

間樹上搜索問題解的算法。一般情況下分支限界法和回溯法的求解目標不同?；厮莘ǖ那蠼?/p>

目標是找出解空間樹中滿足約束條件的所有解而分支限界法的求解目標則是找出滿足約束

條件的一個解，或在滿足約束條件的解中找出使某一目標函數(shù)值達到極大或極小的解，即在

某種意義下的最優(yōu)解。所以(53)應是C找出最優(yōu)的答案節(jié)點。

分支限界法中，對問題空間樹檢索的方法有兩種：廣度優(yōu)先和最小耗費優(yōu)先。在LC-

檢索中為了避免算法過分偏向于縱深檢查，提出了改進成本估計函數(shù)c(x),使其不只是

考慮節(jié)點X到一個答案節(jié)點的估計成本，還應考慮由根節(jié)點到節(jié)點X的成本h(X)。

試題答案

(53)C(54)D

1.1.33例題33

例題33(2005年5月試題55)

以比較為基礎的排序算法在最壞情況下的計算時間下界為.

A.0(n)B.0(n2)C.O(Iog2n)D.O(nlog2n)

試題分析

此題求基礎的排序算法在最壞情況下的計算時間下界。由于下界的含義是最小值，而時

間復雜度的值最小，表1-3是常用排序算法的時間復雜度比較表，從表中可以看出，最壞

情況下的最好時間復雜度為：o(nlog2n)。

試題答案

D

1.1.34例題34

例題34(2005年5月試題56)

利用動態(tài)規(guī)劃方法求解每對節(jié)點之間的最短路徑問題(allpairsshortestpath

problem)時，設有向圖G=<V,E>共有n個節(jié)點，節(jié)點編號l~n，設C是G的成本鄰接矩

陣，Dk(i,j)即為圖G中節(jié)點i到j并且不經過編號比k還大的節(jié)點的最短路徑的長度(Dn

(i,j)即為圖G中節(jié)點i至!Ij的最短路徑長度)，則求解該問題的遞推關系式為.

A.Dk(i,j)=Dk-l(i,j)+C(ij)

B.Dk(i,j)=min{Dk-l(i,j),Dk-1(i,j)+C(ij)}

C.Dk(i,j)=Dk-l(i,k)+Dk-1(k,j)

D.Dk(ij)=min{Dk-l(ij),Dk-1(i,k)+Dk-1(kJ)}

試題分析

在題目中有說明：”Dk(ij)即為圖G中節(jié)點i至I」j并且不經過編號比k還大的節(jié)點的

最短路徑的長度”.此句給我們一個提示，在求i,j之間最短路徑的時候，會考慮它經過哪些節(jié)

點會縮短原來的路徑。在Dk(i,j)=min{Dk-l(ij),Dk-1(i,k)+Dk-1(k,j)}中,Dk-1

(ij)表示i到j不經過k的路徑長度，而Dk-1(i,k)+Dk-1(k,j)表示i到j經過k的路

徑長度，且min()函數(shù)用于找最小值，所以此式正確。

試題答案

D

1.1.35例題35

例題35(2005年11月試題16~18)

在活動圖中，節(jié)點表示項目中各個工作階段的里程碑，連接各個節(jié)點的邊表示活動，邊

上的數(shù)字表示活動持續(xù)的時間。在下面的活動圖中,從A至!|J的關鍵路徑是(16)，關鍵

路徑長度是,從開始的活動啟動的最早時間是

(17)E(18)0

圖1-23例題35圖

(16)A.ABEGJB.ADFHJC.ACFGJD.ADFIJ

(17)A.22B.49C.19D.35

(18)A.10B.12C.13D.15

試題分析

根據題意可知，這是一個AOE網，可能是出題者忘記在邊上加上箭頭了，但這不影響

做題。關鍵路徑就是從源點到匯點權和最大的那條路徑，顯然ADFHJ是關鍵路徑，長為49.

某活動的最早開始時間是從源點到該活動對應點的最長路徑的長度，顯然E啟動的最早

時間是3+10=13.

試題答案

(16)B(17)B(18)C

1.1.36例題36

例題36(2005年11月試題38)

已知某二叉樹的中序、層序序列分別為DBAFCE.FDEBCA廁該二叉樹的后序序列為

A.BCDEAFB.ABDCEFC.DBACEFD.DABECF

試題分析

平時已知二叉樹的中序和后序求前序或已知前序和中序求后序的題出現(xiàn)得比較多。像本

題已知中序和層序求后序的題非常少見，但解法是相同的。我們現(xiàn)在來看試題，由于層序是

從根節(jié)點開始逐層向下訪問，所以最開始訪問的節(jié)點為樹的根節(jié)點，此題層序為：FDEBCA,

所以F為根節(jié)點，再看中序DBAFCE,由于F是根節(jié)點，中序的遍歷次序為：左、根、右，

所以DBA是左子樹節(jié)