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

第一章緒論

一、單項選擇題

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.動態(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ù)項B.字符C.二進制位D.數(shù)據(jù)記錄

答案：Ao

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

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

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

A.一對一的B.一對多的C.多對多的D.不確定的

答案：Bo

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

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

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

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

有多個后繼。

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

A.順序存儲方式B.鏈?zhǔn)酱鎯Ψ绞紺.分布存儲方式D.散列存儲方式

答案：Co

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

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

5.算法分析要評估的兩個主要方面是。

A.正確性和簡明性B.時間復(fù)雜性和空間復(fù)雜性

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

答案：Bo

算法的正確性是必須的，簡明性、可讀性、可維護性等都不是算法要評估的內(nèi)容（選項

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

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

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

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

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

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

答案：Co

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

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

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

7.設(shè)〃是描述問題規(guī)模的非負(fù)整數(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開始，每次倍增，達到或超過n/2時倍增的次數(shù)與log2〃的大小相

當(dāng)。

8.設(shè)〃是描述問題規(guī)模的非負(fù)整數(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)課程中，將所有能輸入計算機并被計算機程序處理的符號集合稱為

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

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

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

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

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

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

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

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

答案：索引項。

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

答案：有窮性。

三、解答題

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

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

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

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

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

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

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

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

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

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

weight)等。

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

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

brand：〃品牌，字符串

color：//顏色，字符串

price：〃價格，實型

speed：//最大速度，實型

deadweight：〃自重，實型，單位噸

操作部分：

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

輸入：speed

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

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

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

輸入：weight

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

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

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

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

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

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

real：〃實部，實型

imaginary：〃虛部，實型

操作部分：

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

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

輸出：它們的和

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

sub(complexl,conplex2)：〃減法

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

輸出：它們的差

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

multiplication(complexl,complex2)：〃乘法

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

輸出：它們的積

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

division(complexl,complex2)：//除法

輸入：兩個夏數(shù)

輸出：它們的商

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

5.為什么不使用算法的絕對運行時間來衡顯算法的時間效率？

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

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

用算法的絕對運行時間不能有效衡量算法的時間效率。

6.評估算法的空間效率時，需要考慮占用的哪些存儲空間？

【參考答案】算法運行過程中，臨時占用的空間大小是要考慮的存儲空間。算法代碼占

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

四、算法設(shè)計題

1.試設(shè)計一個算法，使用最少的比較次數(shù)找出三個不同整數(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è)計一個算法，對于給定的正整數(shù)〃，列出斐波那契數(shù)列的前〃項。

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

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

然后計算新的項f3=fl+f2,計算后用f2的值更新fl,用f3的值更新￡2。

voidfibonacci(intn)

(

intfl=l,f2=lzf3,i;

if(n<=0){

printf("n值錯誤\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");

第二章線性表

?、單項選擇題

1.下列選項中，不是鏈表特點的是_______。

A.插入、刪除時不需要移動元素B.可隨機訪問任一元素

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

答案：Bo

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

其他的元素不必像順序表那樣進行移動（選項A）。而且鏈表占用的空間隨需分配，隨用隨

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

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

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

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

A.線性表采用鏈?zhǔn)酱鎯Ψ绞剑阌谶M行插入和刪除操作

B.線性表采用順序存儲方式，便于進行插入和刪除操作

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

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

答案：Bo

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

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

不正確）。當(dāng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，因為各結(jié)點的地址并不要求是相鄰的（選項C）,所以插

入和刪除操作不會引起其他元素的移動（選項A）。

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

作的時間復(fù):雜度好，則下列選項中，為L選擇的存儲結(jié)構(gòu)為o

A.順序表B.雙向鏈表

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

答案：Ao

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

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

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

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

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

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

操作的時間復(fù)雜度好，則下列選項中，為L選擇的存儲結(jié)構(gòu)為。

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

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

答案：Do

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

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

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

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

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

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

構(gòu)。

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

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

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

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

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

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

答案：Bo

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

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

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

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

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

答案：Co

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

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

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

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

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

答案：Co

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

點的時間復(fù)雜度是05)。

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

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

答案：D。

鏈?zhǔn)酱鎯€性表時，如果要訪問表中的結(jié)點，通常會從表頭開始，逐個結(jié)點依次遍歷過

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

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

A.p==NULLB.p==head

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

答案：Co

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

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

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

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

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

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

A.head==NULLB.head!=NULL

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

答案：Do

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

即它沒有后繼結(jié)點。因為含有頭結(jié)點，故頭指針head在任何時刻都不能為空(選項A不正

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

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

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

條件。

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

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

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

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

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

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

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

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

點，則執(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

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

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

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

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

執(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.線性表是一個有限序列，組成線性表的是〃（〃20）個o

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

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

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

答案：head==NULLo

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

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

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

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

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

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

答案：前驅(qū)。

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

修改它的next值。

三、解答題

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

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

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

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

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

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

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

況的判定及處理情況。

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

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

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

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

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

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

【參考答案】

if(?isEmpty(L)){

intpos,x;

pos=find(L,19);

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

)

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

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

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

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

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

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

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

樣的。

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

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

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

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

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

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

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

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

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

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

和刪除操作的時間復(fù)雜度均為0(1)，因為操作過程中不需要進行元素的移動，也不需要將

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

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

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

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

四、算法閱讀題

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

出這些整數(shù)的平均值。請在空白處填上適當(dāng)內(nèi)容將算法補充完整。

floataverage(LinkListhead)

(

LinkNode*p;

intcounter=0,sum=O;

if(head==NULL){

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

return0;

}

if((D)prints("這是一個空鏈表\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

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

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

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

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

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

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

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

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

個實型值。

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

typedefstructnode{

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

structnode*next;〃指針域

JLinkNode;

typedefLinkNode*LinkList;〃單鏈表

算法largest找出這些整數(shù)中的最大值。請在空白處填上適當(dāng)內(nèi)容將算法補充完整。

intlargest(LinkListhead)

(

LinkNode*p;

intmaxitem;

if(head==NULL){

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

return0;

}

iff(1))printf("這是一個空鏈表\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

對于(1),空單鏈表中僅含有一個頭結(jié)點，頭指針指向結(jié)點的nexl域為NULL。

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

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

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

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

的內(nèi)容。

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

intcounterofodd(LinkListhead)

(

LinkNode*p;

intcounter=0;

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

if(head->next==NULL)printf("這是一-個空鏈表\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)計單鏈表head中保存的奇數(shù)的個數(shù)。

五、算法設(shè)計題

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

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

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

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

(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(“鏈表錯誤\n");

return0;

}

if(head->next==NULL)printf("這是一個空鏈表\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;

因為單鏈表有序，所以，如果有相同的整數(shù)，則它僅一定是相鄰的。使用變量laslone記

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

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

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

intreversesmallthanxiLinkListhead,intx)

(

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

if(head==NULL){

printf("鏈表錯誤\nn);

return0;

}

if(head->next==NULL){

printf(“這是一個空鏈表\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ù)按遞減次序重排，實際上是將單鏈表前面的若干結(jié)點逆

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

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

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

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

intremoveevenlargethanx(LinkListhead,intx)

(

LinkNode*current;

intk;

if(head==NULL){

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

return0;

)

if(head->next==NULL){

printf("這是一個空鏈表\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;

)

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

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

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

2.在單鏈表L中保存了若干整數(shù)。實現(xiàn)算法將L分為兩個單鏈表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(“鏈表錯誤\nM);

return0;

}

initList(LI);

initList(L2);

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

printf("這是一個空鏈表\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拆分為兩個單鏈表L1和L2,實際上就是從L中刪除一個結(jié)點，然后根據(jù)

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

因為刪除和插入都是依次進行的，所以，設(shè)置一個當(dāng)前工作指針記錄三個鏈表的當(dāng)前位

置。

3.已知帶頭結(jié)點的單鏈表的每個結(jié)點中保存一個整數(shù)，數(shù)據(jù)結(jié)點有八個。請設(shè)計算法以判

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

【參考答案】

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

intisFibonacci(LinkListhead)

(

LinkNode*plz*p2z*p3;

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

if(head==NULL){

printf(“鏈表錯誤\nn);

return0;

}

if(head->next==NULL){

printf("這是一個空鏈表\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ù)列中含有多個整數(shù)值，如果整數(shù)的個數(shù)少于3個，則為特殊情況，程序中需

要對此進行特殊的處理。即單鏈表中數(shù)據(jù)結(jié)點的個數(shù)少于3個時，需要單獨進行判定。前兩

個結(jié)點中的整數(shù)都是1。

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

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

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

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

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

intisincrease(LinkListhead)

{

LinkNode*p;

intcurrmax;

if(head==NULL)(

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

return0;

}

if(head->next==NULL){

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

return1;

)

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

currmax=p->data;

p=p->next;

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

p=p->next;

}

if(p==NULL)return1;

elsereturn0;

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

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

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

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

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

采用順序存儲方式的程序?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ù)組中刪除一個重復(fù)元素時，后面的元素都要依次向前移動。為避免過多的元素移動,

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

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

使用NA標(biāo)記要刪除的元素。

采用鏈?zhǔn)酱鎯Ψ绞降某绦驅(qū)崿F(xiàn)如下所示。

voidunique(LinkListhead)

(

LinkNode*pz*current;

intk;

if(head==NULL){

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

return;

}

if(head->next==NULL){

printf(“這是一個空鏈表\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é)點。使用另一個指針p從當(dāng)前位置開始向后依次掃描

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

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

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

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

表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;

}

因為兩個單鏈表A和B是遞增有序的，合并后的鏈表也要求是遞增有序的，所以可以

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

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

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

第三章棧和隊列

一、單項選擇題

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

A.先進先出B.后進先出C.后進后出D.隨機處理

答案：B。

棧的特性是后進先出，選項A是隊列的特性。有些情況下，可以將選項C理解為先進

先出，這也是隊列的特性.選項D既不是棧的特性，也不是隊列的特性.

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個元素,這是棧含元素最多的時刻。所以棧的容量

最小是4o

3.6個元素6,5,4,3,2,1依次進棧，不能得到的出棧序列是

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］選項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⑵。

得到選項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)。

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

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