第1章緒論

1?簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。

答案：

數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學計算中

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

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

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數(shù)據(jù)元素也

稱為元素、結(jié)點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學生記錄，樹中棋盤的一個格局（狀態(tài)）、

圖中的一個頂點等。

數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學生基本信息表中的學號、姓名、

性別等都是數(shù)據(jù)項。

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N={0，士1，

±2,…}，字母字符數(shù)據(jù)對象是集合C={'A','B…，'Z,*a

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

數(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ù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以

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

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

抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學模型，以及定義在這個模型上的一組操作的總稱。具體

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

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

答案：

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

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

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

錄），其他的結(jié)點則各有一個也只有一個直接前趨和直接后繼。學生記錄之間的這種關(guān)系就確

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

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

示）來存放這些記錄，則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行鏈

接，則稱為鏈式存儲結(jié)構(gòu)。

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

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

1

答案：

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

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

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

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

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

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

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

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

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

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

數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學之間的朋友關(guān)系，任何兩位同學都可以是朋友，從而構(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?存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)？

答案：

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

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

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

(2)鏈式存儲結(jié)構(gòu)

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

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

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

5?選擇題

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

構(gòu)分成()°

A.動態(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)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的()。

A.存儲結(jié)構(gòu)B?存儲實現(xiàn)

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

答案：C

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

A.數(shù)據(jù)具有同一特點

B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致

C.每個數(shù)據(jù)元素都一樣

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

答案：B

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

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

B.數(shù)據(jù)項是數(shù)據(jù)的基本單位

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

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

答案：D

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

合。

(5)算法的時間復雜度取決于()。

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

C.計算機的配置口.人和8

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

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

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

A.樹B?字符串C?隊列D?棧

答案：A6.試分析下面各程序段的時間復雜度。

(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)順序表中第一個元素的存儲地址是100，每個元素的長度為2>則第5個元素的地址是()。

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

答案：B

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

(2)在n個結(jié)點的順序表中，算法的時間復雜度

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

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

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

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

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

答案：A

解釋：在順序表中插入一個結(jié)點的時間復雜度都是0(/)，排序的時間復雜度為0(/)

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

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

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

動一的元素個數(shù)為()。

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

答案：B

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

(4)鏈接存儲的存儲結(jié)構(gòu)所占存儲空間()。

A?分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B?只有一部分，存放結(jié)點值

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

D-分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)答案：A

(5)線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址(

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

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

答案：D

(6)線性表1在()情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。

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

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

答案：B

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

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

5

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

答案：C

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

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

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

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

A?nB?2n-1C.2nD,n-1

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

個表中的第一個元素依次與第一個表的元素比較，總計比較n次。

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

之前插入一個新元素時

須向后移動()個元素。

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

答案：B

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

正確的是()°

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

B?線性表中至少有一個元素

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

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

答案：D

(11)創(chuàng)建一個包括n個結(jié)點的有序單鏈表的時間復雜度是()。

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

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

新結(jié)點時需要和已有的結(jié)點進行比較，確定合適的插入位置，所以時間復雜度是

O(n2)=

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

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

B?順序存儲的線性表可以隨機存取

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

D-線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)

答案：D

解釋：鏈式存儲結(jié)構(gòu)和順序存儲結(jié)構(gòu)各有優(yōu)缺點，有不同的適用場合。

(13)在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應(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)在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針()。

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指針所指的結(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是()。

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è)計題

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

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

［題目分析］

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

個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新鏈接

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

無重復的元素。當一個表到達表尾結(jié)點，為空時，將非空表的剩余元素直接鏈接在Lc表的最后。

［算法描述］

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

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

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

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

點作為Lc的頭結(jié)點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〃相等時取La中的元素，刪除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;

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

)

}pc->next=pa?pa:pb;//插入剩余段deleteLb;//釋放Lb的頭結(jié)點

)

7

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

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

［題目分析］

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

個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新鏈接

在Lc表的表頭結(jié)點之后，如果兩個表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當一個表到

達表尾結(jié)點，為空時，將非空表的剩余元素依次摘取，鏈接在Lc表的表頭結(jié)點之后。

［算法描述］

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

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

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

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

作為Lc的頭結(jié)點

Lc->next=NULL;

while(pa||pb)

{//只要存在一個非空表，用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é)點插在Lc表的表頭結(jié)點之后

)

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

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

別表示兩個集合，其元素遞增排列。請設(shè)計算法求出A與B

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

［題目分析］

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

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

始進行比較，當兩個鏈表La和Lb均為到達表尾結(jié)點時，如果兩個表中相等的元素時，摘取La表中的元素，刪

除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當鏈表

La和Lb有一個到達表尾結(jié)點，為空時，依次刪除另一

8

個非空表中的所有元素。

［算法描述］

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

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

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

Lc=pc=La;〃用La的頭結(jié)點作為Lc的頭結(jié)點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é)點空間

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

pc->next=null;/置鏈表尾標記。

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

)

(4)已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出兩個集

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

該集合的元素個數(shù)。

［題目分析］

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

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

Lb的工作指針，初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當兩個鏈表La和Lb均為到達表

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

其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當鏈表La和Lb有一個為空時，依

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

［算法描述］

9

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

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

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

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

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

while(pa&&pb)

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

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

IA鏈表中當前結(jié)點指針后移elseif(pa->data>q->data

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

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

I刪除結(jié)點

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

于零的結(jié)點，而

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

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

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

［題目分析］

B表的頭結(jié)點使用原來A表的頭結(jié)點，為C表新申請一個頭結(jié)點。從A表的第一個結(jié)點

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

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

［算法描述］voidDisCompose(LinkedListA)

{B=A;

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

C=newLNode;I為C申請結(jié)點空間

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

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

{r=p->next;

"簪存p的后繼

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

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

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

)

if(p->data<0)

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

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

10

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

11

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

大值，反復進行比較，直到遍歷完該鏈表。

［算法描述］

ElemTypeMax(LinkListL){

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

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

p=L->next->next;

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

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

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

)

returnpmax->data;

存儲空間。

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

個地把鏈表L的當前結(jié)點p插入新的鏈表頭部。

［算法描述］

voidinverse(LinkList&L)

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

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

while(p){

指向*P的后繼

q=p->next;//q

p->next=L->next;

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

L->next=p;//*p

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

p=q;

)

}

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

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

［題目分析］

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

mink且小于maxk的所有元素。

［算法描述］

voiddelete(LinkList&L,intmink,intmaxk){

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

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

12

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

if(P)

13

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

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

修改指針

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

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

釋放結(jié)點空間

}//if

(9)已知p指向雙向循環(huán)鏈表中的一個結(jié)點，其結(jié)點結(jié)構(gòu)為data、prior、next三個域，寫出算法change(p),

交換P所指向的結(jié)點和它的前綴結(jié)點的順序。

[題目分析]

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

驅(qū)的前驅(qū)結(jié)點，后繼結(jié)點)六條鏈。

[算法描述]

voidExchange(LinkedListp)

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

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

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采用順序存儲結(jié)構(gòu)，請寫一時間復雜度為雜度為0(1)的算法，該算法刪除線性表中所有值0(n)、空間復

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

[題目分析]

在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動(刪第i個元素，第

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

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

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

[算法描述]

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

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

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

(i<j)

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

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

14

第3章棧和隊列

1?選擇題

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

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

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

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

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

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

pi為()

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

C

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

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

pi=n-i+1。

(3)數(shù)組Q：n］用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置-r為隊尾元素

的位置，假定隊列中元素的個數(shù)小于n,計算隊列中元素個數(shù)的公式為()。

A-r-fB?(n+f-r)%nC?n+r-fD-(n+r-f)%n

答案：D解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循

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

然后與MAXSIZE(本題為n)

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

(4)鏈式棧結(jié)點為：(data,link)，top保存到旨軻棧喇畫戴摘物救頂綃點，并將刪除結(jié)點的值

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é)點的值保存到即摘除伐頂結(jié)點。，…一

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

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

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

則計算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解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧的后進先出性質(zhì)。

（7）為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依

次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。

A.隊列B?棧C.線性表D.有序表

答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。

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

一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和el，則棧S的容

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

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

答案：B

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

解釋：元素出隊的序列是…

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

e4、e5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。

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

作是（）。

A.