一、判斷正誤

（? F? ）1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。?

（? F? ）2. 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。

（? F? ）3. 鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)將后續(xù)各個(gè)單元向前移動(dòng)。

（? F? ）4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。

（? F? ）5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。

?

二、單項(xiàng)選擇題

（?? A? ）1. 鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：

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

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

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

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

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

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

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

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

（Ａ）需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值????? （Ｂ）需不斷對(duì)Ｌ進(jìn)行刪除插入

（Ｃ）Ｌ中含有大量的結(jié)點(diǎn)????????? （Ｄ）Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜

（? C?? ）4． 單鏈表的存儲(chǔ)密度

（Ａ）大于1； （Ｂ）等于1；? （Ｃ）小于1； （Ｄ）不能確定

（?? B? ）5． 設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為

?	P0	?	?	3	?	?	4	?	?
P0	à	a1	3	à	a2	4	à	a3	0

（Ａ）循環(huán)鏈表?? （Ｂ）單鏈表? （Ｃ）雙向循環(huán)鏈表??? （Ｄ）雙向鏈表

（? B?? ）6．下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？

A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。

D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。

（?? A? ）7．若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用______存儲(chǔ)方式最節(jié)省時(shí)間。

A．順序表? ?B．雙鏈表???? C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表??? D．單循環(huán)鏈表

（? D?? ）8．某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用? _______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

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

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

（?? B? ）9. 鏈表不具有的特點(diǎn)是_________. ?

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

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

（?? D? ）10．完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作是（??? ）.

A． p^.next:=s ; s^.priou:=p; p^.next^.prior:=s ; s^.next:=p^.next;

B． p^.next^.prior:=s; p^.next:=s; s^.prior:=p; s^.next:=p^.next;

C． s^.prior:=p; s^.next:=p^.next; p^.next:=s; p^.next^.prior:=s ;

D． s^.prior:=p; s^.next:=p^.next; p^.next^.prior:=s ; p^.next:=s;

（? B?? ）11．在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（??? ）。

A．p->next=s;s->next=p->next;? B． s->next=p->next;p->next=s;

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

（?? B? ）12．對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（??? ）

A．head==NULL? B．head->next==NULL ???C．head->next==head?? D．head!=NULL

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

A． (p^.llink)^.rlink:=p^.rlink??? (p^.rlink)^.llink:=p^.llink;

B． p^.llink:=(p^.llink)^.llink??? (p^.llink)^.rlink:=p;

C． (p^.rlink)^.llink:=p?????????? p^.rlink:=(p^.rlink)^.rlink

D． p^.rlink:=(p^.llink)^.llink???? p^.llink:=(p^.rlink)^.rlink;

?

三、簡(jiǎn)答題

1．線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：

（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？

應(yīng)選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，可以動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長(zhǎng)度的影響。插入、刪除時(shí)間復(fù)雜度為O(1)

（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？

選擇順序存儲(chǔ)結(jié)構(gòu)，順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O(1)

?

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

便于首元結(jié)點(diǎn)的處理

增加了頭結(jié)點(diǎn)后，首元結(jié)點(diǎn)的地址保存在頭結(jié)點(diǎn)的指針域中，對(duì)鏈表的第一個(gè)數(shù)據(jù)元素的操作與其他數(shù)據(jù)元素相同，無(wú)需進(jìn)行特殊處理

便于空表和非空表的統(tǒng)一處理

增加頭結(jié)點(diǎn)后，無(wú)論鏈表是否為空，頭指針都是指向頭節(jié)點(diǎn)的非空指針，若為空表，頭結(jié)點(diǎn)的指針域?yàn)榭铡?/p>

?

?

四、線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式。現(xiàn)有一個(gè)具有五個(gè)元素的線性表L={23，17，47，05，31}，若它以鏈接方式存儲(chǔ)在下列100～119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié)）組成，如下所示：

05	U	17	X	23	V	31	Y	47	Z
^	?	?	?	?	?	?	?	?	?	^
100	?	?	?	?	?	?	?	?	?	120

其中指針X，Y，Z的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？

尾結(jié)點(diǎn)指針域的值為0

X=116

Y=0

Z=100

末節(jié)點(diǎn)的起始地址為23的起始地址，即112

?

五、編程題

1. 已知一個(gè)帶頭結(jié)點(diǎn)的單鏈表L，請(qǐng)編程求該單鏈表中數(shù)據(jù)元素的個(gè)數(shù)。

int?Listlength(LinkList?L)

{

????int?sum=0;

????LinkList?p=L->next;

????while(p)

????{

????????p=p->next;

????????sum++;

????}

????return?sum;

}

?

?

2. 設(shè)有一帶頭結(jié)點(diǎn)的單鏈表,編程將鏈表顛倒過(guò)來(lái)，即（a1...an）逆置為(an...a1)，要求不用另外的數(shù)組或結(jié)點(diǎn)完成.

int?ListReverse(LinkList?&L)

{

????if(L->next)

????????return?1;

????LNode*pre=NULL;

????LNode*p=L->next;

????while(p)

????{

????????LNode*temp=p->next;

????????p->next=pre;

????????pre=p;

????????p=temp;

????}

????return?1;

}

總結(jié)

以上是生活随笔為你收集整理的数据结构练习题——线性表（二）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。