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

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

3、。（1in+1）AO（0） BO（1） CO（n） DO（n2）10線性表中各鏈接點(diǎn)之間的地址_C_。A必須連續(xù)B部分地址必須連續(xù)C不一定連續(xù)D連續(xù)與否無(wú)所謂11在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組表示中，算法的時(shí)間復(fù)雜度是O（1）的操作是_A_。A訪問第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in）B在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1in）C刪除第i個(gè)結(jié)點(diǎn)（1in）D以上都不對(duì)12單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了_C_。A使單鏈表至少有一個(gè)結(jié)點(diǎn)B標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn)D說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)13對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條

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

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

6、作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用_D_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表22對(duì)于一個(gè)線性表既要求能夠進(jìn)行較快的插入和刪除，又要求存儲(chǔ)結(jié)構(gòu)能夠反映數(shù)據(jù)之間的邏輯關(guān)系，則應(yīng)用_C_。A順序方式存儲(chǔ) B散列方式存儲(chǔ) C鏈接方式存儲(chǔ) D以上方式均可23若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用_A_存儲(chǔ)方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表24若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)和后繼元素的值，為節(jié)省時(shí)間應(yīng)采用的存儲(chǔ)方式為_D_。A單鏈表 B雙向鏈表

7、 C單循環(huán)鏈表 D順序表25下面哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？_C_A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大D刪除運(yùn)算方便26下面關(guān)于線性表的敘述中，錯(cuò)誤的是_B_。A.線性表采用順序存儲(chǔ)，必須占用一批連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除的操作C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作27在非空線性鏈表中由p所指的鏈接點(diǎn)后面插入一個(gè)由q所指的鏈接點(diǎn)的過(guò)程是依次執(zhí)行動(dòng)作_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在非空雙向循環(huán)鏈表中由q所指的鏈接點(diǎn)前面插入一個(gè)由p指的鏈接點(diǎn)的過(guò)程是依次執(zhí)行語(yǔ)句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在非空雙向循環(huán)鏈表中由q所指的鏈接點(diǎn)后面插入一個(gè)由p指的鏈接點(diǎn)的動(dòng)作依次為_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在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針_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單鏈表的存儲(chǔ)密度為_C_。A大于1 B等于5 C小于1 D不能確定二判斷題1. 線性表的邏輯順序與存儲(chǔ)順序總是一致的。 （ ）2. 線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。 （ ）3. 線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。 （ ）4. 不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X 的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。 （ ）5. 線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。 （ ）6. 非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。（ ）7. 用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。 （

12、 ）8. 線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。（ ）9. 順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 （ ）10. 順序表中所有結(jié)點(diǎn)的類型必須相同。 （ ）11. 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。 （ ）12. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。 （ ）13. 鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序。 （ ）14. 單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。 （ ）15. 符號(hào)p->next 出現(xiàn)在表達(dá)式中表示p 所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。（ ）16.

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

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

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

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

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

18、點(diǎn)的地址；在執(zhí)行A-B運(yùn)算之前，用于表示結(jié)果集合的鏈表首先增加一個(gè)附加的表頭結(jié)點(diǎn)，以便新結(jié)點(diǎn)的添加，當(dāng)A-B運(yùn)算執(zhí)行完畢后，再刪除并釋放表示結(jié)果集合的鏈表的表頭結(jié)點(diǎn)。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.設(shè)一單向鏈表的頭指針為head，鏈表的記錄中包含著整數(shù)類型的key域，試設(shè)計(jì)算法，將此鏈表的記錄按照key遞增的次序進(jìn)行就地排序。15.設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于等于零的結(jié)點(diǎn)（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點(diǎn)）。16.將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，使得A表中含有原表中序號(hào)為奇數(shù)的元素，而B表中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序不變。 1）寫出其類型定義。 2）寫出算法。17.兩個(gè)整數(shù)序列A=a1，a2，a3，am和B=b1，b2，b3，bn已經(jīng)存入兩個(gè)單鏈表中，設(shè)計(jì)一個(gè)算法，判斷序列B是