浙江工業大學 843 數據結構（c語言版）2008真題回憶 +考試技巧

王爽

浙江工業大學 843 數據結構（c語言版）_2008真題回憶

試卷滿分150分 一共兩個題型

一-簡答題（10*10=100分）
1、怎樣評價一個算法（5個方面，嚴老的書上有的）
2、樹和森林的轉畫（只要畫圖即可）
3、已知二叉樹的先根和中根，畫出該二叉樹（這題和07年真題上的第4題很相似，我待會會貼上07真題）
4、寫出棧的變化過程（就是下面這個題）
計算算術表達式的值時，可用兩個棧作輔助工具。對于給出的一個表達式，從左向右掃描它的字符，并將操作數放入棧S1中，運算符放入棧S2中，但每次掃描到運算符時，要把它同S2的棧頂運算符進行優先級比較，當掃描到的運算符的優先級不高于棧頂運算符的優先級時，取出棧S1的棧頂和次棧頂的兩個元素，以及棧S2的棧頂運算符進行運算將結果放入棧S1中（得到的結果依次用T1、T2等表示）。為方便比較，假設棧S2的初始棧頂為®（®運算符的優先級低于加、減、乘、除中任何一種運算）。現假設要計算表達式： A-B*C/D+E/F。寫出棧S1和S2的變化過程。
5、是關于串的一些函數的功能是什么 當然考題是一個程序 叫你閱讀結果（這題和07年真題上的第6題很相似，我待會會貼上07真題）
6、矩陣存儲方面的（主要是那個公式，認真看過教材的那個題目算的出來 沒什么大問題的）
7、廣義表 求HEAD（（（）））好幾層括號的 （考試時候千萬別緊張，看清楚，不然錯了，很可惜 因為這個是送分的）
8、給你一個圖，畫出其存儲結構（鄰接矩陣，鄰接表，逆鄰接表）（這題和07年真題上的第8題很相似，我待會會貼上07真題）
9、最優二叉樹，哈夫曼樹（你要看的出來模型）題目沒那么直接說就 想的進去就很快的（考場上的時候可以靜心想想出題的考點是什么，問題就迎刃而解了。）
10、哈希表 試卷上表格已經給考生畫好了，只需填好就OK了，當然過程最好寫下，萬一我們填錯了沒過程就慘拉~~。（這題和07年真題上的第7題很相似，我待會會貼上07真題）

二、算法設計題（10+12+12+16=50分）
1、關于循環隊列的（這個是他們本科生的期末考試原題，可見如果即將考研的你條件無論允許否 都要盡力搞到他們專業課的內部資料 最重要的是真題 當然本科試卷有是最好不過的了，哈哈~~）
2、寫出冒泡排序的算法（是嚴老書上的原程序，可見以本為本很重要）
3、一個單鏈表的程序（書上的插入結點的程序稍微改了下）
4、關于隊列的問題 考后發現這個題目也是很經典的 很多高校研究生入學考試的時候也曾采用過，他們是【西安電子科技大學2001軟件五(10分)】【上海交通大學1999 二(12分)】【河海大學1998 三(12分)】【浙江工業大學2008 二(16分)】
題目是： 請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運算來實現該隊列的三個運算：enqueue:插入一個元素入隊列； dequeue:刪除一個元素出隊列；queue_empty：判隊列為空。（請寫明算法的思想及必要的注釋）


考研業務課應考總結：
1、看好指定教材，最好過下相應的習題集（這里推薦嚴老師的，不過上面的題目要自己選會挑，太難的有些是一定不會考的）
數據結構好書：李春葆/朱站立/徐孝凱/這幾個作者的都不錯的，而且都有相應的習題集，是我為大家精心挑選過的哦，也是大家公認的比較好的。
2、做好真題（上面相似的題目我都標注出來了，而且這才是07年一年呢），本校生期末題的大題也看看（因為數據結構考研一般沒選擇的）不過提醒下 象二叉樹畫圖這類題 很多就是選擇題。
3、如果公共課實在緊張，不想 給專業課太多時間，那只好搞到他們的PPT上面確實很經典的，老師都有他們的風格，應付考研很奏效的。
最后，就是考前好好翻看一下做過的，適當做做總結，想想知識點，考點，因為工科專業課有題量不多分值大的特點，很多題目都是有情景的，只要你抓住了考點，就可以以不變應萬變了。
只要堅持，勝利就一定屬于你們，09年考研的朋友們！

PS：附件是07真題

王爽