第二章 線性表 自測題 自測題答案

1、 第二章-線性表-自測題-自測題 答案 班級 第2章 自測卷答案 姓名 五題號 一 二 三 四 六 七 總分100 10 7 10 40 10 題分 13 10 得分 分）1分，共13一、填空（每空 表中一 2.2】在順序表中插入或刪除一個(gè)元素，需要平均移動1. 【嚴(yán)題集 有關(guān)。 表長和該元素在表中的位置 半元素，具體移動的元素個(gè)數(shù)與 2. 線性表中結(jié)點(diǎn)的集合有 的，結(jié)點(diǎn)間的關(guān)系一對一的。 3. 向一個(gè)長度為n的向量的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí)，需向后移n-i+1個(gè)元素。 4. 向一個(gè)長度為n的向量中刪除第i個(gè)元素(1in)時(shí)，需向前移n-i 個(gè)元素。 5. 在順序表中訪問任意

2、一結(jié)點(diǎn)的時(shí)間復(fù)雜度均O(1 ，因此，順序表也稱為 隨機(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ǎng)h除已知結(jié)點(diǎn)*p，需找到它前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n）。 二、判斷正誤（在正確的說法后面打勾，反之打叉）（每小題1分，共10分） （ ）1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指

3、針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。 （ ）2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。 錯(cuò)，鏈表的存儲結(jié)構(gòu)特點(diǎn)是無序，而鏈表的示意圖有序。 （ ）3. 鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會自動地將后續(xù)的各個(gè)單元向前移動。 錯(cuò)，鏈表的結(jié)點(diǎn)不會移動，只是指針內(nèi)容改變。 （ ）4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。 （ ）5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 2 錯(cuò)，正好說反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“

4、順藤摸瓜” 6. 順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。 ）（那是鏈前一半正確，但后一半說法錯(cuò)誤，錯(cuò)，刪除運(yùn)算式存儲的優(yōu)點(diǎn)。順序存儲方式插入、插入和刪n的順序表中，效率較低，在表長為平均需移動表長一半個(gè)數(shù)的除一個(gè)數(shù)據(jù)元素， 數(shù)據(jù)元素。 7. 線性表在物理存儲空間中也一定是連續(xù)的。 ）（ 錯(cuò)，線性表有兩種存儲方式，順序存儲和鏈?zhǔn)酱鎯?。后者不要求連續(xù)存放。線性表在順序存儲時(shí)，邏輯上相鄰的元素未必在存儲的物理位）8. （ 置次序上相鄰。在順序存儲時(shí)，錯(cuò)誤。線性表有兩種存儲方式，邏輯上相鄰的元素在存儲的物理位置次序上 也相鄰。 9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。 ）（ 錯(cuò)誤。順

5、序存儲方式不僅能用于存儲線性結(jié)例如完全二還可以用來存放非線性結(jié)構(gòu)，構(gòu)，但其最佳存儲方式是叉樹是屬于非線性結(jié)構(gòu)， （后一節(jié)介紹）順序存儲方式。 線性表的邏輯順序與存儲順序總是一致的。 ）10. （ 。鏈?zhǔn)酱鎯蜔o需一致。錯(cuò)，理由同7 分）三、單項(xiàng)選擇題（每小題1分，共10數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且1 ）C（ 是連續(xù)的，稱之為： ）鏈?zhǔn)酱鎯Y(jié)構(gòu) （DB）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu)（A）存儲結(jié)構(gòu) （ ，100，每個(gè)元素的長度為2） B 2.一個(gè)向量第一個(gè)元素的存儲地址是（ 則第5個(gè)元素的地址是 120 ）（D （C）100 （A）110 （B）108 的操作是：個(gè)結(jié)點(diǎn)的

6、順序表中，算法的時(shí)間復(fù)雜度是O(1)）3. 在n（ A 2i個(gè)結(jié)點(diǎn)的直接前驅(qū)（in）和求第A） 訪問第i個(gè)結(jié)點(diǎn)（1（ ） in ）in） 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1（B ）in刪除第i個(gè)結(jié)點(diǎn)（1）（C 個(gè)結(jié)點(diǎn)從小到大排序?qū)（D） 個(gè)元素的順序表中插入一個(gè)新元素并保持原來順向一個(gè)有127B ）4. （ 個(gè)元素序不變，平均要移動 （A）8 （B）63.5 （C）63 （D）7 （ A ）5. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間： (A)分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 (B)只有一部分，存放結(jié)點(diǎn)值 3 C）只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針（ D）分兩部分，一部分

7、存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)（ 存儲結(jié)構(gòu)存儲的線性表； （ B ）6. 鏈表是一種采用 （D）網(wǎng)狀）星式 （B）鏈?zhǔn)?（C A（）順序 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地 ）7. （ D : 址 （B）部分地址必須是連續(xù)的（A）必須是連續(xù)的 D）連續(xù)或不連續(xù)都可以（C）一定是不連續(xù)的 （ 線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。8（ B ） （）需經(jīng)常修改中的結(jié)點(diǎn)值 （）需不斷對進(jìn)行刪除插入 （）中含有大量的結(jié)點(diǎn) （）中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 代表地址，則，4個(gè)結(jié)點(diǎn)，整數(shù)P，33 （ B ）10設(shè)a1、a2、a3為0 如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱34 0 ? ? 0 P4a3Aa

8、0 （）循環(huán)鏈表 （）單鏈表 （）雙向循環(huán)鏈表 （）雙向鏈表 四、簡答題（每小題5分，共10分） 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)：存儲密度?。?），存儲空間利用率低。 順序表適宜于做查找這樣的

9、靜態(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)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素a的結(jié)點(diǎn)。為了1操作方便，通常在鏈表的首元結(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)

10、）的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，4 則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針是否設(shè)置頭結(jié)點(diǎn)，這三個(gè)概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。為空。 是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。 頭結(jié)點(diǎn) ?link data head 首元結(jié)點(diǎn)頭指針 簡而言之， 頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo) 志和表長等信息。 a的結(jié)點(diǎn)。首元素結(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素1 線性表具有兩種存儲方式，即順序方式和鏈接方式?，F(xiàn)有一五、【軟考題】，若它以鏈接方式存儲在05，31，個(gè)具有五個(gè)元素的

11、線性表L=23，17，4722個(gè)字節(jié)）和指針（占119下列100號地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（個(gè)字節(jié)）組成，如下所示ZY4717X23V31U05 120 100 的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？ZY，X其中指針， 分）末結(jié)點(diǎn)的起始地址為多少？（10 112 末址108 = 首址 0 答：X= 116 Y= Z= 100 = 10分）六、閱讀分析題（】指出以下算法中的錯(cuò)誤和低效（即費(fèi)時(shí)）之處，并將它改【嚴(yán)題集2.10 寫為一個(gè)既正確又高效的算法Status DeleteK(SqList&a, int i, int k)個(gè)元個(gè)元素起中刪除/本過程從順序存儲結(jié)構(gòu)的線性參數(shù) i1 |

12、 k a.lengtif ) return INFEASIBLE; /合else; count + ) for(count = 1;count =i+1; j-) a.elemj-1 = a.elemj a.length - -; return OK; 注：上題涉及的類型定義如下： # define LIST INIT SIZE 100 # define LISTINCREMENT 10 typedef struct Elem Type *elem; /存儲空間基址 當(dāng)前長度Int length; / 當(dāng)前分配的存儲容量Int listsize; / SqList; 5 答：錯(cuò)誤有三處：）刪i

13、=1，若從第一位置（參數(shù)不合法的判別條件不完整。例如表長為10 要求合理但會被判為非法。k=10）,除10個(gè)元素（ a.length-i+1)k合法的入口參數(shù)條件為(0ia.length) (0 return INFEASIBLE )應(yīng)將if ( i1 | k a.length return INFEASIBLEa.length-i+1)(0=i+1; j-) a.elemj-1 = a.elemj; 應(yīng)將for) a.elemj-1 = a.elemj; j=i+1; j=a.length-count+1; j+ ( 改為for ; count+)for(count=1; countk 應(yīng)將

14、; count+) count=k改為for(count=1; 改寫算法為： Status DeleteK(SqList &a,int i,int k) k個(gè)元素a中第i個(gè)元素起的/刪除線性表個(gè)元素的數(shù)個(gè)元素起的第k(i-1),從第i第/i個(gè)元素在數(shù)組中的下標(biāo)是個(gè)元素來講都得往(a.length-i-k+1) aa到的組下標(biāo)為(i+k-2)，而對于從n-1i+k-1 前移動。 if(i1|ka.length-i+1) return INFEASIBLE; 注意循環(huán)結(jié)束的條件 /for(count=1; count=a.length-k-i+1;count+) a.elemi+count-2=a

15、.elemi+count+k-2; a.length-=k; return OK; /DeleteK 40分）七、編程題（每題10分，共寫出在順序存儲結(jié)構(gòu)下將線性表1月省統(tǒng)考題】【徐士良題集，2002年1. 逆轉(zhuǎn)的算法，要求使用最少的附加空間。void invsl(int &a,int &b) int t; t=a;a=b;b=t; void reverse(SqList &A) 順序表的就地逆置/ for(i=0,j=A.length-1;inext;q=p-next; s=q-next;p-next=NULL; 6 while(s-next) q-next=p;p=q; q=s;s=s-next; 的元素逐個(gè)插入表頭把L/ q-next=p;s-next=q;L-next=s; /LinkList_reverse 結(jié)點(diǎn)既不是首元結(jié)是無表頭結(jié)點(diǎn)的單鏈表，且P已知【嚴(yán)題集2.6】L2. S結(jié)點(diǎn)的核心語句序列。后)插入前點(diǎn)，也不是尾元結(jié)點(diǎn)，請寫出在P結(jié)點(diǎn)答：此題答案不唯一，但若從已給定序列中挑選，則限制頗多 (7) Q=P;已結(jié)點(diǎn)，則不必“順藤摸瓜，直(11) P=L;接鏈接即可 (8) while(P-nex