清華大學(xué) - 話題

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

一周有幾天？（答案為數(shù)字）

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