數(shù)據(jù)結(jié)構(gòu)第二章習(xí)題.ppt

1、,一、選擇題 1下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ ）【北方交通大學(xué) 2001 一、4（2分）】A存儲(chǔ)密度大 B插入運(yùn)算方便 C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示 2下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ ）【北方交通大學(xué) 2001 一、14（2分）】A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。 3線性表是具有n個(gè)（ ）的有限序列（n0）。 【清華大學(xué) 1998 一、4（2分）】A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) E信息項(xiàng),4若

2、某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。【哈爾濱工業(yè)大學(xué) 2001 二、1（2分）】A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表 5某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！灸祥_大學(xué) 2000 一、3】A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表 6設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( )最節(jié)省時(shí)間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表【合肥工業(yè)大學(xué) 200

3、0 一、1（2分）】,7若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間?！颈本├砉ご髮W(xué) 2000 一、1（2分）】A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 8. 靜態(tài)鏈表中指針表示的是（ ）. 【北京理工大學(xué) 2001 六、2（2分）】A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址 9. 鏈表不具有的特點(diǎn)是（ ） 【福州大學(xué) 1998 一、8 (2分)】A插入、刪除不需要移動(dòng)元素 B可隨機(jī)訪問(wèn)任一元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比,10. 下面的敘述不正確的是（ ）【南京理工大學(xué) 199

4、6 一、10（2分）】A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān)C. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無(wú)關(guān) 12.(1) 靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。(2) 靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。(3) 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。,以上錯(cuò)誤的是（ ）【南京理工大學(xué) 2000 一、3（1.5分）】A（1），（2） B（1）

5、 C（1），（2）,(3) D.（2） 13. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ ）(1=i=n+1)?！颈本┖娇蘸教齑髮W(xué) 1999 一、1（2分）】A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1),15線性表（ a1,a2,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（ ）AO（i） BO（1） CO（n） DO（i-1）【中山大學(xué) 199

6、9 一、2】16非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（ ）。【武漢大學(xué) 2000 二、10】Ap.link=head Bp.link=NIL Cp=NIL Dp= head17循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是（ ）?！局猩酱髮W(xué) 1998 二、2（2分）】AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一個(gè)以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（）【南京理工大學(xué)1998 一、15（2分）】A. p.next=h B. p.next=NIL C. p.next.next=h D. p.data=-1,19完成在雙循環(huán)鏈表結(jié)點(diǎn)p之后插入s的操作

7、是（ ）；【北方交通大學(xué) 1999 一、4（3分）】A p.next:=s ; s.priou:=p; p.next.priou:=s ; s.next:=p.next;B p.next.priou:=s; p.next:=s; s.priou:=p; s.next:=p.next;C s.priou:=p; s.next:=p.next; p.next:=s; p.next.priou:=s ;D s.priou:=p; s.next:=p.next; p.next.priou:=s ; p.next:=s; 20在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指

8、針的操作是( )?！颈本┼]電大學(xué) 1998 二、2（2分）】注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(llink,data,rlink)。 供選擇的答案：A p.llink：=q； q.rlink：=p； p.llink.rlink：=q； q.llink：=q；B p.llink：=q； p.llink.rlink：=q ； q.rlink：= p； q.llink:=p.llink；C q.rlink：=p； q.llink：=p.llink； p.llink.rlink：=q; p.llink：=q;D q.llink:=p.llink；q.rlink:=p； p.llink：=q；p.llink：=q

9、；（編者按：原題如此）,二、判斷1. 鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。( )【南京航空航天大學(xué) 1997 一、1（1分）】 2. 順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。( )【南京航空航天大學(xué)1997 一、2（1分）】 3線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。( )【北京郵電大學(xué) 1998 一、2（2分）】 4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。( )【北京郵電大學(xué) 2002 一、2（1分）】 5. 對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。( )【南京航空航天大學(xué) 1997 一、3（1分）】 6順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。(

10、 )【中科院軟件所 1999 六、1-2（2分）】【上海海運(yùn)學(xué)院 1997 一、1（1分）】,7集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。( )【大連海事大學(xué) 2001 一、5 ( 1分)】 8. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。( )【合肥工業(yè)大學(xué) 2000 二、1（1分）】 9. 線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。( )【合肥工業(yè)大學(xué)2001 二、1（1分）】 10. 取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān). ( )【南京理工大學(xué) 1997 二、9（2分）】 11. 循環(huán)鏈表不是線性表. ( )【南京理工大學(xué) 1998 二、1（2分）】 12. 線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)

11、現(xiàn)。( )【青島大學(xué) 2001 四、2（1分）】 13. 線性表就是順序存儲(chǔ)的表。( )【青島大學(xué) 2002 一、1（1分）】 14為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。( ),15. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( )【上海海運(yùn)學(xué)院 1996 一、1（1分）】 【上海海運(yùn)學(xué)院 1999 一、1（1分）】 16. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。 ( ) 【上海海運(yùn)學(xué)院 1998 一、2（1分）】 三、填空1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元

12、素時(shí)，應(yīng)采用_存儲(chǔ)結(jié)構(gòu)?！颈狈浇煌ù髮W(xué) 2001 二、4】,2線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。【北方交通大學(xué) 2001 二、9】 3設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn) , 若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句:_； _;【華中理工大學(xué) 2000 一、4（2分）4在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1=i=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_個(gè)元素。 5在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_?！竟枮I工業(yè)大學(xué)

13、2000 二、1（1分）】 6對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_?！竟枮I工業(yè)大學(xué) 2001 一、1（2分）】,7根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_?！疚靼搽娮涌萍即髮W(xué)1998 二、4（3分） 8 在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_、_、_、_。【中國(guó)礦業(yè)大學(xué) 2000 一、1（3分）】 9. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：

14、s .next:=p； s .prior:= _；p .prior:=s；_:=s；【福州大學(xué) 1998 二、7 (2分)】 10鏈接存儲(chǔ)的特點(diǎn)是利用_來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系?！局猩酱髮W(xué) 1998 一、1 （1分）】,19. 請(qǐng)?jiān)谙铝兴惴ǖ臋M線上填入適當(dāng)?shù)恼Z(yǔ)句。【清華大學(xué) 1994 五 （15分）】FUNCTION inclusion(ha,hb:linklisttp):boolean;以ha和hb為頭指針的單鏈表分別表示有序表A和B，本算法判別表A是否包含在表B內(nèi)，若是，則返回“true”，否則返回“false”BEGIN pa:=ha.next; pb:=hb.next; （1） ;

15、WHILE（2） DOIF pa.data=pb.data THEN（3） ELSE（4） ;（5） END;,(1)pre:=pb; (2) paNIL AND pbNIL AND pb.data=pa.data (3)pa:=pa.next; pb:=pb-next;(4)pb:=pre.next;pre:=pb;pa:=pa.next;(5)IF pa=NIL THEN return(true) ELSE return(false);注：本題是在鏈表上求模式匹配問(wèn)題。非遞歸算法中用指針pre指向主串中開始結(jié)點(diǎn)（初始時(shí)為第一元素結(jié)點(diǎn)）。若主串與子串對(duì)應(yīng)數(shù)據(jù)相等,20完善算法：已知單鏈表結(jié)點(diǎn)

16、類型為：TYPE ptr=node；node=RECORDdata：integer； next：ptrEND；過(guò)程create建立以head為頭指針的單鏈表。PROCEDURE create ( (1) )；VAR p,q：ptr； k：integer；BEGIN new（head）； q:=head；read（k）；WHILE k0 DO BEGIN (2); (3); (4); (5);read（k）END;q.next：=NIL;END;【北京師范大學(xué) 1999 三】,30.以下程序的功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)的單鏈表 數(shù)據(jù)結(jié)點(diǎn)逆序連接，請(qǐng)?zhí)羁胀晟浦oid reverse(pointer

17、 h)/* h為附加頭結(jié)點(diǎn)指針；類型pointer同算法設(shè)計(jì)第3題*/ pointer p,q;p=h-next; h-next=NULL;while(1)_)q=p; p=p-next; q-next=h-next; h-next=(2)_; 【西南交通大學(xué) 2000 一、9】,31. 下面是用c語(yǔ)言編寫的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z(yǔ)句。void reverse（linklist 【北京理工大學(xué) 2001 九、1 （6分）】,09年真題(15分) 已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表,節(jié)點(diǎn)結(jié)構(gòu)為 假設(shè)該鏈表只給出了頭指針list.在不改變鏈表的前提下,請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法,查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù)).若查找成功,算法輸出該結(jié)點(diǎn)的data值,并返回1;否則,只返回0.要求: (1)描述算法的基本設(shè)計(jì)思想. (2)描述算法的詳細(xì)實(shí)現(xiàn)步驟 (3)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟,采用程序設(shè)計(jì)語(yǔ)言描述算法(使用c或c+或java語(yǔ)言實(shí)現(xiàn)),關(guān)鍵之處請(qǐng)給出簡(jiǎn)要