DS(50分）
一。（15分）回答下列各題，并簡要說明理由，每題3分
1。什么是線形表？線形表的各元素類型是否必須是同一類型？為什么？
2。線形表有兩種不同的繼承形式，順序的和鏈接的存儲結(jié)構(gòu)，
在使用時，如何確定使用哪種存儲結(jié)構(gòu)
3。給出一個二*樹的前序和中序遍歷序列，要求寫出后序遍歷序列。
4。（記不清楚具體數(shù)字了，大概的數(shù)字把）
一個文件用B+樹做索引，給定文件大小2000000 B，每個頁塊大小為4000 B,
每個指針大小為5 B。每個記錄是200 B,其中關鍵碼為5 B
問：
1）應采用多少階B+樹?
2)該文件索引塊數(shù)目。
5。下列哪些可以做Hash函數(shù)？哪些效果不好？哪些效果好？其中，n為Hash表的表長；Random(n)可以產(chǎn)生一個0---n=1 的隨機數(shù)
p(n)為小于n的最大素數(shù)。
1）Hash(key) = key/n;
2) Hash(key) = 1;
3) Hash(key) = (key + Random(n)) % n;
4) Hash(key) = key % p(n);
二。（5分
證明：一棵二*樹的前序，中序，后序遍歷序列中，葉結(jié)點的相對位置是不變的
三。（15分）
1）
給定一組關鍵碼，要求依次插入建立一棵AVL樹，大約12個關鍵碼左右，（和03年那個真題只是關鍵碼的不同）需要旋轉(zhuǎn)的時候，要求標出旋轉(zhuǎn)的類型：左單旋，右單旋，先左后右雙旋，先右后
左雙旋。
2）在建成的這棵AVL樹上，依次刪除關鍵碼****（四個），要求：如果需要旋轉(zhuǎn)，那要標出旋轉(zhuǎn)類型；用中序的直接前驅(qū)代替關鍵碼
四。（15分）
將書上284頁的Dijkstra算法挖去5個空，讓添。（5分）具體字母有差別，但是確實就是那個算法，我按照書上的來了。

在中國5月1日是什么節(jié)？（答案為兩個字）

考研論壇提示：
1、請勿發(fā)布個人聯(lián)系方式或詢問他人聯(lián)系方式，包括QQ和手機等。
2、未經(jīng)允許不得發(fā)布任何資料出售、招生中介等廣告信息。
3、如果發(fā)布了涉及以上內(nèi)容的話題或跟帖，您在考研網(wǎng)的注冊賬戶可能被禁用。