數(shù)據(jù)結(jié)構(gòu)（自考） 課后習(xí)題及解答

第一章緒論

一、單項(xiàng)選擇題

1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為。

A.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

答案：Bo

從邏輯角度看，基本的數(shù)據(jù)結(jié)構(gòu)包括4類，分別是集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)。

其中，樹結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)。集合也可以使用線性結(jié)構(gòu)表示。

2.數(shù)據(jù)元素可以細(xì)分為o

A.數(shù)據(jù)項(xiàng)B.字符C.二進(jìn)制位D.數(shù)據(jù)記錄

答案：Ao

根據(jù)定義，數(shù)據(jù)元索可以細(xì)分為數(shù)據(jù)項(xiàng)。字符和二進(jìn)制位都是表示數(shù)據(jù)的具體單位（選

項(xiàng)B和C都不正確）。數(shù)據(jù)元素有時(shí)稱為記錄（選項(xiàng)D不正確）。

3.如果說線性結(jié)構(gòu)中元素之間是一對(duì)一的關(guān)系，則樹結(jié)構(gòu)中元素之間的關(guān)系是。

A.一對(duì)一的B.一對(duì)多的C.多對(duì)多的D.不確定的

答案：Bo

線性結(jié)構(gòu)中，每個(gè)元素有唯一的前驅(qū)和唯一的后繼，所以對(duì)于每個(gè)元素而言，它對(duì)應(yīng)唯

一的后繼，形成一對(duì)一的關(guān)系。當(dāng)然，首元素和尾元素除外。在樹結(jié)構(gòu)中，每個(gè)元素僅有唯

一的前驅(qū)，但可以有多個(gè)言繼，所以是一對(duì)多的關(guān)系。當(dāng)然，樹中的根（最前面的元素）和

葉結(jié)點(diǎn)（后面的元素）除外。圖結(jié)構(gòu)中是多對(duì)多的關(guān)系，每個(gè)元素可以有多個(gè)前驅(qū)，也可以

有多個(gè)后繼。

4.下列選項(xiàng)中，不屬于數(shù)據(jù)結(jié)構(gòu)常用存儲(chǔ)方式的是。

A.順序存儲(chǔ)方式B.鏈?zhǔn)酱鎯?chǔ)方式C.分布存儲(chǔ)方式D.散列存儲(chǔ)方式

答案：Co

數(shù)據(jù)結(jié)構(gòu)課程中沒有討論分布存儲(chǔ)方式，除了選項(xiàng)口給定的A、B和D以外，還討論了

索引存儲(chǔ)方式。這是數(shù)據(jù)結(jié)構(gòu)中常用的4種存儲(chǔ)方式.

5.算法分析要評(píng)估的兩個(gè)主要方面是。

A.正確性和簡(jiǎn)明性B.時(shí)間復(fù)雜性和空間復(fù)雜性

C.可讀性和可維護(hù)性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

答案：Bo

算法的正確性是必須的，簡(jiǎn)明性、可讀性、可維護(hù)性等都不是算法要評(píng)估的內(nèi)容（選項(xiàng)

A和選項(xiàng)C不正確），它們都屬于算法應(yīng)具備的眾多特性中的內(nèi)容。數(shù)據(jù)復(fù)雜性是數(shù)據(jù)本身

的狀態(tài)，也不是算法要評(píng)估的，程序復(fù)雜性說得不明確（選項(xiàng)D不正確）。算法要評(píng)估的是

時(shí)間和空間復(fù)雜性。

6.下列選項(xiàng)中，定義抽象數(shù)據(jù)類型時(shí)不需要做的事情是。

A.給出類型的名字B.定義類型上的操作

C.實(shí)現(xiàn)類型上的操作D.用某種語言描述抽象數(shù)據(jù)類型

答案：Co

定義抽象數(shù)據(jù)類型時(shí)，需要給類型命名（選項(xiàng)A）,需要指明相關(guān)的操作有哪些（選項(xiàng)

B）,需要使用程序語言或是自然語言描述抽象數(shù)據(jù)類型（選項(xiàng)D）。在確定了存儲(chǔ)結(jié)構(gòu)之后

才能具體實(shí)現(xiàn)操作過程，所以在定義抽象數(shù)據(jù)類型階段，不涉及這些操作的實(shí)現(xiàn)。

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

x=2;

while(x<n/2)

x=2*x;

A.O(log2〃)B.0(〃)C.0(〃log2〃)D.O(/r)

答案：Ao

〃是輸入規(guī)模。x從2開始，每次倍增，達(dá)到或超過n/2時(shí)倍增的次數(shù)與log2〃的大小相

當(dāng)。

8.設(shè)〃是描述問題規(guī)模的非負(fù)整數(shù)，下列程序片段的時(shí)間復(fù)雜度是o

X=1;

while(n>=(x+1)*(x+1))

x=x+l;

A.0(〃'/)B.O(log2〃)C.0(n)D.0(nlogin)

答案：Ao

二、填空題

1.在數(shù)據(jù)結(jié)構(gòu)課程中，將所有能輸入計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)集合稱為

答案：數(shù)據(jù)。

2.構(gòu)成數(shù)據(jù)的基本單位是o

答案：數(shù)據(jù)元素。

3.數(shù)據(jù)元素及其關(guān)系在L算機(jī)內(nèi)的存儲(chǔ)方式稱為數(shù)據(jù)的。

答案：存儲(chǔ)結(jié)構(gòu)。

4.數(shù)據(jù)的邏輯結(jié)構(gòu)表示數(shù)據(jù)元素之間的關(guān)系，與存儲(chǔ)關(guān)系是o

答案：無關(guān)的。

5.構(gòu)成索引表的基本內(nèi)容是。

答案：索引項(xiàng)。

6.一個(gè)算法必須在執(zhí)行有為步之后結(jié)束，這個(gè)特性是算法的。

答案：有窮性。

三、解答題

1.舉例說明計(jì)算機(jī)能處理哪些數(shù)據(jù)？

【參考答案】計(jì)算機(jī)能處理的數(shù)據(jù)多種多樣，大到可以是一幅地圖、一本書、一部電影，

小到可以是一個(gè)字符，甚至是計(jì)算機(jī)中的一位?？梢允菙?shù)值型的數(shù)據(jù)，也可以是非數(shù)值型的

數(shù)據(jù)。只可以是簡(jiǎn)單結(jié)構(gòu)的，也可以是復(fù)雜結(jié)構(gòu)的。

2.線性結(jié)構(gòu)中，如何理解元素之間是一對(duì)一的關(guān)系？

【參考答案】線性結(jié)構(gòu)中，除表頭元素和表尾元素外，每個(gè)元素有唯一的前驅(qū)和唯一的

后繼。所以對(duì)于每個(gè)元素而言，當(dāng)有后繼時(shí)，它與其后繼形成一對(duì)一的關(guān)系。

3.定義代表交通工具的拍象數(shù)據(jù)類型vehicle,添加必要的數(shù)據(jù)和操作。

【參考答案】對(duì)?于vehicle,可以定義表示其基本屬性的數(shù)據(jù)，包括品牌brand、顏色color.

價(jià)格price等。相應(yīng)的操作可以是設(shè)置最大速度setSpeed(intspeed)、設(shè)置自重setdeadweight(int

weight)等。

ADTvehicle(〃交通工具的抽象數(shù)據(jù)類型定義

數(shù)據(jù)部分：

brand：〃品牌，字符串

color：//顏色，字符串

price：〃價(jià)格，實(shí)型

speed：//最大速度，實(shí)型

deadweight：〃自重，實(shí)型，單位噸

操作部分：

setSpeed(speed)：〃設(shè)置最大速度

輸入：speed

輸出：是否設(shè)厘成功

前提條件：設(shè)置的speed值不能超出限制

setdeadweight(weight)：〃設(shè)置自重

輸入：weight

輸出：是否設(shè)置成功

前提條件：設(shè)置的weight值不能超出限制

4.定義表示復(fù)數(shù)的抽象數(shù)據(jù)類型。

【參考答案】復(fù)數(shù)由實(shí)部和虛部表示，實(shí)部和虛部都是實(shí)型值。相應(yīng)的操作有算術(shù)操作。

ADTcomplex(〃復(fù)數(shù)的抽象數(shù)據(jù)類型定義

數(shù)據(jù)部分：

real：〃實(shí)部，實(shí)型

imaginary：〃虛部，實(shí)型

操作部分：

add(complexl,complex?)：//加法

輸入：兩個(gè)復(fù)數(shù)

輸出：它們的和

前提條件：兩個(gè)復(fù)數(shù)正確

sub(complexl,conplex2)：〃減法

輸入：兩個(gè)復(fù)數(shù)

輸出：它們的差

前提條件：兩個(gè)復(fù)數(shù)正確

multiplication(complexl,complex2)：〃乘法

輸入：兩個(gè)復(fù)數(shù)

輸出：它們的積

前提條件：兩個(gè)復(fù)數(shù)正確

division(complexl,complex2)：//除法

輸入：兩個(gè)夏數(shù)

輸出：它們的商

前提條件：兩個(gè)第數(shù)正確

5.為什么不使用算法的絕對(duì)運(yùn)行時(shí)間來衡顯算法的時(shí)間效率？

【參考答案】同一個(gè)算法處理不同數(shù)量的數(shù)據(jù)時(shí)，所花的絕對(duì)運(yùn)行時(shí)間可能不同。同一

個(gè)算法處理相同數(shù)量的數(shù)據(jù)時(shí)，在不同配置的電腦上的絕對(duì)運(yùn)行時(shí)間也可能不同。所以，使

用算法的絕對(duì)運(yùn)行時(shí)間不能有效衡量算法的時(shí)間效率。

6.評(píng)估算法的空間效率時(shí)，需要考慮占用的哪些存儲(chǔ)空間？

【參考答案】算法運(yùn)行過程中，臨時(shí)占用的空間大小是要考慮的存儲(chǔ)空間。算法代碼占

川的空間、算法中初始數(shù)據(jù)占用的存儲(chǔ)空間不考慮在內(nèi)。

四、算法設(shè)計(jì)題

1.試設(shè)計(jì)一個(gè)算法，使用最少的比較次數(shù)找出三個(gè)不同整數(shù)的中值。

【參考答案】

intmiddle(inta,intb,intc)

{

if(a>b){

if(b>c)returnb;//a>b>c

elseif(a>c)returnc;//a>c>b

elsereturna;//c>b>a

I

else{

if(a>c)returna;//b>a>c

elseif(b>c)returnc;//b>c>a

elsereturnb;//c>b>a

}

2.試設(shè)計(jì)一個(gè)算法，對(duì)于給定的正整數(shù)〃，列出斐波那契數(shù)列的前〃項(xiàng)。

【參考答案】斐波那契數(shù)列的前兩項(xiàng)均為1，從第二項(xiàng)開始，每一項(xiàng)都是其前兩項(xiàng)之

和。使用整型變量fl、粒和f3表示數(shù)列中相鄰三項(xiàng)的值，初始時(shí)，fl和f2的值均為1。

然后計(jì)算新的項(xiàng)f3=fl+f2,計(jì)算后用f2的值更新fl,用f3的值更新￡2。

voidfibonacci(intn)

(

intfl=l,f2=lzf3,i;

if(n<=0){

printf("n值錯(cuò)誤\n");

return;

}

elseif(n==l){

printf("l\n");

return;

else{

printf("11");

for(i=3;i<=n;i++){

f3=fl+f2;

printf(n%d”，f3);

fl=f2;

f2=f3;

}

printf("\n");

第二章線性表

?、單項(xiàng)選擇題

1.下列選項(xiàng)中，不是鏈表特點(diǎn)的是_______。

A.插入、刪除時(shí)不需要移動(dòng)元素B.可隨機(jī)訪問任一元素

C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與元素個(gè)數(shù)成正比

答案：Bo

鏈表中的元素可以不必保存在相鄰的地址空間中，所以當(dāng)鏈表中的元素個(gè)數(shù)有變化時(shí)，

其他的元素不必像順序表那樣進(jìn)行移動(dòng)（選項(xiàng)A）。而且鏈表占用的空間隨需分配，隨用隨

分配，不必提前預(yù)估數(shù)量（選項(xiàng)C）,表中有多少個(gè)元素就分配多少個(gè)表結(jié)點(diǎn)（選項(xiàng)D）。但

要訪問鏈表中的元素時(shí)，只能從表頭開始，沿指針的指示逐個(gè)結(jié)點(diǎn)地查找下去，所以不能像

在數(shù)組中那樣通過下標(biāo)定位到所需的地址，即不能實(shí)現(xiàn)隨機(jī)訪問。

2.下列關(guān)于線性表的敘述中，錯(cuò)誤的是o

A.線性表采用鏈?zhǔn)酱鎯?chǔ)方式，便于進(jìn)行插入和刪除操作

B.線性表采用順序存儲(chǔ)方式，便于進(jìn)行插入和刪除操作

C.線性表采用鏈?zhǔn)酱鎯?chǔ)方式，不必占用一片連續(xù)的存儲(chǔ)單元

D.線性表采用順序存儲(chǔ)方式，必須占用一片連續(xù)的存儲(chǔ)單元

答案：Bo

線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，各

元素要連續(xù)存放（選項(xiàng)D）,當(dāng)有插入和刪除操作時(shí)，通常會(huì)導(dǎo)致其他元素的移動(dòng)（選項(xiàng)B

不正確）。當(dāng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，因?yàn)楦鹘Y(jié)點(diǎn)的地址并不要求是相鄰的（選項(xiàng)C）,所以插

入和刪除操作不會(huì)引起其他元素的移動(dòng)（選項(xiàng)A）。

3.若線性表L最常用的操作是訪問任一位置的元素和在最后進(jìn)行插入和刪除運(yùn)算，為使操

作的時(shí)間復(fù):雜度好，則下列選項(xiàng)中，為L(zhǎng)選擇的存儲(chǔ)結(jié)構(gòu)為o

A.順序表B.雙向鏈表

C.帶頭結(jié)也的雙向循環(huán)鏈表D.單循環(huán)鏈表

答案：Ao

采用順序存儲(chǔ)結(jié)構(gòu)保存線性表時(shí)，能以。（1）訪問線性表任一位置的元素。要在線性表中

間位置進(jìn)行插入和刪除時(shí)，會(huì)引發(fā)部分元素在數(shù)組中的移動(dòng)，但如果僅在最后位置進(jìn)行插入

和刪除，則避免了元素的移動(dòng)，操作也能達(dá)到。（1）。選項(xiàng)B、C和D都是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，

雖然它們進(jìn)行插入和刪除操作時(shí)能達(dá)到。（1）,但訪問任一位置元素時(shí)，平均情況下，僅能達(dá)

到。（〃）。綜合來看，選擇順序表更合適。

4.線性表L中最常用的操作是在最后?個(gè)元素之后插入?個(gè)元素和刪除第一個(gè)元素，為使

操作的時(shí)間復(fù)雜度好，則下列選項(xiàng)中，為L(zhǎng)選擇的存儲(chǔ)結(jié)構(gòu)為。

A.單鏈表B.僅有頭指針的單循環(huán)鏈表

C.雙向鏈表D.僅有尾指針的單循環(huán)鏈表

答案：Do

4個(gè)選項(xiàng)給出的都是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。根據(jù)題意，操作的位置是表尾和表頭，所以要選擇

能快速訪問這兩個(gè)位置的結(jié)構(gòu)。

單鏈表中僅有表頭指針，能快速訪問表頭，但不能快速訪問表尾。單循環(huán)鏈表中，通過

頭指針能快速訪問表頭位置，訪問表尾也是不方便的。雙向鏈表也是類似的。選項(xiàng)D給出

的鏈表，通過尾指針可以快速訪問到表尾結(jié)點(diǎn)，實(shí)現(xiàn)在其之后的插入，也能通過表尾結(jié)點(diǎn)的

next指針快速找到表頭結(jié)點(diǎn)，實(shí)現(xiàn)刪除操作。所以，僅有尾指針的單循環(huán)鏈表是最合適的結(jié)

構(gòu)。

5.為了提供全程對(duì)號(hào)的高速鐵路售票系統(tǒng)，保證每一位旅客從上車到下車期間都有獨(dú)立座

位，短途乘客卜.車后該座位可以銷售給其他乘客，鐵路公司設(shè)計(jì)了基于內(nèi)存的系統(tǒng)，系

統(tǒng)中需要描述座位信息和每個(gè)座位的售票情況。保存座位信息和每個(gè)座位售票情況的數(shù)

據(jù)結(jié)構(gòu)分別是。

A.數(shù)組，數(shù)組B.數(shù)組，鏈表

C.鏈表，數(shù)組D.鏈表，鏈表

答案：Bo

高鐵上，每節(jié)車廂都有自己固定的座位數(shù)，不變化，所以可以使用數(shù)組來描述座位。但

每個(gè)座位的售票情況是隨時(shí)變化的，應(yīng)當(dāng)使用動(dòng)態(tài)的結(jié)構(gòu)來描述，故選用鏈表來描述。

6.若長(zhǎng)度為〃的線性表采用順序存儲(chǔ)結(jié)構(gòu)，則在其第個(gè)位置插入一個(gè)新元素的算

法的時(shí)間復(fù)雜度為O

A.0(1)B.。⑺C.。(〃)D.0(〃2)

答案：Co

順序表中，插入操作會(huì)導(dǎo)致從插入位置至表尾的全部元素依次后移一個(gè)位置。平均情況

下，要移動(dòng)一半的元素，所以時(shí)間復(fù)雜度是。(〃)。

7.對(duì)于含n個(gè)元素采用順序存儲(chǔ)的線性表，訪問位置z(O<i<n-l)處的元素和在位置KO<i<n)

插入元素的時(shí)間復(fù)雜度分別為。

A.。(〃)和。(〃)B.。⑺和。⑴C.0⑴和。(〃)D.0(1)和0(1)

答案：Co

順序表中，訪問結(jié)點(diǎn)時(shí)可以根據(jù)下標(biāo)直接計(jì)算地址，所以時(shí)間復(fù)雜度是0(1)。而插入結(jié)

點(diǎn)的時(shí)間復(fù)雜度是05)。

8.線性表(ao,ai,…,az)以鏈接方式存儲(chǔ)時(shí)，訪問位置i的元素的時(shí)間復(fù)雜度為。

A.0(1)B.0(/-1)C.。⑺D.。(〃)

答案：D。

鏈?zhǔn)酱鎯?chǔ)線性表時(shí)，如果要訪問表中的結(jié)點(diǎn)，通常會(huì)從表頭開始，逐個(gè)結(jié)點(diǎn)依次遍歷過

來，平均而言，要訪問表中一半的元素。

9.在帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表head中，指向尾結(jié)點(diǎn)的指針p滿足的條件是o

A.p==NULLB.p==head

C.p->next==headD.p->next==NULL

答案：Co

若單循環(huán)鏈表head非空，則必有尾結(jié)點(diǎn)，尾結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)，也就是說，p指

向結(jié)點(diǎn)的next值應(yīng)該等于head的值(選項(xiàng)C正確)。

若指針p的值是NULL(選項(xiàng)A),則表示指針p沒有指向任何結(jié)點(diǎn)。若p==head(選

項(xiàng)B),則表示p與頭指針指向相同，而頭指針指向的是頭結(jié)點(diǎn)(虛擬結(jié)點(diǎn))，在非空鏈表中，

尾結(jié)點(diǎn)不是頭結(jié)點(diǎn)。如果不是循環(huán)鏈表，則尾結(jié)點(diǎn)的next值為NULL(選項(xiàng)D)。

10.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是o

A.head==NULLB.head!=NULL

C.head->next==headD.head->next==NULL

答案：Do

帶頭結(jié)點(diǎn)的空單鏈表是僅含有頭結(jié)點(diǎn)(虛擬結(jié)點(diǎn))的鏈表，頭結(jié)點(diǎn)的nexl值為NULL,

即它沒有后繼結(jié)點(diǎn)。因?yàn)楹蓄^結(jié)點(diǎn)，故頭指針head在任何時(shí)刻都不能為空(選項(xiàng)A不正

確)。對(duì)于空表與非空表，head!=NULL(選項(xiàng)B)都是成立的，所以用這個(gè)條件不能判定表

是否為空。head->next==head表明頭結(jié)點(diǎn)的next指針又指向頭結(jié)點(diǎn)，這是空循環(huán)鏈表的狀

態(tài)。hcad->ncxt==NULL表示的是頭指針指向的結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，這正是空鏈表要滿足的

條件。

11.在雙向循環(huán)鏈表中，在指針p所指結(jié)點(diǎn)之后插入指針s所指結(jié)點(diǎn)的操作是。

A.p->next=s;s->prev=p;p->nexl->prev=s;s->next=p->next;

B.p->next=s;p->next->prev=s;s->prev=p;s->next=p->next;

C.s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;

D.s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;

答案：De

解答這樣的題目時(shí)，畫圖是個(gè)不錯(cuò)的方法。比如，執(zhí)行了選項(xiàng)A中前兩個(gè)語句

（p->next=s;s->prev=p;）后,得到的鏈表狀態(tài)如圖2.1所示。

圖2.1對(duì)應(yīng)于選項(xiàng)A的單鏈表

其中，第3個(gè)語句"p->ncxt->prcv=s;"是將結(jié)點(diǎn)X的prev指針又指【可自己,這顯然是錯(cuò)誤

的。其他的3個(gè)選項(xiàng)，可以畫出類似的鏈表狀態(tài)。

12.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)

點(diǎn)，則執(zhí)行的操作是O

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;D.p->next=s;s->next=q;

答案：Co

以選項(xiàng)A為例，執(zhí)行了其中的兩條語句后，單鏈表的狀態(tài)如圖2.2所示。這表明，結(jié)點(diǎn)

s插入在了結(jié)點(diǎn)p的后面，而不是插入在q和p之間。

圖2.2對(duì)應(yīng)于選項(xiàng)A的單鏈表

13.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是終端結(jié)點(diǎn)，在p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)，則

執(zhí)行的操作是。

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;D.p->next=s;s->next=p;

答案：Bo

二、填空題

1.線性表是一個(gè)有限序列，組成線性表的是〃（〃20）個(gè)o

答案：同類型的數(shù)據(jù)元素，

線性表的定義要求組成線性表的數(shù)據(jù)元素是同類型的。

2.不帶頭結(jié)點(diǎn)的單鏈表L（head為頭指針）為空的判定條件是。

答案：head==NULLo

不帶頭結(jié)點(diǎn)的空單鏈表中一個(gè)結(jié)點(diǎn)都沒有，頭指針的值為NULLo

3.帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L(head為頭指針)為空的條件是。

答案：hcad->ncxt==hcad或是hcad->prcv==hcad

帶頭結(jié)點(diǎn)的空雙向循環(huán)鏈表中僅有一個(gè)頭結(jié)點(diǎn)，且這個(gè)結(jié)點(diǎn)的next指針和prev指針都

指向結(jié)點(diǎn)本身，即與head指向相同。

4.在帶頭結(jié)點(diǎn)的單鏈表中，當(dāng)刪除某一指定結(jié)點(diǎn)時(shí)，必須要找到該結(jié)點(diǎn)的。

答案：前驅(qū)。

被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)，變?yōu)楸粍h除結(jié)點(diǎn)原前驅(qū)結(jié)點(diǎn)的后繼，所以要找到前驅(qū)結(jié)點(diǎn)，并

修改它的next值。

三、解答題

1.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？

【參考答案】在單鏈表中進(jìn)行插入和刪除操作時(shí)，都要找到操作位置結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

但根據(jù)線性表當(dāng)前指針的原始定義，前驅(qū)結(jié)點(diǎn)是不能通過當(dāng)前指針直接找到的。所以，修改

當(dāng)前指針指向的結(jié)點(diǎn)，讓其前移一個(gè)位置，即指向操作位置的前驅(qū)結(jié)點(diǎn)。這樣修改后，通過

當(dāng)前指針很容易訪問到插入和刪除操作所涉及的各個(gè)結(jié)點(diǎn)。但當(dāng)操作位置是第一個(gè)結(jié)點(diǎn)時(shí)，

或是單鏈表是空表時(shí)，當(dāng)前指針的指向又成為特殊情況，需要單獨(dú)處理。為了能統(tǒng)一處理各

種情況，給單鏈表添加一個(gè)虛擬結(jié)點(diǎn)，即頭結(jié)點(diǎn)，從而減少實(shí)現(xiàn)插入和刪除操作時(shí)對(duì)特殊情

況的判定及處理情況。

2.什么是單鏈表中的頭結(jié)點(diǎn)、第一個(gè)數(shù)據(jù)結(jié)點(diǎn)和頭指針？

【參考答案】單鏈表中保存線性表中各數(shù)據(jù)的結(jié)點(diǎn)是數(shù)據(jù)結(jié)點(diǎn)，這些結(jié)點(diǎn)中的第一個(gè)是

第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。它的前面是一個(gè)虛擬結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。一個(gè)特殊的指向單鏈表中最前面

結(jié)點(diǎn)的指針是頭指針。如果單鏈表中一個(gè)結(jié)點(diǎn)都沒有，則頭指針為空。

3.假設(shè)線性表L=(51,40,19,15,24,36),使用線性表ADT中定義的方法,列出刪除19時(shí)

對(duì)應(yīng)的語句序列。

【參考答案】

if(?isEmpty(L)){

intpos,x;

pos=find(L,19);

if(pos>=0)remove(&L,pos,&x);

)

4.已知線性表中一個(gè)元素占8個(gè)字節(jié)，一個(gè)指針占2個(gè)字節(jié)，數(shù)組的大小為20個(gè)元素。在

順序及鏈?zhǔn)絻煞N存儲(chǔ)方式中，線性表應(yīng)該采用哪種方式保存？為什么？

【參考答案】設(shè)線性表中元素個(gè)數(shù)為〃。單純考慮空間復(fù)雜度。

采用順序存儲(chǔ)時(shí)，占用的空間大小=20x8=160個(gè)字節(jié)。

采用鏈?zhǔn)酱鎯?chǔ)時(shí)，假設(shè)采用單鏈表存儲(chǔ)，占用的空間大小二”(8+2)=10〃個(gè)字節(jié)。

列方程，10〃=160,求得〃=16。即若線性表中元素個(gè)數(shù)少于16個(gè)時(shí)，采用單鏈表保存

更好，元素個(gè)數(shù)多于16個(gè)時(shí)，采用數(shù)組保存更好。等于16個(gè)時(shí)，兩種方式保存的效果是一

樣的。

5.在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到表中的任何一個(gè)結(jié)點(diǎn)？

【參考答案】在單鏈表和雙向鏈表中，如果是從頭結(jié)點(diǎn)或第一個(gè)數(shù)據(jù)結(jié)點(diǎn)出發(fā)，能訪問

到表中的任一結(jié)點(diǎn)，但從其他結(jié)點(diǎn)出發(fā)，都只能訪問到該結(jié)點(diǎn)及其全部的后繼結(jié)點(diǎn)，它的前

驅(qū)結(jié)點(diǎn)是訪問不到的。

6.線性表(ao,ai,…,a.)采用順序存儲(chǔ)方式時(shí)，器和器+i(0<i<n-l)的物理位置相鄰嗎?采

用鏈?zhǔn)椒绞綍r(shí)呢？

【參考答案】采用順序存儲(chǔ)方式時(shí)，a和(O<i<n-1)的物理位置是相鄰的。采用鏈

式存儲(chǔ)時(shí)，雷和ai+i(OWKn-1)的物理位置不一定是相鄰的?？赡芟噜徱部赡懿幌噜彙?/p>

7.試分析雙向鏈表中插入、刪除、查找等基本操作的時(shí)間復(fù)雜度。

【參考答案】在雙向鏈表中進(jìn)行插入和刪除操作時(shí)，如果給定了當(dāng)前指針，則插入操作

和刪除操作的時(shí)間復(fù)雜度均為0(1)，因?yàn)椴僮鬟^程中不需要進(jìn)行元素的移動(dòng)，也不需要將

當(dāng)前指針從表頭后移到當(dāng)前位置.。查找操作的時(shí)間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而

定的。若在雙向鏈表中一定能找到查找目標(biāo)，則最優(yōu)情況下，比較1次就能找到，時(shí)間復(fù)雜

度為。(I)。最壞的情況下，需要進(jìn)行〃次比較，時(shí)間更雜度為。(〃)。平均來看，需要查找

約一半的鏈表，所以時(shí)間復(fù)雜度是0(〃)。

四、算法閱讀題

1.在如主教材圖2.13(b)所示的帶頭結(jié)點(diǎn)的非空循環(huán)鏈表中保存了若干整數(shù)。算法average求

出這些整數(shù)的平均值。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。

floataverage(LinkListhead)

(

LinkNode*p;

intcounter=0,sum=O;

if(head==NULL){

printf(“鏈表錯(cuò)誤\n");

return0;

}

if((D)prints("這是一個(gè)空鏈表\n");

else(

p=head->next;

while((2)){

counter++;

sum+=p->data;

p=p->next;

}

}

return(3);

)

【參考答案】

(1)head->next==head

(2)p!=head

(3)sum*l.0/counter

對(duì)于(1),根據(jù)后面輸出的內(nèi)容可知，這里需要補(bǔ)上判定空表的條件。帶頭結(jié)點(diǎn)的空循

環(huán)鏈表只含有一個(gè)頭結(jié)點(diǎn)，且該結(jié)點(diǎn)的next域指向結(jié)點(diǎn)本身。

對(duì)于(2),根據(jù)題意，循環(huán)體中要對(duì)?表中的全部結(jié)點(diǎn)進(jìn)行處理。進(jìn)入循環(huán)之前，指針p

指向了第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。while循環(huán)的結(jié)束條件是什么呢？當(dāng)指針p轉(zhuǎn)回到表頭時(shí)，表明已

經(jīng)處理完全部的數(shù)據(jù)結(jié)點(diǎn)，此時(shí)循環(huán)可以結(jié)束。也就是在p沒有指向頭結(jié)點(diǎn)時(shí)，循環(huán)不結(jié)

束。當(dāng)p==head時(shí)表明p指向頭結(jié)點(diǎn)，當(dāng)p!=head時(shí)表明p沒有指向頭結(jié)點(diǎn)。

對(duì)于(3),返回的是表中元素的平均值。while循環(huán)體中已經(jīng)計(jì)算了全部元素的和及元

素個(gè)數(shù)，兩個(gè)值做除法就可以了。注意不要進(jìn)行整除，兩個(gè)整數(shù)相除，結(jié)果可能除不盡，是

個(gè)實(shí)型值。

2.單鏈表的結(jié)點(diǎn)及鏈表定義如下：

typedefstructnode{

intdata;//數(shù)據(jù)域

structnode*next;〃指針域

JLinkNode;

typedefLinkNode*LinkList;〃單鏈表

算法largest找出這些整數(shù)中的最大值。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)內(nèi)容將算法補(bǔ)充完整。

intlargest(LinkListhead)

(

LinkNode*p;

intmaxitem;

if(head==NULL){

printf("鏈表錯(cuò)誤\n");

return0;

}

iff(1))printf("這是一個(gè)空鏈表\n");

else{

p-hcad->ncxt;

maxitem=p->data;

p=p->next;

while(p!=NULL){

iff(2))(3);

p=p->next;

}

}

returnmaxitem;

)

【參考答案】

(1)head->next==NULL

(2)p->data>maxitem

(3)maxitem=p->data

對(duì)于(1),空單鏈表中僅含有一個(gè)頭結(jié)點(diǎn)，頭指針指向結(jié)點(diǎn)的nexl域?yàn)镹ULL。

根據(jù)題意，要記錄表中元素的最大值，這由if語句來完成。顯然，if的條件是篩選最大

值，后面的語句是將最大值保存下來。relurn語句中返I口I的是maxilem的值，意味著這個(gè)變

量是用來保存最大值的，所以(3)的內(nèi)容很容易寫下來，就是將當(dāng)前結(jié)點(diǎn)中的值賦給maxitem。

那么，當(dāng)前結(jié)點(diǎn)需要滿足什么條件呢？是要大于原來保存的maxiiem值，這是(2)要填寫

的內(nèi)容。

3.閱讀程序，并回答下列問題。

intcounterofodd(LinkListhead)

(

LinkNode*p;

intcounter=0;

if(head==NULL)(printf("鏈表錯(cuò)誤\n");return0;)

if(head->next==NULL)printf("這是一-個(gè)空鏈表\r");

else{

p=head->next;

while(p!=NULL){

if(p->data%2.=0)counter++;

p=p->next;

}

}

returncounter;

)

(1)若單鏈表head中保存的是(1,3,5,7,10),則執(zhí)行cointcrofodd(hcad)后，返回的結(jié)果是什

么？

(2)counterofodd。的功能是什么？

【參考答案】

(1)返回的結(jié)果是4。

(2)counierofodd()的功能是統(tǒng)計(jì)單鏈表head中保存的奇數(shù)的個(gè)數(shù)。

五、算法設(shè)計(jì)題

1.設(shè)有一個(gè)正整數(shù)序列組成的有序單鏈表(按遞增次序有序，且允許有相等的整數(shù)存在),

試編寫能實(shí)現(xiàn)下列功能的算法：

(1)確定在序列中比正整數(shù)x大的數(shù)有幾個(gè)(相同的數(shù)只計(jì)算一次，如有序序列

{10,20,30,30,40,41:50,50,51}中比30大的數(shù)有4個(gè));

(2)將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，仍放置在單鏈表中；如保存有序

序列{10,20,30,30,40,41,50,50,51}的單鏈表中，將比40小的數(shù)重排后，得到的單鏈

表中保存的序列是{30,30,20,10,40,41,50,50,51},

(3)將比x大的偶數(shù)從單鏈表中刪除。

【參考答案】

(1)程序?qū)崿F(xiàn)如下所示。

intlargerthanx(LinkListhead,intx)

intcounter=0,lastone;

LinkNode*p;

if(head==NULL){

printf(“鏈表錯(cuò)誤\n");

return0;

}

if(head->next==NULL)printf("這是一個(gè)空鏈表\r");

else{

p=head->next;

lastone=p->data-l;

while(p!=NULL){

if(p->data>x){

if(p->data>lastone){

counter++;

lastone=p->data;

)

}

p=p->next;

}

returncounter;

因?yàn)閱捂湵碛行?，所以，如果有相同的整?shù)，則它僅一定是相鄰的。使用變量laslone記

錄前一個(gè)整數(shù)，如果當(dāng)前整數(shù)與lastone相等，則不計(jì)數(shù)。lastone的初值設(shè)為比第一個(gè)整數(shù)

小的任何數(shù)即可。

（2）程序?qū)崿F(xiàn)如下所示.

intreversesmallthanxiLinkListhead,intx)

(

LinkNode*left,"middle,*right,*temp;

if(head==NULL){

printf("鏈表錯(cuò)誤\nn);

return0;

}

if(head->next==NULL){

printf(“這是一個(gè)空鏈表\n”)；

return1;

else{

temp=left=head->next;

if(left!=NULL)niddle=left->next;

while(middle!=NULL&&middle->data<x){

right=middle->next;

middle->next=left;

left=midcile;

middle=right;

if(middle==NULL){

temp->next=NULL;

head->next=left;

else{

temp->next=middle;

head->next=left;

return1;

將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，實(shí)際上是將單鏈表前面的若干結(jié)點(diǎn)逆

置。與教材第二章第五節(jié)中給出的reverse有些類似，但情況更復(fù)雜一些。當(dāng)找不到比x小

的元素時(shí)，單鏈表維持不變。當(dāng)所有元素均小于x時(shí)，整個(gè)鏈表逆置。當(dāng)部分元素小于x時(shí)，

只逆置前面的這些元素，逆置后的了?表還要與原來的后半部分了表拼起來。

(3)程序?qū)崿F(xiàn)如下所示。

intremoveevenlargethanx(LinkListhead,intx)

(

LinkNode*current;

intk;

if(head==NULL){

printf("鏈表錯(cuò)誤\n");

return0;

)

if(head->next==NULL){

printf("這是一個(gè)空鏈表\nn);

return1;

}

else(

current=head;

while(current->next!=NULL){

if(current->next->data>x&¤t->next->data%2==0){

rcmovcmy(head,current,ik);

)

elsecurrent=current->next;

}

}

return1;

)

刪除滿足條件的元素時(shí)，可以調(diào)用單鏈表中實(shí)現(xiàn)的remove操作。要注意的是，刪除一

個(gè)結(jié)點(diǎn)后，當(dāng)前指針current不改變，此時(shí)，current不后移，繼續(xù)判斷它指向結(jié)點(diǎn)的后繼結(jié)

點(diǎn)。但如果沒有刪除結(jié)點(diǎn)，則current需要后移一個(gè)位置。

2.在單鏈表L中保存了若干整數(shù)。實(shí)現(xiàn)算法將L分為兩個(gè)單鏈表L1和L2,其中L1中保

存奇數(shù)，L2中保存偶數(shù)。

【參考答案】

程序?qū)崿F(xiàn)如下所示。

intpartition(LinkList*L,LinkList*L1,LinkList*L2)

(

LinkNode*Llcurrz*L2curr;

LinkNode*temp;

if((*L)==NULL){

prints(“鏈表錯(cuò)誤\nM);

return0;

}

initList(LI);

initList(L2);

if((*L)->next==NULL){

printf("這是一個(gè)空鏈表\nH);

return1;

else(

temp=(*L)->next;

Llcurr=*Ll;

L2curr=*L2;

while(temp!=NULL){

(*L)->next=temp->next;

temp->next=NULL;

if(t.Rmp->data^2==0){

L2curr->next=temp;

L2curr=L2curr->next;

(*L2)->data++;

}

else{

Llcurr->next=teinp;

Llcurr=Llcurr->next;

(*L1)->data++;

}

temp=(*L)->next;

}

}

return1;

I

將單鏈表L拆分為兩個(gè)單鏈表L1和L2,實(shí)際上就是從L中刪除一個(gè)結(jié)點(diǎn)，然后根據(jù)

結(jié)點(diǎn)中值的奇偶性，或是將結(jié)點(diǎn)添加到L1中，或是將結(jié)點(diǎn)添加到L2中。

因?yàn)閯h除和插入都是依次進(jìn)行的，所以，設(shè)置一個(gè)當(dāng)前工作指針記錄三個(gè)鏈表的當(dāng)前位

置。

3.已知帶頭結(jié)點(diǎn)的單鏈表的每個(gè)結(jié)點(diǎn)中保存一個(gè)整數(shù)，數(shù)據(jù)結(jié)點(diǎn)有八個(gè)。請(qǐng)?jiān)O(shè)計(jì)算法以判

斷該鏈表中保存的值是否構(gòu)成斐波那契數(shù)列中的前〃項(xiàng)。若是算法返回I,否則返回0。

【參考答案】

程序?qū)崿F(xiàn)如下所示。

intisFibonacci(LinkListhead)

(

LinkNode*plz*p2z*p3;

intf1=1,f2=l,f3/i;

if(head==NULL){

printf(“鏈表錯(cuò)誤\nn);

return0;

}

if(head->next==NULL){

printf("這是一個(gè)空鏈表\nH);

return0;

if(head->data==l&&head->next->data==l)return1;

if(head->data==2&fihead->next->data==l&&head->next->next->data==l)

return1;

pl=head->next;

if(pl->data!=1)return0;

p2=pl->next;

if(p2->data!=l)return0;

p3=p2->next;

while(p3!=NULL&&p3->data==pl->data+p2->daza){

pl=p2;

p2=p3;

p3=p3->next;

)

if(p3==NULL)return1;

elsereturn0;

}

斐波那契數(shù)列中含有多個(gè)整數(shù)值，如果整數(shù)的個(gè)數(shù)少于3個(gè)，則為特殊情況，程序中需

要對(duì)此進(jìn)行特殊的處理。即單鏈表中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)少于3個(gè)時(shí)，需要單獨(dú)進(jìn)行判定。前兩

個(gè)結(jié)點(diǎn)中的整數(shù)都是1。

當(dāng)結(jié)點(diǎn)個(gè)數(shù)大于等于3個(gè)時(shí)，從第三個(gè)結(jié)點(diǎn)開始，一直到尾結(jié)點(diǎn)，判定每個(gè)結(jié)點(diǎn)中保存

的整數(shù)是否是相鄰的前兩個(gè)結(jié)點(diǎn)中值的和。

4.實(shí)現(xiàn)算法，判斷帶頭結(jié)點(diǎn)的單鏈表中所保存的整數(shù)，是否構(gòu)成遞增有序序列。若是遞增

有序序列，則算法返回1；若不是有序序列，則算法返回0。

【參考答案】程序?qū)崿F(xiàn)如下所示。

intisincrease(LinkListhead)

{

LinkNode*p;

intcurrmax;

if(head==NULL)(

printf(“鏈表錯(cuò)誤\n");

return0;

}

if(head->next==NULL){

printf("這是一個(gè)空鏈表\n”)；

return1;

)

p=head->next;〃第一個(gè)數(shù)據(jù)結(jié)點(diǎn)

currmax=p->data;

p=p->next;

while(p!=NULL&&p->data>=currmax){

p=p->next;

}

if(p==NULL)return1;

elsereturn0;

5.設(shè)線性表元素為整數(shù)，其中可能有相同的元素。試設(shè)計(jì)一個(gè)算法刪除表中重復(fù)的元素(即

相同元素只保留一個(gè))，使刪除后表中各元素均不相同。給出在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種

方式下的實(shí)現(xiàn)程序。

【參考答案】線性表如果有序，則很容易刪除表中的重復(fù)元素。但當(dāng)線性表無序時(shí)，需

要進(jìn)行更多的比較才能實(shí)現(xiàn)。

采用順序存儲(chǔ)方式的程序?qū)崿F(xiàn)如下所示。

intunique(LinearList*L)

(

inti,jzk,len;

intNA=-65535;//NA用來做標(biāo)記

len=L->n;

for(i=l;i<len;i++)

for(j=0;j<i;j++){

if(L->element[i]==L->element[j])L->element[i]=NA;

}

k=l;

for(i=l;i<len;i++){

if(L->clcmcnt[i]!=NA)(

L->element(k-+]=L->element(i];

}

}

L->n=k;

return1;

)

從數(shù)組中刪除一個(gè)重復(fù)元素時(shí)，后面的元素都要依次向前移動(dòng)。為避免過多的元素移動(dòng),

當(dāng)發(fā)現(xiàn)重復(fù)元素時(shí)，僅對(duì)重復(fù)元素進(jìn)行標(biāo)記，而不是立艮]進(jìn)行刪除。當(dāng)查找到所有重發(fā)元素

后，再將剩余元素依次保存到數(shù)組最前面的若干位置中。

使用NA標(biāo)記要?jiǎng)h除的元素。

采用鏈?zhǔn)酱鎯?chǔ)方式的程序?qū)崿F(xiàn)如下所示。

voidunique(LinkListhead)

(

LinkNode*pz*current;

intk;

if(head==NULL){

printf(“鏈表錯(cuò)誤\n");

return;

}

if(head->next==NULL){

printf(“這是一個(gè)空鏈表\n");

return;

}

if(head->data==l)return;

current=head->next;

p=current;

while(current!=NULL&¤t->next!=NULL){

p=current;

while(p->next!=NULL)(

if(p->next->data==current->data){

removemy(head,p,&k);

}

elsep=p->next;

}

current.=currAnt->npxt;

)

return;

)

current是當(dāng)前指針，指示當(dāng)前結(jié)點(diǎn)。使用另一個(gè)指針p從當(dāng)前位置開始向后依次掃描

結(jié)點(diǎn)。當(dāng)p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)中的值與current所指結(jié)點(diǎn)中的值相等時(shí)，刪除重復(fù)結(jié)點(diǎn)，

即刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)?？梢哉{(diào)用remove函數(shù)完成刪除操作。當(dāng)p指向表尾時(shí)，表

示一輪掃描完成，current指向下一個(gè)結(jié)點(diǎn)，繼續(xù)同樣的查重及刪除操作。

6.設(shè)有兩個(gè)按元素值遞增有序排列的單鏈表A和B。試實(shí)現(xiàn)算法，將它們合并成一個(gè)單鏈

表C,要求C的元素值仍按遞增有序排列(允許C中有值相同的元素)。

【參考答案】程序?qū)崿F(xiàn)如下所示。

voidmergelist(LinkList*A,LinkList*BZLinkList*C)

{

LinkNode*pA=*A,*pC=*C,*temp;

while(pA->next!=NULL&&pB->next!=NULL){

if(pA->next->data<pB->next->data){

temp=pA->next;

pA->next=temp->next;

temp->next=NULL;

pC->next=temp;

(*A)->data--;

}

else(

temp=pB->next;

pB->next=temp->next;

temp->next=NULL;

pC->next=temp;

(*B)->data--;

}

pC=pC->next;

(*C)->data++；

)

if(pA->next==NULL){

pC->next=pB->next;

pB->next=NULL;

(*C)->data+=(*B)->data;

else{

pC->next=pA->next;

pA->next=NULL;

(*C)->data+=(*A)->data;

}

return;

}

因?yàn)閮蓚€(gè)單鏈表A和B是遞增有序的，合并后的鏈表也要求是遞增有序的，所以可以

分別從前向后掃描A和B。使用三個(gè)工作指針分別指向A、B和C的當(dāng)前位置。比較A和

B當(dāng)前結(jié)點(diǎn)中元素的值，將更小值的結(jié)點(diǎn)移至鏈表C中。這個(gè)思想是二路歸并排序中兩個(gè)

有序歸并段合并的思想?？梢詤⒖嫉?章第五節(jié)的相關(guān)內(nèi)容。

第三章棧和隊(duì)列

一、單項(xiàng)選擇題

I.棧操作數(shù)據(jù)的原則是。

A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.隨機(jī)處理

答案：B。

棧的特性是后進(jìn)先出，選項(xiàng)A是隊(duì)列的特性。有些情況下，可以將選項(xiàng)C理解為先進(jìn)

先出，這也是隊(duì)列的特性.選項(xiàng)D既不是棧的特性，也不是隊(duì)列的特性.

2.入棧序列是ai,a3,as,a2,山,我,出棧序列是a$,甌a?,浜⑶,則棧的容量最小是。

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

答案：Co

用圖3.1表示棧狀態(tài)的變化情況。

a.入棧a3入棧as入棧as出棧az入棧a」入棧

34

asa2a2

aaS3asasa3

aiaiaiaiaiai

34出棧az出棧36入棧36出棧33出棧ai出棧

azU6

asa3a3a3

aiaiaiaiai

圖3.1棧的狀態(tài)

可以看到，在34入棧后，棧中有4個(gè)元素,這是棧含元素最多的時(shí)刻。所以棧的容量

最小是4o

3.6個(gè)元素6,5,4,3,2,1依次進(jìn)棧，不能得到的出棧序列是

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

答案：Co

可以使用操作過程來描述。

得至I］選項(xiàng)A的操作過程是：push(6),push(5),pop(5),push(4),pop(4),push(3),pop(3),

pop(6),pu$h(2),push(l),pop(1),pop⑵。

得到選項(xiàng)B的操作過程是:push(6),push(5),push(4),pop(4),pop(5),push(3),pop(3),

push(2),push(l),pop(1),pop(2),pop(6)。

得到選項(xiàng)D的操作過程是：push(6),push(5),push(4),push(3),push(2),pop(2),pop(3),

pop(4),push⑴,pop(l),pop⑸,po