Java程序員面試分類真題13

Java程序員面試分類真題13一、單項選擇題1.

若輸入序列已經是排好序的，下列排序算法中，速度最快的是______。A.插入排序B.Shell排序C.歸并排序D.快速排序正確答案：A[解（江南博哥）析]對于選項A，插入排序一遍掃描即可。

對于選項B，Shell排序雖不需要交換數據，但也要進行幾次插入排序。

對于選項C，歸并排序雖不需要交換數據，但也要進行l(wèi)ogn次合并。

對于選項D，快速排序在數列有序的情況下效率是最低的。

通過上面的分析可知，如果序列已經排好序，那么，此時插入排序算法速度最快。所以，選項A正確。

2.

現有個數約為50K的數列需要進行從小到大排序，數列特征是基本逆序(多數數字從大到小，個別亂序)，以下排序算法中，在事先不了解數列特征的情況下性能大概率最優(yōu)(不考慮空間限制)的是______。A.冒泡排序B.堆排序C.選擇排序D.快速排序正確答案：B[解析]由于排序元素個數為50K，數據量大，所以，冒泡、選擇、插入等排序算法基本不適用，所以，選項A與選項C錯誤。由于數列特性基本逆序，而快速排序的最差情況就是基本逆序或者基本有序的情況，所以，選項D錯誤。根據排除法可知，堆排序是最為合理的排序方法，所以，選項B正確。

所以，本題的答案為B。

3.

下面排序算法中，初始數據集的排列順序對算法的性能無影響的是______。A.堆排序B.插入排序C.冒泡排序D.快速排序正確答案：A[解析]對于選項A，堆排序的過程如下：構造最大堆，從而得到最大的元素，將最大的元素與最后一個元素交換(即取出最大的元素)，然后對以根結點為首的、除最后一個元素之外的n-1個元素進行一次構造堆操作，由堆的性質可知，經過該次操作后得到的堆仍為最大堆，所以，可以繼續(xù)將根結點與第n-1個結點交換，取出第二大元素……重復上述操作，直到依次取出第n-1大元素即完成了排序。所以，堆排序的時間復雜度一直都是O(nlogn)，它是一種不穩(wěn)定的排序算法。所以，初始數據集的排列順序對算法的性能無影響。因此，選項A正確。

對于選項B，插入排序的平均時間復雜度為O(n^2)，在序列初始有序的情況下，其時間復雜度為O(n)，它是一種穩(wěn)定的排序算法。因此，選項B錯誤。

對于選項C，冒泡排序的平均時間復雜度為O(n^2)，在序列初始有序的情況下，增加交換標志flag可將時間復雜度降到O(n)，它是一種穩(wěn)定的排序算法。因此，選項C錯誤。

對于選項D，快速排序與主元的選擇有關，如果選擇子序列左側第一個元素比較，那么第一個元素最好是大小居中的，以使得分成的兩個子數組長度大致相等，性能才能最佳，否則，在序列初始有序的情況下，時間復雜度可能會退化到O(n^2)，它是一種不穩(wěn)定的排序算法。因此，選項D錯誤。

所以，本題的答案為A。

4.

假設某文件經內排序后得到100個初始歸并段(初始順串)，若使用多路歸并排序算法，且要求三趟歸并完成排序，問歸并路數最少為______。A.8B.7C.6D.5正確答案：D[解析]本題首先要弄懂歸并排序的思路。m個元素k路歸并的歸并次數s=logk(m)，當m=100，s=3時，代入公式，logk(100)＜=3，即k^3＞=100，所以，k值最小為5，選項D正確。

5.

快速排序在已經有序的情況下效率最差，此時其時間復雜度為______。A.O(nlogn)B.O(n^2)C.O(n^1.5)D.O(n^2logn)正確答案：B

6.

在排序方法中，從未排序序列中挑選元素，并將其依次插入已排序序列(初始時為空)的一端的方法，稱為______。A.歸并排序B.希爾排序C.插入排序D.選擇排序正確答案：C

7.

對一個已經排好序的數組進行查找，時間復雜度為______。A.O(n)B.O(logn)C.O(nlogn)D.O(1)正確答案：B[解析]通常，對一個有序數組進行查找的最好方法為二分查找法。

二分查找的過程如下(假設表中元素是按升序排列)：首先，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者值相等，則查找成功；否則，利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字的值大于查找關鍵字的值，則進一步查找前一子表，否則，進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，查找成功，或直到子表不存在為止，此時查找不成功。

例如，對于數組{1，2，3，4，5，6，7，8，9}，當需要查找元素6時，如果用二分查找的算法執(zhí)行，其順序如下：

1)第一步查找中間元素，即5，由于5＜6，所以，6必然在5之后的數組元素中，那么就在{6，7，8，9}中查找。

2)尋找{6，7，8，9}的中位數，為7，7＞6，所以，6應該在7左邊的數組元素中，那么只剩下6，即找到了。

本題中，數組序列共11個數據元素，第一次比較下標為10/2=5的元素32。第二次比較下標為4/2=2的元素15，得到要查找的數。

通過以上的分析可知，二分查找的時間復雜度為O(logn)。所以，選項B正確。

8.

對有序數組{2、11、15、19、30、32、61、72、88、90、96}進行二分查找，則成功找到數值15需要比較______次。A.2B.3C.4D.5正確答案：A

9.

一個文件包含了200個記錄，若采用分塊查找法，每塊長度為4，則平均查找長度為______。A.30B.28C.29D.32正確答案：B[解析]分塊查找是折半查找和順序查找的一種改進方法，分塊查找由于只要求索引表是有序的，對塊內結點沒有排序要求，因此，它特別適合于結點動態(tài)變化的情況。

對于分塊查找的平均查找長度，通常由兩部分組成，一個是對索引表進行查找的平均查找長度，一個是對塊內結點進行查找的平均查找長度。假設線性表中共有n個結點，分成大小相等的b塊，每塊有s=n/b個結點。假定查找索引表采用順序查找，只考慮查找成功的情況，并假定對每個結點的查找概率是相等的，則其平均查找長度ASL=(b+1)/2+(s+1)/2；假設索引表中采用折半查找，則其平均查找長度ASL=(s+1)/2+log2(b+1)-1。

本題中，s=200/4=50，b=4，所以，其平均查找長度ASL=(200/4+4)/2+1=28，選項B正確。

所以，本題答案為B。

引申：有一個2000項的表，采用等分區(qū)間順序查找的分塊查找法，問：

1)每塊的理想長度是多少?

2)分成多少塊最為理想?

3)平均查找長度是多少?

4)若每塊是20，ASL是多少?求詳解。

分塊查找的平均查找長度包括索引表和分塊內的兩部分之和，即索引表+塊中。

假設線性表長n，均勻分成m塊，每塊中記錄個數s，則(其中符號表示上取整)，在等概率查找的前提下，如果約定在索引表中確定關鍵字所在的分塊也是順序查找，因為順序查找的平均查找長度為(L+1)/2，則ASL=(n/s+s)/2+1。當s=sqrt(n)時，該和值有極小值：sqrt(n)+1。

因此，如果索引表內也是順序查找，則每塊的理想元素個數是sqrt(2000)，約為44.7，近似為45，同樣分塊數量也是45，因此，ASL=2*(45+1)/2=46。

如果每塊長20，則分塊為2000/20=100塊，按照上面的結果，則ASL=(100+1)/2+(20+1)/2=61。

10.

設某棵二叉樹中有360個結點，則該二叉樹的最小高度是______。A.7B.9C.10D.8正確答案：B[解析]本題中的二叉樹并沒有說明到底是一棵什么類型的二叉樹(完全二叉樹、滿二叉樹、普通二叉樹還是其他二叉樹)，所以，其高度存在不確定性。

定義二叉樹中的結點總數為n，當每個結點只有一棵子樹的時候，其高度值最大，為n。當該二叉樹為完全二叉樹時，其高度值最小，為(其中符號表示取下整)，其他情況的二叉樹的高度都是介于這兩個值之間，即，不大于最大值也不小于最小值。

本題中要想求二叉樹的最小高度，那么此時該二叉樹為完全二叉樹，其對應的高度為。所以，選項B正確。

11.

一棵有12個結點的完全二叉樹，其深度為______。A.4B.5C.3D.6正確答案：A

12.

將一棵有100個結點的完全二叉樹從根這一層開始，進行廣度遍歷編號，那么編號最小的葉子結點的編號是______。A.49B.50C.51D.52正確答案：C[解析]在解答本題前，首先需要弄懂一個概念，什么是完全二叉樹?所謂完全二叉樹是指除樹的最后一層外，每一層上的結點數均達到最大值，且在最后一層上只缺少右邊的若干結點的二叉樹。

通過完全二叉樹的定義，可以引出以下兩種性質：①對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱為完全二叉樹；②一棵二叉樹至多只有最下面兩層上的結點的度數可以小于2，并且最下層上的結點都集中在該層最左邊的若干位置上，則此二叉樹為完全二叉樹。

假設n0是度為0的結點總數(即葉子結點數)，n1是度為1的結點總數，n2是度為2的結點總數，由二叉樹的性質可知：n0=n2+1，n=n0+n1+n2(其中n為完全二叉樹的結點總數)，由上述公式把n2消去得n=2n0+n1-1，由于完全二叉樹中度為1的結點數只有兩種可能：0或1，由此得到n0=(n+1)/2或n0=n/2，即?？筛鶕耆鏄涞慕Y點總數計算出葉子結點數。

本題中，n的值為100，根據上面的分析可知，n0=50。所以，度為0的結點有50個，度為1的結點有1個，度為2的結點有49個，二叉樹前k層最多有2^k-1個結點。所以，100個結點二叉樹高度為7，按照廣度優(yōu)先遍歷編號，有50個非葉子結點，所以，最小的葉子結點編號為51。

下面給出另外一種求解方法：

100個結點時，二叉樹高度為7。

7層包含數據個數為100-(2^6-1)=37。

6層包含數據的編號為32～63，6層中前19個數據包含子樹(37/2=18.5)，故最小的葉結點應該為32+19=51。所以，選項C正確。

13.

已知一棵二叉樹，如果先序遍歷的結點順序為ADCEFGHB，中序遍歷的結點順序為cDFEGHAB，則后序遍歷的結點順序為______。A.CFHGEBDAB.CDFEGHBAC.FGHCDEBAD.CFHGEDBA正確答案：D[解析]要解答出本題，首先需要對各種遍歷方式有一個清晰的認識?？梢酝ㄟ^圖1來介紹二叉樹的三種遍歷方式的區(qū)別。

圖1

二叉樹的遍歷方式

1)先序遍歷：先遍歷根結點，再遍歷左子樹，最后遍歷右子樹。所以，圖1的先序遍歷序列是ABDECFG。

2)中序遍歷：先遍歷左子樹，再遍歷根結點，最后遍歷右子樹。所以，圖1的中序遍歷序列是DBEAFCG。

3)后序遍歷：先遍歷左子樹，再遍歷右子樹，最后遍歷根結點。所以，圖1的后序遍歷序列是DEBFGCA。

從上面的介紹可以看出，先序遍歷序列的第一個結點一定是根結點，因此，本題中可以確定這個二叉樹的根結點為A。由中序遍歷的特點可以把樹分為三部分：根結點A、A的左子樹和A的右子樹。在中序遍歷的序列中，在A結點前面的序列一定是在A的左子樹上，在結點A后面的序列一定在A的右子樹上。由此可以確定：A的左子樹包含的結點為CDFEGH，右子樹包含的結點為B(見圖2a)。接下來對A的左子樹上的結點采用同樣的方法進行分析：對于序列CDFEGH，先序遍歷的時候先遍歷到結點D，因此，結點D是這個子樹的根結點；通過對中序遍歷進行分析可以把CDFEGH分為三部分：根結點D、D的左子樹包含的結點為C、D的右子樹上包含的結點為FEGH(見圖2b)。然后對FEGH用同樣的方法進行分析：在先序遍歷的序列中先遍歷到的結點為E，因此，根結點為E，通過分析中序遍歷的序列，可以把這個序列分成三部分：根結點E、E的左子樹上的結點F和E的右子樹上的結點GH(見圖2c)。最后分析結點GH，在先序遍歷序列中先遍歷到G，則說明G為根結點，在中序遍歷序列中先遍歷到結點G，說明H是G右子樹上的結點(見圖2d)。由此可以發(fā)現，通過先序遍歷和中序遍歷完全確定了二叉樹的結構，可以非常容易

圖2

二叉樹的遍歷

所以，本題的答案為D。

14.

有以下二叉樹：

對其進行后序遍歷的結果是______。A.丙乙丁甲戊己B.甲乙丙丁戊己C.丙丁乙己戊甲D.丙丁己乙戊甲正確答案：C

15.

已知一棵二叉樹的前序遍歷結果是ACDEFHGB，中序遍歷結果是DECALHFBG，那么該二叉樹的后序遍歷的結果為______。A.HGFEDCBAB.EDCHBGFAC.BGFHEDCAD.EDCBGHFA正確答案：B

16.

某二叉樹按中序遍歷的序列為SYZ，則該二叉樹可能存在______種情況。A.2B.3C.4D.5正確答案：D[解析]由于二叉樹的中序遍歷序列為SYZ，所以，可以分別以字符S、Y、Z為根構建二叉樹。

(1)S為根

此時可以構建2種不同的二叉樹。

二叉樹結構如圖1所示。

圖1

S為根的二叉樹

(2)Y為根

此時可以構建1種二叉樹。

二叉樹結構如圖2所示。

圖2

Y為根的二叉樹

(3)Z為根

此時可以構建2種不同的二叉樹。

二叉樹結構如圖3所示。

圖3

Z為根的二叉樹

所以，一共可以構建2+1+2=5種不同的二叉樹。所以，選項D正確。

17.

某棵完全二叉樹上有699個結點，則該二叉樹的葉子結點數為______。A.349B.350C.188D.187正確答案：B[解析]二叉樹有如下性質：對于一棵非空的二叉樹，度為0的結點(即葉子結點)總是比度為2的結點多一個，即如果葉子結點(度為0的結點)數為n0，度數為2的結點數為n2，則有n0=n2+1。

對于本題而言，假設度為i的結點的個數為ni，則n0=n2+1，所以，n0+n1+n2=n0+n1+n0-1=699，可以得到n0=(700-n1)/2，顯然，n1只能是偶數。由于在完全二叉樹中，度為1的結點只有0個或1個兩種情況，因此，n1=0，n0=350。所以，葉子結點個數為350，選項B正確。

18.

對于一棵排序二叉樹，可以得到有序序列的遍歷方式是______遍歷。A.前序B.中序C.后序D.都可以正確答案：B[解析]排序二叉樹的特點為：對于一個結點而言，所有左子樹結點元素的值都小于這個結點元素的值，所有右子樹結點的元素的值都大于這個結點元素的值，且左右子樹都是排序二叉樹。由于中序遍歷的順序為左子樹、根、右子樹，顯然，中序遍歷得到的序列是有序的。所以，選項B正確。

19.

最佳二叉搜索樹是______。A.關鍵碼個數最少的二叉搜索樹B.搜索時平均比較次數最少的二叉搜索樹C.所有結點的左子樹都為空的二叉搜索樹D.所有結點的右子樹都為空的二叉搜索樹正確答案：B[解析]二叉查找樹(BinarySearchTree)又稱為二叉搜索樹、二叉排序樹，它或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分別為二又查找樹。

二叉搜索樹的優(yōu)點是：樹中的元素是有序的，對二叉搜索樹的查找類似于二分查找，顯然，查找過程中比較的次數越少，效率就越高。顯然，選項B正確。

對于選項A，二叉搜索樹的好壞與關鍵碼的個數沒有直接關系。所以，選項A錯誤。

對于選項C與選項D，如果所有結點的左孩子(右孩子)都為空，那么查找效率與線性查找相同，都為O(n)。所以，選項C與選項D錯誤。

20.

若一棵二叉樹的前序遍歷序列為aebdc，后序遍歷序列為bcdea，則根結點的孩子結點______。A.只有eB.有e，bC.有e，cD.不確定正確答案：A[解析]二叉樹是每個結點最多有兩個子樹的樹結構，通常子樹被稱作“左子樹”(LeftSubtree)和“右子樹”(RightSubtree)。所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。而通常情況下，如果中序遍歷未知，則是無法還原出二叉樹的。但本題只要求判斷根結點的孩子結點，因此，是可以實現的。

二叉樹中的前序遍歷也叫作先根遍歷、先序遍歷，遵循的原則為“根左右”，即首先遍歷根結點，再遍歷根結點的左子樹結點，最后遍歷根結點的右子樹結點。從前序遍歷序列可知，結點e緊跟著結點a，可得結論：①結點a為根結點；②當結點e為結點a的右孩子時，結點a有且僅有結點e一個孩子。

二叉樹中的后序遍歷也叫作后根遍歷，遵循的原則為“左右根”，即首先遍歷左子樹結點，再遍歷右子樹結點，最后遍歷根結點。從后序遍歷序列可知，結點e之后緊跟結點a，可得結論：③當結點e為結點a的左孩子時，結點a有且僅有結點e一個孩子。從結論①②③可知根結點的孩子有且僅有e。

通過前序遍歷序列和后序遍歷序列不能夠唯一確定一棵二叉樹，本例子存在如圖所示的兩種情況。

本題的兩種情況

但無論是以上哪一種情況，都可以看出根結點的孩子結點只有e。

通過以上分析可知，選項A是正確的。

21.

現有一個包含m個結點的三叉樹，即每個結點都有三個指向孩子結點的指針，請問：在這3m個指針中，空指針的個數是______。A.2mB.2m-1C.2m+1D.3m正確答案：C[解析]根據題目意思可知，m個結點共有3m個指針，而除了根結點外，每個結點都有父結點(即需要占用一個父結點的指針)，所以，空指針數為3m-(m-1)=2m+1，選項C正確。

22.

一個具有20個葉子結點的二叉樹，它有______個度為2的結點。A.16B.21C.17D.19正確答案：D[解析]度的含義是一個結點所擁有的孩子個數。結點的度為0表示該結點沒有孩子結點，也就是說，該結點為葉子結點。結點的度為2表示該結點有兩個孩子結點。

在二叉樹中，存在這樣一個結論：對于任何的一棵二叉樹，度為0的結點(就是葉子結點)數總是比度為2的結點數多一個。即假定度為0的結點(就是葉子結點)個數為n0，度為2的結點的個數為n2，那么數值上滿足如下計算公式：n0=n2+1。證明過程如下：

假設n1為二叉樹T中度為1的結點數，因為二叉樹中所有結點的度都小于或等于2，所以，其結點總數為

n=n0+n1+n2

(1)

而二叉樹中的分支數，除了根結點外，其余結點都有一個分支進入，設B為分支總數，則n=B+1。由于這些分支是由度為1或2的結點射出的，所以，B=n1+2n2，于是得出如下結論：

n=n1+2n2+1

(2)

由表達式(1)和(2)可得：n0=n2+1。

本題中，由于己知葉子結點數為20，即n0的值為20，所以，n2的值就為19，選項D正確。

23.

一個完全二叉樹總共有289個結點，則該二叉樹中的葉子結點數為______。A.145B.128C.146D.156正確答案：A[解析]對于任何的一棵二叉樹，度為0的結點(就是葉子結點)數總是比度為2的結點數多一個。即假定度為0的結點(就是葉子結點)個數為n0，度為2的結點的個數為n2，那么數值上滿足如下計算公式：n0=n2+1。

而在一個完全二叉樹中，其左右子樹的深度之差不大于1，所以，要么只有一個度為1的結點，要么沒有。定義二叉樹中所有結點個數為n，度為1的結點數為n1，那么n0+n1+n2=n，而n0=n2+1，所以葉子結點的個數n0=(n+1-n1)/2，其中n1要么為0，要么為1，n=289，只有當n1=0的時候，n+1-n1才能整除2，因此，n1=0，此時n0=(289+1)/2=145。所以，選項A正確。

24.

一棵二叉樹有1000個結點，則該二叉樹的最小高度是______。A.9B.10C.11D.12正確答案：B

25.

二叉排序樹的定義是：①若它的左子樹不為空，則左子樹所有結點均小于它的根結點的值；②若它的右子樹不為空，則右子樹所有結點的值均大于根結點的值；③它的左右子樹也分別為二叉排序樹。下列遍歷方式中，能夠得到一個遞增有序序列的是______。A.前序遍歷B.中序遍歷C.后序遍歷D.廣度遍歷正確答案：B[解析]如果需要得到的序列為遞增序列，按照二叉排序樹的定義，應該先訪問左子樹，再訪問根結點，最后訪問右子樹，根據定義可知，能夠得到一個遞增有序序列的遍歷方式是為中序遍歷。所以，選項B正確。

26.

遞歸式地先序遍歷一個有n個結點、深度為d的二叉樹，則需要?？臻g的大小為______。A.O(n)B.O(d)C.O(logn)D.(nlogn)正確答案：B[解析]本題中，由于沒有明確交代二叉樹的類型或性質，所以，本題中的二叉樹是無法確定類型的，自然而然也就并不一定是平衡的了，也就是說，深度d的值并不一定等于logn，很有可能d的值比logn的值大，而?？臻g的大小通常為二叉樹的深度，所以，棧的大小應該是O(d)，而不是O(logn)。因此，本題的答案為B。

27.

用關鍵字序列10、20、30、40、50構造的二叉排序樹(二叉查找樹)為______。

A．

B．

C．

D．正確答案：D[解析]對于二叉排序樹而言，右結點元素的值總是比根結點元素的值大，左結點元素的值總是比根結點元素的值小。本題中，給出的序列是遞增的。通過逐一對比可知，只有選項D正確。

28.

具有n個頂點的有向圖，所有頂點的出度之和為m，則所有頂點的入度之和為______。A.mB.m+1C.n+1D.2m+1正確答案：A[解析]度指的是與該頂點相關聯的邊數。在有向圖中，度又分為入度(In-degree)和出度(Out-degree)。以某頂點為弧頭，終止于該頂點的弧的數目稱為該頂點的入度。以某項點為弧尾，起始于該頂點的弧的數目稱為該頂點的出度。在某頂點的入度和出度的和稱為該頂點的度。

在有向圖的鄰接表中，從一個頂點出發(fā)的弧鏈接在同一鏈表中，鄰接表中結點的個數恰為圖中弧的數目，所以，頂點入度之和為弧數和的一倍。如果為無向圖，同一條邊有兩個結點，分別出現在和它相關的兩個頂點的鏈表中，因此，無向圖的鄰接表中結點個數為邊數的2倍。本題中頂點的出度之和為m，所以，所有頂點的入度之和也為m(一條弧對應一個入度與一個出度)，通過以上分析可知，選項A正確。

29.

具有n個頂點的有向圖最多有______條邊。A.nB.n(n-1)C.n(n+1)D.n^2正確答案：B[解析]如果圖中的每條邊都是有方向的，則稱為有向圖。在一個有向圖中，邊是由兩個頂點組成的有序對，有序對通常用尖括號表示，例如＜vi,vj＞表示一條有向邊，其中vi是邊的始點，vj是邊的終點。在有向圖中，＜vi,vj＞和＜vi,vj＞代表兩條不同的有向邊。

在有向圖中，任意兩個結點之間都可以形成一對有向邊，因此，對于具有n個頂點的有向圖，其邊的條數為n(n-1)。所以，選項B正確。

30.

n個頂點的強連通圖至少有______條邊。A.nB.n-1C.n+1D.n(n-1)正確答案：A[解析]n個頂點的強連通圖至少有n條邊，最多有n(n-1)/2條邊。所以，選項A正確。

31.

在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為______。A.sB.s-1C.s+1D.n正確答案：A[解析]在有向圖中，所有頂點的入度之和等于出度之和。本題中，所有頂點的出度之和為s，則所有頂點的入度之和也為s。所以，選項A正確。

32.

對于一個有向圖，若一個頂點的入度為k1、出度為k2，則對應鄰接表中該頂點的單鏈表中的結點數為______。A.k1B.k2C.k1-k2D.k1+k2正確答案：A[解析]在有向圖的鄰接表中，某頂點鏈表的結點個數是發(fā)出去的弧的數量，也就是出度，反過來說，逆鄰接表的某頂點鏈表的結點個數是進入的弧的數量，也就是入度，所以，選項A正確。

33.

在有向圖G的拓撲序列中，若頂點vi在頂點vj之前，則下列情況下不可能出現的是______。A.G中有弧＜vi,vj＞B.G中有一條從vi到vj的路徑C.G中沒有?。紇i,vj＞D.G中有一條從vj到vi的路徑正確答案：D

34.

判斷有向圖是否存在回路，最好的方法是______。A.拓撲排序B.求最短路徑C.求關鍵路徑D.廣度優(yōu)先遍歷正確答案：A[解析]針對有向圖是否存在回路的問題，最好的方法就是對有向圖構造其頂點的拓撲有序序列，如果有向圖的所有頂點可以排出拓撲序列，則該有向圖無環(huán)路。具體步驟如下：

在求拓撲算法的過程中，最重要的是要維護一個入度為0的頂點的集合，每次從這個集合中取出一個頂點，放入保存拓撲結構結果的列表中，然后從圖中刪除從這個頂點引出的所有邊，在刪除這些邊后，這個邊的另外一個結點，如果入度變成0，則加入到存放入度為0的結點的集合中。依次類推，直到把所有頂點都遍歷完成，就求出了拓撲結構。如果在求解的過程中，存放入度為0的集合為空，但是此時圖中還有沒有遍歷的邊，則說明圖中至少存在一個回路。所以，選項A正確。

35.

無向圖G=(V，E)，其中V={a，b，c，d，e，f}，E={＜a，b＞，＜a，e＞，＜a，c＞，＜b，e＞，＜e，f＞，＜f，d＞，＜e，d＞}，對該圖進行深度優(yōu)先排序，得到的頂點序列正確的是______。A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，dD.a，e，d，f，c，b正確答案：D[解析]圖的深度優(yōu)先遍歷類似于樹的前序遍歷。假設給定無向圖G的初態(tài)是所有頂點均未曾被訪問過，深度優(yōu)先遍歷過程是這樣的：在無向圖G中任選一個頂點v為初始出發(fā)點(源點)，首先訪問源點v，并將其標記為已訪問過，然后，依次從源點v出發(fā)，搜索源點v的每個相鄰結點w。如果結點w未曾被訪問過，那么以結點w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。如果此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。

本題中，按照上述方法可知，選項D正確。

36.

已知一個無向圖(邊為正數)中頂點A、B的一條最短路徑P，如果把各個邊的權重(即相鄰兩個頂點的距離)變?yōu)樵瓉淼?倍，那么在新圖中，P仍然是A、B之間的最短路徑。以上說法______。A.不確定B.正確C.錯誤正確答案：B[解析]如果從圖中某一頂點(源點)到達另一頂點(終點)的路徑可能不止一條，有這樣一條路徑，沿此路徑上各邊的權值總和(稱為路徑長度)最小，該路徑稱為最短路徑。

本題中，如果將各條邊的權值按從小到大排序，則權值乘以2之后的排序不變，也就是權重的相對關系不變，p仍是最短路徑。所以，選項B正確。

37.

一個具有8個頂點的連通無向圖，最多有______條邊。A.28B.7C.26D.8正確答案：A[解析]所謂連通無向圖，指的是對圖中任意頂點u、v，都存在路徑使u、v連通，即任何兩個點都有邊相連。本題中，8個點中任選擇兩個，都可以有一條邊，所以，最多有8*7/2=28條邊，選項A正確。

所以，本題的答案為A。

結論1：一個有n個頂點的有向強連通圖最多有n(n-1)條邊，最少有n條邊。

強連通圖必須從任何一點出發(fā)都可以回到原處，每個結點至少要一條出路(單結點除外)，至少有n條邊，正好可以組成一個環(huán)。

結論2：一個有n個頂點的無向連通圖最多有n(n-1)/2條邊，最少有n-1條邊。

可以通過數學歸納法進行證明。有興趣的讀者可以自行驗證。

引申：若一個非連通的無向圖最多有28條邊，則該無向圖至少有多少個頂點?

9個。假設有8個頂點，則8個頂點的無向圖最多有28條邊且該圖為連通圖。連通無向圖構成條件：邊=頂點數*(頂點數-1)/2。頂點數＞=1，所以，該函數存在單調遞增的單值反函數，邊與頂點為增函數關系。故28條邊的連通無向圖頂點數最少為8個。

因此，28條邊的非連通無向圖為9個(加入一個孤立點)。

38.

對于一個具有n個頂點的無向圖，若采用鄰接表數據結構表示，則存放表頭結點的數組大小為______。A.nB.n+1C.n-1D.n+邊數正確答案：A[解析]無向圖指的是邊沒有方向的圖。采用鄰接表表示的無向圖，存放表頭結點的數組的大小為圖的頂點個數。本題中，無向圖的頂點個數為n，所以，存放表頭結點的數組大小為n，選項A正確。

39.

在一個具有n個頂點的無向圖中，要連通全部頂點至少需要______條邊。A.nB.n+1C.n-1D.n/2正確答案：C

40.

一個有n個頂點的無向連通圖，它所包含的連通分量個數為______。A.0B.1C.nD.n+1正確答案：B

41.

在一個無向圖中，若兩個頂點之間的路徑長度為k，則該路徑上的頂點數為______。A.kB.k+1C.k+2D.2k正確答案：B

二、多項選擇題1.

二叉樹是一種樹形結構，每個結點至多有兩棵子樹，下列一定是二叉樹的是______。A.紅黑樹B.B樹C.AVL樹D.B+樹正確答案：AC[解析]對于選項A，紅黑樹是每個結點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。除了具有二叉查找樹的一般性質以外，對于任何有效的紅黑樹，還有如下的額外要求：

1)結點是紅色或黑色。

2)根結點是黑色。

3)每個葉子結點(空結點)是黑色的。

4)每個紅色結點的兩個子結點都是黑色(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結點)。

5)從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。

所以，紅黑樹是二叉樹。所以，選項A正確。

對于選項B，B樹是一種平衡的多叉樹。所以，選項B不正確。

對于選項C，AVL樹是平衡二叉樹。所以，選項C正確。

對于選項D，B+樹是一種樹數據結構，是一個n叉樹，每個結點通常有多個孩子，一棵B+樹包含根結點、內部結點和葉子結點。根結點可能是一個葉子結點，也可能是一個包含兩個或兩個以上孩子結點的結點。所以，選項D不正確。

所以，本題的答案為AC。

2.

堆的形狀是一棵______。A.完全二叉樹B.平衡二叉樹C.二叉排序樹D.滿二叉樹正確答案：AB[解析]堆是一種特殊的樹形結構，有大頂堆和小頂堆兩種。大頂堆(小頂堆)的特點是根結點的值最大(最小)，且根結點的子樹也為一個大項堆(小頂堆)。

對于選項A，完全二叉樹是指除最后一層外，每一層上的結點數均達到最大值；在使用的時候堆是采用數組來存儲的，因此，它滿足完全二叉樹的特點。所以，選項A正確。

對于選項B，平衡二叉樹(BalancedBinaryTree)又稱為AVL樹(有別于AVL算法)，具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩棵子樹都是一棵平衡二叉樹。由于完全二叉樹一定滿足平衡二叉樹的性質。所以，選項B正確。

對于選項C，排序二叉樹有如下性質：

1)若左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值。

2)若右子樹不為空，則右子樹上所有結點的值均大于或等于它的根結點的值。

3)左、右子樹也分別為二叉排序樹。

4)沒有鍵值相等的結點。

顯然，堆不滿足這個性質。所以，選項C不正確。

對于選項D，滿二叉樹是指樹中除最后一層無任何子結點外，每一層上的所有結點都有兩個子結點的二叉樹。滿二叉樹中結點的個數為1，3，7等特殊的數字，而堆中的結點可以是任意的，因此，不能保證堆是個滿二叉樹。所以，選項D不正確。

所以，本題的答案為AB。

3.

2-3樹是一種特殊的樹，它滿足以下兩個條件：

1)每個內部結點有兩個或三個子結點。

2)所有的葉子結點到根的路徑長度相同。

如果一棵2-3樹有9個葉子結點，則它可能有的非葉結點個數為______。A.8B.7C.6D.5E.4正確答案：BE[解析]根據條件2)，葉子結點只能在同一層，根據條件1)，上一層的父結點只能是3個或4個，只能是下圖所示的兩種結果。

本題的兩種結構

所以，本題的答案為BE。

三、填空題1.

程序的局部變量存在于______中，全局變量存在于______中，動態(tài)申請數據存在于______中。正確答案：棧，靜態(tài)區(qū)，堆。

2.

設有字母序列{Q，D，F，X，A，P，N，B，Y，M，C，W}，按二路歸并方法對該序列進行一趟掃描后的結果為______。正確答案：DQFXAPBNMYCW。[解析]歸并排序是利用遞歸與分治技術將數據序列劃分成越來越小的子序列，再對子序列進行排序，最后再用遞歸法將排好序的子序列合并成越來越大的有序序列。其中，“歸”代表的是遞歸的意思，即遞歸地將數組折半分離為單個數組，例如數組[2，6，1，0]，會先折半，分為[2，6]和[1，0]兩個子數組，然后再折半將數組分離，分為[2]、[6]和[1]、[0]。“并”就是將分開的數據按照從小到大或者從大到小的順序再放到一個數組中。例如上面的[2]、[6]合并到一個數組中是[2，6]，[1]、[0]合并到一個數組中是[0，1]，然后再將[2，6]和[0，1]合并到一個數組中，即為[0，1，2，6]。

具體而言，歸并排序算法的原理如下：對于給定的一組記錄(假設共有n個記錄)，首先將數組中的元素兩兩分組，得到n/2(向上取整)個長度為2或1的有序子序列，對每個分組中的元素進行排序，再將其兩兩歸并，反復執(zhí)行此過程，直到得到一個有序序列為止。

對于本題而言，一趟掃描后的結果為：

3.

設有關鍵碼序列(Q，H，C，Y，Q，A，M，S，R，D，F，X)，按照關鍵碼值遞增的次序進行排序，若采用初始步長為4的Shell的排序法，則一趟掃描的結果是______；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結果是______。正確答案：QACSQFXRHMY、FHCDQAMQRSYX。[解析]希爾排序也稱為“縮小增量排序”，它的基本原理如下：首先將待排序的元素分成多個子序列，使得每個子序列的元素個數相對較少，對各個子序列分別進行直接插入排序，待整個待排序序列“基本有序”后，再對所有元素進行一次直接插入排序。當步長為4時，一趟掃描排序的過程如圖所示。

一趟掃描排序過程

快速排序是一種非常高效的排序算法，它采用“分而治之”的思想，把大的拆分為小的，小的再拆分為更小的。其原理如下：對于一組給定的記錄，先選取一個分界的元素，然后通過一趟排序后，將原序列分為三部分：數組前半部分、分界元素和數組后半部分。其中數組前半部分的所有記錄均比分界元素小，數組后半部分元素均比分界元素大。遞歸該過程，直到序列中的所有記錄均有序為止。

一趟快速排序的實現方法如下：首先確定分界元素pivotkey，接著用兩個指針low和high，它們分別指向待排序數組首尾元素。然后從high所指的位置起向前搜索找到第一個小于pivotkey的元素與pivotkey交換，然后從low開始向右搜索找到第一個大于pivotkey的元素與pivotkey交換，重復這兩個步驟，直到low==high為止。

根據這個思路可以很容易得到一趟排序后的結果為FHCDQ