2019北京計算機專碩844專業課真題回憶

todayswork · 發表于 2019-2-15 16:19

[芒果]綜合應用題（55分）
給一組數，用的是取余的求關鍵字方法，分別用線性探測法，除留余數法，鏈地址法，求查找成功ASL（15分）

給一組數，分別用二叉排序樹和二叉平衡樹求查找成功ASL給一組數，用小根堆法排序，寫出每一步步驟。(7分)

給一個圖分別用普里姆算法，克魯斯卡爾算法求最小生成樹，寫出每步步驟。

給一個無向圖，第一問寫出鄰接矩陣，第二問根據鄰接矩陣寫出深度優先搜索，第三問寫廣度優先搜索。

[芒果]算法題一共45分，三個大題每個15分。

寫出順序表和鏈表的定義類型，數據類型（3分好像），設計一個算法將含有n個元素的順序表轉換為帶頭結點的單鏈表（12分）

一共三問，第一問寫出孩子鏈表表示法定義類型，數據類型用戶自己定義；第二問，寫出求二叉樹上一個已知的結點的度的算法；第三問，設計一個算法求二叉樹的度。

給出二叉排序樹的結構體定義，設計一個算法實現二叉排序樹的插入，已知幾個指針（好像有父結點指針，指向當前結點的指針）

[芒果]選擇題有求時間復雜度，已知出棧第一個數i求第j個數什么時候出棧，

[芒果]填空題求棧的最小容量，算法的五個特性（什么輸入輸出正確性什么的），給了三個填兩個空。程序填空題，填三個空（折半查找的算法），帶頭結點的雙循環單鏈表為空的條件是什么，插入類排序除了有直接插入排序還有什么，哈夫曼樹的前綴碼已知已經有0，10問還可以表示幾個數，迪杰斯特拉算法是根據什么次序求最短路徑的，構建哈希表的三要素除了函數，表長還有什么。

其他的不知道了

來自Android客戶端