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

　　三、填空

　　1.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(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)之前插入一個元素時，需向后移動________個元素。

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

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

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

　　7.根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成________和_______;而又根據(jù)指針的連接方式，鏈表又可分成________和________?！?a target="_blank">西安電子科技大學(xué)1998 二、4(3分)】

　　8. 在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是_______、_______、_______、________。【中國礦業(yè)大學(xué) 2000 一、1(3分)】

　　9. 在雙向鏈表結(jié)構(gòu)中，若要求在p 指針所指的結(jié)點之前插入指針為s 所指的結(jié)點，則需執(zhí)行下列語句：

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

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

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

　　11.順序存儲結(jié)構(gòu)是通過________表示元素之間的關(guān)系的;鏈式存儲結(jié)構(gòu)是通過________表示元素之間的關(guān)系的?！?a target="_blank">北京理工大學(xué) 2001 七、2 (2分)】

　　12. 對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 ______個，單鏈表為_______個。

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

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

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

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

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

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

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

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

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

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

　　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) ;

　　WHILE(2) DO

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

　　(5)

　　END;

　　20.完善算法：已知單鏈表結(jié)點類型為：

　　TYPE ptr=^node;

　　node=RECORD

　　data：integer; next：ptr

　　END;

　　過程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)于單鏈表的類型說明：

　　TYPE

　　list=^node ;

　　node=RECORD

　　data: integer; next: list;

　　END;

　　以下程序采用鏈表合并的方法，將兩個已排序的單鏈表合并成一個鏈表而不改變其排序性(升序)，這里兩鏈表的頭指針分別為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;【廈門大學(xué) 2000 三、2 (8分)】

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

　　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分)】