第二章線性表答案

1、第2章線性表一選擇題1 下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（A ）A存儲密度大 B 插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示2 下面關(guān)于線性表的敘述中，錯誤的是哪一個？（B）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D 線性表采用鏈接存儲，便于插入和刪除操作。3 線性表是具有n 個（C ）的有限序列（n>0）。A表元素B 字符C數(shù)據(jù)元素D 數(shù)據(jù)項E信息項4 若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ A ）存儲方式最節(jié)省時

2、間。A順序表B 雙鏈表C帶頭結(jié)點的雙循環(huán)鏈表D 單循環(huán)鏈表5 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D ）存儲方式最節(jié)省運算時間。A單鏈表B僅有頭指針的單循環(huán)鏈表C雙鏈表D 僅有尾指針的單循環(huán)鏈表6 設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用(D) 最節(jié)省時間。A.單鏈表B. 單循環(huán)鏈表C. 帶尾指針的單循環(huán)鏈表D. 帶頭結(jié)點的雙循環(huán)鏈表7 若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。則采用（ D ）存儲方式最節(jié)省運算時間。A單鏈表B 雙鏈表C單循環(huán)鏈表D 帶頭結(jié)點的雙循環(huán)鏈表8.靜態(tài)鏈表中指針表示的是（BC

3、） .A 內(nèi)存地址B 數(shù)組下標C下一元素地址D 左、右孩子地址9.鏈表不具有的特點是（C）A插入、刪除不需要移動元素B可隨機訪問任一元素C 不必事先估計存儲空間D 所需空間與線性長度成正比10.下面的敘述不正確的是（BC）A線性表在鏈式存儲時，查找第i 個元素的時間同i 的值成正比B.線性表在鏈式存儲時，查找第i 個元素的時間同i 的值無關(guān)C. 線性表在順序存儲時，查找第i 個元素的時間同i 的值成正比D.線性表在順序存儲時，查找第i 個元素的時間同i 的值無關(guān)11. 線性表的表元存儲方式有 ( 順序 ) 和鏈接兩種。試指出下列各表中使用的是何種存儲方式：表 1 是 ( 順序 ) 存儲方式；表

4、 2 是( 循環(huán)鏈接 ) 存儲方式；表 3 是 ( 單向鏈接 ) 存儲方式；表 4 是 ( 雙向鏈接 ) 存儲方式。表左的 s 指向起始表元。表表元元數(shù)貨號間編量聯(lián)號系1618·4022205233103154450120557811766901240表 1s表表元元數(shù)貨號間編量聯(lián)號系1618·4052205213103154450120257811766901243表 2s 表表元元數(shù)貨號間編量聯(lián)號系1618·4052205213103156450120057811746901243表 3s >表元數(shù)表元間聯(lián)系貨號編量12號1618·405222

5、0521031031546450120035781176169012435表 4s 供選擇的答案：A. 連續(xù)B. 單向鏈接C. 雙向鏈接F. 樹狀G. 網(wǎng)狀H. 隨機I. 順序D. 不連接 J. 順序循環(huán)E. 循環(huán)鏈接12.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i 個元素的時間與i 無關(guān)。(2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3) 靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（ B ）A （ 1），（ 2）B（ 1）C（ 1），（ 2） ,(3)D. （2）13. 若長度為 n 的線性表采用

6、順序存儲結(jié)構(gòu)， 在其第 i 個位置插入一個新元素的算法的時間復(fù)雜度為（C） (1<=i<=n+1)。A. O(0)B. O(1)C. O(n)D. O(n 2)14.對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（C）。A O(n)O(n)B. O(n)O(1)C. O(1)O(n)D. O(1) O(1)15線性表（ a1,a2,an）以鏈接方式存儲時， 訪問第 i 位置元素的時間復(fù)雜性為（ C）A O （i ） B O（ 1 ）C O（ n ）D O（ i-1 ）16非空的循環(huán)單鏈表head的尾結(jié)點 p 滿足（ A ）。A p.link=headB p.link=

7、NILC p=NILD p= head17循環(huán)鏈表 H 的尾結(jié)點 P 的特點是（A ）。A P.NEXT=HB P.NEXT= H.NEXTC P=HD P=H.NEXT18在一個以h 為頭的單循環(huán)鏈中， p 指針指向鏈尾的條件是（ A）A. p.next=hB. p.next=NILC. p .next. next=hD. p .data=-1二、判斷1. 鏈表中的頭結(jié)點僅起到標識的作用。( × )2.順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。( )3線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。( )4順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好

8、。(× )5.對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。( × )6順序存儲方式只能用于存儲線性結(jié)構(gòu)。( × )7 集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。(× )8. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。( × )9. 線性表的特點是每個元素都有一個前驅(qū)和一個后繼。( × )10. 取線性表的第 i 個元素的時間同 i 的大小有關(guān) . ( × )11. 循環(huán)鏈表不是線性表 . ( × )12. 線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。( × )13. 線性表就是順序存儲的表。 ( × )14 為

9、了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。()15.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。(×)16. 鏈表是采用鏈式存儲結(jié)構(gòu)的線性表 ,進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。 ( )三、填空1 當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用 _ 順序 _ 存儲結(jié)構(gòu)。2 線性表 L= （ a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_n-1/2_。3 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)為 x 的結(jié)點，指針py 指向 dat

10、a為 y行以下語句 :_py->next=px->next_，next的新結(jié)點；為指針域， 已知指針px,若將結(jié)點 y 插入結(jié)點_px->next=py_;指向單鏈表中datax 之后，則需要執(zhí)4 在一個長度為動_n-i+1_n 的順序表中第個元素。i 個元素（1<=i<=n）之前插入一個元素時，需向后移5 在單鏈表中設(shè)置頭結(jié)點的作用是 _ 主要是使插入和刪除等操作統(tǒng)一，在第一個元素之前插入元素和刪除第一個結(jié)點不必另作判斷。另外，不論鏈表是否為空，鏈表指針不變。_。6 對于一個具有_o(1)_,n 個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為在給

11、定值為x 的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_O(n)_。7 根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成_和_ 多重鏈表 _ ；而又根據(jù)指針的連接方式，鏈表又可分成_ 和 _ 靜態(tài)鏈表 _。_ 單鏈表動態(tài)鏈表8 在雙向循環(huán)鏈表中 _f->next=p->next;_, 向p 所指的結(jié)點之后插入指針、_f->next=p;_f 所指的結(jié)點，其操作是、_p->next->prior=f;_、_p->next=f;_。10 鏈接存儲的特點是利用_ 指針 _ 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。11. 順序存儲結(jié)構(gòu)是通過 _ 物理上相鄰 _ 表示

12、元素之間的關(guān)系的 ; 鏈式存儲結(jié)構(gòu)是通過_ 指針 _ 表示元素之間的關(guān)系的。12.對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共_4_個，單鏈表為_2_ 個。13.循環(huán)單鏈表的最大優(yōu)點是：_ 從任一結(jié)點出發(fā)都可訪問到鏈表中每一個元素_ 。14. 已知指針 p 指向單鏈表 L 中的某結(jié)點， 則刪除其后繼結(jié)點的語句是： _q=p->next; p->next=q->next;delete q;_15. 帶頭結(jié)點的雙循環(huán)鏈表 L 中只有一個元素結(jié)點的條件是：_ L->next->next=L或者 L->next->prior=L或者L->pr

13、ior->next=L或者L->prior->prior=L_16.在單鏈表L 中，指針p 所指結(jié)點有后繼結(jié)點的條件是：_ p->next!=null17. 帶頭結(jié)點的雙循環(huán)鏈表 L 為空表的條件是： _ L->next=L&&L->prior=L _。18. 在單鏈表 p 結(jié)點之后插入 s 結(jié)點的操作是：_ s->next=p->next;p->next=s _。四應(yīng)用題1 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1 ）如果有 n 個線性表同時并存， 并且在處理過程中各表的長度會動態(tài)變化，數(shù)也會自動地改變。在此

14、情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？線性表的總答：選鏈式存儲結(jié)構(gòu)， 它可動態(tài)申請內(nèi)存空間， 不受長度 （即表中元素個數(shù)） 的影響， 插入、刪除復(fù)雜度為 O(1)（ 2 ）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？答：選取順序結(jié)構(gòu)，順序表可以隨機存取，時間復(fù)雜度為O（1）。2 線性表的順序存儲結(jié)構(gòu)具有三個弱點：其一， 在作插入或刪除操作時，需移動大量元素；其二，由于難以估計， 必須預(yù)先分配較大的空間， 往往使存儲空間不能得到充分利用； 其三，表的容量難以擴充。線性表的鏈式存儲結(jié)構(gòu)是否一定都能夠克服上述三個弱點，試討論之。

15、答：鏈式存儲結(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。 首先，插入、刪除不需移動元素，只修改指針， 時間復(fù)雜度為 O(1) ；其次，不需要預(yù)先分配空間， 可根據(jù)需要動態(tài)申請空間；其三， 表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當空間不允許時，就不能克服順序存儲的缺點。3 若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結(jié)構(gòu)？為什么？答：采用鏈式存儲結(jié)構(gòu)， 它根據(jù)實際需要申請內(nèi)存空間， 而當不需要時又可將不用結(jié)點空間返還給系統(tǒng)。在鏈式存儲結(jié)構(gòu)中插入和刪除操作不需要移動元素。4 線性結(jié)構(gòu)包括_ 線性表 _ 、 _ 棧 _ 、 _ 隊列 _ 和 _ 串 _ 。線性

16、表的存儲結(jié)構(gòu)分成 _ 順序存儲結(jié)構(gòu)_ 和 _ 鏈式存儲結(jié)構(gòu)_ 。5 線性表（a 1 ， a 2， ， an ）用順序映射表示時，a i 和a i+1（ 1<=i<n的物理位置相鄰嗎？鏈接表示時呢？答：順序映射時，a i 與ai+1的物理位置相鄰；鏈表表示時a i 與a i+1的物理位置不要求相鄰。6. 說明在線性表的鏈式存儲結(jié)構(gòu)中，頭指針與頭結(jié)點之間的根本區(qū)別；頭結(jié)點與首元結(jié)點的關(guān)系。答：在線性表的鏈式存儲結(jié)構(gòu)中， 頭指針指鏈表的指針， 若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的， 放在第一元素結(jié)點之前， 其數(shù)據(jù)域一般無意義 （當然有些情況下也可存放鏈表的長度、 用做監(jiān)視哨等等） ，有頭結(jié)點后， 對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。 而且無論鏈表是否為空， 頭指針均不為空。 首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。7.在單鏈