Java程序員面試分類真題13一、單項(xiàng)選擇題1.

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

對(duì)于選項(xiàng)B，Shell排序雖不需要交換數(shù)據(jù)，但也要進(jìn)行幾次插入排序。

對(duì)于選項(xiàng)C，歸并排序雖不需要交換數(shù)據(jù)，但也要進(jìn)行l(wèi)ogn次合并。

對(duì)于選項(xiàng)D，快速排序在數(shù)列有序的情況下效率是最低的。

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

2.

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

所以，本題的答案為B。

3.

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

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

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

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

所以，本題的答案為A。

4.

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

5.

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

6.

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

7.

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

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

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

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

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

本題中，數(shù)組序列共11個(gè)數(shù)據(jù)元素，第一次比較下標(biāo)為10/2=5的元素32。第二次比較下標(biāo)為4/2=2的元素15，得到要查找的數(shù)。

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

8.

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

9.

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

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

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

所以，本題答案為B。

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

1)每塊的理想長(zhǎng)度是多少?

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

3)平均查找長(zhǎng)度是多少?

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

分塊查找的平均查找長(zhǎng)度包括索引表和分塊內(nèi)的兩部分之和，即索引表+塊中。

假設(shè)線性表長(zhǎng)n，均勻分成m塊，每塊中記錄個(gè)數(shù)s，則(其中符號(hào)表示上取整)，在等概率查找的前提下，如果約定在索引表中確定關(guān)鍵字所在的分塊也是順序查找，因?yàn)轫樞虿檎业钠骄檎议L(zhǎng)度為(L+1)/2，則ASL=(n/s+s)/2+1。當(dāng)s=sqrt(n)時(shí)，該和值有極小值：sqrt(n)+1。

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

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

10.

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

定義二叉樹中的結(jié)點(diǎn)總數(shù)為n，當(dāng)每個(gè)結(jié)點(diǎn)只有一棵子樹的時(shí)候，其高度值最大，為n。當(dāng)該二叉樹為完全二叉樹時(shí)，其高度值最小，為(其中符號(hào)表示取下整)，其他情況的二叉樹的高度都是介于這兩個(gè)值之間，即，不大于最大值也不小于最小值。

本題中要想求二叉樹的最小高度，那么此時(shí)該二叉樹為完全二叉樹，其對(duì)應(yīng)的高度為。所以，選項(xiàng)B正確。

11.

一棵有12個(gè)結(jié)點(diǎn)的完全二叉樹，其深度為______。A.4B.5C.3D.6正確答案：A

12.

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

通過完全二叉樹的定義，可以引出以下兩種性質(zhì)：①對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱為完全二叉樹；②一棵二叉樹至多只有最下面兩層上的結(jié)點(diǎn)的度數(shù)可以小于2，并且最下層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹為完全二叉樹。

假設(shè)n0是度為0的結(jié)點(diǎn)總數(shù)(即葉子結(jié)點(diǎn)數(shù))，n1是度為1的結(jié)點(diǎn)總數(shù)，n2是度為2的結(jié)點(diǎn)總數(shù)，由二叉樹的性質(zhì)可知：n0=n2+1，n=n0+n1+n2(其中n為完全二叉樹的結(jié)點(diǎn)總數(shù))，由上述公式把n2消去得n=2n0+n1-1，由于完全二叉樹中度為1的結(jié)點(diǎn)數(shù)只有兩種可能：0或1，由此得到n0=(n+1)/2或n0=n/2，即?？筛鶕?jù)完全二叉樹的結(jié)點(diǎn)總數(shù)計(jì)算出葉子結(jié)點(diǎn)數(shù)。

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

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

100個(gè)結(jié)點(diǎn)時(shí)，二叉樹高度為7。

7層包含數(shù)據(jù)個(gè)數(shù)為100-(2^6-1)=37。

6層包含數(shù)據(jù)的編號(hào)為32～63，6層中前19個(gè)數(shù)據(jù)包含子樹(37/2=18.5)，故最小的葉結(jié)點(diǎn)應(yīng)該為32+19=51。所以，選項(xiàng)C正確。

13.

已知一棵二叉樹，如果先序遍歷的結(jié)點(diǎn)順序?yàn)锳DCEFGHB，中序遍歷的結(jié)點(diǎn)順序?yàn)閏DFEGHAB，則后序遍歷的結(jié)點(diǎn)順序?yàn)開_____。A.CFHGEBDAB.CDFEGHBAC.FGHCDEBAD.CFHGEDBA正確答案：D[解析]要解答出本題，首先需要對(duì)各種遍歷方式有一個(gè)清晰的認(rèn)識(shí)?？梢酝ㄟ^圖1來介紹二叉樹的三種遍歷方式的區(qū)別。

圖1

二叉樹的遍歷方式

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

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

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

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

圖2

二叉樹的遍歷

所以，本題的答案為D。

14.

有以下二叉樹：

對(duì)其進(jìn)行后序遍歷的結(jié)果是______。A.丙乙丁甲戊己B.甲乙丙丁戊己C.丙丁乙己戊甲D.丙丁己乙戊甲正確答案：C

15.

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

16.

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

(1)S為根

此時(shí)可以構(gòu)建2種不同的二叉樹。

二叉樹結(jié)構(gòu)如圖1所示。

圖1

S為根的二叉樹

(2)Y為根

此時(shí)可以構(gòu)建1種二叉樹。

二叉樹結(jié)構(gòu)如圖2所示。

圖2

Y為根的二叉樹

(3)Z為根

此時(shí)可以構(gòu)建2種不同的二叉樹。

二叉樹結(jié)構(gòu)如圖3所示。

圖3

Z為根的二叉樹

所以，一共可以構(gòu)建2+1+2=5種不同的二叉樹。所以，選項(xiàng)D正確。

17.

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

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

18.

對(duì)于一棵排序二叉樹，可以得到有序序列的遍歷方式是______遍歷。A.前序B.中序C.后序D.都可以正確答案：B[解析]排序二叉樹的特點(diǎn)為：對(duì)于一個(gè)結(jié)點(diǎn)而言，所有左子樹結(jié)點(diǎn)元素的值都小于這個(gè)結(jié)點(diǎn)元素的值，所有右子樹結(jié)點(diǎn)的元素的值都大于這個(gè)結(jié)點(diǎn)元素的值，且左右子樹都是排序二叉樹。由于中序遍歷的順序?yàn)樽笞訕?、根、右子樹，顯然，中序遍歷得到的序列是有序的。所以，選項(xiàng)B正確。

19.

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

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

對(duì)于選項(xiàng)A，二叉搜索樹的好壞與關(guān)鍵碼的個(gè)數(shù)沒有直接關(guān)系。所以，選項(xiàng)A錯(cuò)誤。

對(duì)于選項(xiàng)C與選項(xiàng)D，如果所有結(jié)點(diǎn)的左孩子(右孩子)都為空，那么查找效率與線性查找相同，都為O(n)。所以，選項(xiàng)C與選項(xiàng)D錯(cuò)誤。

20.

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

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

二叉樹中的后序遍歷也叫作后根遍歷，遵循的原則為“左右根”，即首先遍歷左子樹結(jié)點(diǎn)，再遍歷右子樹結(jié)點(diǎn)，最后遍歷根結(jié)點(diǎn)。從后序遍歷序列可知，結(jié)點(diǎn)e之后緊跟結(jié)點(diǎn)a，可得結(jié)論：③當(dāng)結(jié)點(diǎn)e為結(jié)點(diǎn)a的左孩子時(shí)，結(jié)點(diǎn)a有且僅有結(jié)點(diǎn)e一個(gè)孩子。從結(jié)論①②③可知根結(jié)點(diǎn)的孩子有且僅有e。

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

本題的兩種情況

但無論是以上哪一種情況，都可以看出根結(jié)點(diǎn)的孩子結(jié)點(diǎn)只有e。

通過以上分析可知，選項(xiàng)A是正確的。

21.

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

22.

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

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

假設(shè)n1為二叉樹T中度為1的結(jié)點(diǎn)數(shù)，因?yàn)槎鏄渲兴薪Y(jié)點(diǎn)的度都小于或等于2，所以，其結(jié)點(diǎn)總數(shù)為

n=n0+n1+n2

(1)

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

n=n1+2n2+1

(2)

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

本題中，由于己知葉子結(jié)點(diǎn)數(shù)為20，即n0的值為20，所以，n2的值就為19，選項(xiàng)D正確。

23.

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

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

24.

一棵二叉樹有1000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度是______。A.9B.10C.11D.12正確答案：B

25.

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

26.

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

27.

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

A．

B．

C．

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

28.

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

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

29.

具有n個(gè)頂點(diǎn)的有向圖最多有______條邊。A.nB.n(n-1)C.n(n+1)D.n^2正確答案：B[解析]如果圖中的每條邊都是有方向的，則稱為有向圖。在一個(gè)有向圖中，邊是由兩個(gè)頂點(diǎn)組成的有序?qū)Γ行驅(qū)νǔＳ眉饫ㄌ?hào)表示，例如＜vi,vj＞表示一條有向邊，其中vi是邊的始點(diǎn)，vj是邊的終點(diǎn)。在有向圖中，＜vi,vj＞和＜vi,vj＞代表兩條不同的有向邊。

在有向圖中，任意兩個(gè)結(jié)點(diǎn)之間都可以形成一對(duì)有向邊，因此，對(duì)于具有n個(gè)頂點(diǎn)的有向圖，其邊的條數(shù)為n(n-1)。所以，選項(xiàng)B正確。

30.

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

31.

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

32.

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

33.

在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)vi在頂點(diǎn)vj之前，則下列情況下不可能出現(xiàn)的是______。A.G中有弧＜vi,vj＞B.G中有一條從vi到vj的路徑C.G中沒有?。紇i,vj＞D.G中有一條從vj到vi的路徑正確答案：D

34.

判斷有向圖是否存在回路，最好的方法是______。A.拓?fù)渑判駼.求最短路徑C.求關(guān)鍵路徑D.廣度優(yōu)先遍歷正確答案：A[解析]針對(duì)有向圖是否存在回路的問題，最好的方法就是對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，如果有向圖的所有頂點(diǎn)可以排出拓?fù)湫蛄?，則該有向圖無環(huán)路。具體步驟如下：

在求拓?fù)渌惴ǖ倪^程中，最重要的是要維護(hù)一個(gè)入度為0的頂點(diǎn)的集合，每次從這個(gè)集合中取出一個(gè)頂點(diǎn)，放入保存拓?fù)浣Y(jié)構(gòu)結(jié)果的列表中，然后從圖中刪除從這個(gè)頂點(diǎn)引出的所有邊，在刪除這些邊后，這個(gè)邊的另外一個(gè)結(jié)點(diǎn)，如果入度變成0，則加入到存放入度為0的結(jié)點(diǎn)的集合中。依次類推，直到把所有頂點(diǎn)都遍歷完成，就求出了拓?fù)浣Y(jié)構(gòu)。如果在求解的過程中，存放入度為0的集合為空，但是此時(shí)圖中還有沒有遍歷的邊，則說明圖中至少存在一個(gè)回路。所以，選項(xiàng)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＞}，對(duì)該圖進(jìn)行深度優(yōu)先排序，得到的頂點(diǎn)序列正確的是______。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)先遍歷類似于樹的前序遍歷。假設(shè)給定無向圖G的初態(tài)是所有頂點(diǎn)均未曾被訪問過，深度優(yōu)先遍歷過程是這樣的：在無向圖G中任選一個(gè)頂點(diǎn)v為初始出發(fā)點(diǎn)(源點(diǎn))，首先訪問源點(diǎn)v，并將其標(biāo)記為已訪問過，然后，依次從源點(diǎn)v出發(fā)，搜索源點(diǎn)v的每個(gè)相鄰結(jié)點(diǎn)w。如果結(jié)點(diǎn)w未曾被訪問過，那么以結(jié)點(diǎn)w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)(亦稱為從源點(diǎn)可達(dá)的頂點(diǎn))均已被訪問為止。如果此時(shí)圖中仍有未訪問的頂點(diǎn)，則另選一個(gè)尚未訪問的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)均已被訪問為止。

本題中，按照上述方法可知，選項(xiàng)D正確。

36.

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

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

37.

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

所以，本題的答案為A。

結(jié)論1：一個(gè)有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有n(n-1)條邊，最少有n條邊。

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

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

可以通過數(shù)學(xué)歸納法進(jìn)行證明。有興趣的讀者可以自行驗(yàn)證。

引申：若一個(gè)非連通的無向圖最多有28條邊，則該無向圖至少有多少個(gè)頂點(diǎn)?

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

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

38.

對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接表數(shù)據(jù)結(jié)構(gòu)表示，則存放表頭結(jié)點(diǎn)的數(shù)組大小為______。A.nB.n+1C.n-1D.n+邊數(shù)正確答案：A[解析]無向圖指的是邊沒有方向的圖。采用鄰接表表示的無向圖，存放表頭結(jié)點(diǎn)的數(shù)組的大小為圖的頂點(diǎn)個(gè)數(shù)。本題中，無向圖的頂點(diǎn)個(gè)數(shù)為n，所以，存放表頭結(jié)點(diǎn)的數(shù)組大小為n，選項(xiàng)A正確。

39.

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

40.

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

41.

在一個(gè)無向圖中，若兩個(gè)頂點(diǎn)之間的路徑長(zhǎng)度為k，則該路徑上的頂點(diǎn)數(shù)為______。A.kB.k+1C.k+2D.2k正確答案：B

二、多項(xiàng)選擇題1.

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

1)結(jié)點(diǎn)是紅色或黑色。

2)根結(jié)點(diǎn)是黑色。

3)每個(gè)葉子結(jié)點(diǎn)(空結(jié)點(diǎn))是黑色的。

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

5)從任一結(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)。

所以，紅黑樹是二叉樹。所以，選項(xiàng)A正確。

對(duì)于選項(xiàng)B，B樹是一種平衡的多叉樹。所以，選項(xiàng)B不正確。

對(duì)于選項(xiàng)C，AVL樹是平衡二叉樹。所以，選項(xiàng)C正確。

對(duì)于選項(xiàng)D，B+樹是一種樹數(shù)據(jù)結(jié)構(gòu)，是一個(gè)n叉樹，每個(gè)結(jié)點(diǎn)通常有多個(gè)孩子，一棵B+樹包含根結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)和葉子結(jié)點(diǎn)。根結(jié)點(diǎn)可能是一個(gè)葉子結(jié)點(diǎn)，也可能是一個(gè)包含兩個(gè)或兩個(gè)以上孩子結(jié)點(diǎn)的結(jié)點(diǎn)。所以，選項(xiàng)D不正確。

所以，本題的答案為AC。

2.

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

對(duì)于選項(xiàng)A，完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在使用的時(shí)候堆是采用數(shù)組來存儲(chǔ)的，因此，它滿足完全二叉樹的特點(diǎn)。所以，選項(xiàng)A正確。

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

對(duì)于選項(xiàng)C，排序二叉樹有如下性質(zhì)：

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

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

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

4)沒有鍵值相等的結(jié)點(diǎn)。

顯然，堆不滿足這個(gè)性質(zhì)。所以，選項(xiàng)C不正確。

對(duì)于選項(xiàng)D，滿二叉樹是指樹中除最后一層無任何子結(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹。滿二叉樹中結(jié)點(diǎn)的個(gè)數(shù)為1，3，7等特殊的數(shù)字，而堆中的結(jié)點(diǎn)可以是任意的，因此，不能保證堆是個(gè)滿二叉樹。所以，選項(xiàng)D不正確。

所以，本題的答案為AB。

3.

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

1)每個(gè)內(nèi)部結(jié)點(diǎn)有兩個(gè)或三個(gè)子結(jié)點(diǎn)。

2)所有的葉子結(jié)點(diǎn)到根的路徑長(zhǎng)度相同。

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

本題的兩種結(jié)構(gòu)

所以，本題的答案為BE。

三、填空題1.

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

2.

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

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

對(duì)于本題而言，一趟掃描后的結(jié)果為：

3.

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

一趟掃描排序過程

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

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

根據(jù)這個(gè)思路可以很容易得到一趟排序后的結(jié)果為FHCDQ