1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)測(cè)試（長(zhǎng)春理工大學(xué)精品課）第2章線性表一、選擇題1下述( )是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？查看答案A存儲(chǔ)密度大 B插入運(yùn)算方便C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示正確答案為A解釋：插入運(yùn)算和刪除運(yùn)算對(duì)于順序存儲(chǔ)結(jié)構(gòu)需要移動(dòng)大量的數(shù)據(jù)元素，順序存儲(chǔ)結(jié)構(gòu)對(duì)于非線性的邏輯結(jié)構(gòu)表示比較復(fù)雜，順序存儲(chǔ)結(jié)構(gòu)中只需要存儲(chǔ)數(shù)據(jù)元素，不像鏈?zhǔn)浇Y(jié)構(gòu)除了存數(shù)據(jù)元素還要存儲(chǔ)關(guān)系，因此順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度比較大。收起2下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（)查看答案A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用

2、鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。正確答案是B解釋：順序存儲(chǔ)不利于插入刪除，需要移動(dòng)近一半的數(shù)據(jù)元素。收起3線性表是具有n個(gè)（）的有限序列（n0）。查看答案A表元素 B字符C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng)正確答案是C解釋：根據(jù)線性表的定義。收起4若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。查看答案A順序表 B雙鏈表C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表正確答案是A解釋：順序存儲(chǔ)結(jié)構(gòu)做相應(yīng)的操作時(shí)間復(fù)雜度分別為O(1)，O(1)，O(1)因此是最節(jié)省時(shí)間的。收起5某線性表中最常用的操作是在最后一個(gè)元素之后

3、插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。查看答案A單鏈表B僅有頭指針的單循環(huán)鏈表C雙鏈表 D僅有尾指針的單循環(huán)鏈表正確答案是D解釋：在僅有尾指針的單循環(huán)鏈表做相應(yīng)操作的時(shí)間復(fù)雜度為O(1)，O(1)收起6.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1=inext=head BP-next=NILCp=NIL Dp=head正確答案是A解釋：循環(huán)單鏈表的尾結(jié)點(diǎn)的后繼結(jié)點(diǎn)應(yīng)當(dāng)是頭結(jié)點(diǎn)。收起8在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（）。查看答案Ap-next=s;s-next=p-next; Bs-next

4、=p-next;p-next=s;Cp-next=s;p-next=s-next; Dp-next=s-next;p-next=s;正確答案是B解釋：p結(jié)點(diǎn)插入前的后繼應(yīng)成為s的后繼，s應(yīng)成為p的新后繼，而且兩個(gè)操作不能換位，否則p結(jié)點(diǎn)的后繼鏈將丟失。收起9.鏈表不具有的特點(diǎn)是（）。查看答案A插入、刪除不需要移動(dòng)元素 B可隨機(jī)訪問任一元素C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比正確答案是B解釋：鏈?zhǔn)酱鎯?chǔ)方式不能隨機(jī)訪問，只能采用順序訪問的方式。收起10.(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ù)的

5、最大數(shù)在表定義時(shí)就確定了，以后不能增加。 (3)靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。以上錯(cuò)誤的是（）。查看答案 A（1），（2） B（1）C（1），（2）,(3) D.（2）正確答案是B解釋：靜態(tài)鏈表采用數(shù)組做為存儲(chǔ)結(jié)構(gòu)，是方便沒有指針的編程語言使用，元素的后繼地址記錄的是元素所在的下標(biāo)，因此和單鏈表一樣只能采用順序訪問方式，插入刪除操作只需修改相應(yīng)下標(biāo)不需移動(dòng)元素。收起二、填空題1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_存儲(chǔ)結(jié)構(gòu)。查看答案正確答案是：順序存儲(chǔ)結(jié)構(gòu)解釋：元素總數(shù)穩(wěn)定，說明很少做插入刪除操作，

6、因此采用順序存儲(chǔ)最合適。收起2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。查看答案正確答案是：（n-1）/2解釋：長(zhǎng)度為n的線性表，刪除任一元素的概率為1/n，刪除一個(gè)元素平均移動(dòng)的元素的個(gè)數(shù)為(n-1)+(n-2)+.+0/n=(n-1)/2收起3對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_,查看答案正確答案是：O(1)解釋：在已知結(jié)點(diǎn)的后面插元素，只需修改后繼元素的指針。收起4對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_。查看答案正確答案是：O(n)解

7、釋：查找值為x的結(jié)點(diǎn)，只能順序查找，時(shí)間復(fù)雜度為O(n)收起。5.已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是：_。查看答案正確答案是：p-next=p-next-next解釋：刪除其后繼只需讓后繼的后繼成為其后繼。收起6 在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_、_、_、_。查看答案正確答案是：f-next=p-next; f-prior=p; p-next-prior=f; p-next=f;收起7.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：_。查看答案正確答案是：L-next=L & L-prior=L解釋：雙循環(huán)鏈表為空，前驅(qū)和后繼都應(yīng)指向頭結(jié)點(diǎn)。

8、收起8.對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共_個(gè)。查看答案正確答案是：4個(gè)解釋：修改的指針分別為前一個(gè)結(jié)點(diǎn)的后繼，后一個(gè)結(jié)點(diǎn)的前驅(qū)，新結(jié)點(diǎn)的前驅(qū)和后繼。收起9.在雙向鏈表結(jié)構(gòu)中，若要求在p指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s所指的結(jié)點(diǎn)，則需執(zhí)行下列語句：S-next=p； s-prior= _； p-prior=s； _=s；查看答案正確答案是：p-prior s-prior-next解釋：插入后p的前驅(qū)成為s，s的前驅(qū)應(yīng)是原來p的前驅(qū)。收起10.在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：查看答案正確答案是：p-next！=null收起三、應(yīng)用題1.線性表的順序存儲(chǔ)結(jié)構(gòu)具有

9、三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。查看答案參考答案：鏈?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)。收起2.下面是一算法的核心部分，試說明該算法的功能.查看答案pre=L-next;L是一單鏈表，結(jié)點(diǎn)有數(shù)據(jù)域data和指針域nextIF (pre!=null) WHILE (pre-next!=null） p=pr