數(shù)據(jù)結(jié)構(gòu)試題精選（2）-應(yīng)用題_跨考網(wǎng)

四? 應(yīng)用題

1．線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：

（1）如果有 n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？

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

2．線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之?！?a target="_blank">重慶大學(xué) 2000 二、5】

3．若較頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)？為什么？

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

4．線性結(jié)構(gòu)包括______、______、_______和_______。線性表的存儲(chǔ)結(jié)構(gòu)分成______和______。請(qǐng)用類PASCＡL語(yǔ)言描述這兩種結(jié)構(gòu)。【華北計(jì)算機(jī)系統(tǒng)工程研究所1999一、2（10分）】

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

【東南大學(xué) 1996 一、1 （5分）】

6. 說(shuō)明在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別；頭結(jié)點(diǎn)與首元結(jié)點(diǎn)的關(guān)系。

【廈門(mén)大學(xué) 2000 五、1 （14%/3分）】

7. 試述頭結(jié)點(diǎn),首元結(jié)點(diǎn),頭指針這三個(gè)概念的區(qū)別.

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

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

???? TYPE?? component=RECORD

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

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

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

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

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

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

? （2） 如何得到當(dāng)前結(jié)點(diǎn)p的前驅(qū)（pre）的前驅(qū)，給出計(jì)算式;

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

9. 在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到任何一個(gè)結(jié)點(diǎn)?

【西安電子科技大學(xué)1999計(jì)應(yīng)用一、1 （5分）】

10. 如何通過(guò)改鏈的方法，把一個(gè)單向鏈表變成一個(gè)與原來(lái)鏈接方向相反的單向鏈表？

【中國(guó)人民大學(xué) 2001 二、4 （2分）】