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

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

2、結(jié)點的時間復(fù)雜度均為0(1)_,因此，順序表也稱為一隨機存取一的數(shù)據(jù)結(jié)構(gòu)。6 .【嚴(yán)題集2.2】順序表中邏輯上相鄰的元素的物理位置一必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定 相鄰。7 .【嚴(yán)題集2.2】在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由_具 直接前驅(qū)結(jié)點的鏈域的值一指示。8 .在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為0 (n)。二、判斷正誤( 在正確的說法后面打勾，反之打叉)( 每小題 1 分，共 10 分 ) (X ) 1.鏈表的每個結(jié)點中都恰好包含一個指針。答：錯誤。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表

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

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

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

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

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

8、。，3, 4代表地址，則 如下的鏈?zhǔn)酱鎯Y(jié) 構(gòu)稱為Po34Po | al | 3| a2 | 4| A3 | 0（A）循環(huán)鏈表（E）單鏈表（C）雙向循環(huán)鏈表（D）雙向鏈表四、簡答題（每小題5分，共10分） 1.【嚴(yán)題集2.3試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么 情況下用順序 表比鏈表好？ 答：順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。 優(yōu)點：存儲密度大（二1?）,存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針。

9、優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小 （<1）,存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2 .【嚴(yán)題集2.1】描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。在單鏈表中設(shè)置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。為了操作方便，通常在鏈表的首元結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進(jìn)行操

10、作時，可以對空表、非空表的情況以及對首元結(jié)點進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。若鏈表中附設(shè)頭結(jié)點，為空。這三個則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針,是不同的存儲結(jié)構(gòu)表示同一概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點 邏輯結(jié)構(gòu)的問題。頭結(jié)點headdatalink頭指針首元結(jié)點頭結(jié)點是在鏈簡而言之，頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針;志和表長等信息。ai的結(jié)點。表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo) 首元素結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素五、【軟考題】線性表具有兩種存

11、儲方式，即順序方式和鏈接方式?，F(xiàn)有一個具有五個元素的線性表L=23, 17, 47, 05, 31,若它以鏈接方式存儲在下列100? 119號地址空間中，每個結(jié)點由數(shù)據(jù)（占 2個字節(jié)）和指針（占 2個字節(jié)）組成，如下所示：如下所示：05 | U | 17 X | 23 | V | 31 I Y 47 |Z100100 120其中指針X, 丫，Z的值分別為多少？該線性表的首結(jié)點起始地址為多少？ 末結(jié)點的起始地址為多少？（ 10分）答：X= _11 匚 丫 = _0_ Z=_10L 首址=_108末址=_112_六、閱讀分析題（10分）【嚴(yán)題集2.10】指由以下算法中的錯誤和低效（即費時）之處，并

12、將它改寫為一個既正確又高效的算法。Status DeleteK(SqList &a, int i, int k)本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個元素起的k個元素if ( i<1 | k<0 | i+k> a.le ngth) return INFEASIBLE; 參數(shù)不合法elsefor(count = 1; count <k ; count + ) 刪除一個元素for ( j = a.le ngth; j>=i+1; j-) a.elemj-1 = a.elemj; a.len gth -;return OK;注：上題涉及的類型定義如下：# d

13、efine LIST INIT SIZE 100存儲空間基址當(dāng)前長度當(dāng)前分配的存儲容量# defi ne LISTINCREMENT 10 typedef struct Elem Type *elem; /Int len gth; /Int listsize; /SqList;答：錯誤有三處： 參數(shù)不合法的判別條件不完整。例如表長為10,若從第一位置(i=1 )刪除10個元素(k=10)要求合理但會被判為非法。合法的入口參數(shù)條件為(0<i < a.lengthF (0 < k < a.length-i+1)應(yīng)將 if ( i<1 | k<0 | i+k>

14、; a.length ) return INFEASIBLE改為：if (! (0<i < a.lengthF (0 < k< a.length-i+1) return INFEASIBLE 第三個FOR語句中，元素前移的次序錯誤。應(yīng)將 for ( j = a.length; j>=i+1; j-) a.elemj-1 = a.elemj;改為 for ( j=i+1; j<=aength-count+1; j+ ) a.elemj-1 = a.elemj; 應(yīng)將 for(count=1; count<k; count+)改為 for(count=1;

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

16、 un t-2=a.elemi+co un t+k-2;a.len gth-=k;return OK;DeleteK七、編程題(每題10分，共40分)1 .【徐士良題集，2002年1月省統(tǒng)考題】寫生在順序存儲結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法,要求使用最少的附加空間。void in vsl(i nt &a,int &b) int t;t=a;a=b;b=t;void reverse(SqList &A) 順序表的就地逆置for(i=O,j=A.le ngth-1;i<j;i+,j-)inv sl(A.elemi,A.elemj);/reverse void Li nkLis

17、t reverse(Li nklist &L) 鏈表的就地逆置；為簡化算法)假設(shè)表長大于2p=L->n ext;q=p->n ext;s=q->n ext;p->n ext=NULL;while(s->n ext) q->n ext=p;p=q; q=s;s=s->n ext;把L的元素逐個插入表頭q->n ext=p;s->n ext=q;L->n ext=s;Li nkList_reverse2 .【嚴(yán)題集2.6】已知L是無表頭結(jié)點的單鏈表，且 P結(jié)點既不是首元結(jié) 點，也不是尾 元結(jié)點，請寫生在 P結(jié)點前(后)插入S結(jié)點的核心語句序列。答：此題答案不唯一，但若從已給定序列中挑選，則限制頗多。 Q=P;(11) P=L;(8) while(P-> next!=Q)P=P-> next;(4) S-> next=P-> next;(1) P-> next=S;已知P結(jié)點,則不必“順藤摸瓜 接鏈接即可白I(4) S->next=P->ne