單鏈表題目和答案

1、丙度文厲.1第2章自測卷答案一、填空1順序表中邏輯上相鄰的元素的物理位置相互相鄰。單鏈表中邏輯上相鄰的元素的物理位置丕相鄰。2. 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位宜由其直接前驅(qū)結(jié)點(diǎn)值域指示。3. 在n個(gè)結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn)*p,需找到它的地址。二、判斷正誤（在正確的說法后面打勾，反之打叉）1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。X2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。X3. 鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，il算機(jī)會自動地將后續(xù)的各個(gè)單元向前移動。X4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。Y5. 順序表結(jié)構(gòu)適宜

2、于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。Y6. 順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。X7. 線性表在物理存儲空間中也一定是連續(xù)的。X&線性表在順序存儲時(shí)，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。X9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。X10. 線性表的邏輯順序與存儲順序總是一致的。X三、單項(xiàng)選擇題（A）1.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：（A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針（B）只有一部分，存放結(jié)點(diǎn)值（C）只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針（D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（B ） 2.鏈表是一種

3、采用存儲結(jié)構(gòu)存儲的線性表：（A）順序 （B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀（D ） 3.線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址：（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的（C） 一定是不連續(xù)的（D）連續(xù)或不連續(xù)都可以（B ） 4.線性表L在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（B）需不斷對L進(jìn)行刪除插入（D） L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜（C）小于1：（D）不能確定（A）需經(jīng)常修改L中的結(jié)點(diǎn)值（C）L中含有大量的結(jié)點(diǎn)C） 5.單鏈表的存儲密度（A）大于1：（B）等于1：A） 6、在單鏈表的一個(gè)結(jié)點(diǎn)中有個(gè)指針。A、1B、2C、3D、4（D ） 7、設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，

4、則選用最節(jié)省時(shí)間。A、單鏈表B、單循環(huán)鏈表C、帶尾指針的單循環(huán)鏈表D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表（B ） 8、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是。A、p->next=s;s->next=p->next; Bs->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;（C ） 9、對于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判泄該表為空表的條件是。A、head=NULLB、head-*next=NULLC

5、、head-*next=headD.head!=NULL （head 指向誰的）（c ） 10、在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是。A、p->prior=q;q->next=p;p->prior->next=q:q->prior=q;B、p->prior=q:p->prior->next=q:q->next=p;q->prior=p->prior;C、q->next=p;q->prior=p->prior;p->Prior->next=q;p->prior=q;D、q->

6、prior=p->prior;q->next=q:p->prior=q;p->prior=q;（A） 11、在一個(gè)單鏈表中，若刪除P所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行。A p-next=p->next->next;B、p=p->next;p->next=p->next->next;C p->next=p->next;D、p=p->next->next;（A ） 12、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A> head=NULLB、head->next=NULLhead->next=headD、

7、head!=NULL（B ） 13、鏈表不具有的特點(diǎn)是。A、插入、刪除不需要移動元素B、可隨機(jī)訪問任一元素C、不必事先估計(jì)存儲空間D、所需空間與線性長度成正比X ） 1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可 以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。（X ）2.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點(diǎn)是無序, 而鏈表的示意圖有序。（X ） 3.鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會自動地將后續(xù) 的各個(gè)單元向前移動。錯，鏈表的結(jié)點(diǎn)不會移動，只是指針內(nèi)容改變。

8、（X ）4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類 型。錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（X ） 5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。錯，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”（X ） 6.順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn)。順序存儲方式插入、刪除運(yùn)算 效率較低，在表長為n的順序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動表長一半個(gè)數(shù)的 數(shù)據(jù)元素。（X ） 7.線性表在物理存儲空間中也一定是連續(xù)的。錯，

9、線性表有兩種存儲方式，順序存儲和鏈?zhǔn)酱鎯Α：笳卟灰筮B續(xù)存放。3百度文庫-讓毎個(gè)人平等地提升自我（x ） 8.線性表在順序存儲時(shí)，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時(shí)，邏輯上相鄰的元素在存儲的物理位置次序上 也相鄰。（X ） 9.順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二義 樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。（后一節(jié)介紹）（X ） 10.線性表的邏輯順序與存儲順序總是一致的。錯，理曲同7。鏈?zhǔn)酱鎯蜔o需一致。三、填空題1、在帶頭結(jié)點(diǎn)的單鏈表L中，若要刪除第

10、一個(gè)元素，則需要執(zhí)行下列三條語句：:next =Unext； free （U）。2、在單鏈表L中，若要在指針P所指結(jié)點(diǎn)之后插入由指針S所指的結(jié)點(diǎn)，則需執(zhí)行下列語句:S->next二P->next； :3、在帶有頭結(jié)點(diǎn)的單鏈表L中，第一個(gè)元素結(jié)點(diǎn)的指針是°4、雙循環(huán)鏈表L中由指針P所指向的某結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是1. 【嚴(yán)題集2. 2】在順序表中插入或刪除一個(gè)元素，需要平均移動 表中一半元素,具體 移動的元素個(gè)數(shù)與表長和該元素在表中的位置有關(guān)。2. 線性表中結(jié)點(diǎn)的集合是有限的,結(jié)點(diǎn)間的關(guān)系是一對一 的。3. 向一個(gè)長度為n的向量的第i個(gè)元素（lWiWn+1）之前插入一個(gè)元素時(shí)

11、，需向后移動 n-i+l 個(gè)元素。4. 向一個(gè)長度為n的向量中刪除第i個(gè)元素（lWiWn）時(shí)，需向前移動個(gè)元素。5. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0,因此，順序表也稱為隨機(jī)存 取的數(shù)據(jù)結(jié)構(gòu)。6. 【嚴(yán)題集2. 2】順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相 鄰的元素的物理位置不一定相鄰。7. 【嚴(yán)題集2. 2】在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置山其直接前驅(qū)結(jié) 點(diǎn)的鏈域的值指示。8. 在n個(gè)結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn)*p,需找到它的前驅(qū)結(jié)點(diǎn)的地址,其時(shí)間復(fù)雜度為 0 （n） odatanext1、設(shè)有兩個(gè)單鏈表L和L1,各結(jié)點(diǎn)結(jié)構(gòu)如下：試畫出該鏈表的

12、結(jié)構(gòu)圖，并編寫算法，判斷單鏈表L1是否與單鏈表L相同，相同返回 1,不同返回0。五、簡答題1.【嚴(yán)題集2. 3】試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表 比鏈表好？答：順序存儲時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用 存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：存儲密度大（ = 1?）,存儲空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯r(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值， 另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn):存儲密度小«1）,存儲空間利用率低。順序表適宜于做査找這樣

13、的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2 .【嚴(yán)題集2.1】描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié) 點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？首元結(jié)點(diǎn)答：苴元結(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素6的結(jié)點(diǎn)。為了操作方便，通常在鏈 表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素， 其作用是為了對鏈表進(jìn)行操作時(shí)，可以對空表.非空表的情況以及對首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。 頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn), 則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表