數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案

第1章緒論

1?簡述下列概念：數(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)的總稱。如數(shù)學(xué)計(jì)算中

用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、

圖像、聲音、劫畫等通過特殊編碼定義后的數(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={'A','B…，'Z,*a

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

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(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ǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以

看作是從具體問題抽象出來的數(shù)學(xué)模型。

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

抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(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é)構(gòu)兩方面的含義和相互關(guān)系。

答案：

例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號(hào)、姓名、性別'籍貫、專業(yè)等。每個(gè)學(xué)生基本信息記錄對(duì)應(yīng)一

個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性序列。對(duì)于整個(gè)表來說，只有一個(gè)開始

結(jié)點(diǎn)（它的前面無記錄）和一個(gè)終端結(jié)點(diǎn)（它的后面無記

錄），其他的結(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ù)組表

示）來存放這些記錄，則稱為順序存儲(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é)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。

1

答案：

(1)集合結(jié)構(gòu)

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

將班級(jí)看做一個(gè)集合結(jié)構(gòu)。

(2)線性結(jié)構(gòu)

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

一個(gè)線性結(jié)構(gòu)。

(3)樹結(jié)構(gòu)

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

從而構(gòu)成樹形結(jié)構(gòu)。

(4)圖結(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)。

0—0—

四類基本邏輯結(jié)構(gòu)關(guān)系圖

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

答案：

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

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

數(shù)組類型來描述。

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

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

間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)

結(jié)構(gòu)通常借助于程序設(shè)計(jì)語言的指針類型來描述。

5?選擇題

(1)在數(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)

2

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D?內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

答案：C

(2)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(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

(3)通常要求同一邏輯結(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

(4)以下說法正確的是()。

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ù)元素的集

合。

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

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

C.計(jì)算機(jī)的配置口.人和8

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

法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞以及平均時(shí)間復(fù)雜度的評(píng)價(jià)。

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

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

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

(1)x=90;y=100;

while(y>0)if(x>100)

{x=x-10;y-;}elsex++;

答案：0(1)

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

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

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

答案：0(m*n)

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

3

(3)s=0;

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

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

s+=B[i]j

sum=s;

答案：0(n2)

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

(4)i=1；

while(i<=n)

i=i*3;

答案：O(log3n)

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

(5)x=0;

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

for(j=1;jv=n-i;j++)

x++;

答案：0(n2)

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

(6)x=n;〃n>1

y=o；

while(x>(y+1)*(y+1))

y++;

答案：0(、.n)

解釋：語句y++;的執(zhí)行次數(shù)為-.n。

4

第2章線性表

i?選擇題

(1)順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2>則第5個(gè)元素的地址是()。

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

答案：B

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

(2)在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度

是0(1)的操作是()。

A.訪問第i個(gè)結(jié)點(diǎn)(1<i<n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2<i<n；

B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1<i<"

C?刪除第i個(gè)結(jié)點(diǎn)(Ki<n；

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

答案：A

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

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

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

(3)向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移

動(dòng)一的元素個(gè)數(shù)為()。

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

答案：B

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

(4)鏈接存儲(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

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

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

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

答案：D

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

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

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

答案：B

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

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

5

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-1C.2nD,n-1

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

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

(9)在一個(gè)長度為n的順序表中，在第i個(gè)元素(1<i<n+1)

之前插入一個(gè)新元素時(shí)

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

A-n-iB-n-i+1C-n-i-1D-I

答案：B

(10)線性表L=(a1,a2,……an)，下列說法

正確的是()°

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

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

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

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

答案：D

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

A-0(1)B-O(n)C-O(n2)D-O(nlog2n)

答案：C解釋：單鏈表創(chuàng)建的時(shí)間復(fù)雜度是O(n)，而要建立一個(gè)有序的單鏈表，則每生成一個(gè)

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

O(n2)=

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

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

B?順序存儲(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)，有不同的適用場合。

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

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

6

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->next=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ì)題

(1)將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間，不

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

［題目分析］

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一

個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘取其中較小者重新鏈接

在Lc表的最后。如果兩個(gè)表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中

無重復(fù)的元素。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素直接鏈接在Lc表的最后。

［算法描述］

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

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

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

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

點(diǎn)作為Lc的頭結(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指針后移

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)

)

7

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

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

［題目分析］

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針，初始化為相應(yīng)鏈表的第一

個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(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)

作為Lc的頭結(jié)點(diǎn)

Lc->next=NULL;

while(pa||pb)

{//只要存在一個(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)

(3)已知兩個(gè)鏈表A和B分

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

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

［題目分析］

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

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

始進(jìn)行比較，當(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í)，依次刪除另一

8

個(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)作為Lc的頭結(jié)點(diǎn)while(pa&&pb)

{if(pa->data==pb->data)//交集并入結(jié)果表中。

{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{u=pb;pb=pb->next;deleteu;}

)

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

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

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

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

)

(4)已知兩個(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)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表

尾結(jié)點(diǎn)時(shí)，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果

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

次刪除另一個(gè)非空表中的所有元素。

［算法描述］

9

voidDifference(LinkList&La,LinkList&Lb,int*n{I差集)

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

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

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

preLa中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針

while(pa&&pb)

{if(pa->data<q->data

{pre=pa;pa=pa->next;*n++;}

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

else{pre->next=pa->next;q=q->next;IB鏈表中當(dāng)前結(jié)點(diǎn)指針后移

u=pa;pa=pa->next;deleteu;})I處理A,B中元素值相同的結(jié)點(diǎn),應(yīng)刪除

I刪除結(jié)點(diǎn)

(5)設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表表的結(jié)點(diǎn)為A表中值小

于零的結(jié)點(diǎn)，而

A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表8、。,其中3

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

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

［題目分析］

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

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

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

［算法描述］voidDisCompose(LinkedListA)

{B=A;

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

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

C->next=NULL;p=A->next;IC初始化為空表

while(p!=NULL)IP為工作指針

{r=p->next;

"簪存p的后繼

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

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

P=r；Ip指向新的待處理結(jié)點(diǎn)。

)

if(p->data<0)

{p->next=B->next;B-

else{p->next=C->next;

10

(6)設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。［題目分析］

11

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

大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。

［算法描述］

ElemTypeMax(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;

存儲(chǔ)空間。

［題目分析］從首元結(jié)點(diǎn)開始，逐

個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部。

［算法描述］

voidinverse(LinkList&L)

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

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

while(p){

指向*P的后繼

q=p->next;//q

p->next=L->next;

插入在頭結(jié)點(diǎn)之后

L->next=p;//*p

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

p=q;

)

}

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

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

［題目分析］

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

mink且小于maxk的所有元素。

［算法描述］

voiddelete(LinkList&L,intmink,intmaxk){

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

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

12

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

if(P)

13

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

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

修改指針

pre->next=p;//while(q!=p)

{s=q->next;deleteq;q=s;}//

釋放結(jié)點(diǎn)空間

}//if

(9)已知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)

II。是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將P所指結(jié)

{q=p->llink；點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。

q->llink->rlink=p；I

p->llink=q->llink；IP的前驅(qū)的前驅(qū)之后繼為P

q->rlink=p->rlink；IP的前驅(qū)指向其前驅(qū)的前驅(qū)。

q->llink=p；IP的前驅(qū)的后繼為P的后繼。

p->rlink->llink=q；IP與其前驅(qū)交換

p->rlink=q；IP的后繼的前驅(qū)指向原P的前驅(qū)

}I算法exchange結(jié)束。P的后繼指向其原來的前驅(qū)

(in、口左n匕住F%r>缺i婦1，卜生圭

A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為雜度為0(1)的算法，該算法刪除線性表中所有值0(n)、空間復(fù)

為item的數(shù)據(jù)元素

[題目分析]

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

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

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

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

[算法描述]

voidDelete(ElemTypeA[]，intn)if(i<j)A[i++]=A[j-]，}

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

{i=1；j=n"/設(shè)置數(shù)組低、高端指針(下標(biāo))while

(i<j)

{while(i<j&&A[i]!=item)i++:I若值不為計(jì)em，左移指針。

if(i<j)while(i<j&&A[j]==item止-;//若右端元素為計(jì)em，指針左移

14

第3章棧和隊(duì)列

1?選擇題

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

2,1B-2,1,5,4,3C?4，3，1，2，D-2,3,5,4,1

答案：C解釋：棧是后進(jìn)先出的線性表，不難5

發(fā)現(xiàn)的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)中元素1比元素先出棧，違背了棧

(2)若已知一個(gè)棧的入棧序列是若的迪項(xiàng)斯示的情況。

A?i答案：解釋：第一個(gè)元素為1,2,3，…，n,其輸出序列為pl,P2,p3,?-?,pn,

pi為()

B-n-i?n-i+1?不確定

C

棧是后進(jìn)先出的線性表一個(gè)棧的入棧序列是n_1,2,3'n，而輸出序列的

說明1,2,3，…，n—次性全部進(jìn)棧，再進(jìn)行輸出，同p1=n,p2=n-1，…，

pi=n-i+1。

(3)數(shù)組Q：n］用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置-r為隊(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ì)列的長度，而對(duì)于循

環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE(本題為n),

然后與MAXSIZE(本題為n)

求余，即(n+r-f)%n。

(4)鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top保存到旨軻棧喇畫戴摘物救頂綃點(diǎn)，并將刪除結(jié)點(diǎn)的值

A-x=top->data;top=top->link:

C-x=top;top=top->link;B-top=top->link;x=top->link；

D?x=top->link；

答案：A

解釋：x=top->data將結(jié)點(diǎn)的值保存到即摘除伐頂結(jié)點(diǎn)。，…一

單，top=top->hnk棧頂指針指向棧頂下一結(jié)點(diǎn)，

(5)設(shè)有一個(gè)遞歸算法如下intfact(intn){〃n大于等于0

if(n<=0)return1;elsereturnn*fact(n-1);}

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

A-n+1B-n-1

)°

C-nD-n+2

答案：A

15

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

（6）棧在（）中有所應(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ì)。

（7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(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ū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。

（8）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、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

e2、e3、e6、e5和e1，可知元素入隊(duì)的序列是e2、

解釋：元素出隊(duì)的序列是…

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

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

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

作是（）。

A.