清華大學 - 話題

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

北京在中國地圖的東南西北哪個方向？（答案為一個字）

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