2012年考研數(shù)據(jù)結(jié)構(gòu)精選試題（五）_跨考網(wǎng)

　　三、填空

　　1.當(dāng)線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表中的元素時(shí)，應(yīng)采用_______存儲(chǔ)結(jié)構(gòu)?！颈狈浇煌ù髮W(xué) 2001 二、4】

　　2.線(xiàn)性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是________?！颈狈浇煌ù髮W(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è)元素。

　　【北京工商大學(xué) 2001 二、4(4分)】

　　5.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________?！?a target="_blank">哈爾濱工業(yè)大學(xué) 2000 二、1(1分)】

　　6.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)_______,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)_______?！竟枮I工業(yè)大學(xué) 2001 一、1(2分)】

　　7.根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線(xiàn)性鏈表分成________和_______;而又根據(jù)指針的連接方式，鏈表又可分成________和________。【西安電子科技大學(xué)1998 二、4(3分)】

　　8. 在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作是_______、_______、_______、________?！?a target="_blank">中國(guó)礦業(yè)大學(xué) 2000 一、1(3分)】

　　9. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：

　　s^ .next:=p; s^ .prior:= ________;p^ .prior:=s;________:=s;

　　【福州大學(xué) 1998 二、7 (2分)】

　　10.鏈接存儲(chǔ)的特點(diǎn)是利用________來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系?！?a target="_blank">中山大學(xué) 1998 一、1 (1分)】

　　11.順序存儲(chǔ)結(jié)構(gòu)是通過(guò)________表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)________表示元素之間的關(guān)系的。【北京理工大學(xué) 2001 七、2 (2分)】

　　12. 對(duì)于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 ______個(gè)，單鏈表為_(kāi)______個(gè)。

　　【南京理工大學(xué) 2000 二、2 (3分)】

　　13. 循環(huán)單鏈表的最大優(yōu)點(diǎn)是：________?！靖Ｖ荽髮W(xué) 1998 二、3 (2分)】

　　14. 已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是：________

　　【合肥工業(yè)大學(xué) 1999 三、2 (2分)】

　　15. 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是：________

　　【合肥工業(yè)大學(xué) 1999 三、3 2000 三、2(2分)】

　　16. 在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是：__ 【合肥工業(yè)大學(xué) 2001 三、3 (2分)】

　　17.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是：________。

　　【北京理工大學(xué) 2000 二、1 (2分)】 【青島大學(xué) 2002 三、1 (2分)】

　　18. 在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是：_______。【青島大學(xué) 2002 三、2(2分)】

　　19. 請(qǐng)?jiān)谙铝兴惴ǖ臋M線(xiàn)上填入適當(dāng)?shù)恼Z(yǔ)句?！?a target="_blank">清華大學(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) ;

　　WHILE(2) DO

　　IF pa^.data=pb^.data THEN(3) ELSE(4) ;

　　(5)

　　END;

　　20.完善算法：已知單鏈表結(jié)點(diǎn)類(lèi)型為：

　　TYPE ptr=^node;

　　node=RECORD

　　data：integer; next：ptr

　　END;

　　過(guò)程create建立以head為頭指針的單鏈表。

　　PROCEDURE create ( (1) );

　　VAR p,q：ptr; k：integer;

　　BEGIN

　　new(head); q:=head;read(k);

　　WHILE k>0 DO

　　BEGIN

　　(2); (3); (4); (5);

　　read(k)

　　END;

　　q^.next：=NIL;

　　END;【北京師范大學(xué) 1999 三】

　　21. 已給如下關(guān)于單鏈表的類(lèi)型說(shuō)明：

　　TYPE

　　list=^node ;

　　node=RECORD

　　data: integer; next: list;

　　END;

　　以下程序采用鏈表合并的方法，將兩個(gè)已排序的單鏈表合并成一個(gè)鏈表而不改變其排序性(升序)，這里兩鏈表的頭指針?lè)謩e為p和q.

　　PROCEDURE mergelink(VAR p,q:list):

　　VAR h,r: list;

　　BEGIN

　　(1)______

　　h^.next:= NIL; r:=h;

　　WHILE((p<>NIL) AND (q<>NIL)) DO

　　IF (p^.data<=q^.data)

　　THEN BEGIN (2)___; r:=p; p:=p^.next; END

　　ELSE BEGIN (3)____; r:=q; q:=q^.next; END;

　　IF (p=NIL) THEN r^.next:=q;

　　(4)__;

　　p:=h^.next; dispose(h);

　　END;【廈門(mén)大學(xué) 2000 三、2 (8分)】

　　22.假設(shè)鏈表p和鏈表q中的結(jié)點(diǎn)值都是整數(shù),且按結(jié)點(diǎn)值的遞增次序鏈接起來(lái)的帶表頭結(jié)點(diǎn)的環(huán)形鏈表。各鏈表的表頭結(jié)點(diǎn)的值為max,且鏈表中其他結(jié)點(diǎn)的值都小于max，在程序中取max為9999。在各個(gè)鏈表中，每個(gè)結(jié)點(diǎn)的值各不相同，但鏈表p和鏈表q可能有值相同的結(jié)點(diǎn)(表頭結(jié)點(diǎn)除外)。下面的程序?qū)㈡湵韖合并到鏈表p中，使得合并后的鏈表是按結(jié)點(diǎn)值遞增次序鏈接起來(lái)的帶表頭結(jié)點(diǎn)的環(huán)形鏈表，且鏈表中各個(gè)結(jié)點(diǎn)的值各不相同。請(qǐng)?jiān)趧澗€(xiàn)處填上適當(dāng)內(nèi)容，每個(gè)框只填一個(gè)語(yǔ)句或一個(gè)表達(dá)式，鏈表的結(jié)點(diǎn)類(lèi)型如下

　　TYPE nodeptr=^nodetype;

　　nodetype=RECORD

　　data：integer; link：nodeptr;

　　END;

　　CONST max=9999;

　　PROCEDURE merge(VAR p:nodeptr;q:nodeptr);

　　VAR r,s: nodeptr;

　　BEGIN

　　r:=p;

　　WHILE (A)___ DO

　　BEGIN

　　WHILE r^.link^.data

　　IF r^.link^.data>q^.link^.data

　　THEN BEGIN s:=(C)_; (D)_:=s^.link; s^.link:=(E)_; (F)_ _:=s; (G)_; END

　　ELSE BEGIN (H)__; s:=q^.link; (I)__; dispose(s) END

　　END;

　　dispose(q)

　　END;【復(fù)旦大學(xué) 1997 五(18分)】