算法與數(shù)據(jù)結(jié)構(gòu) 線性表答案

1、第2章線性表線性表一、判斷題一、判斷題1線性關(guān)系的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)總是一致的。解：錯。解：錯。單鏈表的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)有可能是不一致的，有可能兩個相鄰結(jié)點(diǎn)的存儲地址并不是相鄰的。2每種數(shù)據(jù)結(jié)構(gòu)都包括插入、刪除和查找這三種基本運(yùn)算。解：錯。散列結(jié)構(gòu)無插入與刪除運(yùn)算；棧沒有查找，查找須配有另一個棧。解：錯。散列結(jié)構(gòu)無插入與刪除運(yùn)算；棧沒有查找，查找須配有另一個棧。3線性表中的每個結(jié)點(diǎn)最多只有一個前驅(qū)和一個后繼。解：對。解：對。線性表的定

2、義為：表中任意一個元素至多有一個前驅(qū)，至多有一后繼。4線性的數(shù)據(jù)結(jié)構(gòu)既可以順序存儲，也可以鏈接存儲；非線性的數(shù)據(jù)結(jié)構(gòu)則只能鏈接存儲。解：錯。解：錯。對于非線性的數(shù)據(jù)結(jié)構(gòu)，若對它的數(shù)據(jù)規(guī)定某種次序之后，也可以順序存儲。如，樹的前、中、后序遍歷之后的存儲，一個前驅(qū)可能對應(yīng)多個后繼。5順序存儲方式只能用于存儲線性結(jié)構(gòu)。解：錯。解：錯。非線性結(jié)構(gòu)也可采用順序存儲。6多維數(shù)組是向量的推廣。解：對。解：對。多維向量的存儲方式實(shí)際上與一維向量是一致的

3、。7設(shè)串s的長度為n，則s的子串個數(shù)最多為n(n1)2。解：錯。解：錯。s的長度為n，故它含有n個字符，它的子串應(yīng)包括：1個字符的子串，2個字符的子串，…，n個字符的子串；這些子串的個數(shù)分別為121)11(321?????????nnnnnnnCCCC?8單鏈表從任何一個結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。解：錯。解：錯。單鏈表僅能從頭結(jié)點(diǎn)出發(fā)去訪問所有結(jié)點(diǎn)，不能訪問前驅(qū)。9線性表的長度是線性表所占用的存儲空間的大小。解：錯。解：錯。線性表所

4、占用的存儲空間大小為：每個結(jié)點(diǎn)所占用的存儲字節(jié)數(shù)乘以線性表的長度。10雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。解：錯。解：錯。任意結(jié)點(diǎn)的后繼結(jié)點(diǎn)包含有兩個指針llink和rlink，只有rlink指向其邏輯后繼，而llink指向其邏輯前驅(qū)。11數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計算機(jī)中的映象(或表示)分別稱為存儲結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。解：對。解：對。12線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。解：錯。解：錯。各有優(yōu)缺點(diǎn)。順序存儲結(jié)構(gòu)的

5、優(yōu)點(diǎn)是：（1）存儲效率高。（2）可隨機(jī)訪問任意結(jié)點(diǎn)，存取速度快。順序存儲結(jié)構(gòu)的缺點(diǎn)是：（1）插入與刪除操作麻煩。（2）順序表的長度擴(kuò)充麻煩。鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)是：（1）插入與刪除方便。（2）順序表的長度可任意（動態(tài)分配內(nèi)存）。鏈?zhǔn)酱鎯Y(jié)構(gòu)的缺點(diǎn)是：解：選解：選D。8在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點(diǎn)，則執(zhí)行。(A)HL=ppnext=HL(B)plink=HLHL=p(C)plink=HLp=HL(D)plink=

6、HLlinkHLlink=p解：解：若單鏈表不帶頭結(jié)點(diǎn)，則應(yīng)選B。若單鏈表帶頭結(jié)點(diǎn)，則應(yīng)選D。9在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行。(A)p=qlinkplink=qlinkp(B)p=qlinkqlink=pp(C)p=qlinkqlink=plinkp(D)qlink=qlinklinkqlink=q解：選解：選C。若選D，則鏈表中沒有了q的后繼結(jié)點(diǎn)，但未刪除。僅C選項(xiàng)可使q的后繼結(jié)點(diǎn)被刪除，并按原有結(jié)

7、點(diǎn)順序重新拉鏈。10設(shè)p為有頭結(jié)點(diǎn)雙向循環(huán)鏈表中某結(jié)點(diǎn)的指針，lLink為左鏈指針，rLink為右鏈指針，則下述表達(dá)式中，不恒為真。(A)prLinklLink==p(B)prLinklLink==plLinkrLink(C)plLinkrLink==p(D)prLinkrLink==plLinklLink解：選解：選D。因?yàn)閜rLinklLink==p==plLinkrLink，故只有D不一定為真。11若某鏈表最常用的操作是在最后一個

8、結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)，則采用存儲方式最節(jié)省時間。(A)單鏈表(B)雙向鏈表(C)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表(D)單循環(huán)鏈表解：選解：選C。12鏈表不具有的特點(diǎn)是。(A)可隨機(jī)訪問任一元素(B)插入刪除不需要移動元素(C)不必事先估計存儲空間(D)所需空間與線性表長度成正比解：選解：選A。13線性表采用鏈?zhǔn)酱鎯r，其地址。(A)連續(xù)的(B)部分連續(xù)的(C)一定是不連續(xù)的(D)連續(xù)與否均可解：選解：選D。14設(shè)有一88下三角矩陣

9、A[8][8]，采用按行壓縮存儲的方式存放在一維數(shù)組B[]中，則數(shù)組B[]的容量至少需要B個元素空間。(A)32(B)36(C)16(D)64解：選解：選B。矩陣的第1行有8個非零元素，第2行有7個非零元素，…，第8行有1個非零元素，故需要存儲的非零元素的個數(shù)為87654321=8(18)2=36三、填空題三、填空題1對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為，在表尾插入元素的時間復(fù)雜度為。解：解：在表頭（即第0個