Java程序員面試分類真題12

Java程序員面試分類真題12(總分：100.00，做題時間：120分鐘)一、單項選擇題(總題數(shù)：30，分?jǐn)?shù)：60.00)1.

在主存和CPU之間增加Cache的目的是______。

（分?jǐn)?shù)：2.00）

A.增加內(nèi)存容量

B.為程序員編程提供方便

C.解決CPU與內(nèi)存間的速度匹配問題

√

D.提高內(nèi)存工作的可靠性解析：計算機的存儲系統(tǒng)由主存、外存和Cache(緩存)組成。Cache存取速度快、容量小，它存儲的內(nèi)容是主存中經(jīng)常被訪問的程序和數(shù)據(jù)的剮本。通過Cache可以提高計算機的運行速度，解決CPU與內(nèi)存之問的速度匹配問題。所以，選項C正確。

對于選項A、選項B和選項D，其描述內(nèi)容均不是Cache的目的。所以，選項A、選項B和選項D錯誤。2.

在多級存儲體系中，“cache-主存”結(jié)構(gòu)的作用是解決______。

（分?jǐn)?shù)：2.00）

A.主存容量不足

B.輔存與CPU速度不匹配

C.主存與輔存速度不匹配

D.主存與CPU速度不匹配

√解析：3.

對于順序存儲的線性數(shù)組，訪問結(jié)點和增加結(jié)點、刪除結(jié)點的時間復(fù)雜度分別為______。

（分?jǐn)?shù)：2.00）

A.A.O(n)，O(n)

B.B.O(n)，O(1)

C.C.O(1)，O(n)

√

D.D.O(1)，O(1)

E.解析：對于線性數(shù)組，它支持隨機訪問，因此，訪問結(jié)點的時間復(fù)雜度為O(1)，增加結(jié)點、刪除結(jié)點的時候需要移動新增結(jié)點或待刪除結(jié)點后面的元素，因此，時間復(fù)雜度為O(n)。所以，選項C正確。4.

在有n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是______。

（分?jǐn)?shù)：2.00）

A.訪問第i個結(jié)點(1＜=i＜=n)和求第i個結(jié)點的直接前驅(qū)(2＜=i＜=n)

√

B.在第i個結(jié)點后插入一個新結(jié)點(1＜=i＜=n)

C.刪除第i個結(jié)點(1＜=i＜=n)

D.將n個結(jié)點從小到大排序解析：線性表也叫順序表，在線性表中的數(shù)據(jù)元素，其關(guān)系是一一對應(yīng)的，即除了第一個數(shù)據(jù)元素和最后一個數(shù)據(jù)元素之外，其他數(shù)據(jù)元素都是首尾相接的。

本題中，對于選項A，線性表是隨機存取結(jié)構(gòu)，當(dāng)對其執(zhí)行插入和刪除操作時，只要不是針對最后一個元素，此時都需要進行元素的搬家，最壞情況下的時間復(fù)雜度是O(n)。因此，訪問第i個結(jié)點(1＜=i＜=n)和求第i個結(jié)點的直接前驅(qū)(2＜=i＜=n)，其時間復(fù)雜度都為O(1)。所以，選項A正確。

對于選項B和選項C，由于插入和刪除操作都需要移動元素，此時算法的時間復(fù)雜度為O(n)，它與題目要求的O(1)的時間復(fù)雜度不相符。所以，選項B與選項C錯誤。

對于選項D，將n個結(jié)點從小到大排序的時間復(fù)雜度通常介于O(n)與O(n^2)之間，它與題目要求的O(1)的時間復(fù)雜度不相符。所以，選項D錯誤。5.

二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于其存儲結(jié)構(gòu)的描述中，正確的是______。

（分?jǐn)?shù)：2.00）

A.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲

B.它不能用順序存儲結(jié)構(gòu)存儲

C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用

D.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲

√解析：二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，即每個數(shù)據(jù)結(jié)點至多只有一個前驅(qū)，但可以有多個后繼，可以使用順序存儲和鏈?zhǔn)酱鎯煞N結(jié)構(gòu)來存儲。以下將分別對這兩種存儲結(jié)構(gòu)進行介紹。

(1)順序存儲結(jié)構(gòu)

二叉樹的順序存儲指的是用元素在數(shù)組中的下標(biāo)表示一個結(jié)點與其孩子和父結(jié)點的關(guān)系。這種結(jié)構(gòu)特別適用于近似滿二叉樹。這種方法的缺點是可能會有大量空間的浪費，在最壞的情況下，一個深度為k且只有k個結(jié)點的右單支樹需要2^k-1個結(jié)點存儲空間。圖1和圖2分別給出完全二叉樹和非完全二叉樹的存儲示意圖。

圖1

完全二叉樹的存儲方式

圖2

非完全二叉樹的存儲方式

(2)鏈?zhǔn)酱鎯Y(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用鏈表來表示一棵二叉樹。

每個結(jié)點有一個數(shù)據(jù)域，兩個指針域分別指向左孩子和右孩子。其結(jié)點結(jié)構(gòu)為：lchicddatarchild

圖3給出了一個二叉樹的鏈表存儲方式。

圖3

鏈表存儲方式

通過上面的分析可知，選項D正確。6.

線性表如果要頻繁地執(zhí)行插入和刪除操作，該線性表采取的存儲結(jié)構(gòu)應(yīng)該是______。

（分?jǐn)?shù)：2.00）

A.散列

B.順序

C.鏈?zhǔn)?/p>

√

D.索引解析：線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

鏈?zhǔn)酱鎯Y(jié)構(gòu)又叫鏈接存儲結(jié)構(gòu)，在計算機中用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)。它不要求邏輯上相鄰的元素在物理位置上也相鄰。因此，它沒有順序存儲結(jié)構(gòu)所具有的弱點，但也同時失去了順序表可隨機存取的優(yōu)點。

鏈?zhǔn)酱鎯Y(jié)構(gòu)有以下5個特點：

1)比順序存儲結(jié)構(gòu)的存儲密度小(每個結(jié)點都由數(shù)據(jù)域和指針域組成，所以，相同空間內(nèi)假設(shè)全存滿，則鏈?zhǔn)酱鎯Ρ软樞虼鎯λ艽鎯Φ臄?shù)據(jù)少)。

2)邏輯上相鄰的結(jié)點物理上不必相鄰。

3)插入、刪除靈活(不必移動結(jié)點，只要改變結(jié)點中的指針)。

4)查找結(jié)點時鏈?zhǔn)酱鎯σ软樞虼鎯β?/p>

5)每個結(jié)點由數(shù)據(jù)域和指針域組成。

鏈?zhǔn)浇Y(jié)構(gòu)的插入和刪除操作只需要修改插入和刪除結(jié)點以及其前驅(qū)結(jié)點的指針域即可，而順序存儲結(jié)構(gòu)在插入和刪除操作的時候需要執(zhí)行大量數(shù)據(jù)的移動操作。由此可以看出，順序表適合隨機訪問，不適合插入和刪除操作，而鏈?zhǔn)奖磉m合插入和刪除操作，不適合隨機訪問操作。散列表適合查找運算，索引表在插入和刪除的時候還需要修改索引表，由此鏈?zhǔn)奖碜钸m合插入和刪除操作。所以，選項C正確。7.

鏈表要求元素的存儲地址______。

（分?jǐn)?shù)：2.00）

A.必須連續(xù)

B.部分連續(xù)

C.必須不連續(xù)

D.連續(xù)與否均可

√解析：鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(鏈表中每一個元素稱為結(jié)點)組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。由此可見，可以通過結(jié)點的指針域找到下一個結(jié)點，存儲地址是否連續(xù)并不重要。所以，選項A、選項B和選項C錯誤，選項D正確。

需要注意的是，數(shù)組與鏈表不同，對數(shù)組的訪問是通過數(shù)組的下標(biāo)來實現(xiàn)的，所以，對于數(shù)組而言，存儲地址必須是連續(xù)的。

所以，本題的答案為D。8.

以鏈接方式存儲的線性表(x1、x2、...、Xn)，訪問第i個元素的時間復(fù)雜度為______。

（分?jǐn)?shù)：2.00）

A.O(1)

B.O(n)

√

C.O(logn)

D.O(n^2)解析：單鏈表查找的時候從頭結(jié)點開始一直找下一個結(jié)點，如果要查找的元素在最后，就相當(dāng)于找了n次，所以，時間復(fù)雜度為O(n)。所以，選項B正確。9.

從表中任意一個結(jié)點出發(fā)可以依次訪問到表中其他所有結(jié)點的結(jié)構(gòu)是______。

（分?jǐn)?shù)：2.00）

A.線性單鏈表

B.雙向鏈表

C.循環(huán)鏈表

√

D.線性鏈表解析：對于選項A，單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素(數(shù)據(jù)元素的映象)+指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。根據(jù)定義可知，單鏈表中中間部分出發(fā)只能訪問結(jié)點的后續(xù)結(jié)點。因此，選項A錯誤。

對于選項B，雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。但是從中間結(jié)點出發(fā)只能訪問所有的后繼結(jié)點，或者只能訪問所有的前驅(qū)結(jié)點。因此，選項B錯誤。

對于選項C，循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)(鏈表最后一個結(jié)點的指針域指向鏈表的首結(jié)點)。它的特點是可以從任意結(jié)點出發(fā)依次訪問所有結(jié)點。因此，選項C正確。

對于選項D，線性鏈表是一個更大的概念，單鏈表、雙向鏈表都可以看作是一種線性表。因此，選項D錯誤。

所以，本題的答案為C。10.

以下關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的描述中，錯誤的是______。

（分?jǐn)?shù)：2.00）

A.查找結(jié)點時鏈?zhǔn)酱鎯Ρ软樞虼鎯?/p>

√

B.每個結(jié)點由數(shù)據(jù)域和指針域組成

C.比順序存儲結(jié)構(gòu)的存儲密度小

D.邏輯上不相鄰的結(jié)點物理上可能相鄰解析：鏈?zhǔn)酱鎯Y(jié)構(gòu)又叫鏈接存儲結(jié)構(gòu)，指的是在計算機中用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)。它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此，它沒有順序存儲結(jié)構(gòu)所具有的缺點，但同時它也失去了順序表可隨機存取的優(yōu)點。

具體而言，鏈?zhǔn)酱鎯Y(jié)構(gòu)具有以下幾個特點：

1)每個結(jié)點都是由數(shù)據(jù)域和指針域組成的。

2)它比順序存儲結(jié)構(gòu)的存儲密度小。由于鏈?zhǔn)酱鎯Y(jié)構(gòu)的每個結(jié)點都是由數(shù)據(jù)域和指針域組成，所以，在相同空間內(nèi)，順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的元素更多。

3)邏輯上相鄰的結(jié)點物理上不必相鄰。

4)插入結(jié)點、刪除結(jié)點靈活，原因在于此時它不必移動結(jié)點，只要改變結(jié)點中的指針即可。

5)當(dāng)查找結(jié)點時，鏈?zhǔn)酱鎯σ软樞虼鎯β?/p>

通過上面的分析可知，選項B與選項C正確，選項A錯誤。

對于選項D，因為對于鏈?zhǔn)酱鎯Y(jié)構(gòu)，數(shù)據(jù)的邏輯關(guān)系與物理關(guān)系沒有直接關(guān)系，邏輯上相鄰的結(jié)點在物理上可能相鄰也可能不相鄰，而邏輯上不相鄰的結(jié)點在物理上也是有可能相鄰也有可能不相鄰。所以，選項D正確。

所以，本題的答案為A。11.

如果用數(shù)組S[0...n]作為兩個棧S1和S2的存儲結(jié)構(gòu)，對任何一個棧，只有當(dāng)S全滿時才不能做入棧操作，那么為S1、S2這兩個棧分配空間的最佳方案是______。

（分?jǐn)?shù)：2.00）

A.S1的棧底位置為0，S2的棧底位置為n+1

√

B.S1的棧底位置為1，S2的棧底位置為n/2

C.S1的棧底位置為0，S2的棧底位置為n/2

D.S1的棧底位置為1，S2的棧底位置為n+1解析：棧是一個后進先出、先進后出的數(shù)據(jù)結(jié)構(gòu)，當(dāng)采用選項A的方案時，兩個棧的棧底位置分別設(shè)在了存儲空間的兩端，棧項各自向中間延伸，兩個棧的空間就可以相互調(diào)節(jié)，充分共享所有的存儲空間，互補余缺，只有在整個存儲空間被占滿時，才會發(fā)生上溢，這樣產(chǎn)生上溢的概率要小得多。所以，選項A正確。

如果采用選項B或者選項C的方案，相當(dāng)于把數(shù)組平均分配給兩個棧，各自有獨立的存儲空間，即使當(dāng)棧s2為空的時候，棧s1最多能存放的元素個數(shù)為n/2。所以，選項B、選項C錯誤。

對于選項D，s1的棧底位置設(shè)置不正確，所以，選項D錯誤。

所以，本題的答案為A。12.

一個棧的入棧序列是ABCDE，則該棧的出棧序列不可能是______。

（分?jǐn)?shù)：2.00）

A.EDCBA

B.DECBA

C.DCEAB

√

D.ABCDE解析：棧是一個后進先出的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)這個特點進行分析。

對于選項A，可以把字符A、B、C、D、E按順序入棧，然后出棧，此時就可以得到選項A中的序列。所以，選項A正確。

對于選項B，由于序列第一個元素為字符D，那么肯定需要先把字符A、B、C、D入棧，然后，字符D出棧得到第一個元素字符D，由于序列的下一個元素為字符E，所以，下一步需要把字符E入棧再出棧，此時就可以得到字符E，接下來棧中的元素依次出棧得到序列CBA。所以，選項B正確。

對于選項C，序列第一個元素為字符D，那么肯定需要先把字符A、B、C、D入棧，然后字符D出棧得到第一個元素字符D，由于第二個元素為字符C，那么下一步字符C出棧得到序列DC，接下來序列為E，那么需要把字符E入棧再出棧得到字符E，此時棧中字符A在棧底，字符B在棧頂，只能得到出棧序列BA，而無法得到序列AB。因此，不可能得到輸出序列DCEAB。所以，選項C錯誤。

對于選項D，字符A、B、C、D、E五個元素每個元素入棧后就馬上出棧，此時就可以得到這個序列。所以，選項D正確。

所以，本題的答案為C。13.

如果讓元素a、b、c依次進棧，那么出棧次序不可能是______。

（分?jǐn)?shù)：2.00）

A.c，a，b

√

B.b，a，c

C.c，b，a

D.a，c，b解析：14.

往一個棧中順序push下列元素：ABCDE，其pop可能的序列中，不可能存在的情況是______。

（分?jǐn)?shù)：2.00）

A.BACDE

B.ACDBE

C.AEBCD

√

D.AEDCB解析：15.

如果入棧序列是a1，a3，a5，a2，a4，a6，出棧序列是a5，a4，a2，a6，a3，a1，那么棧的容量最小是______。

（分?jǐn)?shù)：2.00）

A.2

B.3

C.4

√

D.5解析：本題解題的關(guān)鍵是了解棧的后進先出的性質(zhì)。

通過入棧序列與出棧序列可以模擬一下其具體的出棧與入棧過程，過程如下：

第一步：a1進棧，此時棧中元素為1。

第二步：a3進棧，此時棧中元素為2。

第三步：a5進棧，此時棧中元素為3。

第四步：根據(jù)進棧出棧順序，a5出棧，a2進棧，此時棧中元素為3。

第五步：a4進棧，此時棧中元素為4。

第六步：根據(jù)進棧出棧順序，a4出棧，此時棧中元素為3。

第七步：根據(jù)進棧出棧順序，a2出棧，此時棧中元素為2。

第八步：a6進棧，此時棧中元素為3。

第九步：根據(jù)進棧出棧順序，a6出棧，此時棧中元素為2。

第十步：根據(jù)進棧出棧順序，a3出棧，此時棧中元素為1。

第十一步：根據(jù)進棧出棧順序，a1出棧，此時棧中元素為0。

由以上分析可知，棧中元素最多的時候為4個，所以，棧容量至少為4，選項C正確。16.

采用順序存儲的棧，執(zhí)行入棧運算，棧頂指針的變化是______。

（分?jǐn)?shù)：2.00）

A.top++

√

B.top--

C.不變

D.(top++)++解析：棧是一種特殊的線性表，在實現(xiàn)的時候可以把順序表的頭看作棧底。棧頂索引top指向棧頂?shù)南乱粋€位置，初始化top=0，每次壓棧操作：首先，向索引為top的位置放入入棧的元素，然后，top+1，由此可見，入棧操作棧指針的變化為top++；而對于出棧操作，首先要判斷棧是否為空(top=0時棧為空)，如果不為空，則首先執(zhí)行top-1操作，然后再取出top所在位置的元素，此時指針的變化為--top。所以，選項A正確。17.

在循環(huán)隊列中，用數(shù)組A[0，m-1]存放隊列元素，其隊頭和隊尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)是______。

（分?jǐn)?shù)：2.00）

A.(front-rear+1)%m

B.(rear-front+1)%m

C.(front-rear+m)%m

D.(rear-front+m)%m

√解析：隊列是一種線性表，它只允許在表的前端(front)進行刪除操作，而在表的后端(rear)進行插入操作，進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

在循環(huán)隊列中，隊頭指向的是隊首元素的前一個位置，隊尾指向隊尾元素所在位置。循環(huán)隊列的front和rear必有一個不指向?qū)嵸|(zhì)元素，否則，無法判斷隊列滿或空。而且隊列頭的下標(biāo)有可能會小于隊列尾的下標(biāo)。所以，當(dāng)前隊列中的元素個數(shù)是(rear-froot+m)%m。所以，選項D正確。18.

下列情況中，不能使用棧(stack)來解決問題的是______。

（分?jǐn)?shù)：2.00）

A.將數(shù)學(xué)表達式轉(zhuǎn)換為后輟形式

B.實現(xiàn)遞歸算法

C.高級編程語言的過程調(diào)用

D.操作系統(tǒng)分配資源(例如CPU)

√解析：棧的性質(zhì)是先進先出。

對于選項A，后綴表達式指的是不包含括號，運算符放在兩個運算對象的后面，所有的計算按運算符出現(xiàn)的順序，嚴(yán)格從左向右進行(不再考慮運算符的優(yōu)先規(guī)則)，例如，對于表達式(2+1)*3，其后綴表達式為21+3*，通過定義可知，可以通過棧來實現(xiàn)。所以，選項A正確。

對于選項B，根據(jù)遞歸算法的性質(zhì)可知，可以通過棧來實現(xiàn)。所以，選項B正確。

對于選項C，根據(jù)過程調(diào)用的性質(zhì)可知，可以通過棧來實現(xiàn)。所以，選項C正確。

對于選項D，操作系統(tǒng)資源分配有多種分配策略，例如先到先執(zhí)行，此時就可以使用隊列來完成。

所以，選項D不正確。

所以，本題的答案為D。19.

以下關(guān)于排序算法的描述中，正確的是______。

（分?jǐn)?shù)：2.00）

A.快速排序的平均時間復(fù)雜度為O(nlogn)，最壞時間復(fù)雜度為O(nlogn)

B.堆排序的平均時間復(fù)雜度為O(nlogn)，最壞時間復(fù)雜度為O(n^2)

C.冒泡排序的平均時間復(fù)雜度為O(n^2)，最壞時間復(fù)雜度為O(n^2)

√

D.歸并排序的平均時間復(fù)雜度為O(nlogn)，最壞時間復(fù)雜度為O(n^2)解析：各種算法的性能見下表。各種排序算法的性能排序方法最好時間復(fù)雜度平均時間復(fù)雜度最壞時間復(fù)雜度輔助存儲穩(wěn)定性備注簡單選擇排序O(n^2)O(n^2)O(n^2)O(1)不穩(wěn)定n小時較好直接插入排序O(n)O(n^2)O(n^2)O(1)穩(wěn)定大部分已有序時較好冒泡排序O(n)O(n^2)O(n^2)O(1)穩(wěn)定n小時較好希爾排序O(n)O(nlogn)O(ns)1＜s＜2O(1)不穩(wěn)定s是所選分組快速排序O(nlogn)O(nlogn)O(n^2)O(logn)不穩(wěn)定n大時較好堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不穩(wěn)定n大時較好歸并排序O(nlogn)O(nlogn)O(nlogn)O(n)穩(wěn)定n大時較好

所以，本題的答案為C。20.

下列排序方法中，屬于穩(wěn)定排序的是______。

（分?jǐn)?shù)：2.00）

A.選擇排序

B.希爾排序

C.堆排序

D.歸并排序

√解析：所謂穩(wěn)定排序，指的是一個序列中的相同的元素在排序完畢之后，它們的順序仍然不會改變。反之，排序算法則是不穩(wěn)定的。

對于選項A，選擇排序是給每個位置選擇當(dāng)前元素最小的，比如給第一個位置選擇最小的，在剩余元素里面給第二個元素選擇第二小的，依次類推，直到第n-1個元素，第n個元素不用選擇了，因為只剩下它一個最大的元素了。例如，序列37329，第一遍選擇第1個元素3會和第4個元素2交換，那么原序列中兩個3的相對前后順序就被破壞了，所以，選擇排序不是一個穩(wěn)定的排序算法，選項A錯誤。

對于選項B，希爾排序是按照不同步長對元素進行插入排序，當(dāng)剛開始元素很無序的時候，步長最大，所以，插入排序的元素個數(shù)很少，速度很快；當(dāng)元素基本有序了，步長很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時間復(fù)雜度會比O(n^2)好一些。由于涉及多次插入排序，而一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以，希爾排序是不穩(wěn)定的，選項B錯誤。

對于選項C，堆的結(jié)構(gòu)是結(jié)點i的孩子為2*i和2*i+1結(jié)點，大頂堆要求父結(jié)點大于等于其2個子結(jié)點，小頂堆要求父結(jié)點小于等于其2個子結(jié)點。對于一個長為n的序列，堆排序的過程是從第n/2開始和其子結(jié)點共3個值選擇最大(大頂堆)或者最小(小頂堆)，這3個元素之間的選擇當(dāng)然不會破壞穩(wěn)定性。但當(dāng)為n/2-1，n/2-2，…，1這些父結(jié)點選擇元素時，就會破壞穩(wěn)定性。有可能第n/2個結(jié)點的父結(jié)點與它的孩子結(jié)點(假設(shè)這個結(jié)點的值為X)進行了交換，而第n/2-1個結(jié)點如果也有一個孩子結(jié)點的值為X，但是這個父結(jié)點沒有與孩子結(jié)點進行交換，那么這2個相同的元素之間的穩(wěn)定性就被破壞了。所以，堆排序不是穩(wěn)定的排序算法，選項C錯誤。

對于選項D，歸并排序是把序列遞歸地分成短序列，遞歸出口是短序列只有1個元素(認(rèn)為直接有序)或者2個序列(1次比較和交換)，然后把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序?？梢园l(fā)現(xiàn)，在1個或2個元素時，1個元素不會交換，2個元素如果大小相等也不會交換，這不會破壞穩(wěn)定性。那么，在短的有序序列合并的過程中，穩(wěn)定是否受到破壞?沒有，合并過程中，可以保證如果兩個當(dāng)前元素相等，則把處在前面的序列的元素保存在結(jié)果序列的前面，這樣就保證了穩(wěn)定性。所以，歸并排序是穩(wěn)定的排序算法，選項D正確。

所以，本題的答案為D。21.

排序算法的穩(wěn)定是指關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下面排序算法中，______是不穩(wěn)定的。

（分?jǐn)?shù)：2.00）

A.插入排序

B.冒泡排序

C.快速排序

√

D.歸并排序解析：22.

有字符序列(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，x)，那么新序列(F，H，C，D，P，A，M，Q，R，S，Y，X)是下列______算法一趟掃描結(jié)果。

（分?jǐn)?shù)：2.00）

A.堆排序

B.快速排序

√

C.希爾排序

D.冒泡排序解析：對于選項A，堆排序的思想是對于給定的n個記錄，初始時把這些記錄看作一棵順序存儲的二叉樹，然后將其調(diào)整為一個大頂堆，然后將堆的最后一個元素與堆頂元素(即二叉樹的根結(jié)點)進行交換后，堆的最后一個元素即為最大記錄；接著將前n-1個元素(即不包括最大記錄)重新調(diào)整為一個大頂堆，再將堆頂元素與當(dāng)前堆的最后一個元素進行交換后得到次大的記錄，重復(fù)該過程，直到調(diào)整的堆中只剩一個元素時為止，該元素即為最小記錄，此時可得到一個有序序列。

對于選項B，快速排序的原理如下：對于一組給定的記錄，首先，通過一趟排序后，將原序列分為兩部分，其中前半部分的所有記錄均比后半部分的所有記錄小，然后再依次對前后兩部分的記錄進行快速排序，遞歸該過程，直到序列中的所有記錄均有序為止。

對于選項C，希爾排序的實質(zhì)是分組插入排序，該方法又稱縮小增量排序，基本思想如下：先將整個待排元素序列分割成若干個子序列(由相隔某個“增量”的元素組成)，分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序(增量足夠小)時，再對全體元素進行一次直接插入排序。因此，直接插入排序在元素基本有序的情況下(接近最好情況)，效率是很高的。

對于選項D，冒泡排序的原理是臨近的數(shù)字兩兩進行比較，按照從小到大或者從大到小的順序進行交換，這樣一趟排序后，最大或最小的數(shù)字被交換到了最后一位，針對所有的元素重復(fù)以上的步驟，每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

所以，本題的答案為B。23.

快速排序算法在序列已經(jīng)有序的情況下的復(fù)雜度為______。

（分?jǐn)?shù)：2.00）

A.O(nlogn)

B.(n^2)

√

C.O(n)

D.O(n^2logn)解析：快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法?？焖倥判蛩惴ㄌ幚淼淖詈们闆r指每次都是將待排序列劃分為均勻的兩部分，通常認(rèn)為快速排序在平均情況下的時問復(fù)雜度為O(nlogn)。但是，如果初始記錄序列按關(guān)鍵字有序或基本有序，那么此時快速排序?qū)⑼懟癁槊芭菖判颍鋾r間復(fù)雜度為O(n^2)。

那么對于其他排序算法，當(dāng)序列已經(jīng)有序時，又是哪種情況呢?無論原始序列中的元素如何排列，歸并排序和堆排序算法的時間復(fù)雜度都是O(nlogn)。插入排序是將一個新元素插入已經(jīng)排列好的序列中。如果在數(shù)據(jù)已經(jīng)是升序的情況下，新元素只需插入到序列尾部，這就是插入排序的最好情況，此時，時間復(fù)雜度為O(n)。所以，選項B正確。24.

下列排序算法中，對一個list排序的最快方法是______。

（分?jǐn)?shù)：2.00）

A.快速排序

√

B.冒泡排序

C.二分插入排序

D.線性排序解析：對于選項A，需要注意的是，在C++語言中，list采用的是雙向列表來存儲的，因此，它比較適合用快速排序(快速排序不需要隨機的訪問元素)。此時的時間復(fù)雜度為O(nlogn)。所以，選項A正確。

對于選項B，冒泡排序也是對數(shù)據(jù)順序遍歷，不需要隨機訪問，因此，它也適合對list進行排序，但由于算法的時間復(fù)雜度為O(n^2)，沒有快速排序效率高。所以，選項B不正確。

對于選項C，首先需要弄清楚二分插入排序的基本思想。二分插入排序的基本思想如下：假設(shè)列表[0...n]被分成兩部分，其中一部分[0...i]為有序序列，另一部分[i+1...n]為無序序列，排序的過程為從無序序列中取一個數(shù)d，利用二分查找算法找到d在有序序列中的插入位置并插入。不斷重復(fù)上述步驟，直到無序序列中的元素全部插入有序序列，就完成了排序。由此可以看出，二分插入排序需要對列表中的元素進行隨機訪問，因此，它不適合對list進行排序。所以，選項C不正確。

對于選項D，只有當(dāng)被排序的元素滿足某種特定的條件的時候，線性排序算法才能有較好的性能。由于list有非常好的通用性，對任意的數(shù)據(jù)類型都能排序，因此，線性排序算法不適用對list進行排序。所以，選項D不正確。

所以，本題的答案為A。25.

用某種排序方法對關(guān)鍵字序列(25，84，21，47，15，27，68，35，20)進行排序，序列的變化情況如下所示：

(1)20，15，21，25，47，27，68，35，84

(2)15，20，21，25，35，27，47，68，84

(3)15，20，21，25，27，35，47，68，84

則采用的排序方法是______。

（分?jǐn)?shù)：2.00）

A.選擇排序

B.快速排序

√

C.希爾排序

D.歸并排序解析：讀者要想解答出本題，必須對各種排序算法的原理有著較為深刻的認(rèn)識。以下將分別對這幾種排序算法進行介紹與分析。

對于選項A，選擇排序是一種簡單直觀的排序算法，它的基本原理如下：對于給定的一組記錄，經(jīng)過第一輪比較后得到最小的記錄，然后將該記錄與第一個位置的記錄進行交換；接著對不包括第一個記錄以外的其他記錄進行第二輪比較，得到最小的記錄并與第二個記錄進行位置交換；重復(fù)該過程，直到進行比較的記錄只有一個時為止。

對于選項B，快速排序是一種非常高效的排序算法，它采用“分而治之”的思想，把大的拆分為小的，小的再拆分為更小的。其原理為：對于一組給定的記錄，通過一趟排序后，將原序列分為兩部分，其中前部分的所有記錄均比后部分的所有記錄小，然后再依次對前后兩部分的記錄進行快速排序，遞歸該過程，直到序列中的所有記錄均有序為止。

對于選項C，希爾排序也稱為“縮小增量排序”，它的基本原理如下：首先，將待排序的元素分成多個子序列，使得每個子序列的元素個數(shù)相對較少，對各個子序列分別進行直接插入排序，待整個待排序序列“基本有序后”，再對所有元素進行一次直接插入排序。希爾排序也是形成部分有序的序列。

對于選項D，歸并排序是利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成越來越小的子序列(子序列指的是在原來序列中找出一部分組成的序列)，再對子序列排序，最后再用遞歸步驟將排好序的子序列合并成為越來越大的有序序列。歸并排序會在第一趟結(jié)束后，形成若干個部分有序的予序列，并且長度遞增，直到最后的一個有序的完整序列。

本題中，很容易發(fā)現(xiàn)，第一個序列前4個數(shù)都小于等于25，而后5個數(shù)都大于25，很顯然滿足快速排序的方法，而且根據(jù)以上對各種排序算法的分析可知，選項B正確。26.

有字符序列{Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X}，則新序列{F，H，C，D，P，A，M，O，R，S，Y，X}是下列______算法一趟掃描的結(jié)果。

（分?jǐn)?shù)：2.00）

A.二路歸并排序

B.快速排序

√

C.步長為4的希爾排序

D.冒泡排序解析：27.

初始序列為{1，8，6，2，5，4，7，3}的一組數(shù)，采用堆排序的方法進行排序，當(dāng)建堆(小根堆)完畢時，堆所對應(yīng)的二叉樹的中序遍歷序列為______。

（分?jǐn)?shù)：2.00）

A.8，3，2，5，1，6，4，7

√

B.3，2，8，5，1，4，6，7

C.3，8，2，5，1，6，7，4

D.8，2，3，5，1，4，7，6解析：堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其每個結(jié)點都有一個值，通常提到的堆都是指一棵完全二叉樹。

堆排序是樹形選擇排序，在排序過程中，將R[1...N]看成是一棵完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。

堆一般分為大頂堆和小頂堆兩種不同的類型。對于給定n個記錄的序列(r(1)，r(2)，…，r(n))，當(dāng)且僅當(dāng)滿足條件(r(i)＞=r(2i)且r(i)＞=r(2i+1))時稱為大頂堆，此時，堆頂元素為最大值。對于給定n個記錄的序列(r(1)，r(2)，…，r(n))，當(dāng)且僅當(dāng)滿足條件(r(i)＜=r(2i)且r(i)＜=r(2i+1))時稱為小頂堆，此時，堆頂元素必為最小值。

以小頂堆為例：堆排序的思想是對于給定的n個記錄，初始時把這些記錄看作一棵順序存儲的二叉樹，然后將其調(diào)整為一個小頂堆，將堆的最后一個元素與堆頂元素(即二叉樹的根結(jié)點)進行交換后，堆的最后一個元素即為最小記錄；接著將前(n-1)個元素(即不包括最小記錄)重新調(diào)整為一個小頂堆，再將堆頂元素與當(dāng)前堆的最后一個元素進行交換后得到次小的記錄，重復(fù)該過程直到調(diào)整的堆中只剩一個元素時為止，該元素即為最大記錄，此時可得到一個有序序列。

堆排序主要包括兩個過程：一是構(gòu)建堆；二是交換堆頂元素與最后一個元素的位置。

建立小頂堆的方法為：從最后一個非葉子結(jié)點開始，找出這個結(jié)點、左孩子、右孩子的最小值與這個結(jié)點的值交換，由于交換可能會引起孩子結(jié)點不滿足小頂堆的性質(zhì)，所以，每次交換之后需要重新對被交換的孩子結(jié)點進行調(diào)整。對于題目所給的數(shù)組構(gòu)建小頂堆的過程如圖所示。

構(gòu)建小頂堆過程

由此可以得出，樹的中序遍歷序列為83251647。所以，選項A正確。28.

已知數(shù)組序列為{46、36、65、97、76、15、29}，以46為關(guān)鍵字進行一趟快速排序后，結(jié)果為______。

（分?jǐn)?shù)：2.00）

A.29、36、15、46、76、97、65

√

B.29、15、36、46、76、97、65

C.29、36、15、46、97、76、65

D.15、29、36、46、97、76、65解析：第一趟排序過程如下：

初始化關(guān)鍵字{46、36、65、97、76、15、29}。

第一次交換后：{29、36、65、97、76、15、46}(從右向左找到小于46的值并交換)。

第二次交換后：{29、36、46、97、76、15、65}(從左向右找到大于46的值并交換)。

第三次交換后：{29、36、15、97、76、46、65}(從右向左找到小于46的值并交換)。

第四次交換后：{29、36、15、46、

76、97、65}(從左向右找到大于46的值并交換)。

所以，選項A正確。29.

以下排序算法中，需要開辟額外的存儲空間的是______。

（分?jǐn)?shù)：2.00）

A.選擇排序

B.歸并排序

√

C.快速排序

D.堆排序解析：30.

下列排序方法中，輔助空間為O(n)的是______。

（分?jǐn)?shù)：2.00）

A.歸并排序

√

B.堆排序

C.選擇排序

D.希爾排序解析：二、多項選擇題(總題數(shù)：5，分?jǐn)?shù)：10.00)1.

以下操作中，數(shù)組比線性表速度更快的是______。

（分?jǐn)?shù)：2.00）

A.原地逆序

√

B.頭部插入

C.返回中間結(jié)點

√

D.返回頭部結(jié)點

E.選擇隨機結(jié)點

√解析：線性結(jié)構(gòu)的基本特征為：

1)集合中必然存在唯一的一個“第一元素”。

2)集合中必然存在唯一的一個“最后元素”。

3)除最后一個元素外，均有唯一的后繼。

4)除第一個元素外，均有唯一的前驅(qū)。

數(shù)組是隨機存取的，線性表是邏輯上連續(xù)但物理上分開存放的，因此，查詢、修改操作數(shù)組更快，但插入、刪除等操作線性表更快。所以，選項B與選項D錯誤，選項E正確。

對于選項A，當(dāng)需要進行原地逆序時，數(shù)組比線性表速度更快。對于數(shù)組的逆序，具體做法如下：定義兩個下標(biāo)，一個下標(biāo)i表示數(shù)組首元素，一個下標(biāo)j表示數(shù)組尾元素，交換i與j兩個位置的元素值，同時執(zhí)行++i，--i操作，一共需要經(jīng)過n/2次交換(n表示數(shù)組的長度)。而鏈表的逆序需要修改指針的指向，需要更多的操作。所以，選項A正確。

對于選項C，數(shù)組可以通過array[length/2]訪問中間結(jié)點，鏈表需要依次查找到中間結(jié)點，所以，數(shù)組比線性表更快。所以，選項C正確。

所以，本題的答案為ACE。2.

下列數(shù)據(jù)結(jié)構(gòu)中，同時具有較高的查找和刪除性能的是______。

（分?jǐn)?shù)：2.00）

A.有序數(shù)組

B.有序鏈表

C.AVL樹

√

D.Hash表

√解析：首先介紹常見的數(shù)據(jù)結(jié)構(gòu)的操作性能：

1)有序數(shù)組：查找的時候可以采用二分查找法，因此，查找的時間復(fù)雜度為O(logn)，其中，n表示數(shù)組序列的長度。由于數(shù)組中的元素在內(nèi)存中是順序存放的，因此，刪除數(shù)組中的一個元素后，數(shù)組中后面的元素就需要向前移動。在最壞的情況下，如果刪除數(shù)組中的第一個元素，那么數(shù)組中后面的n-1個元素都需要向前移動，移動操作的次數(shù)為n-1，因此，此時的時間復(fù)雜度為O(n)。插入操作與刪除操作類似，都需要數(shù)組中元素的移動，因此，其時間復(fù)雜度也為O(n)。

2)有序鏈表：鏈表(以單鏈表為例)的存儲特點為：每個結(jié)點的地址存儲在它的前驅(qū)結(jié)點的指針域中，對鏈表的遍歷只能從鏈表的首結(jié)點開始遍歷，因此，此時查找的時間復(fù)雜度為O(n)，其中，n表示鏈表的長度。對于刪除和插入操作，雖然刪除和插入操作的時間復(fù)雜度都為O(1)(因為不需要結(jié)點的移動操作)，但是在刪除前首先需要找到待刪除結(jié)點的地址，這個操作的時間復(fù)雜度為O(n)，在插入結(jié)點前首先也要找到結(jié)點應(yīng)該被插入的地方，這個操作的時間復(fù)雜度也為O(n)，因此，插入與刪除的時間復(fù)雜度都為O(n)。

3)AVL樹(平衡二叉樹)：AVL樹是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。由于樹的高度為logn，其中，n表示樹中結(jié)點的個數(shù)，因此，查找的時間復(fù)雜度為O(logn)，顯然，刪除與插入的時間復(fù)雜度也為O(logn)。

4)Hash表：Hash表通過Hash值就可以定位到元素的位置，因此，查找、插入與刪除的時間復(fù)雜度都為O(1)。

5)普通數(shù)組：查找的時候只能順序地遍歷數(shù)組，在最壞的情況下需要對數(shù)組中所有的元素遍歷一遍，因此，此時的時間復(fù)雜度為O(n)，其中，n表示數(shù)組序列的長度。插入的時候只需要把元素插入到數(shù)組的最后一個元素的后面即可，因此，時間復(fù)雜度為O(1)，刪除操作也需要移動這個元素后面的所有的元素，因此，此時的時間復(fù)雜度也為O(n)。

6)普通二叉樹：在最壞的情況下，有n個結(jié)點的樹的高度為n，因此，查找、插入與刪除的時間復(fù)雜度都為O(n)。

從上面的分析可以發(fā)現(xiàn)，平衡二叉樹的查找和刪除的時間復(fù)雜度都是O(logn)，Hash表的查找、插入的時間復(fù)雜度都是O(1)。因此，這兩個數(shù)據(jù)結(jié)構(gòu)有較好的查找和刪除的性能。所以，選項C、選項D正確。3.

一個棧的入棧序列為ABCDE，則不可能的出棧序列為______。

（分?jǐn)?shù)：2.00）

A.ECDBA

√

B.DCEAB

√

C.DECBA

D.ABCDE

E.EDCBA解析：4.

下列排序算法中，時間復(fù)雜度不會超過O(nlogn)的是______。

（分?jǐn)?shù)：2.00）

A.快速排序

B.堆排序

√

C.歸并排序

√

D.冒泡排序解析：5.

下列描述錯誤的是______。

（分?jǐn)?shù)：2.00）

A.插入排序算法在某些隋況下時間復(fù)雜度為O(n)

B.排序二叉樹元素查找的時間復(fù)雜度可能為O(n)

C.對于有序列表的排序最快的是快速排序

√

D.在有序列表中通過二分查找的時間復(fù)雜度一定是O(nlogn)

√解析：本題中，對于選項A，當(dāng)數(shù)據(jù)完全有序時，插入排序的時間復(fù)雜度就是O(n)。所以，選項A正確。

對于選項B，當(dāng)二叉樹退化成線性表(只有一叉)出現(xiàn)時，排序二叉樹元素查找的復(fù)雜度可能為O(n)。所以，選項B正確。

對于選項C，快速排序只對無序、隨機序列有優(yōu)勢，針對有序序列，其排序反而沒有了優(yōu)勢，在這種情況下，快速排序的效率最低，時間復(fù)雜度為O(n2)。所以，選項C錯誤。

對于選項D，在有序列表中通過二分查找的復(fù)雜度是O(logn)，而不是O(nlogn)。所以，選項D錯誤。

所以，本題的答案為CD。三、論述題(總題數(shù)：13，分?jǐn)?shù)：30.00)1.

尋找一條從左上角(arr[0][0])到右下角(arr[m-1][n-1])的路線，使得沿途經(jīng)過的數(shù)組中的整數(shù)和最小。

（分?jǐn)?shù)：4.00）__________________________________________________________________________________________

正確答案：(對于這道題，可以從右下角開始倒著來分析：最后一步到達arr[m-1][n-1]只有兩條路，即通過arr[m-2][n-1]到達或通過arr[m-1][n-2]到達，假設(shè)從arr[0][0]到arr[m-2][n-1]沿途數(shù)組最小值為f(m-2,n-1)，到arr[m-1][n-2]沿途數(shù)組最小值為f(m-1,n-2)。因此，最后一步選擇的路線為min{f(m-2,n-1),f(m-1,n-2)}。同理，選擇到arr[m-2][n-1]或arr[m-1][n-2]的路徑可以采用同樣的方式來確定。

由此可以推廣到一般的情況。假設(shè)到arr[i-1][j]與arr[i][j-1]的最短路徑的和為f(i-1,j)和f(i,j-1)，那么到達arr[i][j]的路徑上所有數(shù)字和的最小值為f(i,j)=min{f(i-1,j),f(i,j-1))+arr[i][j]。

方法1：遞歸法

根據(jù)這個遞歸公式可知，可以采用遞歸的方法來實現(xiàn)，遞歸的結(jié)束條件為遍歷到arr[0][0]。在求解的過程中，還需要考慮另外一種特殊情況：遍歷到arr[i][j](當(dāng)i=0或j=0)的時候，只能沿著一條固定的路徑倒著往回走直到arr[0][0]。

但是遞歸算法效率太低，主要因為里面有大量的重復(fù)計算過程，比如在計算(i-1,j)與f(j-1,i)的過程中都會去計算f(i-1,j-1)。如果把第一次計算得到的f(i-1,j-1)緩存起來就不需要額外的計算，而這也是典型的動態(tài)規(guī)劃的思路，下面重點介紹動態(tài)規(guī)劃方法。

方法2：動態(tài)規(guī)劃法

動態(tài)規(guī)劃其實也是一種空間換時間的算法，通過緩存計算的中間值，從而減少重復(fù)計算的次數(shù)，從而提高算法的效率。方法1從arr[m-1][n-1]開始逆向通過遞歸來求解，采用動態(tài)規(guī)劃要求正向求解，以便利用前面計算出來的結(jié)果。

對于本題而言，顯然，f(i,0)=arr[0][0]+…+arr[i][0]，f[0,j]=arr[0][0]+…+arr[0][j]。根據(jù)遞推公式：f(i,j)=min{f(i-1,j),f(i,j-1)}+arr[i][j]。從i=1、j=1開始順序遍歷二維數(shù)組，可以在遍歷的過程中求出所有的f(i,j)的值，同時，把求出的值保存到另外一個二維數(shù)組中以供后續(xù)使用。當(dāng)然，在遍歷的過程中可以確定這個最小值對應(yīng)的路線，在這個算法中，除了求出最小值外順便還打印出了最小值的路線，實現(xiàn)代碼如下：

publicclassTest

{

publicstaticintgetMinPath(int[][]arr){

if(arr==null||arr.length==0)

return0;

introw=arr.length;

inrcol=arr[0].length;

//用來保存計算的中間值

int[][]cache=newint[row][col];

cache[0][0]=arr[0][0];

for(inti=1;i＜col;i++){

cache[0][i]=cache[0][i-1]+arr[0][i];

}

for(intj=1;j＜row;j++){

cache[j][0]=cache[j-1][0]+arr[j][0];

}

//在遍歷二維數(shù)組的過程中不斷把計算結(jié)果保存到cache中

for(inti=1;i＜row;i++){

for(intj=1;j＜col;j++){

//可以確定選擇的路線為arr[i][j-1]

if(cache[i-1][j]>cache[i][j-1]){

cache[i][j]=cache[i][j-1]+arr[i][j];

System.out.print("["+i+","+(j-1)+"]

");

}

//可以確定選擇的路線為arr[i-1][j]

else{

cache[i][j]=cache[i-i][j]+arr[i][j];

System.out.print("["+(i-1)+","+j+"]");

}

}

}

System.out.println("["+(row-1)+","+(col-1)+"]");

returncache[row-1][col-1];

}

publicstaticvoidmain(String[]args){

int[][]arr={{1,4,3},{8,7,5},{2,1,5}};

System.out.print("路徑:");

System.out.println("最小值為:"+getMinPath(arr));

}

}

程序的運行結(jié)果為：

路徑：[0,1][0,2][2,0][2,1][2,2]

最小值為：17

這個方法對二維數(shù)組進行了一次遍歷，因此，其時間復(fù)雜度為O(m*n)。此外由于這個算法同樣申請了一個二維數(shù)組來保存中間結(jié)果，因此，其空間復(fù)雜度也為O(m*n)。)解析：2.

實現(xiàn)對一組無序的字母進行從小到大排序(區(qū)分大小寫)，當(dāng)兩個字母相同時，小寫字母放在大寫字母前。要求時間復(fù)雜度為O(n)。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(如果沒有時間復(fù)雜度的要求，本題可以采用傳統(tǒng)的插入排序或快速排序等方法進行排序，但是傳統(tǒng)的排序方法在最好的情況下的時間復(fù)雜度都為O(nlogn)，顯然，不滿足題目要求的O(n)時間復(fù)雜度。對于對時間復(fù)雜度有很高要求的問題，一般可以考慮用空間換時間的方法。鑒于此，對于本題而言，可以采用如下思路：

通常，字母為26個，當(dāng)區(qū)分大小寫后，變?yōu)?6*2=52個，所以，首先申請一個長度為52的int型數(shù)組，按照aAbBcC...zZ(小寫字母保存在下標(biāo)為偶數(shù)的位置，大寫字母保存在下標(biāo)為奇數(shù)的位置)的順序依次記錄各個字母出現(xiàn)的次數(shù)，當(dāng)記錄完成以后，就可以遍歷這個數(shù)組按照各個字母出現(xiàn)的次數(shù)來重組排序后的數(shù)組，實現(xiàn)代碼如下：

publicclassTest{

publicstaticvoidmain(String[]args)

{

char[]src={'R','B','B','b','W','W','B','R','B','w'};

sort(src);

for(inti=0;i＜src.length;i++){

System.out.print(src[i]+"");}

}

privatestaticvoidsort(char[]src)

{

if(src==null)

{

System.out.pIintln("參數(shù)不合法");

return;

}

//用于保存52個字符出現(xiàn)的次數(shù)，小寫字母保存在下標(biāo)為偶數(shù)的位置，大寫字母保存在奇

//數(shù)的位置

//采用這種保存方法，可以保證在這個數(shù)組中小寫字母出現(xiàn)在大寫字母前面，小的字符出現(xiàn)

//在大的字符前面

int[]charCount=newint[54];

for(inti=0;i＜src.length;i++)

{

//對小寫字母出現(xiàn)的次數(shù)就行計數(shù)

if(src[i]＞'a'&&src[i]＜'z'){charCount[(src[i]-'a')*2]++;}

//對大寫字母出現(xiàn)的次數(shù)就行計數(shù)

elseif(src[i]＜'Z'&&src[i]＞'A')

{charCount[(src[i]-'A')*2+1]++;}

}

//根據(jù)各個字符出現(xiàn)的次數(shù)按順序生成排序后的字符數(shù)組

intindex=0;

for(inti=0;i＜charCount.length;i++)

{

//這個字符在原始字符數(shù)組中存在

if(charCount[i]!=0){

//小寫字母

if(i%2==0)

{

for(intj=0;j＜charCount[i];j++){

src[index++]=(char)(i/2+'a');

}

}

//大寫字母

else{

for(intj=0;j＜charCount[i];j++){

src[index++]=(char)((i-1)/2+'A');

}

}

}

}

}

}

程序的運行結(jié)果為：

bBBBBRRwWW)解析：3.

有N個磁盤，每個磁盤大小為D[i](i=0,…,N-1)，現(xiàn)在要在這N個磁盤上“順序分配”M個分區(qū)，每個分區(qū)大小為P[j](j=0，…，M-1)，順序分配的意思是：分配一個分區(qū)P[j]時，如果當(dāng)前磁盤剩余空間足夠，則在當(dāng)前磁盤分配；如果不夠，則嘗試下一個磁盤，直到找到一個磁盤D[i+k]可以容納該分區(qū)，分配下一個分區(qū)P[j+1]時，則從當(dāng)前磁盤D[i+k]的剩余空間開始分配，不再使用D[i+k]之前磁盤未分配的空間，如果這M個分區(qū)不能在這N個磁盤完全分配，則認(rèn)為分配失敗。請實現(xiàn)函數(shù)isallocable判斷給定N個磁盤(數(shù)組D)和M個分區(qū)(數(shù)組P)，是否會出現(xiàn)分配失敗的情況?舉例：磁盤為[120.120.1201]，分區(qū)為[60,60,80,20,80]可分配，如果為[60,80,80,20,80]，則分配失敗。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(本題的主要思路如下：對所有的分區(qū)進行遍歷，同時用一個變量dIndex記錄上次分配磁盤的下標(biāo)，初始化為0；對于每個分區(qū)，從上次分配的磁盤開始繼續(xù)分配，如果沒有足夠的空間，則順序找其他的磁盤，直到找到合適的磁盤為止，進行分配；如果找不到合適的磁盤，則分配失敗，實現(xiàn)代碼如下：

publicclassTest{

publicstaticvoidmain(String[]args){

int[]d={120,120,120};//磁盤

int[]p={60,60,80,20,80};//分區(qū)

if(is_allocable(d,p)){

System.out.println("分配成功");

}else{

System.out.println("分配失敗");

}

}

privatestaticbooleanis_allocable(int[]d,int[]p)

{

intdIndex=0;//磁盤分區(qū)下標(biāo)

for(inti=0;i＜p.length;i++){

//找到符合條件的磁盤

while(dIndex＜d.length&&p[i]＞d[dIndex])

dIndex++;

//沒有可用的磁盤

if(dIndex＞=d.length)

returnfalse;

//給分區(qū)分配磁盤

d[dIndex]-=p[i];

}

returntrue;

}

}

程序的運行結(jié)果為：

分配成功)解析：4.

假設(shè)有一個中央調(diào)度機，有n個相同的任務(wù)需要調(diào)度到m臺服務(wù)器上執(zhí)行，由于每臺服務(wù)器的配置不一樣，因此，服務(wù)器執(zhí)行一個任務(wù)所花費的時間也不同。現(xiàn)在假設(shè)第i個服務(wù)器執(zhí)行一個任務(wù)需要的時間為t[i]。例如，有2個執(zhí)行機a與b，執(zhí)行一個任務(wù)分別需要7min和10min，有6個任務(wù)待調(diào)度。如果平分這6個任務(wù)，即a與b各3個任務(wù)，則最短需要30min執(zhí)行完所有。如果a分4個任務(wù)，b分2個任務(wù)，則最短28min執(zhí)行完。請設(shè)計調(diào)度算法，使得所有任務(wù)完成所需要的時間最短。輸入m臺服務(wù)器，每臺機器處理一個任務(wù)的時間為t[i]，完成n個任務(wù)，輸出n個任務(wù)在m臺服務(wù)器的分布。intestimate_process_time(int[]t,intm,intn)。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(本題可以采用貪心法來解決，具體實現(xiàn)思路如下：

申請一個數(shù)組來記錄每臺機器的執(zhí)行時間，初始化為0。在調(diào)度任務(wù)的時候，對于每個任務(wù)，在選取機器的時候采用如下的貪心策略：對于每臺機器，計算機器已經(jīng)分配任務(wù)的執(zhí)行時間+這個任務(wù)需要的時間，選用最短時間的機器進行處理。實現(xiàn)代碼如下：

publicclassTest

{

publicstaticvoidmain(String[]args)

{

intt[]={7,10};

intn=6;

intproTime[]=calculate_orocess_time(t,n);

if(proTime==null)

{

System.out.println("分配失敗");

return;

}

inttotalTime=proTime[0];

for(inti=0;i＜proTime.length;i++)

{

System.out.println("第"+(i+1)+"臺服務(wù)器有"+proTime[i]/t[i]

+"個任務(wù),執(zhí)行總時間為："+proTime[i]);

if(proTime[i]＞totalTime)

totalTime=proTime[i];

}

System.out.println("執(zhí)行完所有任務(wù)所需的時間為"+totalTime);

}

/**

*@paramt

每個服務(wù)器處理的時間

*@paramn

任務(wù)的個數(shù)

*@return各個服務(wù)器執(zhí)行完任務(wù)所需的時間

*/

privatestaticint[]calculate_process_time(int[]t,intn)

{

if(t==null||n＜=0)

returnnull;

intm=t.length;

intminlndex;

intminTime;

int[]proTime=newint[m];

for(inti=0;i＜n;i++)

{

minTime=proTime[0]+t[0];//把任務(wù)給第j個機器上后這個機器的執(zhí)行時間

minIndex=0;

//把任務(wù)給第minIndex個機器上

for(intj=1;j＜m;j++)

{

//分配到第j臺機器上后執(zhí)行時間更短

if(minTime＞proTime[j]+t[j])

{

minTime=proTime[j]+t[j];

minIndex=j;

}

}

proTime[minIndex]+=t[minIndex];

}

returnproTime;

}

}

程序的運行結(jié)果為：

第1臺服務(wù)器有4個任務(wù)，執(zhí)行總時間為：28

第2臺服務(wù)器有2個任務(wù)，執(zhí)行總時間為：20

執(zhí)行完所有任務(wù)所需的時間為28)解析：5.

n(1，2，3，…，n)個元素有N!個不同的排列，將這n!個數(shù)按字典序排列，并編號0，1，…，n!-1，每個排號為其字典序的值，如n=3時，字典排序為123，132，213，231,312，321，這6個數(shù)的字典序分別為0，1，2，3，4，5，現(xiàn)給定n，請輸出字典序為k的排列(0＜=k＜n!)。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(算法的主要思路為：從當(dāng)前字符串出發(fā)找出下一個排列(下一個排列為大于當(dāng)前字符串的最小字符串)。

通過引入一個例子來介紹非遞歸算法的基本思想：假設(shè)要對字符串“12345”進行排序。第一個排列一定是“12345”，依此獲取下一個排列：“12345”-＞“12354”-＞“12435”-＞“12453”-＞“12534”-＞“12543”-＞“13245”-＞...。從“12543”-＞“13245”可以看出找下一個排列的主要思路如下：

1)從右到左找到兩個相鄰遞增的字符，在本例中，“12543”中從右到左找出第一個相鄰遞增的子串為“25”，記錄這個小的字符的下標(biāo)為pmin。

2)找出pmin后面的比它大的最小的字符進行交換，在本例中，字符“2”后面的子串中比它大的最小的字符為“3”，因此，交換字符“2”和字符“3”可以得到字符串“13542”。

3)為了保證下一個排列為大于當(dāng)前字符串的最小字符串，在第2)步完成交換后，需要對pmin后的子串重新組合，使其值最小，只需對pmin后面的字符進行逆序即可(因為此時pmin后面的子串中的字符必定是按照降序排列，逆序后字符就按照升序排列了)，逆序后就能保證當(dāng)前的組合是新的最小的字符串；在這個例子中，上一步得到的字符串為“13542”，pmin指向字符“3”，對其后面的子串“542”逆序后得到字符串“13245”。

4)依次類推，直到獲取到字典序為k的排列為止。

有興趣的讀者可以根據(jù)上述思路，自行實現(xiàn)代碼。)解析：6.

定義有數(shù)組inta[200]={1,2,2,3,...}，數(shù)組元素都為正整數(shù)，且a[i+1]＞=a[i]，請快速輸出a[i]=i的數(shù)。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(本題中，最簡單的方法是對數(shù)組進行順序遍歷，判斷遍歷到的數(shù)是否滿足條件，這種方法的效率顯然是最低的。下面介紹另外一種方法，主要思路如下：如果a[i]＞i，則接下來的a[i]-i-1個數(shù)一定不可能滿足a[i]=i，此時可以直接遍歷下標(biāo)為i+(arr[i]-i)的元素，從而減少了遍歷的次數(shù)，實現(xiàn)代碼如下：

importjava.util.ArrayList;;

publicclassTest

{

publicstaticArrayList＜Integer＞find(int[]arr)

{

ArrayList＜Integer＞result=newArrayList＜Integer＞();

for(inti=0,j=arr.length-1;i＜=j;)

{

//找到滿足條件的數(shù)，添加到結(jié)果中，繼續(xù)遍歷下一個數(shù)

if(arr[i]==i)

result.add(i++);

//當(dāng)arr[i]＞i時，則接下來的a[i]-i-1個數(shù)肯定不滿足a[i]=i

elseif(m[i]＞i)

i=i+(arr[i]-i);

//遍歷下一個數(shù)

else

i++;

}

returnresult;

})解析：7.

定義數(shù)組int[n]a={1,2,3,3,4,3,2，...}，數(shù)組a中的數(shù)均為正整數(shù)，當(dāng)滿足a[i]+a[t]=a[x]時，其中，i，t，x均為正數(shù)，且小于等于n，求最大的a[x]。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(本題的主要思路如下：首先對數(shù)組進行排序，然后從后往前遍歷數(shù)組，對于每遍歷到的一個數(shù)組元素a[i]，判斷從0到a[i-1]個元素中，是否有滿足a[j]+a[k]=a[i](j,k＜=i-1)的值。在判斷的時候，可以采用如下思路：從前往后遍歷子數(shù)組a[0...i-1]，對于遍歷到的元素a[j]，判斷在子數(shù)組a[j+1...i-1]中是否存在a[i]-a[j]，如果存在，則說明存在值j和k，使得a[j]+a[k]=a[i]，此時的a[i]就是滿足條件的最大值。

有興趣的讀者可以根據(jù)上述思路，自行實現(xiàn)代碼。)解析：8.

數(shù)組和鏈表有什么區(qū)別?

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(數(shù)組是按照數(shù)據(jù)順序存儲的，其大小固定。而鏈表中的數(shù)據(jù)可以隨機存儲，大小可動態(tài)改變。)解析：9.

如何尋找單鏈表的中間結(jié)點?

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(要尋找到單鏈表的中間結(jié)點，最容易想到的方法是首先求解單鏈表的長度，記為length，然后遍歷length/2的距離即可，但是此種方法需要遍歷兩次鏈表，即第一次遍歷求解單鏈表的長度，第二次遍歷根據(jù)索引獲取中間結(jié)點。

如果是雙向鏈表，可以首尾并行進行尋找，利用兩個指針，一個從頭到尾遍歷，另一個從尾到頭遍歷，當(dāng)兩個指針相遇的時候，就找到了中間結(jié)點。以此思想為基礎(chǔ)，如果是單鏈表，也可以采用雙指針的方式來實現(xiàn)中間結(jié)點的快速查找。

具體而言，第一步，定義兩個指針，二者同時從鏈表頭開始遍歷。第二步，兩個指針每次走的步數(shù)不一樣，其中，快指針一次走2步，慢指針一次走1步。第三步，由于快慢指針每次所走的步數(shù)不一樣，所以，快指針會先到達鏈表尾部，而慢指針則恰好到達鏈表中部。(快指針走到鏈表尾部時，當(dāng)鏈表長度為奇數(shù)時，慢指針指向的即是鏈表中間指針，當(dāng)鏈表長度為偶數(shù)時，慢指針指向的結(jié)點和慢指針指向結(jié)點的下一個結(jié)點都是鏈表的中間結(jié)點。))解析：10.

編寫一個截取字符串的函數(shù)，輸入為一個字符串和字節(jié)數(shù)，輸出為按字節(jié)截取的字符串。但是要保證漢字不被截半個，例如“人ABC”4，應(yīng)該截為“人AB”，輸入“人ABC們DEF”，6，應(yīng)該輸出為“人ABC”而不是“人ABC+們的半個”。

（分?jǐn)?shù)：2.00）__________________________________________________________________________________________

正確答案：(在Java語言中，默認(rèn)使用的Unicode編碼方式，即每個字符占用兩個字節(jié)，因此，可以用來存儲中文。雖然String是由char所組成的，但是它采用了一種更加靈活的方式來存儲，即英文占用一個字符，中文占用兩個字符。采用這種存儲方式的一個重要作用就是可以減少所需的存儲空間，提高存儲效率。根據(jù)這個特點，可以采用如下代碼來完成題目的要求：

publicclassTest

{

//判斷字符c是否是中文字符，如果是返回true

publicstaticbooleanisChinese(charc)

{

Stringsb=String.valueOf(c);

returnsb.getBytes().length＞1?true:false;

}

publicStringmmcateStr(Stringstr,intlen)

{

if(str==null||str.equals("")||len==0)

return"";

char[]chrArr=str.toCharArray();

StringBuildersb=newStringBuilder("");

intcount=0;//用來記錄當(dāng)前截取字符的長度

for(charcc:chrArr)

{

if(count＜len)

{

if(isChinese(cc))

{

//如果要求截取子串的長度只差一個字符，但是接下來的字符是中文，

//則截取結(jié)果子串中不保存這個中文字符

if(count+1==len)

return