數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第2版習(xí)題答案-嚴(yán)蔚敏

WORD

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第2版）

課后習(xí)題答案

冬梅

2015.3

專業(yè)資料.

WORD

目錄

第

2章

線性表..................................................................4

章

第3

棧和隊(duì)列...............................................................13

章

第4

串、數(shù)組和廣義表......................................................26

第

5章

樹和二叉樹............................................................33

章

第

查

7找55

章

排

第

8序66

專業(yè)資料.

WORD

第1章緒論

1.簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)

構(gòu)、抽象數(shù)據(jù)類型。

答案：

數(shù)據(jù)：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序靈理的符號(hào)的

總稱C如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、

圖像、聲音、動(dòng)畫等通過(guò)特殊編碼定義后的數(shù)據(jù)。

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)常作為一個(gè)整體進(jìn)行考慮和欠理。在有些情況

下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生

記錄，樹中棋盤的一個(gè)格局（狀態(tài)）、圖中的一個(gè)頂點(diǎn)等。

數(shù)據(jù)項(xiàng)：是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信

息表中的學(xué)號(hào)、、性別等都是數(shù)據(jù)項(xiàng)。

數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是

集合N={0，士1，±2，…}，字母字符數(shù)據(jù)對(duì)象是集合C={W，'B'，…，‘Z'，'a'，

V，…，'z'}，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對(duì)象。

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說(shuō)，數(shù)據(jù)結(jié)

構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。

邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，

數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。

存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱為物理結(jié)構(gòu)。

抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問(wèn)題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一

組操作的總稱。具體包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象上關(guān)系的集合和對(duì)數(shù)據(jù)對(duì)象的基本操

作的集合。

2.試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)溝兩方面的含義和相互關(guān)系。

答案：

例如有一學(xué)生基本信息表，包括學(xué)生的學(xué)號(hào)、、性別、籍貫、專業(yè)等。每個(gè)學(xué)生基本信息

記錄對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性序列。對(duì)

于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)（它的前面無(wú)記錄）和一個(gè)終端結(jié)點(diǎn)（它的后面無(wú)記錄），其

他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)

生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。

這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元（如用數(shù)組表

示）來(lái)存放這些記錄5則稱為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是陵機(jī)存放各個(gè)記錄，

然后用指針進(jìn)行，則稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

即相同的邏輯結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。

3?簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。

專業(yè)資料.

WORD

答案：

?）集合結(jié)構(gòu)

數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無(wú)其他關(guān)系。例如，確定一名學(xué)生是

否為班級(jí)成員，只需將班級(jí)看做一個(gè)集合結(jié)構(gòu)。

0）線性結(jié)構(gòu)

數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順

序進(jìn)行排列，將組成一個(gè)線性結(jié)構(gòu)。

0）樹結(jié)構(gòu)

數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每

位組長(zhǎng)管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。

④）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可

以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。

其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。

oOocQO。o-O-O-O-O

4.存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？

答案：

（D）順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常

借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類型來(lái)描述。

0）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無(wú)

需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于

存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言的指針類型來(lái)描述。

5.選擇題

①）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。

A?動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B?緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

專業(yè)資料.

WORD

C?線性結(jié)構(gòu)和非線性結(jié)構(gòu)D?部結(jié)構(gòu)和外部結(jié)構(gòu)

答案：C

0）與數(shù)據(jù)元素本身的形式、容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（）。

A?存儲(chǔ)結(jié)構(gòu)B?存儲(chǔ)實(shí)現(xiàn)

C?邏輯結(jié)構(gòu)D?運(yùn)算實(shí)現(xiàn)

答案：C

0）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（）。

A?數(shù)據(jù)具有同一特點(diǎn)

B?不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而由對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

C?每個(gè)數(shù)據(jù)元素都一樣

D?數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答

案：B

④）以下說(shuō)確的是（）。

A?數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B?數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

C?數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合

D?一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

答案：D

解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)

的各數(shù)據(jù)元素的集合。

6）算法的時(shí)間復(fù)雜度取決于（）。

A.問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)

C,計(jì)算機(jī)的配置D,A和B

答案：D

解釋：算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，還與問(wèn)題的其他因素有關(guān)。如某些

排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞

以及平均時(shí)間復(fù)雜度的評(píng)價(jià)。

?）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)

A.樹B?字符串C?隊(duì)列D?棧

答案：A

6.試分析下面各程序段的時(shí)間復(fù)雜度。

（1）x=90;y=100;

while（y>0）

if（x>100）

{x=x-10;y—;}

elsex++;

答案：0（1）

解釋：程序的執(zhí)行次數(shù)為常數(shù)階。

專業(yè)資料.

(2)for(i=0;i<n;i++)

for(j=0;j<m;j++)

a[i][j>0;

答案:0(m*n)

解釋：語(yǔ)句a[i][j]=0;的執(zhí)行次數(shù)為m*n。

(3)s=0;

fori=0;i<n;i++)

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

sum=s;

答案：0(n2)

解釋：語(yǔ)句s+=B[i][j];的執(zhí)行次數(shù)為a。

(4)i=l;

while(i<=n)

i=i*3;

答案：0(logn)

解釋：語(yǔ)句i=i*3;的執(zhí)行次數(shù)為log3n°

(5)x=0;

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

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

x++;

答案：0(皿)

解釋：語(yǔ)句x++;的執(zhí)行次數(shù)為nT+n-2+....+1=n(n-l)/2°

(6)x=n;//n>l

y=0;

while(x2(y+l)米(y+1))

y++;

答案:0(/7)

解釋：語(yǔ)句y++;的執(zhí)行次數(shù)為C°

專業(yè)資料.

WORD

第2章線性表

i.選擇題

（D）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素

的地址是（）。

A-110B?108C?100D?120

答案：B

解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。

0）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0（1）的操作是（）。

A?訪問(wèn)第i個(gè)結(jié)點(diǎn)（IWiWn）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2WiWn）

B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（IWiWn）

C,刪除第i個(gè)結(jié)點(diǎn)（IWiWn）

D.將n個(gè)結(jié)點(diǎn)從小到大排序

答案：A

孥釋：在順序表中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是0（n2），排序的時(shí)間復(fù)雜度為0（n2）

或OSlog^n）。順序表是一種陵機(jī)存取結(jié)構(gòu)，訪問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都

可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是0（1）。

0）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均

要移動(dòng)的元素個(gè)數(shù)為（）。

A-8B-63.5C-63D?7

答案：B

解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n/2。

④）存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。

A-分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針

B-只有一部分，存放結(jié)點(diǎn)值

C-只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針

D?分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)

答案：A

S>）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求存中可用存儲(chǔ)單元的地址（）°

A-必須是連續(xù)的B?部分地址必須是連續(xù)的

C?一定是不連續(xù)的D-連續(xù)或不連續(xù)都可以

答案：D

⑥）線性表L在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。

A-需經(jīng)常修改L中的結(jié)點(diǎn)值B-需不斷對(duì)L進(jìn)行刪除插入

C-L中含有大量的結(jié)點(diǎn)D-L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜

答案：B

專業(yè)資料.

WORD

解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。

0)單鏈表的存儲(chǔ)密度()。

A?大于1B?等于1C?小于1D-不能確定

答案：C

解釋：存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空

間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度

為：D/(D+N)，一定小于1°

8)將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是()。

A-nB-2n-lC-2nD-n-1

答案：A

解釋：當(dāng)?shù)谝粋€(gè)有序表中所有的元素都小于(或大于)第二個(gè)表中的元素，只需

要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。

Q)在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素(IWiWn+l)之前插入一個(gè)新元素

時(shí)須向后移動(dòng)()個(gè)元素。

A,n_iB,n_i+lC,n-i-1D,I

答案：B

(10)線性表L=(a,a,...a)?下列說(shuō)確的是()。

12n

A?每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

B-線性表中至少有一個(gè)元素

C?表中諸元素的排列必須是由小到大或由大到小

D?除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前嶇和直接后

繼。

答案：D

(11;創(chuàng)建一個(gè)包括n個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間復(fù)雜度是()。

A-0(1)B-0(n)C-0(02)D-0(nlogn)

答案：C

解釋：?jiǎn)捂湵韯?chuàng)建的時(shí)間復(fù)雜度是0(n)，而要建立一個(gè)有序的單鏈表，則每生成

一個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定合適的插入位置，所以時(shí)間復(fù)雜度是

0(n2)。

(12)以下說(shuō)法錯(cuò)誤的是()。

A求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鍍式存儲(chǔ)結(jié)

構(gòu)時(shí)實(shí)現(xiàn)的效率低

R順序存儲(chǔ)的線性表可以隨機(jī)存取

C-由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活

D-線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)

答案：D

解釋：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。

(13)在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為()。

專業(yè)資料.

WORD

A-s->next=p+l;p->next=s;

B?(*p).next=s;(*s).next=(*p).next;

C?s->next=p->next;p->next=s->next;

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

答案：D

(14)在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針()。

A-p->next->prior=p->prior;p->prior->next=p->next;

B?p->next=p->next->next;p->next->prior=p;

C-p->prior->nexL=p;p->prior=p->prior->prior;

D,p->prior=p->next->next;p->next=p->prior->prior;

答案：A

(15)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的

操作是()。

A-p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B-p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;

C-q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

D-q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;

答案：C

2.算法設(shè)計(jì)題

(D)將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)

鏈表的存儲(chǔ)空間，不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。

［題目分析］

合并后的新表使用頭指針Lc指向?pa和pb分別是鏈表La和Lb的工作指針，初始化為

相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)

時(shí)，依次摘取其中較小者重新在Lc表的最后。如果兩個(gè)表中的元素相等，只摘取La表中的元

素，刪除Lb表中的元素，這樣確保合并后表中無(wú)重復(fù)的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，

為空時(shí)，將非空表的剩余元素直接在Lc表的最后。

［算法描述］

voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc)

{//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向

pa=La->next;pb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)

Lc二pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)

while(pa&&pb)

(if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}

//取較小者La中的元素，將pa在pc的后面,pa指針后移

elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;)

//取較小者Lb中的元素，將pb在pc的后面，pb指針后移

專業(yè)資料.

WORD

else//相等時(shí)取La中的元素，刪除Lb中的元素

{pc->next=pa;pc=pa;pa=pa->next;

q=pb->next;deletepb;pb=q;

}

}

pc->next=pa?pa:pb;//插入剩余段

deleteLb;//釋放Lb的頭結(jié)點(diǎn)

)

0)將兩個(gè)非遞減的有序琥表合并為一個(gè)非遞增的有序鏈表U要求結(jié)果犍表仍使用原來(lái)

兩個(gè)鏈表的存儲(chǔ)空間，不另外占用其它的存儲(chǔ)空間。表中允許有重復(fù)的數(shù)據(jù)。

［題目分析］

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針，初始化為

相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)

點(diǎn)時(shí)，依次摘取其中較小者重新在Lc表的表頭結(jié)點(diǎn)之后，如果兩個(gè)表中的元素相等，只摘取

La表中的元素，保留Lb表中的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元

素依次摘取，在Lc表的表頭結(jié)點(diǎn)之后。

［算法描述］

voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc,)

{〃合并鏈表La和Lb，合并后的新表使用頭指針Lc指向

pa=La->next;pb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)

Lc=pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)

Lc->next=NULL;

while(pa|Ipb)

{//只要存在一個(gè)非空表，用q指向待摘取的元素

if(!pa){q=pb;pb=pb->next;}

//La表為空，用q指向pb?pb指針后移

elseif(!pb){q=pa;pa=pa->next;}

//Lb表為空，用q指向pa?pa指針后移

elseif(pa->data<=pb->data)(q=pa;pa=pa->next;}

//取較小者(包括相等)La中的元素，用q指向pa，pa指針后移

else{q=pb;pb=pb->next;}

//取較小者Lb中的元素，月q指向pb，pb指針后移

q->next=Lc->next;Lc->next=q;

//將q指向的結(jié)點(diǎn)插在Lc表的表頭結(jié)點(diǎn)之后

}

deleteLb;//釋放Lb的頭結(jié)點(diǎn)

專業(yè)資料.

WORD

0)已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出A與B

的交集，并存放于A鏈表中。

［題3分析］

只有同時(shí)出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中，合并后的新表使用頭指針Lc指向。

pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)

始迸行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等的元素時(shí)，摘取

La表中的元素，刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的

元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個(gè)到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，依次刪除另一

個(gè)非空表中的所有元素。

［算法描述］

voidMix(LinkList&La,LinkList&Lb,LinkList&Lc)

{pa=La->next;pb=Lb->next;

pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)

Lc=pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)

while(pa&&pb)

(

if(pa->data==pb->data)||交集并入結(jié)果表中3

{

pc->next=pa;

pc=pa;pa=pa->next;

u=pb;pb=pb->next;

Deleteu;

(

elseif(pa->data<pb->data)

(

u二pa;pa=pa->next;deleteu;

)

else

{

ii=ph;ph=pb->next;deleten;

)

i

i

while(pa){u=pa;pa=pa->next;deleteu;}||釋放結(jié)點(diǎn)空間

while(pb){u=pb;pb=pb->next;deleteu;}||釋放結(jié)點(diǎn)空間

pc->next=nul1;||置鏈表尾標(biāo)記。

deleteLb;//釋放Lb的頭結(jié)點(diǎn)

專業(yè)資料.

WORD

@)已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列。請(qǐng)?jiān)O(shè)計(jì)算法求出兩個(gè)集合

A和B的差集(即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合)，并以同樣的形式

存儲(chǔ)，同時(shí)返回該集合的元素個(gè)數(shù)。

［題目分析］

求兩個(gè)集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)

點(diǎn)，所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點(diǎn)。pa和pb分別是鏈表La和

Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行比較，當(dāng)兩個(gè)鏈表

La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于Lb表中的元素?pre置為L(zhǎng)a表的工

作拈針pa刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí),刪除此表中較小的元素,

此表的工作指針后移。當(dāng)鏈表La和Lb有一個(gè)為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。

［算法描述］

voidDifference(LinkList&La,LinkList&Lb,int米n)

{||差集的結(jié)果存儲(chǔ)于單鏈表La中，包是結(jié)果集合中元素個(gè)數(shù)，調(diào)用時(shí)為0

pa=La->next;pb=Lb->next;

IIpa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)

pre=La;||pre為L(zhǎng)a中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針

while(pa&&pb)

{if(pa->data<q->data){pre=pa;pa=pa->next;*n++;}

IIA鏈表中當(dāng)前結(jié)點(diǎn)指針后移

elseif(pa->data>q->data)q=q->next;||B鏈表中當(dāng)前結(jié)點(diǎn)指針后移

else{pre->next=pa->next;||欠理A?B中元素值相同的結(jié)點(diǎn)，應(yīng)刪除

u=pa;pa=pa->next;deleteu;)||刪除結(jié)點(diǎn)

)

}

0)設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B

表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)(鏈表A中的元

素為非零整數(shù)，要求B、C表利用A表的結(jié)點(diǎn))。

［題目分析］

B表的頭結(jié)點(diǎn)使用原來(lái)A表的頭結(jié)點(diǎn)，為C表新申請(qǐng)一個(gè)頭結(jié)點(diǎn)。從A表的第一個(gè)結(jié)點(diǎn)開(kāi)

始，依次取其每個(gè)結(jié)點(diǎn)p，判斷結(jié)點(diǎn)p的值是否小于0，利用前插法，將小于0的結(jié)點(diǎn)插入B

表，大于等于0的結(jié)點(diǎn)插入C表。

［算法描述］

voidDisComposeCLinkedListA)

{B=A;

B->next=NULL;||B表初始化

C=newLNode;||為C申請(qǐng)結(jié)點(diǎn)空間

C->next=NULL;||C初始化為空表

p=A->next;||p為工作指針

專業(yè)資料.

WORD

while(p!=NULL)

{r=p->next;||暫存p的后繼

if(p->data<0)

{p->next=B->next;B->next=p;}||將小于0的結(jié)點(diǎn)鏈入B表，前插法

else{p->next=C->next;C->next=p;}||將大于等于0的結(jié)點(diǎn)鏈入C表，前插法

p=r;||p指向新的待欠理結(jié)點(diǎn)。

⑹)設(shè)計(jì)一個(gè)算法，通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。

［題目分析］

假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則

設(shè)其下一個(gè)元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。

［算法描述］

EleraTypeMax(LinkListL){

if(L->next==NULL)returnNULL;

pmax=L->next;//假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值

p=L->next->next;

while(p!=NULL){//如果下一個(gè)結(jié)點(diǎn)存在

if(p->data>pmax->data)pmax=p;//如果p的值大于pmax的值?則重新賦值

p=p->next;//遍歷鏈表

}

returnpmax->data;

0)設(shè)計(jì)一個(gè)算法，通過(guò)遍歷一趟，將鏈表中所有結(jié)點(diǎn)的方向逆轉(zhuǎn)，仍利用原表的存

儲(chǔ)空間。

［題目分析］

從首元結(jié)點(diǎn)開(kāi)始，逐個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部。

［算法描述］

voidinverse(LinkList&L)

{//逆置帶頭結(jié)點(diǎn)的單鏈表L

p=L->next;L->next=NULL;

while(p){

q=p->next;//q指向*p的后繼

p->next=L->next;

L->next=p;//*p插入在頭結(jié)點(diǎn)之后

P=q；

)

)

專業(yè)資料.

WORD

?)設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素(mink

和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同)。

［題目分析］

分別查找第一個(gè)值>mink的結(jié)點(diǎn)和第一個(gè)值2maxk的結(jié)點(diǎn)，再修改指針，刪除值大于

mink且小于maxk的所有元素。

［算法描述］

voiddelete(LinkList&L,intmink,intmaxk)

Ip=L->next;//首元結(jié)點(diǎn)

while(p&&p->data<=mink)

{pre=p;p=p->next;)//查找第一個(gè)值>mink的結(jié)點(diǎn)

if(p)

{while(p&&p->data<maxk)p=p->next;

//查找第一個(gè)值2maxk的結(jié)點(diǎn)

q=pre->next;pre->next=p;//修改指針

while(q!=p)

{s=q->next;deleteq;q=s;}//釋放結(jié)，占、空間

)//if

)

Q)已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data'prior-next三個(gè)域，

寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。

［題目分析］

知道雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，與前驅(qū)交換涉及到四個(gè)結(jié)點(diǎn)(p結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)，前

驅(qū)的前驅(qū)結(jié)點(diǎn)，后繼結(jié)點(diǎn))六條鏈°

［算法描述］

voidExchange(LinkedListp)

IIp是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。

{q=p->llink；

q->l1ink->rlink=p；||p的前驅(qū)的前驅(qū)之后繼為p

p->l1ink=q->llink；IIp的前驅(qū)指向其前驅(qū)的前驅(qū)。

q->rlink=p->rlink；||p的前驅(qū)的后繼為p的后繼。

q->llinkup；UP與其前驅(qū)交換

p->rlink->l1ink=qIIp的后繼的前驅(qū)指向原p的前驅(qū)

p->rlink=q；IIp的后繼指向其原來(lái)的前驅(qū)

}||算法exchange結(jié)束。

?)已知長(zhǎng)度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為0(n)、空間復(fù)

雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。

［題目分析］

專業(yè)資料.

WORD

在順序存儲(chǔ)的線性表上刪除元素，通常要涉及到一系列元素的移動(dòng)(刪第i個(gè)元素，第

i+1至第n個(gè)元素要依次前移)。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求

元素間的相對(duì)位置不變。因此可以考慮設(shè)頭尾兩個(gè)指針(i=l，j=n)，從兩端向中間移動(dòng)，凡

遇到值item的數(shù)據(jù)元素時(shí)，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。

[算法描述]

voidDelete(ElemTypeA[],intn)

||A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。

{i=l；j=n；||設(shè)置數(shù)組低、高端指針(下標(biāo))。

whilc(i<j)

(while(i<j&&A[i]!=item)i++；||若值不為item，左移指針。if

(i<j)while(i<j&&A[j]==item)j一；||若右端元素為item，指針左移if

(i<j)A[i++]=A[j-]；}

專業(yè)資料.

WORD

第3章棧和隊(duì)列

i.選擇題

（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。

A?5,4,3,2，lB?2，l，5,4,3C-4,3，l，2,5D-2,3,5,4，l

答案：C

解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧

的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。

（2）若已知一個(gè)棧的入棧序列是1，2，3，n?其揄出序列為pl，p2，p3，pn，

若pl=n，則pi為（）。

A?iB?n-iC?n-i+1D?不確定

答案：C

解釋：棧是后進(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，n，而輸出序列的

第一個(gè)元素為n，說(shuō)明1，2，3，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以pl=n，p2=n-l，…，

pi=n-i+l。

0）數(shù)組Q〔n〕用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，1?為隊(duì)

尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。

A?r-fB?（n+f-r）%nC?n+r-fD?（n+r-f）%n

答案：D

解釋：對(duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，

差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求

余，即（n+r-f）%n。

@）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：（data,link）?top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)

的值保存到x中，則應(yīng)執(zhí)行操作（）。

A?x=top->data;top=top->1inkIB?top=top->link;x=top->link；

C-x=top;top=top->link；D?x=top->link；

答案：A

解釋：x=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)

點(diǎn)，即摘除棧頂結(jié)點(diǎn)。

<9）設(shè)有一個(gè)遞歸算法如下

intfact（intn）{//n大于等于0

if（n<=0）return1;

elsereturnn*fact（n-l）;}

則計(jì)算fact（n）需要調(diào)用該函數(shù)的次數(shù)為（）。

A.n+1B-n-1C?nD-n+2

答案：A

專業(yè)資料.

WORD

解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact（n）函數(shù)?故選A°

⑹）棧在（）中有所應(yīng)用。

A.遞歸調(diào)用B-函數(shù)調(diào)用C-表達(dá)式求值D-前三個(gè)選項(xiàng)都有

答案：D

解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。

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

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

邏輯結(jié)構(gòu)應(yīng)該是（）。

A.隊(duì)列B?棧C?線性表D?有序表

答案：A

解釋：解決緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線

性表。

<8>）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次進(jìn)入棧S，

一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和el?貝”棧S的容

量至少應(yīng)該是（）。

A-2B-3C-4D-6

答案：B

解釋：元素出隊(duì)的序列是e2、e4、e3、e6、e5和el，可知元素入隊(duì)的序列是e2、e4、e3、

e6、e5和el，即元素出棧的序列也是e2、e4、e3、e6、e5和el，而元素el、e2、e3、e4、e5

和e6依次進(jìn)入棧，易知棧S中最多同時(shí)存在3個(gè)元素，故棧S的容量至少為3。

<9>）若一個(gè)棧以向量V[L,n]存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正

確操作是（）。

A?top++;V[top]=x;B?V[top]=x;top++;

C-top";V[top]=x;D?V[top]=x;top—;

答案：C

解釋：初始棧頂指針top為n+1，說(shuō)明元素從數(shù)組向量的高端地址進(jìn)棧?又因?yàn)樵?/p>

存儲(chǔ)在向量空間V[l..n]中，所?以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。

?）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最

佳。

A.線性表的順序存儲(chǔ)結(jié)構(gòu)B?隊(duì)列

C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧

答案：D

解釋：利用棧的后進(jìn)先出原則。

（11）用方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）°

A.僅修改頭指針B.僅修改尾指針

C.頭、尾指針都要修改D.頭、尾指針可能都要修改

答案：D

專業(yè)資料.

WORD

解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)是指

針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。

?）循環(huán)隊(duì)列存儲(chǔ)在數(shù)紐中，則入隊(duì)時(shí)的操作為（）。

A.rear=rear+lB.rear=（rear+l）

C.rear=（rear+l）%mD.rear=（rear+l）%（m+l）

答案：D

解釋：數(shù)組A［0..m］中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。

?）最大容量為n的循環(huán)隊(duì)列?隊(duì)尾指針是rear,隊(duì)頭是front，則隊(duì)空的條件是（）

A.（rear+1）%n―frentB.rear-front

C?rear+l==frontD.(rear-l)%n==front

答案：B

解釋：最大容量為n的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n=二front,隊(duì)空條件是

rear==front°

?）棧和隊(duì)列的共同點(diǎn)是（）。

A.都是先進(jìn)先出B.都是先進(jìn)后出

C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)

答案：C

解釋：棧只允許在棧頂火進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭

刪除元素。

?）一個(gè)遞歸算法必須包括（）。

A.遞歸部分B.終止條件和遞歸部分

C.迭代部分D.終止條件和迭代部分

答案：B

2.算法設(shè)計(jì)題

。）將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V［m］中，棧底分別欠于數(shù)組的兩端。

當(dāng)?shù)?號(hào)棧的棧頂指針top［0］等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top［l］等于m時(shí)

該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫雙棧初始化，判斷?？?、棧滿、進(jìn)棧和出棧

等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：

Typedefstruct

(inttop[2],bot[2];〃棧頂和棧底指針

SElemType*V;〃棧數(shù)組

intm;〃棧最大可容納元素個(gè)數(shù)

}DblStack

［題目分析］

兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥耍跏紩r(shí)，左棧頂指針為-11右棧頂為m°

兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長(zhǎng)?棧頂指針指向棧頂元素。

［算法描述］

專業(yè)資料.

WORD

(1)棧初始化

intInitO

{S.top[0]=-l;

S.top[l]=m;

return1;//初始化成功

)

(2)入棧操作：

intpush(stkS,inti,intx)

||i為棧號(hào),i=0表示左棧,i