2018考研計(jì)算機(jī)專(zhuān)業(yè)課：計(jì)算機(jī)真題提高班講義

目錄

第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)4

題型一時(shí)空復(fù)雜度4

題型二棧和隊(duì)列5

題型三樹(shù)與二叉樹(shù)8

題型四圖12

題型五查找與排序14

題型六算法題18

題型七綜合題26

第二部分計(jì)算機(jī)組成原理33

題型一馮諾依曼機(jī)33

題型二數(shù)據(jù)的表示與運(yùn)算34

題型三存儲(chǔ)管理36

題型四中央處理器38

題型五指令系統(tǒng)39

題型六總線40

題型七I/O系統(tǒng)42

題型八綜合題43

第三部分操作系統(tǒng)56

題型一操作系統(tǒng)概述56

題型二進(jìn)程管理57

題型三內(nèi)存管理62

題型四文件管理64

題型五輸入輸出管理65

題型六綜合題66

第四部分計(jì)算機(jī)網(wǎng)絡(luò)75

題型一網(wǎng)絡(luò)體系結(jié)構(gòu)75

題型二物理層75

題型三數(shù)據(jù)鏈路層77

題型四網(wǎng)絡(luò)層78

題型五傳輸層81

題型六應(yīng)用層82

題型七綜合題83

第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)

題型一時(shí)空復(fù)雜度

一、循環(huán)時(shí)間復(fù)雜度

1.設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是。

x=2；

while(x<n/2)

x=2*x；

2

A.O(log2n)B.0(n)C.O(nlog2n)D.0(n)

答案：A?？疾闀r(shí)間復(fù)雜度的計(jì)算。

在程序中，執(zhí)行頻率最高的語(yǔ)句為“x=2*x"。設(shè)該語(yǔ)句共執(zhí)行了t次，貝lj,2t+l=n/2,故

t=log2(n/2)-1=log2n-2,得T(n)=0(log2n)o

2.下列程序段的時(shí)間復(fù)雜度是。

count=0;

for(k=l;k<=n;k*=2)

for(j=l;j<=n;j++)

count++;

2

A.O(log2n)B.0(n)C.O(nlog2n)D.O(n)

答案：C

內(nèi)層循環(huán)條件j<=n與外層循環(huán)的變量無(wú)關(guān)，每次循環(huán)j自增1.每次內(nèi)層循環(huán)都執(zhí)

行n次。外層循環(huán)條件為k<=n,增量定義為k*=2,可知循環(huán)次數(shù)為2&=n,即k<=log2n?

所以?xún)?nèi)層循環(huán)的時(shí)間復(fù)雜度是0(n),外層循環(huán)的時(shí)間復(fù)雜度是O(log2n)?對(duì)于嵌套循環(huán)，

根據(jù)乘法規(guī)則可知，該段程序的時(shí)間復(fù)雜度T(n)=Tl(n)*T2(n)=0(n)*0(log2n)=0(nlog2n)o

二'遞歸時(shí)間復(fù)雜度

1,求整數(shù)n(nNO)階乘的算法如下，其時(shí)間復(fù)雜度是。

intfact(intn){

if(n<=l)return1;

returnn*fact(n-l);

}

2

A.O(log2n)B.O(n)C,O(nlog2n)D,O(n)

答案：Bo考查時(shí)間復(fù)雜度的計(jì)算。

該程序中使用了遞歸運(yùn)算。本題中遞歸的邊界條件是n<=l,每調(diào)用一次fact。，傳入該層

fact。的參數(shù)值減1(注意不是n減1),因此執(zhí)行頻率最高的語(yǔ)句是returnn*fact(n-l),

一共執(zhí)行了n-1次，而每一層fact(i)運(yùn)算只包含一次乘法。如果采用遞歸式來(lái)表示時(shí)間復(fù)

雜度，貝I：

Tn=f°(1)nSl

lT(n-1)+1n>1

時(shí)間復(fù)雜度為0(n)。

2.已知程序如下：

intS(intn)

{retrun(n<O)?:O:S(n-l)+n;}

voidmain()

{cout<<S(l);}

程序運(yùn)行時(shí)使用棧來(lái)保存調(diào)用過(guò)程的信息，子棧底到棧頂保存的信息依次對(duì)應(yīng)的是—

A.main()->S(l)->S(0)B.S(0)->S(l)->main()

C.main()->S(0)->S(l)C.S(l)->S(0)->main()

答案：Ao

三'圖的基本算法時(shí)間復(fù)雜度

1.對(duì)有n個(gè)結(jié)點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)

雜度是。

A.0(n)B.0(e)C.O(n+e)D.O(n*e)

答案：C?考查不同存儲(chǔ)結(jié)構(gòu)的圖遍歷算法的時(shí)間復(fù)雜度。

廣度優(yōu)先遍歷需要借助隊(duì)列實(shí)現(xiàn)。鄰接表的結(jié)構(gòu)包括：頂點(diǎn)表；邊表(有向圖為出邊表)。

當(dāng)采用鄰接表存儲(chǔ)方式時(shí)，在對(duì)圖進(jìn)行廣度優(yōu)先遍歷時(shí)每個(gè)頂點(diǎn)均需入隊(duì)一次(頂點(diǎn)表遍

歷)，故時(shí)間復(fù)雜度為0(n),在搜索所有頂點(diǎn)的鄰接點(diǎn)的過(guò)程中，每條邊至少訪問(wèn)一次(出

邊表遍歷)，故時(shí)間復(fù)雜度為0(e),算法總的時(shí)間復(fù)雜度為O(n+e)?

2.若將n個(gè)頂點(diǎn)e條弧的有向圖采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是—。

A.0(n)B.O(n+e)C.0(n2)D.O(n*e)

答案：B。同上

四'排序算法比較

1.對(duì)一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是

A.排序的總趟數(shù)B.元素的移動(dòng)次數(shù)

C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)

答案：Do考查折半插入和直接插入的區(qū)別。

折半插入排序與直接插入排序都是將待插入元素插入前面的有序子表，區(qū)別是：確定當(dāng)前記

錄在前面有序子表中的位置時(shí)，直接插入排序是采用順序查找法，而折半插入排序是采用折

半查找法。排序的總趟數(shù)取決于元素個(gè)數(shù)n,兩者都是n-1趟。元素的移動(dòng)次數(shù)都取決于

初始序列，兩者相同。使用輔助空間的數(shù)量也都是0(1)。折半插入排序的比較次數(shù)與序列

初態(tài)無(wú)關(guān)，為O(nlog2n)；而直接插入排序的比較次數(shù)與序列初態(tài)有關(guān)，為0(n)~0(n2)。

五'變形算法時(shí)空復(fù)雜度

1.已知兩個(gè)長(zhǎng)度分別為m和n的升序鏈表,若將他們合并為一個(gè)長(zhǎng)度為m+n的降序鏈表，

則最壞情況下的時(shí)間復(fù)雜度是()

A.0(n)B,0(m*n)C.0(min(m,n))D.0(max(m,n))

答案：D。

解析：m、n是兩個(gè)升序序列，長(zhǎng)度分別為m,n,在合并過(guò)程中，最壞的情況是兩個(gè)鏈表中

的元素依次進(jìn)行比較，比較的次數(shù)是m和n中的最大值

題型二棧和隊(duì)列

一、棧和隊(duì)列概念理解

1.為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，

主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)

的邏輯結(jié)構(gòu)應(yīng)該是一O

A.棧B.隊(duì)列C.樹(shù)D.圖

答案：B?？疾闂：完?duì)列的特點(diǎn)及應(yīng)用。

C和D直接排除，緩沖區(qū)的特點(diǎn)需要先進(jìn)先出，若用棧，先進(jìn)入緩沖區(qū)的數(shù)據(jù)則要排

隊(duì)到最后才能打印，不符題意，故選Bo

二'出棧出隊(duì)序列

1.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依

次進(jìn)入棧So若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q,且7個(gè)元素出隊(duì)的順序是

b,d,c,f,e,a,g,則棧S的容量至少是。

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

答案：Co考查棧的最大遞歸深度。

時(shí)刻注意棧的特點(diǎn)是先進(jìn)后出。出入棧的詳細(xì)過(guò)程見(jiàn)表A-3O

表A-3

序號(hào)說(shuō)明棧內(nèi)棧外序號(hào)說(shuō)明棧內(nèi)棧外

1a入棧a8e入棧aebdc

2b入棧ab9f入棧aefbdc

3b出棧ab10f出棧aebdcf

4c入棧acbIIe出棧abdcfe

5d入棧acdb12a出棧bdctea

6d出棧acbd13g入棧gbdctea

7c出棧abdc14g出棧bdcfcag

棧內(nèi)的最大深度為3,故棧S的容量至少是3。

2.若元素a、b、c、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許

連續(xù)三次進(jìn)行退棧操作，則不可能得到的出棧序列是。

A.dcebfaB.cbdaef

C.bcaefdD.afedcb

答案：D。考查限定條件的出棧序列。

A可由in,in,in,in,out,out,in,out,out,in,out,out得到；

B可由in,in,in,out,out,in,out,out,in,out,in,out得到；

C可由in,in,out,in,out,out,in,in,out,in,out,out得到；

D可由in,out,in,in,in,in,in,out,out,out,out,out得到，但題意

要求不允許連續(xù)三次退棧操作，故D錯(cuò)。

3.某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作。若元素a、b、

c、d、e依次入此隊(duì)列后再進(jìn)行出隊(duì)操作，則不可能得到的出隊(duì)序列是o

A.bacdeB.dbace

C.dbcaeD.ecbad

答案：Co考查受限的雙端隊(duì)列的出隊(duì)序列。

A可由左入，左入，右入，右入，右入得到；B可由左入，左入，右入，左入，右入得

到；D可由左入，左入，左入，右入，左入得到。所以不可能得到Co

4.元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直

到所有元素都出棧，則在所有可能的出棧序列中，以元素d開(kāi)頭的序列個(gè)數(shù)是。

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

答案：B?？疾槌鰲Ｐ蛄?。

出棧順序必為d_c_b_a_,e的順序不定，在任一個(gè)上都有可能。

三、循環(huán)隊(duì)列

1.已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭

元素和隊(duì)尾元素。若初始時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A⑼處，則初

始時(shí)front和rear的值分別是。

A.0,0B.0,n_1C.n_l,0D.n-1,n-1

答案：B?？疾檠h(huán)隊(duì)列的性質(zhì)。

入隊(duì)時(shí)由于要執(zhí)行(rear+l)%n操作，所以如果入隊(duì)后指針指向0,則rear初值為n-1,而

由于第一個(gè)元素在A[0]中，插入操作只改變r(jià)ear指針，所以front為0不變。

2.循環(huán)隊(duì)列放在一維數(shù)組A[0…M-1]中，endl指向隊(duì)頭元素，end2指向隊(duì)尾元素的后

一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始

時(shí)為空。下列判斷隊(duì)空和隊(duì)滿(mǎn)的條件中，正確的是O

A.隊(duì)空:endl==end2；隊(duì)滿(mǎn):endl==(end2+l)modM

B.隊(duì)空：endl==end2；隊(duì)滿(mǎn)：end2==(endl+l)mod(M-1)

C.隊(duì)空：end2==(endl+l)modM；隊(duì)滿(mǎn):endl==(end2+l)modM

D.隊(duì)空：endl==(end2+l)modM；隊(duì)滿(mǎn)：end2==(endl+l)mod(M-1)

答案：endl指向隊(duì)頭元素，那么可知出隊(duì)的操作是先從A[endl]讀數(shù)，然后endl再加1。

end2指向隊(duì)尾元素的后一個(gè)位置，那么可知入隊(duì)操作是先存數(shù)到A[end2],然后end2再

加1。若把A⑼儲(chǔ)存第一個(gè)元素，當(dāng)隊(duì)列初始時(shí)，入隊(duì)操作是先把數(shù)據(jù)放到A[0],然后end2

自增，即可知end2初值為0；而endl指向的是隊(duì)頭元素，隊(duì)頭元素的在數(shù)組A中的下

標(biāo)為0,所以得知endl初值也為0.可知隊(duì)空條件為endl==end2；然后考慮隊(duì)列滿(mǎn)時(shí)，

因?yàn)殛?duì)列最多能容納M-1個(gè)元素，假設(shè)隊(duì)列存儲(chǔ)在下標(biāo)為0到下標(biāo)為M-2的M-1個(gè)

區(qū)域，隊(duì)頭為A[0],隊(duì)尾為A[M-2],此時(shí)隊(duì)列滿(mǎn)，考慮在這種情況下endl和end2的

狀態(tài)，endl指向隊(duì)頭元素，可知endl=0,end2指向隊(duì)尾元素的后一個(gè)位置，可知

end2=M-2+l=M-l,所以可知隊(duì)滿(mǎn)的條件為endl==(end2+l)modM,選A。

四'棧和隊(duì)列的應(yīng)用

1.已知操作符包括,,+?、，,-?、,,*?、/'、,,(”和,,)如將中綴表達(dá)式a+b-a*((c+d)/e-f)+g

轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操

作符，若棧初始時(shí)為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是O

A.5B.7C.8D.11

答案：A?？疾闂５膽?yīng)用、表達(dá)式求值。

表達(dá)式求值是棧的典型應(yīng)用。通常涉及中綴表達(dá)式和后綴表達(dá)式。中綴表達(dá)式不僅依賴(lài)運(yùn)算

符的優(yōu)先級(jí)，還要處理括號(hào)。后綴表達(dá)式的運(yùn)算符在表達(dá)式的后面且沒(méi)有括號(hào)，其形式已經(jīng)

包含了運(yùn)算符的優(yōu)先級(jí)。所以從中綴表達(dá)式轉(zhuǎn)換到后綴表達(dá)式需要用運(yùn)算符棧對(duì)中綴表達(dá)式

進(jìn)行處理，使其包含運(yùn)算法優(yōu)先級(jí)的信息,從而轉(zhuǎn)換為后綴表達(dá)式的形式。轉(zhuǎn)換過(guò)程如下表：

運(yùn)算符棧中級(jí)未處理部分后綴生成部分

#a+b-a*((c+d)/e-f>+g

#a

b-ae((c-Hl)/e-0+ga

-a*((c+dye-f)+gab

-a*((c+d)/e-0+gab+

-?((c+d)/e-f>+gab+a

((c+d)/e-0+gab+a

??((c+d)/e-f>+gab+a

??((?dj/e-fHgab+ac

-?((+d)/e-f>+gab+ac

-?((+Ve-f>+gab+acd

?%/e-O+gab+acd.

-?(/e-O+gab+acd+

-?(/-0+gab+aod+e

，(-0*gab+acd+e/

H-8ab+acd+e/f

?gab+acd+e/f-

-+gab+acd+e/f->

#+gab+acdWf-0-

+gab+acd+e/f-0-

#ab+acd+e/f^^-g

題型三樹(shù)與二叉樹(shù)

一、樹(shù)、二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)

1.已知一棵完全二叉樹(shù)的第6層(設(shè)根為第1層)有8個(gè)葉結(jié)點(diǎn)，則該完全二叉樹(shù)的結(jié)

點(diǎn)個(gè)數(shù)最多是—0

A.39B.52C.IllD.119

答案：Co考查完全二叉樹(shù)的特點(diǎn)。

完全二叉樹(shù)比滿(mǎn)二叉樹(shù)只是在最下面一層的右邊缺少了部分葉結(jié)點(diǎn)，而最后一層之上是個(gè)滿(mǎn)

二叉樹(shù)，并且只有最后兩層有葉結(jié)點(diǎn)。第6層有葉結(jié)點(diǎn)則完全二叉樹(shù)的高度可能為6或7,

顯然樹(shù)高為7時(shí)結(jié)點(diǎn)更多。若第6層上有8個(gè)葉結(jié)點(diǎn)，則前六層為滿(mǎn)二叉樹(shù)，而第7層

缺失了8x2=16個(gè)葉結(jié)點(diǎn)，故完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多為27-1-16=111個(gè)結(jié)點(diǎn)。

2.在一棵度為4的樹(shù)T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為

3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹(shù)T的葉結(jié)點(diǎn)

個(gè)數(shù)是。

A.41B.82C.113D.122

答案：B?？疾闃?shù)結(jié)點(diǎn)數(shù)的特性。

設(shè)樹(shù)中度為i(i=0,1,2,3,4)的結(jié)點(diǎn)數(shù)分別為Ni,樹(shù)中結(jié)點(diǎn)總數(shù)為N,則樹(shù)中

各結(jié)

點(diǎn)的度之和等于N-1,即N=l+Nl+2N2+3N3+4N4=N0+Nl+N2+N3+N4,根據(jù)題設(shè)中的

數(shù)據(jù)，

即可得到N0=82,即樹(shù)T的葉結(jié)點(diǎn)的個(gè)數(shù)是820

3.若一棵完全二叉樹(shù)有768個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)是

A.257B.258C.384D.385

答案：C?考查完全二叉樹(shù)的性質(zhì)。

根據(jù)完全二叉樹(shù)的性質(zhì)，最后一個(gè)分支結(jié)點(diǎn)的序號(hào)為L(zhǎng)768/2」=384,故葉子結(jié)點(diǎn)的個(gè)數(shù)

為768-384=384。

二、特殊二叉樹(shù)的概念理解

1,下列二叉排序樹(shù)中，滿(mǎn)足平衡二叉樹(shù)定義的是

答案：B?？疾槠胶舛鏄?shù)的定義。

根據(jù)平衡二叉樹(shù)的定義有，任意結(jié)點(diǎn)的左、右子樹(shù)高度差的絕對(duì)值不超過(guò)lo而其余三個(gè)答

案均可以找到不符合的結(jié)點(diǎn)。

2.下列線索二叉樹(shù)中（用虛線表示線索），符合后序線索樹(shù)定義的是。

A.B.C.D.

答案：Do考查線索二叉樹(shù)的基本概念和構(gòu)造。

題中所給二叉樹(shù)的后序序列為dbca。結(jié)點(diǎn)d無(wú)前驅(qū)和左子樹(shù)，左鏈域空，無(wú)右子樹(shù)，

右鏈域指向其后繼結(jié)點(diǎn)b；結(jié)點(diǎn)b無(wú)左子樹(shù)，左鏈域指向其前驅(qū)結(jié)點(diǎn)d；結(jié)點(diǎn)c無(wú)左子樹(shù),

左鏈域指向其前驅(qū)結(jié)點(diǎn)b,無(wú)右子樹(shù)，右鏈域指向其后繼結(jié)點(diǎn)a。

3.在圖B-1所示的平衡二叉樹(shù)中，插入關(guān)鍵字48后得到一棵新

平衡二叉樹(shù)。在新平衡二叉樹(shù)中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)

點(diǎn)中保存的關(guān)鍵字分別是0

24

A.13,48B.24,48

C.24,53D.24,90

答案：Co考查平衡二叉樹(shù)的插入算法。

插入48以后，該二叉樹(shù)根結(jié)點(diǎn)的平衡因子由變?yōu)?2,失去平衡，需進(jìn)行兩次旋轉(zhuǎn)（先

右旋后左旋）操作。

4.對(duì)n（nN2）個(gè)權(quán)值均不相同的字符構(gòu)造成赫夫曼樹(shù)。下列關(guān)于該赫夫曼樹(shù)的敘述中，

錯(cuò)誤的是O

A.該樹(shù)一定是一棵完全二叉樹(shù)

B.樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)

C.樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D.樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值

答案：A?？疾楹辗蚵鼧?shù)的特性。

赫夫曼樹(shù)為帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，不一定是完全二叉樹(shù)。赫夫曼樹(shù)中沒(méi)有度為1的

結(jié)點(diǎn)，B正確；構(gòu)造赫夫曼樹(shù)時(shí)，最先選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左、右子樹(shù)構(gòu)造一棵

新的二叉樹(shù)，C正確；赫夫曼樹(shù)中任一非葉結(jié)點(diǎn)P的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之

和，其權(quán)值不小于其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值，在與結(jié)點(diǎn)P的左、右子樹(shù)根結(jié)點(diǎn)處于同一

層的結(jié)點(diǎn)中，若存在權(quán)值大于結(jié)點(diǎn)P權(quán)值的結(jié)點(diǎn)Q,那么結(jié)點(diǎn)Q的兄弟結(jié)點(diǎn)中權(quán)值較小

的一個(gè)應(yīng)該與結(jié)點(diǎn)P作為左、右子樹(shù)構(gòu)造新的二叉樹(shù)。綜上可知，赫夫曼樹(shù)中任一非葉結(jié)

點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值

5.對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹(shù)中一條查找路徑的序列是o

A.95,22,91,24,94,71B.92,20,91,34,88,35

C.21,89,77,29,36,38D.12,25,71,68,33,34

答案：Ao考查二叉排序樹(shù)的查找過(guò)程。

在二叉排序樹(shù)中，左子樹(shù)結(jié)點(diǎn)值小于根結(jié)點(diǎn)，右子樹(shù)結(jié)點(diǎn)值大于根結(jié)點(diǎn)。在選項(xiàng)A中，

當(dāng)查找到91后再向24查找，說(shuō)明這一條路徑（左子樹(shù)）之后查找的數(shù)都要比91小，而

后面卻查找到了94,因此錯(cuò)誤。

6.若平衡二叉樹(shù)的高度為6,且所有非葉結(jié)點(diǎn)的平衡因子均為1,則該平衡二叉樹(shù)的結(jié)點(diǎn)

總數(shù)為O

A.10B.20C.32D.33

答案：Bo考查平衡二叉樹(shù)的最少結(jié)點(diǎn)情況。

所有非葉結(jié)點(diǎn)的平衡因子均為1,即平衡二叉樹(shù)滿(mǎn)足平衡的最少結(jié)點(diǎn)情況，如圖xxx所示。

畫(huà)圖時(shí)，先畫(huà)出T1和T2；然后新建一個(gè)根結(jié)點(diǎn)，連接T2、T1構(gòu)成T3；新建一個(gè)根結(jié)

點(diǎn)，連接T3、T2構(gòu)成T4…依此類(lèi)推，直到畫(huà)出T6,可知T6的結(jié)點(diǎn)數(shù)為20。對(duì)于高

度為N的題述的平衡二叉樹(shù)，它的左、右子樹(shù)分別為高度為N-1和N-2的所有非葉結(jié)

點(diǎn)的平衡因子均為1的平衡二叉樹(shù)。二叉樹(shù)的結(jié)點(diǎn)總數(shù)公式為：CN=CN-l+CN-2+l.

C2=2,C3=4,遞推可得C6=20o

7.5個(gè)字符有如下4種編碼方案，不是前綴編碼的是o

A.01,0000,0001,001,1B.011,000,001,010,1

C.000,001,010,011,100D.0,100,110,1110,1100

答案：Do

前綴編碼的定義是在一個(gè)字符集中，任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴。D

中編碼110是編碼1100的前綴，違反了前綴編碼的規(guī)則，所以D不是前綴編碼。

三'二叉樹(shù)的遍歷

1.給定二叉樹(shù)如圖A-1所示。設(shè)N代表二叉樹(shù)的根，L代表根結(jié)點(diǎn)的左子樹(shù)，R代表

根結(jié)點(diǎn)的右子樹(shù)。若遍歷后的結(jié)點(diǎn)序列是3,1,7,5,6,2,4,則其遍歷方式是0

B.NRLC.RLND.RNL

答案：D?？疾槎鏄?shù)的特殊遍歷。

分析遍歷后的結(jié)點(diǎn)序列，可以看出根結(jié)點(diǎn)是在中間被訪問(wèn)的，而右子樹(shù)結(jié)點(diǎn)在左子樹(shù)之前,

得遍歷的方法是RNLO本題考查的遍歷方法并不是二叉樹(shù)的三種基本遍歷方法，對(duì)于考生

而言，重要的是要掌握遍歷的思想。

2.若一棵二叉樹(shù)的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1,

則該二叉樹(shù)的中序遍歷序列不會(huì)是。

A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1

答案：Co考查二叉樹(shù)的遍歷算法。

前序序列為L(zhǎng)RN,后序序列為NLR,由于前序序列和后序序列剛好相反，故不可能存

在一個(gè)結(jié)點(diǎn)同時(shí)存在左右孩子，即二叉樹(shù)的高度為4。1為根結(jié)點(diǎn)，由于根結(jié)點(diǎn)只能有左

孩子（或右孩子），因此，在中序序列中，1或在序列首或在序列尾，ABCD皆滿(mǎn)足要求。

僅考慮以1的孩子結(jié)點(diǎn)2為根結(jié)點(diǎn)的子樹(shù)，它也只能有左孩子（或右孩子），因此，在中

序序列中，2或在序列首或序列尾，ABD皆滿(mǎn)足要求。

四、樹(shù)、二叉樹(shù)、森林的轉(zhuǎn)換

1.將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中，結(jié)點(diǎn)U是結(jié)點(diǎn)V的父結(jié)點(diǎn)的父結(jié)點(diǎn)，

則在原來(lái)的森林中，U和V可能具有的關(guān)系是。

I.父子關(guān)系II.兄弟關(guān)系

III.U的父結(jié)點(diǎn)與V的父結(jié)點(diǎn)是兄弟關(guān)系

A,只有IIB.I和IIC.I和川D.I、II和小

答案：Bo考查森林和二叉樹(shù)的轉(zhuǎn)換。

森林與二叉樹(shù)的轉(zhuǎn)換規(guī)則為“左孩子右兄弟”。在最后生成的二叉樹(shù)中，父子關(guān)系在對(duì)

應(yīng)森林關(guān)系中可能是兄弟關(guān)系或原本就是父子關(guān)系。

情形I：若結(jié)點(diǎn)v是結(jié)點(diǎn)u的第二個(gè)孩子結(jié)點(diǎn)，在轉(zhuǎn)換時(shí)，結(jié)點(diǎn)v就變成結(jié)點(diǎn)u第一個(gè)

孩子的右孩子，符合要求。

情形II:結(jié)點(diǎn)u和v是兄弟結(jié)點(diǎn)的關(guān)系，但二者之中還有一個(gè)兄弟結(jié)點(diǎn)k,則轉(zhuǎn)換后，結(jié)

點(diǎn)v就變?yōu)榻Y(jié)點(diǎn)k的右孩子，而結(jié)點(diǎn)k則是結(jié)點(diǎn)u的右孩子，符合要求。

情形川：結(jié)點(diǎn)v的父結(jié)點(diǎn)要么是原先的父結(jié)點(diǎn)或兄弟結(jié)點(diǎn)。若結(jié)點(diǎn)u的父結(jié)點(diǎn)與v的父

結(jié)點(diǎn)是兄弟關(guān)系，則轉(zhuǎn)換之后，不可能出現(xiàn)結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)。

2.已知一棵有2011個(gè)結(jié)點(diǎn)的樹(shù)，其葉結(jié)點(diǎn)個(gè)數(shù)為116,該樹(shù)對(duì)應(yīng)的二叉樹(shù)中無(wú)右孩子的

結(jié)點(diǎn)個(gè)數(shù)是。

A.115B.116C.1895D.1896

答案：Do考查樹(shù)和二叉樹(shù)的轉(zhuǎn)換。

樹(shù)轉(zhuǎn)換為二叉樹(shù)時(shí)，樹(shù)中每一個(gè)分支結(jié)點(diǎn)的所有子結(jié)點(diǎn)中的最右子結(jié)點(diǎn)無(wú)右孩子，根結(jié)點(diǎn)轉(zhuǎn)

換后也沒(méi)有右孩子，因此，對(duì)應(yīng)的二叉樹(shù)中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)=分支結(jié)點(diǎn)數(shù)+1=2011-

116+1=1896。通常本題應(yīng)采用特殊法解，設(shè)題意中的樹(shù)是如下圖所示的結(jié)構(gòu)，則對(duì)應(yīng)的二

叉樹(shù)中僅有前115個(gè)葉結(jié)點(diǎn)有右孩Q子，故無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)=2011-115=1896。

O

;

:

共1895個(gè)中間結(jié)點(diǎn)

共11。個(gè)葉結(jié)點(diǎn)

題型四圖

一、圖的概念理解

1.下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是

I.所有頂點(diǎn)的度之和為偶數(shù)

II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1

III.至少有一個(gè)頂點(diǎn)的度為1

A,只有IB,只有IIC.I和IID.I和III

答案：Ao考查無(wú)向連通圖的特性。

每條邊都連接了兩個(gè)結(jié)點(diǎn)，則在計(jì)算頂點(diǎn)的度之和時(shí)，這條邊都被計(jì)算了兩次，故所有頂點(diǎn)

的度之和為邊數(shù)的兩倍，顯然必為偶數(shù)。而II和III則不一定正確，如對(duì)頂點(diǎn)數(shù)N>1無(wú)向完

全圖不存在一個(gè)頂點(diǎn)的度為1,并且邊數(shù)與頂點(diǎn)數(shù)的差要大于1

2.若無(wú)向圖G=(V,E)中含有7個(gè)頂點(diǎn)，要保證圖G在任何情況下都是連通的，則需要

的邊數(shù)最少是O

A.6B.15C.16D.21

答案：Co考查圖的連通性。

要保證無(wú)向圖G在任何情況下都是連通的，即任意變動(dòng)圖G中的邊，G始終保持連通,

首先需要G的任意6個(gè)結(jié)點(diǎn)構(gòu)成完全連通子圖G1,需15條邊，然后再添一條邊將第7

個(gè)結(jié)點(diǎn)與G1連接起來(lái)，共需16條邊。

3.下列關(guān)于圖的敘述中，正確的是一o

I.回路是簡(jiǎn)單路徑

II,存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間

III.若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路

A.僅IIB.僅I、IIC.僅IIID.僅I、III

答案：Co考查圖的基本概念。

回路對(duì)應(yīng)于路徑，簡(jiǎn)單回路對(duì)應(yīng)于簡(jiǎn)單路徑，故I錯(cuò)誤；稀疏圖是邊比較少的情況，此時(shí)用

鄰接矩陣必將浪費(fèi)大量的空間,應(yīng)該選用鄰接表，故II錯(cuò)誤。存在回路的圖不存在拓?fù)湫蛄校?/p>

故川正確。

二、圖的基本算法

1.對(duì)圖B-2進(jìn)行拓?fù)渑判?可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)

是_____0

圖B-2

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

答案：Bo考查拓?fù)渑判蛐蛄小?/p>

圖B-2中有3個(gè)不同的拓?fù)渑判蛐蛄?，分別為abcedsabecd、aebcd0

2.對(duì)如下有向帶權(quán)圖，若采用迪杰斯特拉(Dijkstra)算法求從源點(diǎn)a到其他各頂點(diǎn)的最

短路徑，則得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b,第二條最短路徑的目標(biāo)頂點(diǎn)是c,后續(xù)

得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是O

答案：C?？疾镈ijkstra算法最單源最短路徑。

從a到各頂點(diǎn)的最短路徑的求解過(guò)程：

頂點(diǎn)第1趟第2趟第3趟第4趟對(duì)5越

b(a,b)2

C(a,c)5(a,b,c)3

dCO(a,b,d)5(a,b,d)5(a.b,d)5

eooOO(a,b,c,f)4

fcooo(a,b,c,e)7(a,b,c,e)7(a,b,d,e)6

集合s{a,b}{a,b,c}{a,b,c,f){a,b,c,f,d){a,b,c,f,d,e}

后續(xù)目標(biāo)頂點(diǎn)依次為f,d,e,

3.下列關(guān)于最小生成樹(shù)的敘述中，正確的是。

I.最小生成樹(shù)的代價(jià)唯一

II.所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹(shù)中

III.使用普里姆（Prim）算法從不同頂點(diǎn)開(kāi)始得到的最小生成樹(shù)一定相同

IV,使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹(shù)總不相同

A.僅IB.僅IIC.僅I、川D.僅II、IV

答案：A?？疾樽钚∩蓸?shù)、及最小生成樹(shù)算法的性質(zhì)。

對(duì)于I,最小生成樹(shù)的樹(shù)形可能不唯一（這是因?yàn)榭赡艽嬖跈?quán)值相同的邊），但是代價(jià)一定是

唯一的，I正確。對(duì)于II,如果權(quán)值最小的邊有多條并且構(gòu)成環(huán)狀，則總有權(quán)值最小的邊將

不出現(xiàn)在某棵最小生成樹(shù)中，II錯(cuò)誤。對(duì)于此設(shè)N個(gè)結(jié)點(diǎn)構(gòu)成環(huán)，N-1條邊權(quán)值相等，

則從不同的頂點(diǎn)開(kāi)始普里姆算法會(huì)得到N-1中不同的最小生成樹(shù)，III錯(cuò)誤。對(duì)于IV.當(dāng)

最小生成樹(shù)唯一時(shí)（各邊的權(quán)值不同），普里姆算法和克魯斯卡爾算法得到的最小生成樹(shù)相

同，IV錯(cuò)誤。

題型五查找與排序

一'相關(guān)概念理解

1.下列敘述中，不符合m階B樹(shù)定義要求的是。

A.根結(jié)點(diǎn)最多有m棵子樹(shù)B.所有葉結(jié)點(diǎn)都在同一層上

C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過(guò)指針鏈接

答案：D?？疾閙階B-樹(shù)的定義。

選項(xiàng)A、B和C都是B-樹(shù)的特點(diǎn)，而選項(xiàng)D則是B+樹(shù)的特點(diǎn)。注意區(qū)別B-樹(shù)和B+

樹(shù)各自的特點(diǎn)。

2.已知關(guān)鍵字序列5,8,12.19.28.20,15,22是小根堆（最小堆），插入關(guān)

鍵字3,調(diào)整后得到的小根堆是

A.3,5,12,8,28,20,15,22,19

B.3,5,12,19,20,15,22,8,28

C.3,8,12,5,20,15,22,28,19

D.3,12,5,8,28,20,15,22,19

答案：A?？疾樾「训恼{(diào)整操作。

小根堆在邏輯上可以用完全二叉樹(shù)來(lái)表示，根據(jù)關(guān)鍵序列得到的小頂堆的二叉樹(shù)形式如圖

A-4a所示

插入關(guān)鍵字3時(shí)，先將其放在小頂堆的末端，再將該關(guān)鍵字向上進(jìn)行調(diào)整，得到的結(jié)果如

圖A-4b所示。所以，調(diào)整后的小頂堆序列為3.5,12,8,28,20,15,22,

19o

3.若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一

得到的第二趟排序后的結(jié)果，則該排序算法只能是。

A.冒泡排序B.插入排序C.選擇排序D.二路歸并排序

答案：Bo考查各排序算法的特點(diǎn)。

解答本題之前要對(duì)不同排序算法的特點(diǎn)極為清楚。對(duì)于冒泡排序和選擇排序而言，每趟過(guò)后

都能確定一個(gè)元素的最終位置，而由題目中所說(shuō)，前兩個(gè)元素和后兩個(gè)元素均不是最小或最

大的兩個(gè)元素并按序排列。答案D中的二路歸并排序，第一趟排序結(jié)束都可以得到若干個(gè)

有序子序列，而此時(shí)的序列中并沒(méi)有兩兩元素有序排列。插入排序在每趟排序結(jié)束后能保證

前面的若干元素是有序的，而此時(shí)第二趟排序后,序列的前三個(gè)元素是有序的，符合其特點(diǎn)。

4.已知一個(gè)長(zhǎng)度為16的順序表L,其元素按關(guān)鍵字有序排列。若采用折半查找法查找一

個(gè)L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多的是。

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

答案：Bo考查折半查找的過(guò)程。

具有n個(gè)結(jié)點(diǎn)的判定樹(shù)的高度為Iog2n+1,長(zhǎng)度為16,高度為5,所以最多比較5次。

5.采用遞歸方式對(duì)順序表進(jìn)行快速排序。下列關(guān)于遞歸次數(shù)的敘述中，正確的是o

A.遞歸次數(shù)與初始數(shù)據(jù)的排列次序無(wú)關(guān)

B.每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)

C.每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)

D.遞歸次數(shù)與每次劃分后得到的分區(qū)的處理順序無(wú)關(guān)

答案：Do考查快速排序。

遞歸次數(shù)與各元素的初始排列有關(guān)。如果每一次劃分后分區(qū)比較平衡，則遞歸次數(shù)少；

如果劃分后分區(qū)不平衡，則遞歸次數(shù)多。遞歸次數(shù)與處理順序無(wú)關(guān)。

6.對(duì)一組數(shù)據(jù)（2,12,16,88,5,10）進(jìn)行排序，若前三趟排序結(jié)果如下

第一趟排序結(jié)果：2,12,16,5,10,88

第二趟排序結(jié)果：2,12.5,10,16,88

第三趟排序結(jié)果：2,5,10,12,16,88

則采用的排序方法可能是。

A.冒泡排序B.希爾排序C.歸并排序D.基數(shù)排序

答案：A。考查各種排序算法的過(guò)程。

看第一趟可知僅有88被移到最后。

如果是希爾排序，則12,88,10應(yīng)變?yōu)?0,12,880因此排除希爾排序。

如果是歸并排序，則長(zhǎng)度為2的子序列是有序的。因此可排除歸并排序。

如果是基數(shù)排序，貝U16,5.10應(yīng)變?yōu)?0,5,160因此排除基數(shù)排序。

可以看到，每一趟都有一個(gè)元素移到其最終位置，符合冒泡排序特點(diǎn)。

7.為提高散列（Hash）表的查找效率，可以采取的正確措施是o

I.增大裝填（載）因子

II.設(shè)計(jì)沖突（碰撞）少的散列函數(shù)

III,處理沖突（碰撞）時(shí)避免產(chǎn)生聚集（堆積）現(xiàn)象

A.僅IB.僅IIC.僅I、IID.僅II、III

答案：D?？疾樯⒘斜淼男再|(zhì)。

Hash表的查找效率取決于：哈希函數(shù)、處理沖突的方法和裝填因子。顯然，沖突的產(chǎn)生概

率與裝填因子（即表中記錄數(shù)與表長(zhǎng)之比）的大小成正比，I錯(cuò)誤。沖突是不可避免的，

但處理沖突的方法應(yīng)避免非同義詞之間地址的爭(zhēng)奪，川正確。

8.為實(shí)現(xiàn)快速排序算法，待排序序列宜采用的存儲(chǔ)方式是o

A.順序存儲(chǔ)B.散列存儲(chǔ)C.鏈?zhǔn)酱鎯?chǔ)D.索引存儲(chǔ)

答案：A。考查排序的基本特點(diǎn)。

對(duì)絕大部分內(nèi)部排序而言，只適用于順序存儲(chǔ)結(jié)構(gòu)?？焖倥判蛟谂判虻倪^(guò)程中，既要從后向

前查找，也要從前向后查找，因此宜采用順序存儲(chǔ)。

9.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18,將其再調(diào)整

為大根堆，調(diào)整過(guò)程中元素之間進(jìn)行的比較次數(shù)是O

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

答案：B?？疾槎训恼{(diào)整。

首先18與10比較，交換位置，再與25比較，不交換位置。共比較了2次，調(diào)整的過(guò)

程如下圖所示

⑤插入結(jié)宓@，篩選單50

Cp?5

5血J|?Q?）?Q?

?OO?（

10.已知一棵3階B-樹(shù)，如下圖所示。刪除關(guān)鍵字78得到一棵新B-樹(shù)，其最右葉結(jié)點(diǎn)

中的關(guān)鍵字是_____。

A.60B.60,62C.62,65D.65

答案：D?？疾锽-樹(shù)的刪除操作。

對(duì)于上圖所示的3階B-樹(shù)，被刪關(guān)鍵字78所在結(jié)點(diǎn)在刪除前的關(guān)鍵字個(gè)數(shù)=1=3/2-

1,且其左兄弟結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=2>3/2,屬于“兄弟夠借”的情況，則需把該結(jié)點(diǎn)的

左兄弟結(jié)點(diǎn)中最大的關(guān)鍵字上移到雙親結(jié)點(diǎn)中，同時(shí)把雙親結(jié)點(diǎn)中大于上移關(guān)鍵字的關(guān)鍵字

下移到要?jiǎng)h除關(guān)鍵字的結(jié)點(diǎn)中，這樣就達(dá)到了新的平衡，如下圖所示：

二、排序算法的比較

1.在內(nèi)部排序過(guò)程中，對(duì)尚未確定最終位置的所有元素進(jìn)行一遍處理稱(chēng)為一趟排序。

下列排序方法中，每一趟排序結(jié)束都至少能夠確定一個(gè)元素最終位置的方法是

I.簡(jiǎn)單選擇排序II,希爾排序川.快速排序

IV.堆排序V.二路歸并排序

A.僅I、IlkIVB.僅I、lllsV

C.僅II、IlkIVD.僅川、IV、V

答案：A。考查各種內(nèi)部排序算法的性質(zhì)。

對(duì)于I,簡(jiǎn)單選擇排序每次選擇未排序列中的最小元素放入其最終位置。對(duì)于II.希爾排序

每次是對(duì)劃分的子表進(jìn)行排序，得到局部有序的結(jié)果，所以不能保證每一趟排序結(jié)束都能確

定一個(gè)元素的最終位置。對(duì)于川，快速排序每一趟排序結(jié)束后都將樞軸元素放到最終位置。

對(duì)于IV,堆排序?qū)儆谶x擇排序，每次都將大根堆的根結(jié)點(diǎn)與表尾結(jié)點(diǎn)交換,確定其最終位置。

對(duì)于V,二路歸并排序每趟對(duì)子表進(jìn)行兩兩歸并從而得到若干個(gè)局部有序的結(jié)果，但無(wú)法確

定最終位置。

2.對(duì)一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是

A.排序的總趟數(shù)B.元素的移動(dòng)次數(shù)

C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)

答案：Do考查折半插入和直接插入的區(qū)別。

折半插入排序與直接插入排序都是將待插入元素插入前面的有序子表，區(qū)別是：確定當(dāng)前記

錄在前面有序子表中的位置時(shí)，直接插入排序是采用順序查找法，而折半插入排序是采用折

半查找法。排序的總趟數(shù)取決于元素個(gè)數(shù)n,兩者都是n-1趟。元素的移動(dòng)次數(shù)都取決于

初試序列，兩者相同。使用輔助空間的數(shù)量也都是0(1)。折半插入排序的比較次數(shù)與序列

2

初態(tài)無(wú)關(guān)，為O(nlog2n)；而直接插入排序的比較次數(shù)與序列初態(tài)有關(guān)，為O(n)-O(n)o

題型六算法題

一、線性表算法題

1.(15分)已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為：

datalink

假設(shè)該鏈表只給出了頭指針listo在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法,

查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù))。若查找成功，算法輸出該結(jié)點(diǎn)的data

域的值，并返回1；否則，只返回Oo要求：

(1)描述算法的基本設(shè)計(jì)思想。

(2)描述算法的詳細(xì)實(shí)現(xiàn)步驟。

(3)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法(使用C、C++或Java語(yǔ)

言實(shí)現(xiàn))，關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。

答案：(1)算法的基本設(shè)計(jì)思想(5分)：

問(wèn)題的關(guān)鍵是設(shè)計(jì)一個(gè)盡可能高效的算法，通過(guò)鏈表的一趟遍歷，找到倒數(shù)第k個(gè)結(jié)點(diǎn)的

位置。算法的基本設(shè)計(jì)思想：定義兩個(gè)指針變量p和q,初始時(shí)均指向頭結(jié)點(diǎn)的下一個(gè)結(jié)

點(diǎn)(鏈表的第一個(gè)結(jié)點(diǎn)).p指針沿鏈表移動(dòng)，當(dāng)p指針移動(dòng)到第k個(gè)結(jié)點(diǎn)時(shí)，q指針

開(kāi)始與p指針同步移動(dòng)；當(dāng)p指針移動(dòng)到最后一個(gè)結(jié)點(diǎn)時(shí)，q指針?biāo)甘窘Y(jié)點(diǎn)為倒數(shù)第

k個(gè)結(jié)點(diǎn)。以上過(guò)程對(duì)鏈表僅進(jìn)行一遍掃描。

(2)算法的詳細(xì)實(shí)現(xiàn)步驟(5分)：

①count=0,p和q指向鏈表表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)；

②若p為空，轉(zhuǎn)⑤；

③若count等于k,則q指向下一個(gè)結(jié)點(diǎn)；否則，count=count+l：

④p指向下一個(gè)結(jié)點(diǎn)，轉(zhuǎn)②：

⑤若count等于k,則查找成功，輸出該結(jié)點(diǎn)的data域的值，返回1；否則，說(shuō)明k值

超過(guò)了線性表的長(zhǎng)度，查找失敗，返回0；

⑥算法結(jié)束。

(3)算法實(shí)現(xiàn)(5分)：

typedefintElemType;〃鏈表數(shù)據(jù)的類(lèi)型定義

typedefstructLNode{〃鏈表結(jié)點(diǎn)的結(jié)構(gòu)定義

ElemTypedata;〃結(jié)點(diǎn)數(shù)據(jù)

structLnode*link;〃結(jié)點(diǎn)鏈接指針

}*LinkList;

intSearch_k(LinkListlistjntk){〃查找鏈表list倒數(shù)第k個(gè)結(jié)點(diǎn)，并輸出該結(jié)點(diǎn)data域的值

LinkListp=list->link,q=list->link;〃指針p、q指示第一個(gè)結(jié)點(diǎn)

intcount=0;

while(p!=NULL){〃遍歷鏈表直到最后一個(gè)結(jié)點(diǎn)

if(count<k)count++;〃計(jì)數(shù)，若count<k只移動(dòng)p

elseq=q->link;p=p->link;〃之后讓p、q同步移動(dòng)

}//while

if(count<k)

return。"/查找失敗返回0

else{〃否則打印并返回1

printf(u%d,,,q->data);

return1;

)

}//Search_k

2.(13分)設(shè)將n(n>l)個(gè)整數(shù)存放到一維數(shù)組R中。試設(shè)計(jì)一個(gè)在時(shí)間和空間兩

方面都盡可能高效的算法。將R中保存的序列循環(huán)左移p(0<p<n)個(gè)位置，即將R中

的數(shù)據(jù)由(XO,XI,,Xn-l)變換為(Xp,Xp+l,,Xn-l,XO,XI,,Xp-l)。要求：

(1)給出算法的基本設(shè)計(jì)思想。

(2)根據(jù)設(shè)計(jì)思想，采用C或C++或Java語(yǔ)言描述算法，關(guān)鍵之處給出注釋。

(3)說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度

解法一：

解答：

(1)算法的基本設(shè)計(jì)思想：

可以將這個(gè)問(wèn)題