數(shù)據(jù)結構試題精選（2）-應用題_跨考網(wǎng)

四? 應用題

1．線性表有兩種存儲結構：一是順序表，二是鏈表。試問：

（1）如果有 n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構？ 為什么？

（2）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應采用哪種存儲結構？為什么？【西安電子科技大學 1999軟件 二、1 （5分）】

2．線性表的順序存儲結構具有三個弱點：其一，在作插入或刪除操作時，需移動大量元素；其二，由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；其三，表的容量難以擴充。線性表的鏈式存儲結構是否一定都能夠克服上述三個弱點，試討論之?！?a target="_blank">重慶大學 2000 二、5】

3．若較頻繁地對一個線性表進行插入和刪除操作，該線性表宜采用何種存儲結構？為什么？

【北京航空航天大學 1998 一、2（4分）】

4．線性結構包括______、______、_______和_______。線性表的存儲結構分成______和______。請用類PASCＡL語言描述這兩種結構?！?a target="_blank">華北計算機系統(tǒng)工程研究所1999一、2（10分）】

5．線性表（a1，a2，…，an）用順序映射表示時，ai和ai+1（1<=i<n〉的物理位置相鄰嗎？鏈接表示時呢？

【東南大學 1996 一、1 （5分）】

6. 說明在線性表的鏈式存儲結構中，頭指針與頭結點之間的根本區(qū)別；頭結點與首元結點的關系。

【廈門大學 2000 五、1 （14%/3分）】

7. 試述頭結點,首元結點,頭指針這三個概念的區(qū)別.

【武漢交通科技大學 1996 二、2 (3分)】【西安電子科技大學2001計應用 二、1（5分）】

8. 已知有如下定義的靜態(tài)鏈表：

???? TYPE?? component=RECORD

??????????????????????? data:elemtp;

??????????????????????? next:0..maxsize

????????????????????? END

???? VAR? stalist:ARRAY[0..maxsize] OF component;

以及三個指針:av指向頭結點，p指向當前結點，pre指向前驅(qū)結點，現(xiàn)要求修改靜態(tài)鏈表中next域中的內(nèi)容，使得該靜態(tài)鏈表有雙向鏈表的功能，從當前結點p既能往后查找，也能往前查找：

? （1） 定義next域中的內(nèi)容。(用老的next域中的值表示)；

? （2） 如何得到當前結點p的前驅(qū)（pre）的前驅(qū)，給出計算式;

（3） 如何得到p的后繼，給出計算式;【中科院計算所 2000 四（10分）】

9. 在單鏈表和雙向鏈表中，能否從當前結點出發(fā)訪問到任何一個結點?

【西安電子科技大學1999計應用一、1 （5分）】

10. 如何通過改鏈的方法，把一個單向鏈表變成一個與原來鏈接方向相反的單向鏈表？

【中國人民大學 2001 二、4 （2分）】