1、本文檔由標(biāo)準(zhǔn)美女（標(biāo)準(zhǔn)王國）整理，僅作學(xué)習(xí)交流使用。如文檔存在缺頁、字跡模糊、亂碼等情況，請大家通過論壇消息與我聯(lián)系。上海交通大學(xué)一九九九年碩士生入學(xué)考試試題試題序號：19試題名稱：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計技術(shù)說明：試卷共十題，第1-5題只需寫出實現(xiàn)算法的函數(shù)或過程即可，不必寫出整個程序，只準(zhǔn)使用pascal或C編寫（類pascal和類C均可），必須寫清楚算法設(shè)計思想及所用的數(shù)據(jù)結(jié)構(gòu)，對程序要加以適當(dāng)?shù)淖⒔?，程序?yīng)有良好的結(jié)構(gòu)，不得使用goto語句，第6-10題直接寫出答案即可。1假設(shè)有兩個按元素值遞增有序排列的線性表A和B，2均以單鏈表作存儲結(jié)構(gòu)，3請編寫算法將表A和表B歸并成一個按元素非遞減有序

2、（允許值相同4）排列的線性表C，5并要求利用原表（即表A和表B）的結(jié)點空間存放表Co（12分）6利用兩個棧S1和S2模擬一個隊列，7寫出入隊和出隊的算法（可用棧的基本操作）。（12分）8試以二叉鏈表作存儲結(jié)構(gòu)，9編寫按層次順序遍歷二叉樹的算法。（12分）10已知一棵二叉樹的先序遍歷和中序遍歷序列分別在于兩個一維數(shù)組中，11試編寫算法建立二叉樹的二叉鏈表。（12分）12、寫出從哈希13、表中刪除關(guān)鍵字為K的一個記錄的算法，14、設(shè)哈希15、 函數(shù)為h,解決沖突的方法為鏈地址法。（12分）16、 考慮下圖：（12分）1） 從頂點A出發(fā)，2）求它的深度優(yōu)先生成樹。3）從頂點E出發(fā)，4）求它的廣度優(yōu)先

3、生成樹。5） 根據(jù)普里姆（Prim）算法,5A2B64D1 C3E53G117、試求按關(guān)鍵字序列（12,18、7,22、8,23、10,二叉樹。（7分）6 ） 求它的最小生成樹。F1 , 19、4 , 20、3 , 21、24、2）插入生成的二叉排序樹和平衡2 , 27、16, 28 >30,25、給出一組關(guān)鍵字T=（12,26、29、8 , 30、2 8, 31、4 , 32、10, 33 >2034 、6,35、18）,36、寫出用下列算法從小到大排序時第一趟結(jié)束時的序列：（9分）1）希2?爾排序（第一趟排序的增量為5）3）快速排序（選第一個記錄為樞軸（分隔）4?鏈接基數(shù)排序（基數(shù)為10）37、判別序列（12,38、70,39>33,40>65,41>24,42、56,43>48,44>92,45>86,46>33）是否為堆，47、如果不48、是，49?則把它調(diào)整為堆。試給出堆排序方法在平均時間性能、最壞情況下的時間性能和輔助存儲量，50、并與快速排序方法在以上三方面進行比較。（8分）51、給出一組關(guān)鍵字T=（12,52、2,53、16,54>30,55、8,56、28,57>4,58、10,59>20,60、6,61、18）,62、設(shè)內(nèi)存工作區(qū)可容納4個記錄，6