三、填空

　　1.當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以比較快的速度存取線性表中的元素時，應采用_______存儲結構。【北方交通大學 2001 二、4】

　　2.線性表L=(a1,a2,…,an)用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數是________。【北方交通大學 2001 二、9】

　　3.設單鏈表的結點結構為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點 , 若將結點y插入結點x之后，則需要執行以下語句:_______; ______;【華中理工大學 2000 一、4(2分)】

　　4.在一個長度為n的順序表中第i個元素(1<=i<=n)之前插入一個元素時，需向后移動________個元素。

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

　　5.在單鏈表中設置頭結點的作用是________。【哈爾濱工業大學 2000 二、1(1分)】

　　6.對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為________,在給定值為x的結點后插入一個新結點的時間復雜度為________。【哈爾濱工業大學 2001 一、1(2分)】

　　7.根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成________和_______;而又根據指針的連接方式，鏈表又可分成________和________。【西安電子科技大學1998 二、4(3分)】

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

　　9. 在雙向鏈表結構中，若要求在p 指針所指的結點之前插入指針為s 所指的結點，則需執行下列語句：

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

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

　　10.鏈接存儲的特點是利用________來表示數據元素之間的邏輯關系。【中山大學 1998 一、1 (1分)】

　　11.順序存儲結構是通過________表示元素之間的關系的;鏈式存儲結構是通過________表示元素之間的關系的。【北京理工大學 2001 七、2 (2分)】

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

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

　　13. 循環單鏈表的比較大優點是：________。【福州大學 1998 二、3 (2分)】

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

　　【合肥工業大學 1999 三、2 (2分)】

　　15. 帶頭結點的雙循環鏈表L中只有一個元素結點的條件是：________

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

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

　　17.帶頭結點的雙循環鏈表L為空表的條件是：________。

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

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

　　19. 請在下列算法的橫線上填入適當的語句。【清華大學 1994 五 (15分)】

　　FUNCTION inclusion(ha,hb:linklisttp):boolean;

　　{以ha和hb為頭指針的單鏈表分別表示有序表A和B，本算法判別表A是否包含在表B內，若是，則返回“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.完善算法：已知單鏈表結點類型為：

　　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;【北京師范大學 1999 三】

　　21. 已給如下關于單鏈表的類型說明：

　　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;【廈門大學 2000 三、2 (8分)】

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

　　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;【復旦大學 1997 五(18分)】

    考試須知：2012考研時間安排 ♦應試技巧及考場須知 ♦首發2012考研真題

    考前必看：準考證下載入口 ♦2012年考研考場規則 ♦2012考研考場查詢

    復習備考：政治時事匯總 必背考點 預測試題 ♦ 英語作文預測 模板大全