清華大學 - 話題

[CS]04考題回憶v0.1

數據結構:
一. 判斷
總共十小題，隔的太久，詳細的內容記不清了，好像第一題是說線性表的各項類
型必須相同？還考了幾道關于圖的概念題（整張卷子就這里提到了圖），不是很難
，比較基礎的說。

二.從C++語法和軟件工程的角度判斷程序片斷的對錯，有則改之。

這個題型以前沒有出現過，我自己也做的糊里糊涂，總共5題，只有一道記得比
較深刻(大概意思如下)

type retvalue (type *p) //時間長了，有可能有些地方不對

{

if(p == null ) return 0;

return *p;

}

這個函數的意思是根據返回值自動判斷指針p是否為空，我覺得應該是錯的，如
果p指向的值為0 ，那么就判斷的有問題了

三.關于樹的遍歷的填空題。應該是03年或者02的第一大題的最后一道小題，由根結
點的中序遍歷的序號，填寫根結點左子樹和右子樹根節點的中序遍歷序號。

四.關于線索樹遍歷的程序題，共兩小題。具體的題目記不太清了，好像是由中序線
索樹推倒前序遍歷的next()函數？第二個是接著第一題問的，由next函數寫出全部
的前序遍歷？

五.關于排序的問答題。那段程序是shell排序（縮減增量排序？）的一個變種，第
一小題回答是什么排序，第二小題根據一個實際的排序例子寫出排序過程中一趟的
詳細情況,比較簡單吧。

六.關于程序復雜度的計算題。大意是一個O(n2)的排序算法，20個數據時時間是t1
,那么200個數據時時間是多少？我感覺這道題要么出得很弱，要么難得沒人能做得
出來，hiahia

七.算法題。根據一個實現隊列功能的類提供的操作模擬一個棧，好像是書上的一個
習題吧？

操作系統:

一.名詞解釋，還算比較基本吧，如果把清華出的那本操作系統書上的習題部分看一
遍就沒什么大問題了，好像考了一道“進程和線程的區別”？

二.有關進程調度的問題，也是比較基本吧，像輪轉，先來先服務，優先級，最短時
間優先等算法都考到了，并且結合了一個具體的例子，寫出每種算法情況下的cpu執
行過程.

三.一個有關磁盤讀寫次數的問題，它是和文件系統的索引部分和起來考的，大意是
考察不建索引和建了索引的訪問過程與訪問次數(好像清華以前沒考過類似的問題，不過
北大考過)

四.pv操作。標準的寫者優先前提下的讀者寫者問題。第四版上有詳細的說明。

五.關于存儲系統的訪問的一個問答題，和分頁的知識混在了一起。大意是描述怎樣
通過頁表，cache,磁盤 進行尋址？

11能被5整除嗎？

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