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

第1章緒論

1.填空

⑴在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)（）個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與（）

和（）有關(guān)。

【解答】表長的一半，表長，該元素在表中的位置

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

【解答】108

【分析】第5個(gè)元素的存儲(chǔ)地址=第1個(gè)元素的存儲(chǔ)地址+（5-1）*2=108

⑶設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,若要?jiǎng)h除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操

作為（）.

［解答］p->next=（p->next）->next

⑷單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）。

【解答】為了運(yùn)算方便

【分析】例如在插入和刪除操作時(shí)不必對(duì)表頭的情況進(jìn)行特殊處理。

⑸非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（）o

【解答】p->ncxt=hcad

【分析】如圖2-8所示。

（6）在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入個(gè)結(jié)點(diǎn)s的操作序列是（）；刪除開始結(jié)點(diǎn)的操作

序列為（）.

【解答】s->ncxt=rcar->ncxt;rear->ncxt=s;rear=s;（將S的指針域先弄成表尾指針域，而表尾指針域是代表

下個(gè)結(jié)點(diǎn)的地址信息，所以要將指針域要用S替代，最后把表尾給S）

q=rear->next->next;rear->next->next=q->next;deleteq;

【分析】操作示意圖如圖2-9所示：

圖2-9帶尾指針的循環(huán)鏈表中插入和刪除操作示意圖

⑺個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）；在給定值為x

的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。

【解答】0（1）,O（n）

【分析】在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)只需修改指針，所以時(shí)間復(fù)雜度為0（1）（是表示常數(shù)計(jì)算時(shí)間）:

而在給定值為x的結(jié)點(diǎn)后插入?個(gè)新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時(shí)間復(fù)雜度為O（n）。

（8）可由一個(gè)尾指針唯一確定的鏈表有（）、（）、（）。

【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表

2.選擇題

⑴線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。

A隨機(jī)存取B順序存取C索引存取D散列存取

【解答】A,B

【分析】參見2.2.1。

⑵線性表采用鏈接存儲(chǔ)時(shí)，其地址（）。

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

C一定是不連續(xù)的D連續(xù)與否均可以

【解答】D

【分析】線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也

可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。

⑶單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）.

A不再需要頭指針了

B從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表；

C已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)；

D在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開。

【解答】B

（4）鏈表不具有的特點(diǎn)是（）。

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

C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長度成正比

【解答】A

⑸若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，則采用（）存儲(chǔ)方法最節(jié)省時(shí)間。

A順序表B單鏈表C雙鏈表D單循環(huán)鏈表

【解答】A

【分析】線性表中最常用的操作是取第i個(gè)元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時(shí)在順序表中

查找第i個(gè)元素的前驅(qū)也很方便。單鏈表和單循環(huán)鏈表既不能實(shí)現(xiàn)隨機(jī)存取，查找第i個(gè)元素的前驅(qū)也不方

便，雙鏈表雖然能快速查找第i個(gè)元素的前驅(qū)，但不能實(shí)現(xiàn)隨機(jī)存取。

（6）若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方法

最節(jié)省時(shí)間。

A單鏈表B帶頭指針的單循環(huán)鏈表C雙鏈表D帶尾指針的單循環(huán)鏈發(fā)

【解答】D

【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、帶頭指針

的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個(gè)結(jié)點(diǎn)，其時(shí)間性能是0（1）,

所以，答案是D。

⑺若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方

法最節(jié)省運(yùn)算時(shí)間。

A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表

【解答】B

【分析】在鏈表中的最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、單循環(huán)鏈

表都不合適，刪除最后一個(gè)結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，所以，帶尾指針的單循環(huán)鏈表不合

適，而循環(huán)雙鏈表滿足條件。

（8）在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是（）。

A0（l）BO（n）C0（n2）DO（nlog2n）

【解答】B

【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。

⑼對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是(

AO(1)B0(n)C0(n2)DO(nlog2n)

【解答】C

【分析】該算法需要將n個(gè)元素依次插入到有序單鏈表中，而插入每個(gè)元素需0(n)。

(10)使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以()。

A提高查找速度B更方便數(shù)據(jù)的插入和刪除

C節(jié)約存儲(chǔ)空間D很快回收存儲(chǔ)空間

【解答】B

【分析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因?yàn)殡p鏈表中有兩個(gè)指針

域，顯然不能節(jié)約存儲(chǔ)空間，對(duì)于動(dòng)態(tài)存儲(chǔ)分配，回收存儲(chǔ)空間的速度是一樣的。由于雙鏈表具有對(duì)稱性，

所以，其插入和刪除操作更加方便。

(11)在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行

()操作。

As->next=p->next;p->next=s;Bq->next=s;s->next=p;

Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;

【解答】B

【分析】注意此題是在q和p之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順序。

(12)在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是()。

Ap->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

Bp->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

Cs->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

Ds->prior=p;s->next=p->next;p->next->prior=s;p->next=s

【解答】D

【分析】在鏈表中，對(duì)指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10

給出備選答案C和D的圖解。

-IXS'-----IXS

(a)備選答案C操作示意圖(第4步指針修改無法進(jìn)行)(b)備選答案D操作示意圖

圖2-10雙捱表插入操作修改指針操作示意圖

3.判斷題

⑴線性表的邏輯順序和存儲(chǔ)順序總是一致的。

【解答】錯(cuò)。順序表的邏輯順序和存儲(chǔ)順序一致，鏈表的邏輯順序和存儲(chǔ)順序不一定一致。

⑵線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈接存儲(chǔ)結(jié)構(gòu)。

【解答】錯(cuò)。兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。

(3)設(shè)p,q是指針，若片口,則*p=*q。

【解答】錯(cuò)。pq只能表示p和q指向同?起始地址，而所指類型則不一定相同。

⑷線性結(jié)構(gòu)的基本特征是：每個(gè)元素有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

【解答】錯(cuò)。每個(gè)元素最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有

后繼。

⑸在單鏈表中，要取得某個(gè)元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)。

【解答】錯(cuò)。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。

4.請(qǐng)說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲(chǔ)結(jié)構(gòu)更好些。

⑴若線性表的總長度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。

⑵如果n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)發(fā)生變化。

⑶描述一個(gè)城市的設(shè)計(jì)和規(guī)劃。

【解答】順序表的優(yōu)點(diǎn)：①無需為表示表中元索之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間；②可以快速地

存取衣中任?位置的元素(即隨機(jī)存取)。順序表的缺點(diǎn)：①插入和刪除操作需移動(dòng)大量元素；②表的容

量難以確定；③造成存儲(chǔ)空間的“碎片

單鏈表的優(yōu)點(diǎn)：①不必事先知道線性表的長度；②插入和刪除元素時(shí)只需修改指針，不用移動(dòng)元素。單

鏈表的缺點(diǎn)：①指針的結(jié)構(gòu)性開銷：②存取表中任意元素不方便，只能進(jìn)行順序存取。

⑴應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎请S機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除

操作，所以空間變化不大，且需?？焖俅嫒?，所以應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。

⑵應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。鏈表容易實(shí)現(xiàn)表容量的擴(kuò)充，適合表的長度動(dòng)態(tài)發(fā)生變化。

⑶應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)。因?yàn)橐粋€(gè)城市的設(shè)計(jì)和規(guī)劃涉及活動(dòng)很多，需要經(jīng)常修改、獷充和刪除各種信息,

才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。

5.算法設(shè)計(jì)

⑴設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為0(n)的算法，實(shí)現(xiàn)將數(shù)組A[n]中所有元素循環(huán)右移k個(gè)位置。

【解答】算法思想清參見主教材第一章思想火花。下面給出具體算法。

循環(huán)右移算法Converse

voidConverse(intA[],intn,intk)

(

Reverse(A,0,k-1);

Reverse(A,k,n-1);

Reverse(A,0,n-l);

)

voidReverse(intA[],intfrom,intto)”將數(shù)組A中元素從from到to逆置

(

for(i=0,i<(to-from+1)/2;i++)

A[from+i]-<—*-A[to-i];/佼換元素

2

分析算法，第一次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(k),第二次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n-k),

第三次調(diào)用Reverse函數(shù)的時(shí)間復(fù)雜度為O(n),所以，總的時(shí)間復(fù)雜度為O(n)。

⑵已知數(shù)組A[n]中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素

為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為O(n)。

【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個(gè)變量i和j,初始時(shí)i=0,j=n-l,若A[i]為偶數(shù)并且A[j]為奇

數(shù)，則將A[i]與A[j]交換。具體算法如下：

數(shù)組奇偶調(diào)整算法Adjust|

voidAdjust(intA[],n)

(

i=O;j=n-l;

while(i<j)

(

while(A[i]%2!=0)i++;

while(A[j]%2=0)j~

if(i<j)A[j];

)

)

分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時(shí)間復(fù)雜度為O(n)。

⑶試編寫在無頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)

現(xiàn)進(jìn)行比較。

【解答】參見223。

(4)試分別以順序表和單鏈表作存儲(chǔ)結(jié)構(gòu)，各寫一實(shí)現(xiàn)線性表就地逆置的算法。

【解答】順序表的逆置，即是將對(duì)稱元素交換，設(shè)順序表的長度為length,則將表中第i個(gè)元素與第length-i-l

個(gè)元素相交換。具體算法如下：

；順序表逆置算法Reverse[

template<classT>

voidReverseddata[],intlength)

(

for(i=0;i<=length/2;i++)

(

temp=data[i];

data[i]=data[length-i-1];

data[length-i_1]=temp;

)

J

單鏈表的逆黃請(qǐng)參見224算法2-4和算法2-6。

⑸假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算

法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。

【價(jià)繪】利用單循環(huán)鏈表的特點(diǎn)，通過指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p,然后將結(jié)點(diǎn)r刪除，

如圖2-11所示，具體算法如下：

循環(huán)布表刪除算法Del|

template<classT>

voidDel(Node<T>*s)

(

p=s；力工作指針p初始化，查找s的前驅(qū)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，用p指示

while(p->next->next!=s)

p=p->next;

r=p->next;Ux為p的前驅(qū)結(jié)點(diǎn)，q為t的前驅(qū)結(jié)點(diǎn)

p->next=s;姍]除r所指結(jié)點(diǎn)

deleter;

)

pr

圖2-11刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)操作示意圖

(6)已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表，

使每個(gè)循環(huán)鏈表中只含同一類字符。

【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數(shù)

字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B,D,A中分別存放字母、數(shù)字和其他字符。

具體算法如下：

單鞋表拆分算法Adjust|

template<classT>

voidAdjust(Node<T>*A,Node<int>*D,Node<char>*B)

(

D=newNode<int>;D->next=D;"創(chuàng)建空循環(huán)鏈表D,存放數(shù)字

B=newNode<char>;B->next=B;。創(chuàng)建空循環(huán)鏈表B,存放字符

p=A;q=p->next;/斤作指針q初始化

while(q)

(

if((,A,<=q->data)&&(q->data>=,Z,)11('a'<=q->data)&&(q->data>-z'))(

p->next=q->next;

q->next=B->next;

B->next=q;/探用頭插法插在循環(huán)捱表B的頭結(jié)點(diǎn)的后面

)

elseif(('0,<=q->data)&&(q->data>=,9')){

p->next=q->next;

q->next=D->next;

D->next=q;/探用頭插法插在循環(huán)鏈表D的頭結(jié)點(diǎn)的后面

)

elsep=q,

q=p->next;

J

p->next=A;R=A,解鏈表A構(gòu)造為循環(huán)鏈表，為除字母和數(shù)字的其他字符

)|

(7)設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)。

【解答】從頭到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除

該后繼結(jié)點(diǎn)。具體算法如下：

單鏈表刪除相同值算法Pui￡]

voidPurge(Node<T>*first)

(

p=first->next;

while(p->next)

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

q=p->next;

p->next=q->next;

deleteq;

}

dsep=p->next;

)

⑻判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱。

【解答】設(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等,

則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點(diǎn)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)），

或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)（循環(huán)雙鏈表中結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)）。如圖2-12所示。

圖2-12判斷循環(huán)雙鏈表對(duì)稱的操作示意圖

判斷雙犍表對(duì)稱算法Equal

template<classT>

stiuctDulNode

(

Tdata;

DulNode<T>*prior,*next;

)；

template<classT>

boolEqual(DulNode<T>*first)

(

p=first->next,q=first->prior;

while(p!=q&&p->prior!=q)

if(p->data==q->data){

p=p->next;//工作指針p后移

q=q->prior;"工作指針q前移

)

elsereturn0;

return1;

)

學(xué)習(xí)自測及答案

1.已知一維數(shù)組A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144,則第一個(gè)

元素的地址是（）。

A108B180C176D112

【解答】D

2.在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為：（）。

A0（0）B0（1）CO（n）DO（n2）

【解答】C

3.在一個(gè)長度為n的順序表的第i（14區(qū)n+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)（）個(gè)元素，刪除

第i（l<i<n）個(gè)元素時(shí)，需向前移動(dòng)（）個(gè)元素。

【解答】n-i+1,n-i

4.在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（）指示。

【解答】其前驅(qū)結(jié)點(diǎn)的指針域

5.當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，其主要特點(diǎn)是（）。

【解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰

6.在雙鏈表中，每個(gè)結(jié)點(diǎn)設(shè)置了兩個(gè)指針域，其中一個(gè)指向（）結(jié)點(diǎn)，另一個(gè)指向（）結(jié)點(diǎn)。

【解答】前驅(qū)，后繼

7.設(shè)A是一個(gè)線性表（al,a2,...,an）,采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素

n-i

需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間（l<i<n）的概率為“S+D/2,則平均每

插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？

【解答】

s(w-I+1)=-

J12，

B(1)2

=(2?+1)/3

8.線性表存放在整型數(shù)組A[arrsize]的前elenum個(gè)單元中，且遞增有序。編寫算法，將元素x插入到線

性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度。

【解答】本題是在一個(gè)遞增有序表中插入元素x,基本思路是從有序表的尾部開始依次取元素與x比較，

若大于X,此元素后移一位，再取它前面?個(gè)元素重復(fù)上述步驟；否則，找到插入位置，將X插入.具體

算法如下：

有序順序表插入算法Insert[

constintarrsize=100,

classSeqList

(

private:

intdata[arrsize];

intdenum;

public:

Insert(intx);

)；

voidSeqList::Insert(intx)

(

if(elenum==arrsize)throw??overflow',;

else{

i=denum-1;

while(i>=l&&x<data[i])

(

data[i+l]=data[i];

i++;

)

data[i+l]=x;

)

)

9.已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除鏈表中所有大于mink且小于maxk的

所有元素，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間。

【解答】因?yàn)槭窃谟行騿捂湵砩系牟僮?，所以，要充分利用其有序性。在單鏈表中查找第一個(gè)大于mink

的結(jié)點(diǎn)和第一個(gè)小于maxk的結(jié)點(diǎn)，再將二者間的所有結(jié)點(diǎn)刪除。

有序鞋表刪除算法DdeteBetween________________________________________________

template<classT>

voidDeleteBetween(Node<T>*出5"intmink,intmaxk)

(

p=first,

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

p=p->next;

if(p->next){

q=p->next;

while(q->data<maxk)

(

u=q->next;

p->next=q->next;

deleteq;

qf；

)

)

)

10.設(shè)單循環(huán)鏈表L1,對(duì)其遍歷的結(jié)果是：xl,x2,X3,...,xn-lzxn&請(qǐng)將該循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表

L1和L2,使得L1中含有原L1表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：xlzx3z...；L2中含有原L1表中序

號(hào)為偶數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：...，x4,x2。

【解答】算法如下：

循環(huán)犍表拆分算法DePatch__________________________

template<classT>

Node<T>*DePatch(Node<T>*L1)

(

L2=newNode<T>;L2->next=L2;

q=Ll->next;Ll->next=Ll;

p=Ll;i=l;

while(q!=Ll)

(

if(i%2=1){"應(yīng)用尾插法

p->next=q;p=q,p->next=Ll;

q=q->next;i++;

}

else(

L2->next=q;u=q->next;q->next=L2->next;

qn;i++;

}

)

)

第3章特殊線性表一一棧、隊(duì)列和串

課后習(xí)題講解

1.填空

⑴設(shè)有一個(gè)空棧，棧頂指針為1000H,現(xiàn)有輸入序列為1、2、3、4、5,經(jīng)過push,push,pop,push,

pop.push,push后，輸出序列是（），棧頂指針為（）。

【解答】23,1003H

⑵棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（）：其判定?？盏臈l件分別是（），判定棧滿的條件分別是（）。

【解答】順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)（或順序棧和鏈棧），棧頂指針top=-l和top=NULL,棧頂指針

top等于數(shù)組的長度和內(nèi)存無可用空間

⑶（）可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

【解答】棧

【分析】遞歸函數(shù)的調(diào)用和返回正好符合后進(jìn)先出性。

（4）表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）。

【解答】abc+*d-

【分析】將中綴表達(dá)式變?yōu)楹缶Y表達(dá)式有一個(gè)技巧：將操作數(shù)依次寫下來，再將算符插在它的兩個(gè)操作數(shù)

的后面。

⑸棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（），隊(duì)列的操作特性是（），棧和隊(duì)列的主要區(qū)別

在于（）。

【解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同

（6）循環(huán)隊(duì)列的引入是為了克服（）。

【解答】假溢出

⑺數(shù)組Q[n]用來表示一個(gè)循環(huán)隊(duì)列，front為隊(duì)頭元素的前一個(gè)位置，rear為隊(duì)尾元素的位置，計(jì)算隊(duì)列

中元素個(gè)數(shù)的公式為（）。

【解答】（rear-front+n）%n

【分析】也可以是（rear-front）%n，但rear-front的結(jié)果可能是負(fù)整數(shù)，而對(duì)?個(gè)負(fù)整數(shù)求模，其結(jié)果

在不同的編譯器環(huán)境下可能會(huì)有所不同。

⑻用循環(huán)鏈表表示的隊(duì)列長度為n,若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是（）和（）。

【解答】0（1）,0（n）

【分析】在帶頭指針的循環(huán)鏈表中，出隊(duì)即是刪除開始結(jié)點(diǎn)，這只需修改相應(yīng)指針；入隊(duì)即是在終端結(jié)點(diǎn)

的后面插入一個(gè)結(jié)點(diǎn)，這需要從頭指針開始查找終端結(jié)點(diǎn)的地址。

（9）串是一種特殊的線性表，其特殊性體現(xiàn)在（）。

【解答】數(shù)據(jù)元素的類型是?個(gè)字符

（10）兩個(gè)串相等的充分必要條件是（）。

【解答】長度相同且對(duì)應(yīng)位置的字符相等

【分析】例如"abcBabc","abcWbca"。

2.選擇題

⑴若一個(gè)棧的輸入序列是1，2,3，…，n,輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素是（）。

A不確定Bn-iCn-i-1Dn-i+1

【解答】D

【分析】此時(shí)，輸出序列一定是輸入序列的逆序。

（2）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5、e6依次通過棧S,一個(gè)元素出棧后即進(jìn)

入隊(duì)列Q,若6個(gè)元素出隊(duì)的順序是e2、e4、e3、e6、e5、el,則棧S的容量至少應(yīng)該是（）。

A6B4C3D2

【解答】C

【分析】由于隊(duì)列具有先進(jìn)先出性，所以，此題中隊(duì)列形同虛設(shè)，即出棧的順序也是e2、e4、e3、e6、e5、

el0

（3）?個(gè)棧的入棧序列是1,2,3,4,5,則棧的不可能的輸出序列是（）。

A54321B45321C43512D12345

【解答】C

【分析】此題有一個(gè)技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序（指的是元素的序

號(hào)）的兩個(gè)元素。

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

A順序表B棧C隊(duì)列D鏈表

【解答】B

【分析】每個(gè)右括號(hào)與它前面的最后一個(gè)沒有匹配的左括號(hào)配對(duì)，因此具有后進(jìn)先出性。

⑸在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)通常設(shè)置一個(gè)打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個(gè)（）

結(jié)構(gòu)。

A棧B隊(duì)列C數(shù)組D線性表

【解答】B

【分析】先進(jìn)入打印緩沖區(qū)的文件先被打印，因此具有先進(jìn)先出性。

（6）一個(gè)隊(duì)列的入隊(duì)順序是1,2,3,4,則隊(duì)列的輸出順序是（）。

A4321B1234C1432D3241

【解答】B

【分析】隊(duì)列的入隊(duì)順序和出隊(duì)順序總是?致的。

⑺棧和隊(duì)列的主要區(qū)別在于（）。

A它們的邏輯結(jié)構(gòu)不樣B它們的存儲(chǔ)結(jié)構(gòu)不?樣

C所包含的運(yùn)算不一樣D插入、刪除運(yùn)算的限定不一樣

【解答】D

【分析】棧和隊(duì)列的邏輯結(jié)構(gòu)都是線性的，都有順序存儲(chǔ)和鏈接存儲(chǔ)，有可能包含的運(yùn)算不一樣，但不是

主要區(qū)別，任何數(shù)據(jù)結(jié)構(gòu)在針對(duì)具體問題時(shí)包含的運(yùn)算都可能不同。

⑻設(shè)數(shù)組S[n]作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)S[n]全滿時(shí)才不能進(jìn)行進(jìn)棧操作。

為這兩個(gè)棧分配空間的最佳方案是（）。

AS1的棧底位置為0.S2的棧底位置為n-1

BS1的棧底位置為0,S2的棧底位置為n/2

CS1的棧底位置為0.S2的棧底位置為n

DS1的棧底位置為0,S2的棧底位置為1

【解答】A

【分析】兩棧共享空間首先兩個(gè)棧是相向增長的，棧底應(yīng)該分別指向兩個(gè)棧中的第一個(gè)元素的位置，并注

意C++中的數(shù)組下標(biāo)是從0開始的。

（9）設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。

A連接B模式匹配C求子串D求串長

【解答】B

3.判斷題

⑴有n個(gè)元素依次進(jìn)棧，則出棧序列有(n-l)/2種。

(2M)!

2

【解答】錯(cuò)。應(yīng)該有s+DS!)種.

⑵棧可以作為實(shí)現(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。

【解答】對(duì)。只要操作滿足后進(jìn)先出性，都可以采用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。

⑶在棧滿的情況卜一不能做進(jìn)棧操作，否則將產(chǎn)生''上溢"。

【解答】對(duì)。

⑷在循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，則隊(duì)滿的條件是

front=rear。

【解答】錯(cuò)。這是隊(duì)空的判定條件，在循環(huán)隊(duì)列中要將隊(duì)空和隊(duì)滿的判定條件區(qū)別開。

⑸空串與空格串是相同的。

【解答】錯(cuò)?？沾拈L度為零，而空格串的長度不為0,其長度是串中空格的個(gè)數(shù)。

4.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳,B,C,D,E,能否得到如卜.出棧序列，若能，請(qǐng)寫出操作序列，若

不能，請(qǐng)說明原因。

(1)C,E,A,B,D

⑵C,B.A,D,E

【解答】⑴不能，因?yàn)樵贑、E出棧的情況下，A一定在棧中，而且在B的下面，不可能先于B出棧。⑵

可以，設(shè)I為進(jìn)棧操作，0為入棧操作，則其操作序列為HI000I0I。。

5.舉例說明順序隊(duì)列的''假溢出"現(xiàn)象。

【解答】假設(shè)有一個(gè)順序隊(duì)列,如圖3-6所示，隊(duì)尾指針rear=4,隊(duì)頭指針front=l,如果再有元素入隊(duì)，

就會(huì)產(chǎn)生''上溢"，此時(shí)的''上溢"又稱為''假溢出"，因?yàn)殛?duì)列并不是真的溢出了，存儲(chǔ)隊(duì)列的數(shù)組中還有2個(gè)

存儲(chǔ)單元空閑，其下標(biāo)分別為。和1。

圖3-6順序隊(duì)列的假溢出

6.在操作序列push(l)、push(2),pop、push⑸、push⑺、pop、push(6)之后，棧頂元素和棧底元素分

別是什么？(push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。)

【解答】棧頂元素為6,棧底元素為1。其執(zhí)行過程如圖3-7所示。

76

25

71

(a)push(l)?push(2)(b)pop?push(5)?pushC7)(c)pop,push⑹

圖3-7棧的執(zhí)行過程示意圖

7.在操作序歹ijEnQueue(l)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)

之后，隊(duì)頭元素和隊(duì)尾元素分別是什么？(EnQueue(k)表示整數(shù)k入隊(duì)，DeQueue表示隊(duì)頭元素出隊(duì))。

【解答】隊(duì)頭元素為5,隊(duì)尾元素為9c其執(zhí)行過程如圖3-8所示。

出隊(duì)入隊(duì)______________

J131357579

(a)EnQueue(1)jEnQueueG)(b)DeQueue>EnQueue(5)jEnQueue(7)(c)DeQueuejEnQueue(9)

圖3-8隊(duì)列的執(zhí)行過程示意圖

8.空串和空格串有何區(qū)別？串中的空格符有何意義？空串在串處理中有何作用？

【解答】不含任何字符的串稱為空串，其長度為零。僅含空格的串稱為空格串，它的長度為串中空格符的

個(gè)數(shù)。串中的空格符可用來分隔一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長時(shí)應(yīng)包括這些空格符?？?/p>

串在串處理中可作為任意串的子串。

9.算法設(shè)計(jì)

⑴假設(shè)以不帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)?個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針。試設(shè)計(jì)相應(yīng)

的入隊(duì)和出隊(duì)的算法。

【解答】出隊(duì)操作是在循環(huán)鏈表的頭部進(jìn)行，相當(dāng)于刪除開始結(jié)點(diǎn)，而入隊(duì)操作是在循環(huán)鏈表的尾部進(jìn)行,

相當(dāng)于在終端結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。由于循環(huán)鏈表不帶頭結(jié)點(diǎn)，需要處理空表的特殊情況。

入隊(duì)算法如下:

循環(huán)隊(duì)列入隊(duì)算法Enqueue]

template<classT>

voidEnqueue(Node<T>*rear,Tx)

(

s=newNode<T>;

s->data=x;

if(rear==NULL){//處理空表的特殊情況

rear=s;

rear->next=s;

)

else(//處理除空表以外的一般情況

s->next=rear->next;

rear->next=s;

rear=s;

)

)

出隊(duì)算法如下:

循環(huán)隊(duì)列出隊(duì)算法Dequeue]

template〈classT>

TDequeue(Node<T>*rear)

(

if(rear==NULL)throw"underflow",例斷表空

else(

s=rear->next;

if(s==rear)rear=NULL;，腌表中只有一個(gè)結(jié)點(diǎn)

elserear->next=s->next,

deletes;

)

)

(2)設(shè)順序棧S中有2n個(gè)元素，從棧頂?shù)綏５椎脑匾来螢閍2n,a2n-l，…，al,要求通過一個(gè)循環(huán)隊(duì)列

重新排列棧中元素，使得從棧頂?shù)綏５椎脑匾来螢閍2n,a2n-2,…，a2,a2n-l,a2n-3,…，al,請(qǐng)?jiān)O(shè)

計(jì)算法實(shí)現(xiàn)該操作，要求空間復(fù)雜度和時(shí)間復(fù)雜度均為O(n)。

【解答】操作步驟為：

①將所有元素出棧并入隊(duì)；

②依次將隊(duì)列元素出隊(duì)，如果是偶數(shù)結(jié)點(diǎn)，則再入隊(duì)，如果是奇數(shù)結(jié)點(diǎn)，則入棧；

③將奇數(shù)結(jié)點(diǎn)出棧并入隊(duì)；

④將偶數(shù)結(jié)點(diǎn)出隊(duì)并入棧；

⑤將所有元素出棧并入隊(duì)；

?將所有元素出隊(duì)并入棧即為所求。

⑶用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)串S,編寫算法刪除S中第i個(gè)字符開始的連續(xù)j個(gè)字符。

【解答】先判斷串S中要?jiǎng)h除的內(nèi)容是否存在，若存在，則將第i+j-1之后的字符前移j個(gè)位置。算法如下:

串刪除算法Del

voidDel(charS[],inti,intj)〃數(shù)組0號(hào)單元存放串的長度

(

if(i+j<S[O]){

for(k=i;k<S[0];k++)

S[k]=S[k+j];

S[O]=S[(J]-j;

)

elsecout<〈"參數(shù)非法";

)

（4）對(duì)于采用順序存儲(chǔ)結(jié)構(gòu)的串S,編寫?個(gè)函數(shù)刪除其值等于ch的所有字符。

【解答】從后向前刪除值為ch的所有元素，這樣所有移動(dòng)的元素中沒有值為ch的元素，能減少移動(dòng)元素

的次數(shù)，提高算法的效率。算法如下：

串刪除算法而]

voidDel(charS[],charch)滕組的0號(hào)單元存放串的長度

(

for(i=S[0];i>0;i—)

if(S[i]==ch){

for(j=i+l,j<=S[0];j++)

SU-l]=S[j];

s網(wǎng)一；

}

)

⑸對(duì)串的模式匹配KMP算法設(shè)計(jì)求模式滑動(dòng)位置的next函數(shù)。

【解答】參見3.2.5

學(xué)習(xí)自測及答案

1.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即下標(biāo)為0的單元）作為棧底，以top作為棧頂指

針，當(dāng)出棧時(shí)，top的變化為（）。

A不變Btop=0;Ctop=top-l;Dtop=top+l;

【解答】C

2.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的出棧序列是（）。

AedcbaBcdebaCdebcaDabcde

【解答】C

3.從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行（）。

Ax=top;top=top->next;Bx=top->data;

Ctop=top->next;x=top->data;Dx=top->data;top=top->next;

【解答】D

4.設(shè)元素1,2,3,P,A依次經(jīng)過一個(gè)棧，進(jìn)棧次序?yàn)?23PA,在棧的輸出序列中，有哪些序列可作為C++

程序設(shè)計(jì)語言的變量名。

【解答】PA321,P3A21,P32A1,P321A,AP321

5.設(shè)S="I_am_a_teactheH其長度為()。

【解答】15

第4章廣義線性表一多維數(shù)組和廣義表

課后習(xí)題講解

1.填空

⑴數(shù)組通常只有兩種運(yùn)算：()和()，這決定了數(shù)組通常采用()結(jié)構(gòu)來實(shí)現(xiàn)存儲(chǔ)。

【解答】存取，修改，順序存儲(chǔ)

【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了

初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。

⑵二維數(shù)組A中行下標(biāo)從10到20,列下標(biāo)從5到10,按行優(yōu)先存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元,A[10][5]

的存儲(chǔ)地址是1000,則元素的存儲(chǔ)地址是().

【解答】1140

【分析】數(shù)組A中每行共有6個(gè)元素，元素A[15][10]的前面共存儲(chǔ)了(15-10)x6+5個(gè)元素，每個(gè)元素占4

個(gè)存儲(chǔ)單元，所以，其存儲(chǔ)地址是1000+140=1140。

(3)設(shè)有個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，A[0][0]為第個(gè)元素，其存儲(chǔ)地址為d,每個(gè)元素占1個(gè)

存儲(chǔ)單元，則元素A[8][5]的存儲(chǔ)地址為()。

【解答】d+41

【分析】元素A網(wǎng)⑸的前面共存儲(chǔ)了(1+2+...+8)+5=41個(gè)元素。

⑷稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是()和()。

【解答】三元組順序表，十字鏈表

⑸廣義表((a),(((b),c)),(d))的長度是()，深度是()，表頭是()，表尾是().

【解答】3,4,(a),((((b),c)),(d))

(6)已知廣義表LS=(a,(b,c,d),e),用Head和Tail函數(shù)取出LS中原子b的運(yùn)算是().

【解答】Head(Head(Tail(LS)))

2.選擇題

⑴二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，行下標(biāo)的范圍從0~8,列下標(biāo)的范圍是從0~9,則存

放A至少需要()個(gè)字節(jié)，A的第8列和第5行共占()個(gè)字節(jié)，若A按行優(yōu)先方式存儲(chǔ)、

元素A[8][5]的起始地址與當(dāng)A按列優(yōu)先方式存儲(chǔ)時(shí)的()元素的起始地址一致。

A90B180C240D540E108F114G54

HA[8][5]IA[3][10]JA[5][8]KA[4][9]

【解答】D,E,K

【分析】數(shù)組A為9行10列，共有90個(gè)元素，所以，存放A至少需要90x6=540個(gè)存儲(chǔ)單元，第8列

和第5行共有18個(gè)元素(注意行列有個(gè)交叉元素)，所以，共占108個(gè)字節(jié)，元素A[8][5]按行優(yōu)先存

儲(chǔ)的起始地址為d+8xl0+5=d+85,設(shè)元素按列優(yōu)先存儲(chǔ)的起始地址與之相同，則d+jx9+i=d+85,

解此方程，得此4,j=9。

⑵將數(shù)組稱為隨機(jī)存取結(jié)構(gòu)是因?yàn)?)

A數(shù)組元素是隨機(jī)的B對(duì)數(shù)組任一元素的存取時(shí)間是相等的

C隨時(shí)可以對(duì)數(shù)組進(jìn)行訪問D數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定

【解答】B

⑶下面的說法中，不正確的是()

A數(shù)組是一種線性結(jié)構(gòu)B數(shù)組是一種定長的線性結(jié)構(gòu)

C除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等

D數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操

【解答】C

【分析】數(shù)組屬于廣義線性表，數(shù)組被創(chuàng)建以后，其維數(shù)和每維中的元素個(gè)數(shù)是確定的，所以，數(shù)組通常

沒有插入和刪除操作。

⑷對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了()

A表達(dá)變得簡單B對(duì)矩陣元素的存取變得簡單

C去掉矩陣中的多余元素D減少不必要的存儲(chǔ)空間

【解答】D

【分析】在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復(fù)存儲(chǔ)。

⑸下面()不屬于特殊矩陣。

A對(duì)角矩陣B三角矩陣C稀疏矩陣D對(duì)稱矩陣

【解答】C

(6)若廣義表A滿足Head(A)=Tail(A),則人為()

A()B(())C((),())D((),(),())

【解答】B

⑺下面的說法中，不正確的是()

A廣義表是一種多層次的結(jié)構(gòu)B廣義表是一種非線性結(jié)構(gòu)

C廣義表是一種共享結(jié)構(gòu)D廣義表是一種遞歸

【解答】B

【分析】從各層元索各白具有的線性關(guān)系講，廣義表屬于線性結(jié)構(gòu)。

⑻下面的說法中，不正確的是()

A對(duì)稱矩陣只須存放包括主對(duì)角線元素在內(nèi)的下(或上)三角的元素即可。

B對(duì)角矩陣只須存放非零元素即可。

C稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲(chǔ)。

D稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲(chǔ)

【解答】D

【分析】稀疏矩陣中大量值為零的元素分布沒有規(guī)律，因此采用三元組表存儲(chǔ)。如果零元素的分布有規(guī)律,

就沒有必要存儲(chǔ)非零元素的行號(hào)和列號(hào)，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。

3.判斷題

⑴數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。

【解答】錯(cuò)。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。

⑵使用三元組表存儲(chǔ)稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。

【解答】對(duì)。因?yàn)槿M表除了存儲(chǔ)非零元素值外，還需要存儲(chǔ)其行號(hào)和列號(hào)。

⑶稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。

【解答】對(duì)。因?yàn)閴嚎s存儲(chǔ)后，非零元素的存儲(chǔ)位置和行號(hào)、列號(hào)之間失去了確定的關(guān)系。

(4)線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是單元素，則廣義表便成為線性表。

【解答】對(duì)。

⑸若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。

【解答】錯(cuò)。如廣義表L=((),(a,b))的表頭為空表，但L不是空表。

4.一個(gè)稀疏矩陣如圖4-4所示，寫出對(duì)應(yīng)的三元組順序表和十字鏈表存儲(chǔ)表示。

0020

3000

00-15

0000

圖4-4稀疏矩陣

【解答】對(duì)應(yīng)的三元組順序表如圖4-5所示，十字鏈表如圖4-6所示。

下標(biāo)行號(hào)列號(hào)非零元素

132

213

33-1

345

4(行數(shù))

4(列數(shù))

4(非零元個(gè)數(shù))

圖4-5稀疏矩陣的三元組順序表

圖4-6稀疏矩陣的十字鏈表

5.已知A為稀疏矩陣，試從空間和時(shí)間角度比較采用二維數(shù)組和三元組順序表兩種不同的存儲(chǔ)結(jié)構(gòu)完成

求運(yùn)算的優(yōu)缺點(diǎn)。

【解答】設(shè)稀疏矩陣為m行n列，如果采用二維數(shù)組存儲(chǔ)，其空間復(fù)雜度為O(mxn)；因?yàn)橐獙⑺械木?/p>

陣元素累加起來，所以，需要用?個(gè)兩層的嵌套循環(huán)，其時(shí)間復(fù)雜度亦為O(mxn)。如果采用三元組順序

表進(jìn)行壓縮存儲(chǔ)，假設(shè)矩陣中有t個(gè)非零元素，其空間復(fù)雜度為O(t),將所仃的矩陣元素累加起來只需將

三元組順序表掃描?遍，其時(shí)間復(fù)雜度亦為O(t)。當(dāng)t<<mxn時(shí)，采用三元組順序表存儲(chǔ)可獲得較好的

時(shí)、空性能。

6.設(shè)某單位職工工資表ST由''工資"、''扣除"和''實(shí)發(fā)金額"三項(xiàng)組成，其中工資項(xiàng)包括''基本工資"、''津貼"

和''獎(jiǎng)金"，扣除項(xiàng)包括水"、''電"和''煤氣"。

⑴清用廣義表形式表示所描述的工資表ST,并用表頭和表尾求表中的''獎(jiǎng)金"項(xiàng)；

⑵畫出該工資表ST的存儲(chǔ)結(jié)構(gòu)。

【解答】⑴ST=((基本工資，津貼，獎(jiǎng)金)，(水，電，煤氣)，實(shí)發(fā)金額)

Head(Tail(Tail(Head(ST))))=獎(jiǎng)金

⑵工資表ST的頭尾表示法如圖4-7所示。

7.若在矩陣A中存在一個(gè)元素ai,j(OSiSn-l,0<j<m-l),該元素是第i行元素中最小值且又是第j列元

素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。假設(shè)以二維數(shù)組存儲(chǔ)矩陣A,試設(shè)計(jì)一個(gè)求該矩陣所有

馬鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度。

【解答】在矩陣中逐行尋找該行中的最小值，然后對(duì)其所在的列尋找最大值，如果該列上的最大值與該行

上的最小值相等，則說明該元素是鞍點(diǎn)，將它所在行號(hào)和列號(hào)輸出。

具體算法如下:

馬鞍點(diǎn)算法Andian]

voidAndian(inta[][],intm,intn)

(

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

(

d=a[i][0];k=0,"d為第i行中的最小值

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

if(a[i][j]<d){

d=?；

k=j；

)"afi]因?yàn)榈趇行最小值

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

if(a[j][k]>d)break;

if(j==n)cout<〈"輸出鞍點(diǎn)a[i][k];

}

)

分析算法，外層for循環(huán)共執(zhí)行n次，內(nèi)層第?個(gè)for循環(huán)執(zhí)行m次，第二個(gè)for循環(huán)最壞情況下執(zhí)行n

次，所以，最壞情況下的時(shí)間復(fù)雜度為0(mn+n2)。

學(xué)習(xí)自測及答案(沒看)

1.:維數(shù)組M