1、 第二章 線性表一、選擇題1線性表是具有n個_C_的有限序列（n>0）。A表元素 B字符 C數據元素 D數據項2一個順序表所占用的存儲空間大小與_B_無關。A表的長度B元素的存放順序C元素的類型D元素中各字段的類型3線性表的順序存儲結構是一種_A_。A隨機存取的存儲方式B順序存取的存儲方式C索引存取的存儲方式DHash存取的存儲方式4. 若線性表采用順序存儲結構，每個元素占用 4 個存儲單元，第一個元素的存儲地址為 100,則第 12 個元素的存儲地址是_B_。A112 B.144 C.148 D.4125. 線性表是_A_。A一個有限序列，可以為空 B一個有限序列，不能為空C一個無限序

2、列，可以為空 D一個無限序列，不能為空6對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為_C_。AO（n）O（n） BO（n）O（1） CO（1）O（n） DO（1）O(1)7若長度為n的非空線性表采用順序存儲結構，刪除表的第i個數據元素，首先需要移動表中_A_中數據元素。An-i Bn+i Cn-i+1 Dn-i-18對順序存儲的線性表，設其長度為n，在任何位置插入或刪除操作都是等概率的。刪除一個元素時平均要移動表中的_C_個元素。A.n/2 B.（n+1）/2 C.（n-1）/2 D.n9若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為_C_

3、。（1in+1）AO（0） BO（1） CO（n） DO（n2）10線性表中各鏈接點之間的地址_C_。A必須連續B部分地址必須連續C不一定連續D連續與否無所謂11在n個結點的線性表的數組表示中，算法的時間復雜度是O（1）的操作是_A_。A訪問第i個結點后插入一個新結點（1in）和求第i個結點的直接前驅（2in）B在第i個結點后插入一個新結點（1in）C刪除第i個結點（1in）D以上都不對12單鏈表中，增加一個頭結點的目的是為了_C_。A使單鏈表至少有一個結點B標識表結點中首結點的位置C方便運算的實現D說明單鏈表是線性表的鏈式存儲13對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條

4、件是_B_。Ahead=NULLBhead->next=NULLChead->next=headDhead!=NULL14將長度為n的單鏈表鏈接在長度為m的單鏈表后面的算法的時間復雜度采用大O形式表示應該是_C_。AO（1） BO（n） CO（m） DO（n+m）15靜態鏈表中指針表示的是_C_。A下一個元素的地址B內存儲器的地址C下一個元素在數組中的位置D左鏈或右鏈指向的元素的地址16非空的循環單鏈表head的尾結點p滿足_A_。AP->link=head BP->link=NULL CP=NULL DP=head17某線性表用帶頭結點的循環單鏈表存儲，頭指針為hea

5、d，當head->next->next=head成立時，線性表的長度是_B_。A0 B1 C2 D318在什么情況下，應使用鏈式結構存儲線性表L?_B_A需經常修改L中的結點值B需不斷對L進行刪除插入C需要經常查詢L中的結點值DL中結點結構復雜19與單鏈表相比較，雙向鏈表的優點之一是_D_。A可以省略頭結點指針B可以隨機訪問C插入、刪除操作更簡單D順序訪問相鄰結點更靈活20某線性表常發生的操作為刪除第一個數據元素和最后一個元素后添加新元素，采用_D_作為存儲結構，能使其存儲效率和時間效率最高。A單鏈表B僅用頭指針的循環單鏈表C雙向循環鏈表D僅用尾指針的循環單鏈表21若某表最常用的操

6、作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用_D_存儲方式最節省運算時間。A單鏈表 B雙鏈表 C單循環鏈表 D帶頭結點的雙循環鏈表22對于一個線性表既要求能夠進行較快的插入和刪除，又要求存儲結構能夠反映數據之間的邏輯關系，則應用_C_。A順序方式存儲 B散列方式存儲 C鏈接方式存儲 D以上方式均可23若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用_A_存儲方式最節省時間。A順序表 B雙鏈表 C帶頭結點的雙循環鏈表 D單循環鏈表24若線性表最常用的操作是存取第i個元素及其前驅和后繼元素的值，為節省時間應采用的存儲方式為_D_。A單鏈表 B雙向鏈表

7、 C單循環鏈表 D順序表25下面哪一條是順序存儲結構的優點？_C_A插入運算方便B可方便地用于各種邏輯結構的存儲表示C存儲密度大D刪除運算方便26下面關于線性表的敘述中，錯誤的是_B_。A.線性表采用順序存儲，必須占用一批連續的存儲單元B.線性表采用順序存儲，便于進行插入和刪除的操作C.線性表采用鏈接存儲，不必占用一片連續的存儲單元D.線性表采用鏈接存儲，便于插入和刪除操作27在非空線性鏈表中由p所指的鏈接點后面插入一個由q所指的鏈接點的過程是依次執行動作_B_。Aq->link=p；p->link=q；Bq-link=p->link；p->link=q；Cq->

8、link=p->link；p=q；Dp->link=q；q->link=p；26在非空雙向循環鏈表中由q所指的鏈接點前面插入一個由p指的鏈接點的過程是依次執行語句p->rlink=q；p->llink=q->llink;q->llink=p; _D_。Aq->rlink->llink=p;Bq->llink->rlink=p;Cp->rlink->llink=p;Dp->llink->rlink=p;29在非空雙向循環鏈表中由q所指的鏈接點后面插入一個由p指的鏈接點的動作依次為_D_。Ap->lli

9、nk=q ; p->rlink=q->rlink ; q->rlink=p ; q->rlink->llink=p；Bp->rlink=q->rlink ; p->llink=q ; q->rlink ; q->rlink->llink=p；Cp->llink=q ; p->rlink=q->rlink ; q->rlink=p ; p->llink->rlink=p；Dp->llink=q ; p->rlink=q->rlink ; q->rlink=p ; p-&g

10、t;rlink->llink=p；30在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針_A_。Ap->llink->rlink=p->rlink ; p->rlink->llink=p->llink ;Bp->llink=p->llink->llink ; p->llink->rlink=p ;Cp->rlink->llink=p ; p->rlink=p->rlink->rlink ;Dp->rlink=p->llink->llink ; p->llink=p-&g

11、t;rlink->rlink ;31單鏈表的存儲密度為_C_。A大于1 B等于5 C小于1 D不能確定二判斷題1. 線性表的邏輯順序與存儲順序總是一致的。 （ ）2. 線性表的順序存儲結構比鏈式存儲結構更好。 （ ）3. 線性表中的所有元素都有一個前驅元素和后繼元素。 （ ）4. 不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X 的結點的時間復雜度均為O(n)。 （ ）5. 線性的數據結構可以順序存儲，也可以鏈接存儲。非線性的數據結構只能鏈接存儲。 （ ）6. 非空線性表中任意一個數據元素都有且僅有一個直接后繼元素。（ ）7. 用一組地址連續的存儲單元存放的元素一定構成線性表。 （

12、 ）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（ ）9. 順序表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。 （ ）10. 順序表中所有結點的類型必須相同。 （ ）11. 對鏈表進行插入和刪除操作時不必移動鏈表中結點。 （ ）12. 非空的雙向循環鏈表中任何結點的前驅指針均不為空。 （ ）13. 鏈式存儲在插入和刪除時需要保持物理存儲空間的順序分配，不需要保持數據元素之間的邏輯順序。 （ ）14. 單鏈表從任何一個結點出發，都能訪問到所有結點。 （ ）15. 符號p->next 出現在表達式中表示p 所指的那個結點的內容。（ ）16.

13、 帶表頭結點的雙向循環鏈表判空的條件是： first->rlink = first（first 為表頭指針）。 （ ）三、綜合應用題1.利用順序表的操作，實現以下函數： 1）從順序表中刪除具有最小值的元素并由函數返回被刪除元素的值。空出的位置由最后一個元素填補，若順序表為空則顯示出錯信息并退出運行。 2）從順序表中刪除第i個元素并由函數返回被刪除元素的值，如果i不合理或順序表為空則顯示出錯信息并退出運行。 3）向順序表中第i個位置插入一個新元素x。如果i不合理則顯示出錯信息并退出運行 4）從順序表中刪除具有給定值x的所有元素。 5）從順序表中刪除其值在給定值s與t之間（要求s小于t）的所

14、有元素。如果s或t不合理或者順序表為空，則顯示錯誤信息并退出。 6）從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素，如果s或t不合理或順序表為空，則顯示錯誤信息并退出。 7）將兩個有序順序表合并成一個新的有序順序表并由函數返回結果順序表 8）從有序順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同。2.請設計算法將不帶頭結點的單鏈表就地逆置。3.有一個單鏈表L（至少有1個結點），其頭結點指針為head，編寫一個過程將L逆置，即最后一個結點變成第一個結點，原來倒數第二個結點變成第二個結點，如此等等。4.設有一個由正整數組成的無序（向后）單鏈表，編寫完成下列功能的算法：

15、找出最小值結點，且打印該數值。若該數值是奇數，則將其與直接后繼結點的數值交換。若該數值是偶數，則將其直接后繼結點刪除。5.給定（已生成）一個帶表頭結點的單鏈表，設head為頭指針，結點的結構為（data，next），data為整型元素，next為指針，試寫出算法：按遞增次序輸出單鏈表中各結點的數據元素，并釋放結點所占的存儲空間（要求：不允許使用數組作輔助空間）。6.假設有兩個按元素值遞增次序排列的線性表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。7.在一個遞增有序的線性表中，有數值相同的元素存在。若存儲方式為單鏈表，設計算法去掉數值相同的元素，使表中不再有重復的元素。例如：（7,10,

16、10,21,30,42,42,42,51,70）將變為（7,10,21,30,42,51,70）。8.試編寫在帶頭結點的單鏈表中刪除一個最小值結點的高效算法：void delete(Linklist &L)。9.已知兩個單鏈表A和B，其頭指針分別為heada和headb，編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。10.已知非空線性表由list指出，鏈結點的構造為（data，link）。請寫一算法，將鏈表中數據域值最小的那個鏈結點移到鏈表的最前面（要求：不得額外申請新的鏈結點）。11.帶頭結點且頭指針為ha和hb的兩線性表A

17、和B分別表示兩個集合，兩表中的元素皆為遞增有序。請寫一算法求A和B的并集A U B，要求該并集中的元素仍保持遞增有序，且要利用A和B的原有結點空間。12.已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。編寫一函數程序，求A與B的交集，并存放于A鏈表中。13.設計一個求兩個集合A和B之差C=A-B的程序，即當且僅當e是A的一個元素，但不是B中的一個元素時，e才是C中的一個元素。集合用有序鏈表實現，初始時，A、B集合中的元素按遞增排列，C為空；操作完成后，A、B保持不變，C中元素按遞增排列。下面的函數append（last，e）是把值為e的新結點鏈接在由指針last指向的結點的后面，并返回新結

18、點的地址；在執行A-B運算之前，用于表示結果集合的鏈表首先增加一個附加的表頭結點，以便新結點的添加，當A-B運算執行完畢后，再刪除并釋放表示結果集合的鏈表的表頭結點。typedef struct nodeint element;struct node *link;NODE;NODE *A,*B,*C;NODE *append (NODE *last,int e) last->link=(NODE*)malloc(sizeof(NODE); last->link->element=e; return (last->link);NODE *difference (NODE

19、*A,NODE *B)14.設一單向鏈表的頭指針為head，鏈表的記錄中包含著整數類型的key域，試設計算法，將此鏈表的記錄按照key遞增的次序進行就地排序。15.設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于等于零的結點（鏈表A的元素類型為整型，要求B、C表利用A表的結點）。16.將一個帶頭結點的單鏈表A分解為兩個帶頭結點的單鏈表A和B，使得A表中含有原表中序號為奇數的元素，而B表中含有原表中序號為偶數的元素，且保持其相對順序不變。 1）寫出其類型定義。 2）寫出算法。17.兩個整數序列A=a1，a2，a3，am和B=b1，b2，b3，bn已經存入兩個單鏈表中，設計一個算法，判斷序列B是