軟件水平考試中級軟件設(shè)計師上午基礎(chǔ)知識歷年真題試卷匯編1-真題(含答案與解析)-交互

軟件水平考試（中級）軟件設(shè)計師上午（基礎(chǔ)知識）歷年真題試卷匯編1(總分70,做題時間90分鐘)1.選擇題選擇題（）下列各題A、B、C、D四個選項(xiàng)中，只有一個選項(xiàng)是正確的，請將此選項(xiàng)涂寫在答題卡相應(yīng)位置上，答在試卷上不得分。1.

采用順序表和單鏈表存儲長度為n的線性序列，根據(jù)序號查找元素，其時間復(fù)雜度分別為(51)。A

0(1)、0(1)B

0(1)、0(n)C

0(n)、0(1)D

0(n)、0(n)

分值:2答案:B解析：順序表存儲位置是相鄰連續(xù)的，可以隨即訪問的一種數(shù)據(jù)結(jié)構(gòu)，一個順序表在使用前必須指定起長度，一旦分配內(nèi)存，則在使用中不可以動態(tài)的更改。他的優(yōu)點(diǎn)是訪問數(shù)據(jù)是比較方便，可以隨即的訪問表中的任何一個數(shù)據(jù)。鏈表是通過指針來描述元素關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)，他可以是物理地址不連續(xù)的物理空間。不能隨即訪問鏈表元素，必須從表頭開始，一步一步搜索元素。它的優(yōu)點(diǎn)是：對于數(shù)組，可以動態(tài)的改變數(shù)據(jù)的長度，分配物理空間。因此兩者的查找復(fù)雜度就顯而易見了。2.

設(shè)元素序列a、b、c、d、e、f經(jīng)過初始為空的棧S后，得到出棧序列cedfba，則棧S的最小容量為(52)。A

3B

4C

5D

6

分值:2答案:B解析：此題考查棧的用法，根據(jù)題中出棧的順序，當(dāng)元素c出棧后，棧中有元素a、b，當(dāng)元素e出棧之前，棧中有元素a、b、d、e，此時棧中的元素達(dá)到最多。因此棧S最小容量為4。3.

輸出受限的雙端隊(duì)列是指元素可以從隊(duì)列的兩端輸入、但只能從隊(duì)列的一端輸出，如圖8—1所示。若有e1、e2、e3、e4依次進(jìn)入輸出受限的雙端隊(duì)列，則得不到輸出隊(duì)列(53)。A

e4、e3、e2、e1B

e4、e2、e1、e3C

e4、e3、e1、e2D

e4、e2、e3、e1

分值:2答案:D解析：此題考查隊(duì)列的性質(zhì)，隊(duì)列為先進(jìn)先出的線性結(jié)構(gòu)，題中給出的受限的雙端隊(duì)列，兩端都可以進(jìn)，而一端可出，假設(shè)分a和b端，b端可以進(jìn)出，由D選項(xiàng)的出序列，可以看出e1、e2、e3按順序從a端進(jìn)入，而e4從b端進(jìn)入，當(dāng)e4從b端出來之后，無法將后面的e2出隊(duì)列，故D選項(xiàng)有誤。4.

以下關(guān)于線性表存儲結(jié)構(gòu)的敘述，正確的是(57)。A

線性表采用順序存儲結(jié)構(gòu)時，訪問表中任意一個指定序號元素的時間復(fù)雜度為常量級B

線性表采用順序存儲結(jié)構(gòu)時，在表中任意位置插入新元素的運(yùn)算時間復(fù)雜度為常量級C

線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，訪問表中任意一個指定序號元素的時間復(fù)雜度為常量級D

線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，在表中任意位置插入新元素的運(yùn)算時間復(fù)雜度為常量級

分值:2答案:A解析：順序存儲結(jié)構(gòu)可以隨機(jī)存取，時間復(fù)雜度最低為常量級的，答案選A。5.

設(shè)循環(huán)隊(duì)列Q的定義中有front和size兩個域變量，其中front表示隊(duì)頭元素的指針，size表示隊(duì)列的長度，如圖8．2所示(隊(duì)列長度為3，隊(duì)頭元素為X、隊(duì)尾元素為z)。設(shè)隊(duì)列的存儲空間容量為M，則隊(duì)尾元素的指針為(58)。A

(Q．front+Q．size一1)B

(Q．front+Q．size—1+M)％MC

(Q．front—Q．size)D

(Q．front—Q．size+M)％M

分值:2答案:B解析：考慮到循環(huán)，會對M進(jìn)行求模，元素的指針從0開始到M一1，所以隊(duì)尾元素指針為答案B。6.

在字符串的模式匹配過程中，如果模式串的每個字符依次和主串中的一個連續(xù)的字符序列相等，則成為匹配成功。如果不能在主串中找到與模式串相同的子串，則稱為匹配失敗。在布魯特一福斯模式匹配算法(樸素的或基本的模式匹配)中，若主串和模式串的長度分別為n和m(且n遠(yuǎn)大于m)，且恰好在主串末尾的n個字符處匹配成功，則在上述的模式匹配過程中，字符的比較次數(shù)最多為(57)。A

n*mB

(n—m+1)*mC

(n—m一1)*mD

(n—m)*n

分值:2答案:B解析：在最壞的情況下，每一趟不成功的匹配都是模式串的最后一個字符與主串中相應(yīng)的字符不相等，則主串中新一趟的起始位置為i—m+2。若從主串的第i個字符開始匹配時成功，則前i趟不成功的匹配中，每趟都比較了m次，總共比較了i*m次，第i+1趟的成功匹配也比較了m次。因此，在本題所述的匹配模式中，字符的比較次數(shù)最多為(n．m+1)*m次。7.

對于一個長度大于1且不存在重復(fù)元素的序列，令其所有元素依次通過一個初始為空的隊(duì)列后，再通過一個初始為空的棧。設(shè)隊(duì)列和棧的容量都足夠大，一個序列通過隊(duì)列(棧)的含義是序列的每個元素都入隊(duì)列(棧)且出隊(duì)列(棧)一次且僅一次。對于該序列在上述隊(duì)列和棧上的操作，正確的是(57)。A

出隊(duì)序列和出棧序列一定相同B

出隊(duì)序列和出棧序列一定互為逆序C

入隊(duì)序列和出隊(duì)序列一定相同，入棧序列和出棧序列不一定相同D

入棧序列和出棧序列一定互為逆序，入隊(duì)序列和出隊(duì)序列不一定互為逆序

分值:2答案:C解析：隊(duì)列具有先進(jìn)先出的特點(diǎn)，也就是說最先入隊(duì)的元素最先出隊(duì)，所以入隊(duì)序列和出隊(duì)序列一定相同。棧則具有先進(jìn)后出的特點(diǎn)，如果所有元素進(jìn)棧后再依次出棧，則入棧序列和出棧序列互為逆序，否則不一定。8.

在字符串的KMP模式匹配算法中，需要求解模式串p的next函數(shù)值，其定義如下所示。若模式串p為“aaabaaa”，則其next函數(shù)值為(58)。A

123123B

123210C

123432D

123456

分值:2答案:A解析：j=1時，next[1]=0。j=2時，不存在k，滿足1＜k＜j，則next[2]=1。j=3時，k只能取2，等式的左邊為p1，等式的右邊為p2，p1=p2=a，next[3]=2。j=4時，k可以取2和3，k取2的時候，左邊為p1，右邊為p3，p1=p3=a；k取3時，左邊為p1p2，右邊為P29.

對于線性表(由n個同類元素構(gòu)成的線性序列)，采用單向循環(huán)鏈表存儲的特定之一是(58)。A

從表中任意節(jié)點(diǎn)出發(fā)都能遍歷整個鏈表B

對表中的任意節(jié)點(diǎn)可以進(jìn)行隨機(jī)訪問C

對于表中的任意一個節(jié)點(diǎn)，訪問其直接前驅(qū)和直接后繼節(jié)點(diǎn)所有時間相同D

第一個節(jié)點(diǎn)必須是頭節(jié)點(diǎn)

分值:2答案:A解析：對于單向循環(huán)鏈表，可以從表中任意節(jié)點(diǎn)出發(fā)都能遍歷整個鏈表。但并不能對表中的任意節(jié)點(diǎn)進(jìn)行隨機(jī)訪問，需要從設(shè)置的第一個節(jié)點(diǎn)開始，沿著指針訪問表中的節(jié)點(diǎn)。當(dāng)然訪問某一節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)最快，訪問其直接前驅(qū)節(jié)點(diǎn)最慢，因?yàn)槭紫纫闅v要表尾，然后從表頭遍歷到其前驅(qū)節(jié)點(diǎn)。10.

設(shè)循環(huán)隊(duì)列Q的定義中有rear和len兩個域變量，其中rear表示隊(duì)尾元素的指針，len表示隊(duì)列的長度，如圖8—3所示(隊(duì)列長度為3，隊(duì)頭元素為e)。設(shè)隊(duì)列的存儲空間容量為M，則隊(duì)頭元素的指針為(57)。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

分值:2答案:D解析：隊(duì)列的存儲空間容量為M，說明隊(duì)列中最多可以有M個元素；隊(duì)列的長度為len，說明當(dāng)前隊(duì)列中有l(wèi)en個元素。設(shè)隊(duì)列的隊(duì)頭指針為front，front指向隊(duì)頭元素，則有：Q．rear=(Q．front+Q．1en一1)％MQ．front=(Q．rear一Q．len+1+M)％M11.

棧是一種按“后進(jìn)先出”原則進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)，因此，(60)必須用棧。A

實(shí)現(xiàn)函數(shù)或過程的遞歸調(diào)用及返回處理時B

將一個元素序列進(jìn)行逆置C

鏈表節(jié)點(diǎn)的申請和釋放D

可執(zhí)行程序的裝入和卸載

分值:2答案:A解析：棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。將一個元素序列逆置時，可以使用棧也可以不用。鏈表節(jié)點(diǎn)的申請和釋放次序與應(yīng)用要求相關(guān)，不存在“先申請后釋放”的操作要求。可執(zhí)行程序的裝入與卸載，也不存在“后進(jìn)先出”的操作要求。對于函數(shù)的遞歸調(diào)用與返回，一定是后被調(diào)用執(zhí)行的先返回。12.

若對一個鏈表最常用的操作是在末尾插入節(jié)點(diǎn)和刪除尾節(jié)點(diǎn)，則采用僅設(shè)尾指針的單向循環(huán)鏈表(不含頭節(jié)點(diǎn))時，(65)。A

插入和刪除操作的時間復(fù)雜度都為O(1)B

插入和刪除操作的時間復(fù)雜度都為O(n)C

插入操作的時間復(fù)雜度為O(1)，刪除操作的時間復(fù)雜度為O(n)D

插入操作的時間復(fù)雜度為O(n)，刪除操作的時間復(fù)雜度為O(1)

分值:2答案:C解析：設(shè)尾指針的單項(xiàng)循環(huán)鏈表(不含頭節(jié)點(diǎn))如圖8—4所示：設(shè)節(jié)點(diǎn)的指針域?yàn)閚ext，新節(jié)點(diǎn)的指針為s，則在尾指針?biāo)腹?jié)點(diǎn)后插入節(jié)點(diǎn)的操作為：S一>next=t一>next；t一>next=S；t=S；也就是插入操作的時間復(fù)雜度為O(1)。要刪除尾指針?biāo)腹?jié)點(diǎn)，必須通過遍歷操作找到尾節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，其操作序列如下：if(t一>next==t)free(t)；eiSe{P=t一>next；whiie(p一>next!=t)p=p一>next；P一>next=t一>next；free(t13.

對二維數(shù)組a[1一N，1一N]中的一個元素a[i,j](1≤i，j≤N)，存儲在a嘶]之前的元素個數(shù)(21)。A

與按行存儲或按列存儲方式無關(guān)B

在i=j時與按行存儲或按列存儲方式無關(guān)C

在按行存儲方式下比按列存儲方式下要多D

在按行存儲方式下比按列存儲方式下要少

分值:2答案:B解析：存儲在a[i,j]之前的元素個數(shù)與按行存儲或按列存儲方式有關(guān)。按行存儲時，存儲在a[i,j]之前的元素個數(shù)為(i—1)*N+j一1_iN+j—N—1；按列存儲時，存儲在a[i,j]之前的元素個數(shù)為(j—1)*N+i—1=jN+i—N—1。很顯然，i14.

若二維數(shù)組arr[1一M，1一N]的首地址為base，數(shù)組元素按列存儲且每個元素占用K個存儲單元，則元素arr[i，j]在該數(shù)組空間的地址為(21)。A

base+((i—1)×M+j—1)×KB

base+((i一1)×N+j—1)×KC

base+((j一1)×M+i一1)×KD

base+((j一1)×N+i一1)×K

分值:2答案:C解析：數(shù)據(jù)art共M行N列，下標(biāo)均從1開始。元素arr[i,j]在數(shù)據(jù)arr的第i行第j列，如果數(shù)組元素按列存儲，則1~j-1列共有(j—1)×M個元素，a[i,j]之前共(j一1)×M+i一1個元素，元素arr[i，j]在該數(shù)組空間的地址為為base+((j一1)×M+i一1)×K。15.

設(shè)下三角矩陣(上三角部分的元素值都為0)A[0...n，0...n]如下所示，將該三角矩陣的所以非零元素(即行下標(biāo)不小于列下標(biāo)的元素)按行優(yōu)先壓縮存儲在容量足夠大的數(shù)組M[1...m]中，則元素A[i，j](0≤i≤n，j≤i)存儲在數(shù)組M的(57)中。A

B

C

D

分值:2答案:A解析：第0行有1個元素保存在數(shù)組M中，第l行有2個元素保存在數(shù)組M中，第i一1行中有i個元素保存在數(shù)組M中，第i行之前有1+2+3+…+i=i(i+1)／2個元素保存在數(shù)組M中，元素A[i，j]是第i行的j+1個元素。由于數(shù)組M的下標(biāo)從1開始，因此A[i,j]的值存儲在中。16.

設(shè)有如下所示的下三角矩陣A【0...8，0...8】，將該三角矩陣的非零元素(即行下標(biāo)不小于列下標(biāo)的所有元素)按行優(yōu)先壓縮存儲在數(shù)組M[1...m]中，則元素A嘶】(0≤i≤8,j≤i)存儲在數(shù)組M的(58)中。A

B

C

D

分值:2答案:A解析：如圖所示，按行方式壓縮存儲時，A[i，j]之前的元素數(shù)目為(1+2+…+i+j)個，數(shù)組M的下標(biāo)從1開始，因此A[i,j]的值存儲在中。17.

一個高度為h的滿二叉樹的節(jié)點(diǎn)總數(shù)為2b一1，從根結(jié)點(diǎn)開始，自上而下、同層次結(jié)點(diǎn)從左至右，塒結(jié)點(diǎn)按照順序依次編號，即根節(jié)點(diǎn)編號為1，其左、右孩子節(jié)點(diǎn)編號分為2和3，再下一層從左到右的編號為4、5、6、7，依次類推。那么，在一顆滿二叉樹中，對于編號為m和n的兩個節(jié)點(diǎn)，若n=2m+1，則(64)結(jié)點(diǎn)。A

m是n的左孩子B

m是n的右孩子C

n是m的左孩子D

n是m的右孩子

分值:2答案:D解析：由于該二叉樹為滿二叉樹，且根節(jié)點(diǎn)編號從1開始，由滿二叉樹的性質(zhì)可知父節(jié)點(diǎn)m和右孩子之間的關(guān)系為n=2m+1。18.

以下關(guān)于哈夫曼樹的敘述，正確的是(60)。A

哈夫曼樹一定是滿二叉樹，其每層結(jié)點(diǎn)數(shù)都達(dá)到最大值B

哈夫曼樹一定是平衡二叉樹，其每個結(jié)點(diǎn)左右子樹的高度差為一1、0或1C

哈夫曼樹中左孩子結(jié)點(diǎn)的權(quán)值小于父結(jié)點(diǎn)、右孩子結(jié)點(diǎn)的權(quán)值大于父結(jié)點(diǎn)D

哈夫曼樹中葉子結(jié)點(diǎn)的權(quán)值越小則距離樹根越遠(yuǎn)、葉子結(jié)點(diǎn)的權(quán)值越大則距離樹根越近

分值:2答案:D解析：哈夫曼樹即最優(yōu)二叉樹，是一類帶權(quán)路徑長度的最短的樹。樹的帶權(quán)路徑為書中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，記為：其中，n為帶權(quán)葉子節(jié)點(diǎn)的數(shù)目，wk為葉子節(jié)點(diǎn)的權(quán)值，lk為葉子節(jié)點(diǎn)到根的路徑長度。哈夫曼樹是指權(quán)值為w1,w2,…，wn的n個葉子節(jié)點(diǎn)的二叉樹中帶權(quán)路徑長度最小的二又樹。哈夫曼樹與完全二叉樹、平衡二叉樹之間沒有必然的聯(lián)系。選項(xiàng)A、B中的說法是錯誤的。在哈夫曼樹的構(gòu)建中，由哈夫曼樹的19.

若某二叉樹的后序遍歷序列為KBFDCAE，中序遍歷序列為BKFEACD，則該二又樹為(58)。A

B

C

D

分值:2答案:A解析：本題考查二叉樹的遍歷算法，根據(jù)中序遍歷序列和另一種遍歷序列的結(jié)果，可以確定該二叉樹。后序遍歷是按照左子樹、右子樹、根節(jié)點(diǎn)的順序進(jìn)行遍歷，中序遍歷是按照左子樹、根節(jié)點(diǎn)、右子樹的順序進(jìn)行遍歷。E為根節(jié)點(diǎn)，K為B的右子樹，因此應(yīng)選A項(xiàng)描述的二叉樹。20.

若n2、n1、n0分別表示一個二叉樹中度為2、度為1和葉子節(jié)點(diǎn)的數(shù)目(節(jié)點(diǎn)的度定義為節(jié)點(diǎn)的子樹數(shù)目)，則對于任何一個非空的二叉樹，(59)。A

n2一定大于n1B

n1一定大于n0C

n2一定大于n0D

n0一定大于n2

分值:2答案:D解析：由二叉樹的性質(zhì)可知，度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)數(shù)多1，即n0=n2+1，因此n0一定大于n2。21.

一棵滿二叉樹，其每一層節(jié)點(diǎn)個數(shù)都達(dá)到最大值，對其中的節(jié)點(diǎn)從1開始順序編號，即根節(jié)點(diǎn)編號為1，其左、右孩子節(jié)點(diǎn)編號分別為2和3，再下一層從左到右的編號為4、5、6、7，依此類推，每一層都從左到右依次編號，直到最后的葉子節(jié)點(diǎn)層為止，則用(60)可判定編號為m和n的兩個節(jié)點(diǎn)是否在同一層。A

log2m=log2nB

[log2m]=[log2n]C

[log2m]+1=[log2n]D

[log2m]=[log2n]+1

分值:2答案:B解析：由于是滿二叉樹，只有m個節(jié)點(diǎn)的二叉樹一定是完全二叉樹，只有n個節(jié)點(diǎn)的二叉樹也一定是完全二叉樹，因此，具有m個節(jié)點(diǎn)的完全二叉樹的深度為[log2m]+1，具有n個節(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。如果編號為m和n的兩個節(jié)點(diǎn)是在同一層，則有[log2m]+1=[log2n]+1，即[log2m]=[log2,n]。22.

(61)是由權(quán)值集合{8，5，6，2}構(gòu)造的哈夫曼樹(最優(yōu)二叉樹)。A

B

C

D

分值:2答案:C解析：哈夫曼樹是帶權(quán)路徑最短的樹。選項(xiàng)A、B、C、D四棵樹的帶權(quán)路徑長度分別如下。選項(xiàng)A：8×2+5×2+6×2+2×2=412選項(xiàng)B：8×3+5×3+6×2+2=53選項(xiàng)C：8+6×2+2×3+5×3=41選項(xiàng)D：2+5×2+6×3+8×3=5423.

以下編碼方法中，(12)屬于熵編碼。A

哈夫曼編碼B

小波變換編碼C

線性預(yù)測編碼D

行程編碼

分值:2答案:A解析：熵編碼根據(jù)信息熵理論，編碼時只壓縮冗余而不損傷信息熵，是一種無損壓縮。常見的熵編碼有哈夫曼編碼、游程編碼和算術(shù)編碼。24.

在(59)中，任意一個節(jié)點(diǎn)的左、右子樹的高度之差的絕對值不超過1。A

完全二又樹B

二叉排序樹C

線索二叉樹D

最優(yōu)二叉樹

分值:2答案:A解析：對于完全二叉樹，若設(shè)二叉樹的高度為h，除第h層外，其他各層(1～h一1)的節(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h層所有的節(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二又樹。在完全二叉樹中，任意一個節(jié)點(diǎn)的左、右子樹的高度之差的絕對值不超過1。二叉排序樹(BinarySortTree)又稱二叉查找樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：①若左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；②若右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；③左、右子樹也分別為二叉排序樹。對于二叉排序樹，由于左子樹或右子樹可25.

下面關(guān)于哈夫曼樹的敘述中，正確的是(58)。A

哈夫曼樹一定是完全二叉樹B

哈夫曼樹一定是平衡二叉樹C

哈夫曼樹中權(quán)值最小的兩個節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)D

哈夫曼樹中左孩子節(jié)點(diǎn)小于父節(jié)點(diǎn)、右孩子節(jié)點(diǎn)大于父節(jié)點(diǎn)

分值:2答案:C解析：哈夫曼樹即最優(yōu)二叉樹，是一類帶權(quán)路徑長度的最短的樹。樹的帶權(quán)路徑為書中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和，記為：其中，n為帶權(quán)葉子節(jié)點(diǎn)的數(shù)目，wk為葉子節(jié)點(diǎn)的權(quán)值，lk為葉子節(jié)點(diǎn)到根的路徑長度。則哈夫曼樹是指權(quán)值為w1、w2、…、wn的n個葉子節(jié)點(diǎn)的二叉樹中帶權(quán)路徑長度最小的二叉樹。哈夫曼樹與完全二叉樹、平衡二叉樹之間沒有必然的聯(lián)系。選項(xiàng)A、B中的說法是錯誤的。在哈夫曼樹的構(gòu)建中，由哈夫曼樹26.

已知一棵度為3的樹(一個節(jié)點(diǎn)的度是指其子樹的數(shù)目，樹的度是指該樹中所有節(jié)點(diǎn)的度的最大值)中有5個度為1的節(jié)點(diǎn)，4個度為2的節(jié)點(diǎn)，2個度為3的節(jié)點(diǎn)，那么，該樹中的葉子節(jié)點(diǎn)數(shù)目為(61)。A

10B

9C

8D

7

分值:2答案:B解析：樹的節(jié)點(diǎn)總數(shù)為：5+4×2+2×3+1=20，葉子節(jié)點(diǎn)數(shù)為：20—5—4—2=9。27.

2010年11月真題62某算法的時間復(fù)雜度可用遞歸式表示，若用Θ表示該算法的漸進(jìn)時間復(fù)雜度的緊致界，則正確的是(62)。A

Θ(nlg2n)B

Θ(nlgn)C

Θ(n2)D

Θ(n2)

分值:2答案:A解析：采用主定理來求解遞歸式。a=2，b=2，f(n)=nlgn，logba=1，f(n)=O(nlogbalgkn)=nlgn，因此k=1，屬于主定理的情況(2)，因此有T(n)=Θ(nlogbalgk+1n)=Θ(nlg2n)。28.

若用n個權(quán)值構(gòu)造一棵最優(yōu)二叉樹(哈夫曼樹)，則該二叉樹的節(jié)點(diǎn)總數(shù)為(59)。A

2nB

2n一1C

2n+1D

2n+2

分值:2答案:B解析：二叉樹具有以下性質(zhì)：度為2的幾點(diǎn)(雙分支節(jié)點(diǎn))數(shù)比度為0(葉子節(jié)點(diǎn))數(shù)正好少1。而根據(jù)最優(yōu)二叉樹(哈夫曼樹)的構(gòu)造過程可知，最優(yōu)二叉樹中只有度為2和0的節(jié)點(diǎn)，因此，其節(jié)點(diǎn)總數(shù)為2n一1。29.

用關(guān)鍵字序列10、20、30、40、50構(gòu)造的二叉樹排序(二叉查找樹)為(63)。A

B

C

D

分值:2答案:C解析：根據(jù)關(guān)鍵字序列構(gòu)造二叉排序樹的基本過程是，若需插入的關(guān)鍵字大于樹根，則插入到右子樹上，若小于樹根，則插入到左子樹上，若為空，則作為樹根節(jié)點(diǎn)。30.

若某算法在問題規(guī)模為n時，其基本操作的重復(fù)次數(shù)可由下式表示，則該算法的時間復(fù)雜度為(64)。A

O(n)B

O(n2)C

O(logn)D

O(nlogn)

分值:2答案:B解析：根據(jù)題中給出的遞歸定義式進(jìn)行推導(dǎo)，可得T(n)=n+n—1+…+2+1，因此時間復(fù)雜度為O(n2)。31.

在一個有向圖G的拓?fù)湫蛄兄?，頂點(diǎn)vi列在vj之前，說明圖G中(59)。A

一定存在弧i，vj>B

一定存在弧j，vi>C

可能存在vi到vj的路徑，而不可能存在vj到vi的路徑D

可能存在vj到i的路徑，而不可能存在vi到vj的路徑

分值:2答案:C解析：根據(jù)有向圖G的拓?fù)湫蛄卸x，頂點(diǎn)vi排列在vj之前，可以得知可能存在vi到vj的路徑，拓?fù)湫蛄惺菃蜗虻?，所以不可能從vj到vi的路徑。所以本題答案選C。32.

拓?fù)渑判蚴菍⒂邢驁D中所有頂點(diǎn)排成一個線性序列的過程，并且該序列滿足：若在AOV網(wǎng)中從頂點(diǎn)Vi到Vj有一條路徑，則頂點(diǎn)Vi必然在頂點(diǎn)Vj之前。對于圖8—7所示的有向圖，(60)是其拓?fù)湫蛄小?/p>