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

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

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

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

4、6 一、10（2分）】A線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比B. 線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關(guā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)鏈表在元素的插入、刪除上類似，不需做元素的移動。,以上錯誤的是（ ）【南京理工大學(xué) 2000 一、3（1.5分）】A（1），（2） B（1）

5、 C（1），（2）,(3) D.（2） 13. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ ）(1=i=n+1)。【北京航空航天大學(xué) 1999 一、1（2分）】A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（ ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1),15線性表（ a1,a2,an）以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為（ ）AO（i） BO（1） CO（n） DO（i-1）【中山大學(xué) 199

6、9 一、2】16非空的循環(huán)單鏈表head的尾結(jié)點p滿足（ ）?！疚錆h大學(xué) 2000 二、10】Ap.link=head Bp.link=NIL Cp=NIL Dp= head17循環(huán)鏈表H的尾結(jié)點P的特點是（ ）?！局猩酱髮W(xué) 1998 二、2（2分）】AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一個以 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é)點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é)點前插入一個指針q所指向的新結(jié)點,其修改指

8、針的操作是( )?！颈本┼]電大學(xué) 1998 二、2（2分）】注:雙向鏈表的結(jié)點結(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é)點僅起到標(biāo)識的作用。( )【南京航空航天大學(xué) 1997 一、1（1分）】 2. 順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。( )【南京航空航天大學(xué)1997 一、2（1分）】 3線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。( )【北京郵電大學(xué) 1998 一、2（2分）】 4順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩? )【北京郵電大學(xué) 2002 一、2（1分）】 5. 對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。( )【南京航空航天大學(xué) 1997 一、3（1分）】 6順序存儲方式只能用于存儲線性結(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. 線性表的特點是每個元素都有一個前驅(qū)和一個后繼。( )【合肥工業(yè)大學(xué)2001 二、1（1分）】 10. 取線性表的第i個元素的時間同i的大小有關(guān). ( )【南京理工大學(xué) 1997 二、9（2分）】 11. 循環(huán)鏈表不是線性表. ( )【南京理工大學(xué) 1998 二、1（2分）】 12. 線性表只能用順序存儲結(jié)構(gòu)實

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

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

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

14、s .next:=p； s .prior:= _；p .prior:=s；_:=s；【福州大學(xué) 1998 二、7 (2分)】 10鏈接存儲的特點是利用_來表示數(shù)據(jù)元素之間的邏輯關(guān)系?！局猩酱髮W(xué) 1998 一、1 （1分）】,19. 請在下列算法的橫線上填入適當(dāng)?shù)恼Z句。【清華大學(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);注：本題是在鏈表上求模式匹配問題。非遞歸算法中用指針pre指向主串中開始結(jié)點（初始時為第一元素結(jié)點）。若主串與子串對應(yīng)數(shù)據(jù)相等,20完善算法：已知單鏈表結(jié)點

16、類型為：TYPE ptr=node；node=RECORDdata：integer； next：ptrEND；過程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.以下程序的功能是實現(xiàn)帶附加頭結(jié)點的單鏈表 數(shù)據(jù)結(jié)點逆序連接，請?zhí)羁胀晟浦?。void reverse(pointer

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