華電計算機專碩數據結構844真題回憶版

daxiaozuozuo · 發表于 2014-12-30 18:17

忙著補這一學期的作業，總算寫完了，就趕快把真題回憶下整理出來。共5道大題，
第一題選擇，10道題20分，很簡單，比王道上的題要簡單的多把王道的題做了，選擇基本沒問題。
第二題填空題10空20分，也很簡單，數據存儲類型為〔〕〔〕，存儲數據即要存儲〈〉還要存儲〈〉，循環隊列是為了〈〉，給出一組數據和散列函數求與28是同義詞的是〈〉，還有一空求葉子節點數的，最后三空不記了。
第3題簡答15分5問，
1有向圖和無向圖使用鄰接矩陣和鄰接表存儲時的邊數。
2有向圖和無向圖使用鄰接矩陣和鄰接表存儲時的度的度。
3和1.2一樣但求的是什么不記了。
4也不記了但很簡單，
5解釋哈西表查找時同義詞的概念，什么是沖突。
第4題算法題55分4道題5小問。
1.1一組數據使用鍵表存儲，設計算法判斷數據是否有序，升序返回1降序返回-1無序返回0，
1.2將鍵表中的奇數偶數分別存儲在兩個新的鏈表中，
2輸出二叉樹中序遍歷的逆序。
3.設計算法判斷一個圖的連通性。
4.不記了。
第5題40分兩道大題都很簡單。
1給出了一組數據，求：
1.1畫出二叉排序書，
1.2插入數據11后的二叉排序樹，
1.3刪除數據13后的二叉排序樹，
1.4求這顆二叉排序樹的平均成功查找長度，設每個數據查找概率相同。
2給出了一個圖的鄰接表存儲。
2.1畫出這個圖。
2.2畫出用普里姆算法生成的最小生成樹
2.3畫出用克魯斯卡爾算法生成的最小生成樹。
2.4不記了，但很簡單。
最后給大家些建議：卷子中除了算法題外，其他都很簡單。建議大家多看算法，主要是鍵表，樹，圖（主要是深度優先和廣度優先遍歷算法）。
另外考試大綱上沒有寫哈西表，但實際會考。今年有兩小題共5分考哈西表。最后說一句：考研的路很漫長，如果選擇了，希望大家堅持到底，尤其到了10份以后更要堅持。祝學弟們考研成功！

來自Android客戶端