第二章線性表答案VIP

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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