第二章-線性表-答案

1、數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第二章 線性表一、選擇題1、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新的元素算法的時(shí)間復(fù)雜度為 C 。A. O(log2n)B. O(1)C. O(n)D. O(n2)2、以下關(guān)于線性表的說法中，不正確的是 C 。A. 線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、結(jié)構(gòu)等不同類型B. 線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的C. 線性表中的每一個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前驅(qū)和直接后繼D. 存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前驅(qū)和直接后繼3、在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為 B 。A. O(1)B. O(n)C. O(n2)D. O(log2n

2、)4、等概率情況下，在有n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)操作，需平均移動的結(jié)點(diǎn)數(shù)目為 C 。提示：插入的位置有n+1個(gè)，移動總數(shù)為：1+2+3+nA. nB. (n-1)/2C. n/2D. (n+1)/25、在一個(gè)長度為n的順序存儲的線性表中查找值為x的元素時(shí)，平均查找長度(及x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等)為 C 。A. nB. n/2C. (n+1)/2D. (n-1)/26、在順序表中，只要知道 D ，就可以求出任一結(jié)點(diǎn)的存儲地址。A. 基地址B. 結(jié)點(diǎn)大小C. 向量大小D. 基地址和結(jié)點(diǎn)大小7、將兩個(gè)各有n個(gè)元素的有序表歸并為一個(gè)有序表，其最少的比較次數(shù)是 A 。A

3、. nB. 2n-1C. 2nD. n-18、線性表采用鏈表存儲時(shí)其存儲地址要求 D 。A. 必須是連續(xù)的B. 部分地址必須是連續(xù)的C. 必須是不連續(xù)的D. 連續(xù)的和不連續(xù)的都可以9、下面關(guān)于線性表的描述中，錯(cuò)誤的是 B 。A. 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B. 線性表采用順序存儲，便于進(jìn)行插入和刪除操作C. 線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D. 線性表采用鏈?zhǔn)酱鎯?，便于插入和刪除操作10、向具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是 B A. O(1)B. O(n)C. O(n2)D. O(log2n)11、在一個(gè)帶頭結(jié)點(diǎn)的單鏈表HL中，

4、若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行的語句是 D 。A. HL=p; p->next=HL;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. p->next=HL->next; HL->next=p;12、在一個(gè)單鏈表HL中，若要刪除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的語句是 C 。A. p=q->next; p->next=q->next;B. p=q->next; q->next=p;C. p=q->next; q->next=p->next;D. q->

5、next=q->next->next; q->next=q;13、設(shè)有編號為1, 2, 3, 4的4輛列車，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺，下列不可能的出棧順序?yàn)?D 。A. 1234B. 1243C. 1324D. 142314、4個(gè)元素按A, B, C, D順序進(jìn)入S棧，執(zhí)行兩次Pop(S, x)運(yùn)算后，棧頂元素的值是 B 。A. AB. BC. CD. D15、從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列 A 命令。A. x=top; top=top->next;B. top=top->next; x=top->data;C

6、. x=top->data;D. x=top->data; top=top->next;16、向順序棧中輸入元素時(shí) B 。A. 先存入元素，后移動棧頂指針B. 先移動棧頂指針，后存入元素C. 誰先誰后無關(guān)緊要D. 同時(shí)進(jìn)行17、設(shè)有一個(gè)順序棧，元素A, B, C, D, E, F依次進(jìn)棧，如果6個(gè)元素出棧的順序是B, D, C, F, E, A，則棧的容量至少為 A 。A. 3B. 4C. 56. 618、設(shè)已將元素A, B, C依次入棧，元素D正等待進(jìn)棧。那么下列4個(gè)序列中不可能出現(xiàn)的出棧順序?yàn)?A 。A. CADBB. CBDAC. CDBAD. DCBA19、棧和隊(duì)列的

7、相同之處是 C 。 A.元素的進(jìn)出滿足先進(jìn)后出 B.元素的進(jìn)出滿足后進(jìn)先出 C.只允許在端點(diǎn)進(jìn)行插入和刪除操作 D.無共同點(diǎn) 20、設(shè)棧S 和隊(duì)列Q 的初始狀態(tài)為空,元素e1，e2，e3，e4，e5 和e6 依次通過棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6 個(gè)元素出隊(duì)的序列是e2，e4，e3，e6，e5，e1，則棧S 的容量至少應(yīng)該是 C 。 A. 6 B. 4 C. 3 D. 2 21、隊(duì)列通常采用的兩種存儲結(jié)構(gòu)是 A 。A. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) B.散列方式和索引方式C. 鏈表存儲結(jié)構(gòu)和線性存儲結(jié)構(gòu) D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)22、循環(huán)隊(duì)列SQ隊(duì)滿的條件是 D 。A. SQ-&g

8、t;rear=SQ->frontB. (SQ->rear+1)%MAXLEN=SQ->frontC. SQ->rear+2 = SQL->frontD. (SQ->rear+2)%MAXLEN=SQL->front23、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為 B 。A. 5和1B. 4和2C. 2和4D. 1和524、鏈棧與順序棧相比，有一個(gè)較為明顯的優(yōu)點(diǎn)是 A 。A. 通常不會出現(xiàn)滿棧的情況B. 通常不會出現(xiàn)?？盏那闆rC. 插入操作更加

9、方便D. 刪除操作更加方便25、設(shè)用一個(gè)大小為M=60的順序表AM表示一個(gè)循環(huán)隊(duì)列，如果當(dāng)前的尾指針rear=32，頭指針front=15，則當(dāng)前循環(huán)隊(duì)列的元素的個(gè)數(shù)為 C 。A. 42B. 17C. 18D. 4126、串是一種特殊的線性表，其特殊性體現(xiàn)在 B 。A. 可以順序存儲B. 數(shù)據(jù)元素是一個(gè)字符C. 可以鏈?zhǔn)酱鎯. 數(shù)據(jù)元素可以是多個(gè)字符27、設(shè)主串的長度為n，模式串的長度為m，則串匹配的KMP算法的時(shí)間復(fù)雜度為 C 。A. O(m)B. O(n)C. O(m+n)D. O(m×n)28、已知串S=“abab”，其Next數(shù)組值為 C 。A. 0123B. 0121C.

10、 0112D. 012229、若字符串“ABCDEFG”采用不帶表頭的鏈?zhǔn)酱鎯Γ總€(gè)結(jié)點(diǎn)保存一個(gè)字符。假設(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用兩個(gè)字節(jié)，則該字符串的存儲密度為 D 。A. 20%B. 40%C. 50%D. 33.3%30、在雙向鏈表中，在指針p所指的結(jié)點(diǎn)前插入一個(gè)指針q所指向的結(jié)點(diǎn)，操作是 C 。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->

11、;Prior;C. q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q;D. q->Prior=p->Prior; q->Next=q;p->Prior=q; p->Next=q;31、已知循環(huán)隊(duì)列存儲在一維數(shù)組A0n-1中，且隊(duì)列非空時(shí)front和rear分別指向?qū)︻^元素和隊(duì)尾元素，且要求第一個(gè)進(jìn)入隊(duì)列的元素存儲在A0處，則初始時(shí)front和rear的值分別是 B 。A. 0, 0B. 0, n-1C. n-1, 0D. n-1, n-132、某隊(duì)列允許在兩端進(jìn)

12、行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作（稱為輸出受限的雙端隊(duì)列），若a, b, c, d, e元素依次進(jìn)隊(duì)，則不可能得到的順序是 C 。A. bacdeB. dbaceC. dbcaeD. ecbad33、在雙向鏈表中間插入一個(gè)結(jié)點(diǎn)時(shí)，需要修改 D 個(gè)指針域。A. 1B. 2C. 3D. 434、在按行優(yōu)先順序存儲的三元組表中，下述陳述錯(cuò)誤的是 D 。A. 同一行的非零元素，是按列號遞增次序存儲的B. 同一列的非零元素，是按行號遞增次序存儲的C. 三元組表中三元組行號是非遞減的D. 三元組表中三元組列號是非遞減的35、在稀疏矩陣的三元組表示法中，每個(gè)三元組表示 D 。A. 矩陣中非零元素的值B

13、. 矩陣中數(shù)據(jù)元素的行號和列號C. 矩陣中數(shù)據(jù)元素的行號、列號和值D. 矩陣中非零數(shù)據(jù)元素的行號、列號和值36、對特殊矩陣采用壓縮存儲的目的主要是為了 D 。A. 表達(dá)變得簡單B. 對矩陣元素的存取變得簡單C. 去掉矩陣中的多余元素D. 減少不必要的存儲空間37、廣義表是線性表的推廣，它們之間的區(qū)別在于 A 。A. 能否使用子表B. 能否使用原子項(xiàng)C. 表的長度D. 是否能為空38、已知廣義表(a, b, c, d)的表頭是 A ，表尾是 D 。A. aB. ()C. (a, b, c, d)D. (b, c, d)39、下面說法不正確的是 A 。A. 廣義表的表頭總是一個(gè)廣義表B. 廣義表的

14、表尾總是一個(gè)廣義表C. 廣義表難以用順序存儲結(jié)構(gòu)表示D. 廣義表可以是一個(gè)多層次的結(jié)構(gòu)40、若廣義表A滿足Head(A)=Tail(A)，則A為 B 。A. ( )B. ()C. ( ),( )D. ( ), ( ), ( )二、填空題1、線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)之間的關(guān)系是 有序 關(guān)系。2、順序表中訪問任一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O（1） 。3、線性表中第一個(gè)結(jié)點(diǎn)沒有直接前驅(qū)，稱為 頭 結(jié)點(diǎn)。4、在一個(gè)長度為n的順序表中刪除第i個(gè)元素，要移動 n-i 個(gè)元素。5、在一個(gè)長度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移 n-i+1 個(gè)元素，在插入操作中，移動元素的均值為 n/

15、2 。6、根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成 單向鏈表 和 雙向鏈表 。7、鏈?zhǔn)酱鎯Φ奶攸c(diǎn)是利用 next指針 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。8、靜態(tài)鏈表(線性表的游標(biāo)實(shí)現(xiàn))是指用 元素的下標(biāo) 表示單鏈表的指針。9、在靜態(tài)鏈表中，一般都有一個(gè)變量available表示的結(jié)點(diǎn)鏈，其中的結(jié)點(diǎn)為 空閑結(jié)點(diǎn) 。10、在棧中，可進(jìn)行插入和刪除操作的一端稱 棧頂 。11、在進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 滿 。在出棧運(yùn)算時(shí)應(yīng)先判別棧是否 空 。當(dāng)棧中元素為n個(gè)時(shí)，進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為 n 。12、設(shè)有一空棧，現(xiàn)有輸入序列為1, 2, 3, 4, 5，經(jīng)過p

16、ush, push, pop, push, pop, push, push, pop, pop之后，輸出序列為 23541 。13、對于循環(huán)隊(duì)列Q，求隊(duì)列長度的公式為 (Q.rear-Q.front+maxlength+1)%maxlength 。14、棧的邏輯特點(diǎn)是 先進(jìn)后出 。隊(duì)列的邏輯特點(diǎn)是 先進(jìn)先出 。兩者的共同特點(diǎn)是只允許在它們的 端點(diǎn) 出插入和刪除數(shù)據(jù)元素，區(qū)別是 棧從一段進(jìn)出，隊(duì)列從一端進(jìn)，另一端出 。15、鏈隊(duì)列LQ為空時(shí)，LQ->front->next= NULL .16、在一個(gè)鏈隊(duì)列LQ中，若隊(duì)首指針為front，隊(duì)尾指針為rear，則判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條

17、件為 LQ->front->next!=NULL && LQ->front=LQ-rear 。17、設(shè)串S=“Ilikecomputer”，T=“com”，則Length(S)= 13 。Index(S, T)= 5 。18、在KMP算法中，nextj只與 模式 串有關(guān)，而與 主 無關(guān)。19、字符串“ababaab“的Next數(shù)組值是 0112342 。20、稀疏矩陣一般壓縮存儲的方式有三種，分別是 三元組 、 十字鏈表 和 行指針鏈表 。21、二維數(shù)組M中每個(gè)元素的長度是3字節(jié)，行下標(biāo)i從07，列下標(biāo)j從09，從首地址&M00開始連續(xù)存放在存儲器中。

18、若按行優(yōu)先的方式存放，元素M75的起始地址為 &M00+7*8+5 ；若按列優(yōu)先方式存放，元素M75的起始地址為 &M00+5*10+7 。22、廣義表(a, (a, b), d, e, (i, j), k)的長度是 5 ，深度是 3 。23、設(shè)廣義表A( ), (a, (b), c)，則Cal(Cdr(Cal(Cdr(Cal(A)= (b) 三、寫一個(gè)算法合并兩個(gè)已排序的線性表。（用兩種方法：數(shù)組表示的線性表（順序表）和指針表示的線性表（鏈表）要求：1、定義線性表節(jié)點(diǎn)的結(jié)構(gòu)，并定義節(jié)點(diǎn)的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main

19、函數(shù)中進(jìn)行測試：先構(gòu)建兩個(gè)有序的線性表，然后合并這兩個(gè)線性表。四、已知一個(gè)單向鏈表，試給出復(fù)制該鏈表的算法。要求：1、定義線性表的節(jié)點(diǎn)的結(jié)構(gòu)以及節(jié)點(diǎn)的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進(jìn)行測試：先構(gòu)建一個(gè)線性表，并定義一個(gè)空線性表，然后進(jìn)行復(fù)制。五、寫出從一個(gè)帶表頭的單鏈表中刪除其值等于給定值x的結(jié)點(diǎn)的算法函數(shù)：int Delete(LIST &L, int x);如果x在該鏈表中，則刪除對應(yīng)結(jié)點(diǎn)，并返回其在鏈表中的位置（邏輯位置，第一個(gè)結(jié)點(diǎn)的邏輯位置為1），否則返回-1。要求：1、定義線性表的節(jié)點(diǎn)的結(jié)構(gòu)以及節(jié)點(diǎn)的型和位置的

20、型。2、定義線性表的基本操作3、在1，2的基礎(chǔ)上，完成本題。4、在main函數(shù)中進(jìn)行測試：先構(gòu)建一個(gè)線性表，然后調(diào)用函數(shù)刪除值等于給定值的節(jié)點(diǎn)。六、寫出一個(gè)將兩個(gè)靜態(tài)鏈表（屬于同一個(gè)存儲池）合并的算法函數(shù)： void Merge(cursor M, cursor N); 合并的方法是將N鏈表中的所有結(jié)點(diǎn)添加到M鏈表的后面，并將N鏈表的表頭結(jié)點(diǎn)添加到空閑結(jié)點(diǎn)鏈表中。要求：1、定義靜態(tài)鏈表的結(jié)點(diǎn)的結(jié)構(gòu)以及結(jié)點(diǎn)的型SPACE以及位置（position）和游標(biāo)（cursor）的型。2、定義靜態(tài)鏈表的基本操作：void Initialize(); 初始化，將所有存儲池中的結(jié)點(diǎn)設(shè)置為空閑；cursor G

21、etNode(); 從空閑鏈中獲取一個(gè)結(jié)點(diǎn)；void FreeNode(cursor q); 將結(jié)點(diǎn)q加入到空閑鏈； void Insert ( elementtype x, position p, cursor M ); 在鏈表M中的位置為p的元素后面添加一個(gè)值為x的結(jié)點(diǎn)；void Delete (cursor M, position p ); 在鏈表M中刪除位置為p的元素的后一個(gè)元素。3、在1、2的基礎(chǔ)上完成本題。4、在main函數(shù)中進(jìn)行測試：先構(gòu)建一個(gè)存儲池，然后在該存儲池中創(chuàng)建兩個(gè)靜態(tài)表，最后將這兩個(gè)靜態(tài)表合并。七、利用指針表示的線性表(鏈表)表示一個(gè)多項(xiàng)式，并實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加和相

22、乘運(yùn)算。假設(shè)多項(xiàng)式形式為： 其中，系數(shù)ai0，指數(shù)ei滿足em>em-1>>e2>e1>=0。要求：1、定義多項(xiàng)式每一項(xiàng)的結(jié)構(gòu)。2、定義兩個(gè)多項(xiàng)式的相加和相乘運(yùn)算函數(shù)。3、在main函數(shù)中，構(gòu)建兩個(gè)多項(xiàng)式，并測試相加和相乘運(yùn)算。八、試編寫一個(gè)整數(shù)進(jìn)制轉(zhuǎn)換的通用函數(shù)convert(int num, STACK S, int n)，要求將整數(shù)m轉(zhuǎn)換為n進(jìn)制數(shù)，n進(jìn)制數(shù)的各位依次存放在棧S中。并在主函數(shù)中進(jìn)行測試。要求：1、定義棧以及棧的型。2、定義棧的各種操作。 3、實(shí)現(xiàn)函數(shù)convert。 4、在main函數(shù)中，通過調(diào)用函數(shù)convert將num的n進(jìn)制數(shù)存放到一個(gè)

23、棧中，并通過出棧的方法輸出該n進(jìn)制數(shù)九、設(shè)有一個(gè)循環(huán)隊(duì)列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)含有元素個(gè)數(shù)的計(jì)數(shù)器count，試寫出相應(yīng)的判斷隊(duì)列空、判斷隊(duì)列滿、出隊(duì)算法和入隊(duì)算法。要求：1、定義相應(yīng)的循環(huán)隊(duì)列的型（只有頭指針，沒有尾指針，但有一個(gè)元素個(gè)數(shù)的計(jì)數(shù)器）；2、定義該隊(duì)列的四個(gè)算法：判斷隊(duì)列空、判斷隊(duì)列滿、出隊(duì)算法和入隊(duì)算法；3、在main函數(shù)驗(yàn)證算法的正確性。十、設(shè)主串T=“abcaabbabcabaacbacba“，模式為p=“abcabaa”。 1、計(jì)算模式p的nextval函數(shù)值2、不寫算法，只畫出利用KMP算法進(jìn)行模式匹配時(shí)，每一趟的匹配過程。要求：1、寫出

24、模式p的nextval值；2、畫出KMP算法的每一趟匹配過程（可參照教材P61從第8行開始的內(nèi)容）；3、編程檢驗(yàn)p在T中是否存在，如果存在，輸出相應(yīng)的位置，如果不存在，輸出-1。十一、假設(shè)表達(dá)式中允許包含三種括號：圓括號、方括號和大括號。設(shè)計(jì)一個(gè)算法采用順序棧（用數(shù)組表示的棧）判斷表達(dá)式中的括號是否正確配對。要求： 1、定義棧以及棧的型，棧中所存放元素的類型為字符型，定義枚舉類型Boolean，其中兩個(gè)元素分別為TRUE和FALSE。2、定義棧的各種操作。3、定義函數(shù)Boolean check(char *s); 判斷s中的括號是否正確配對，如果正確配對，返回TRUE，否則返回FALSE。4、在主函數(shù)中驗(yàn)證所編寫函數(shù)的正確性。十二、設(shè)有一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表h，設(shè)計(jì)一個(gè)算法用于查找第一個(gè)