計算機科學與技術考研 資料結構可能會問到的問題

總結了 涉及 計網 作業系統 資料結構 資料庫 軟體工程 程式語言等課程

個人覺得可能會問到的問題 部分問題過于簡單或抽象就不寫答案了

自己總結 漏洞疏忽可能比較多 口述答案

有錯告知會改正 勿噴

資料結構

1. 資料結構的三要素 ：實體結構 邏輯結構 運算
2. 資料結構的邏輯結構與實體結構分為

邏輯結構：順序存儲 鍊式存儲 索引存儲 散列存儲

實體結構：集合 線性 樹 圖

1. 算法的五大特征 :有窮性 确定性 可行性 輸入 輸出
2. 時間複雜度和空間複雜度是什麼 :語句執行頻度 占用記憶體空間
3. 什麼時候用連結清單 什麼時候用數組
4. 棧和隊列的定義 循環隊列的優點 使用率高 沒有假溢出
5. 樹的定義 二叉樹 滿二叉樹 完全二叉樹 存儲結構

最多隻有2個結點的樹 除了葉子結點外都有2個結點 和滿二叉樹的序号一緻

順序存儲 鍊式存儲

1. 二叉樹的非遞歸周遊

• 非遞歸先序周遊：1. 沿着根的左孩子，先通路，再入棧，直到左為空

  2. 棧頂出棧，有又子樹，1。

• 非遞歸中序周遊：

  一直左入棧，出棧看右孩，有則1 無則2

  1. 沿着根的左孩子依次入棧，直到左孩子為空

  2. 棧頂元素出棧并通路，右孩子為空繼續執行，若右孩子為空，接着入棧左孩子。

• 非遞歸後序周遊：

  1. 從根節點開始，入棧，沿着左子樹搜尋，直到沒有左孩子。

  2. 如果有右子樹，按同樣的方法通路。

  3. 棧頂元素為空，要麼右子樹為空，要麼右子樹剛被通路完。（左子樹已經被通路）

• 層次周遊：借助隊列 根節點，左右節點依次入隊。

1. 線索二叉樹 : 解決友善尋找某種序列的前驅
2. 哈弗曼樹 最優二叉樹 帶權路徑最小的二叉樹
3. 樹的表示方法 樹和森林的周遊

雙親表示法 孩子表示法 孩子兄弟表示法

二森先中樹先後

1. 二叉排序樹 删除二叉排序樹

左＜根節點＜右 中序周遊是升序

删除：

葉節點直接删

有一個孩子直接代替

有倆孩子 用直接前驅或者後繼

1. 圖的組成 圖的分類 什麼是連通 邊集和結點集
2. 圖的存儲方法

鄰接表法 鄰接矩陣法 十字連結清單法（有） 鄰接多重表（無）

1. 圖的深度優先周遊和廣度優先周遊 棧/隊列
2. 最小生成樹（詳細闡述）[貪心算法]

Prim算法：從某個頂點開始，依次加入目前結點集中路徑最短的結點到結點集中，直到把所有的結點都加入進去。不依賴與邊 時間複雜度O（V²） 适合稠密圖

Kruskal算法：從最短的邊開始，依次選擇最短符合條件的邊，直到所有的點都連通

不依賴與點 适合稀疏圖 時間複雜度O（Elog2E）

1. 最短路徑（詳細闡述）

迪傑斯特卡算法：引進兩個集合S和U。S的作用是記錄已求出最短路徑的頂點(以及相應的最短路徑長度)，而U則是記錄還未求出最短路徑的頂點(以及該頂點到起點s的距離)

(1) 初始時，S隻包含起點s；U包含除s外的其他頂點，且U中頂點的距離為"起點s到該頂點的距離"[例如，U中頂點v的距離為(s,v)的長度，然後s和v不相鄰，則v的距離為∞]。

(2) 從U中選出"距離最短的頂點k"，并将頂點k加入到S中；同時，從U中移除頂點k。

(3) 更新U中各個頂點到起點s的距離。之是以更新U中頂點的距離，是由于上一步中确定了k是求出最短路徑的頂點，進而可以利用k來更新其它頂點的距離；例如，(s,v)的距離可能大于(s,k)+(k,v)的距離。

弗洛伊德算法[動态規劃]：通過圖的權值矩陣，逐漸将各點作為中間結點，看是否會比之前的路徑更短。

1. 拓撲排序

由某個集合上的一個偏序得到該集合上的一個全序

應用于工程 或者 判斷有向圖是否有回路

1. 說一下堆 删除 插入 建堆

優先隊列：取出的元素順序是按照元素的優先權(關鍵字)大小,而不是元素進入隊列的先後順序。

優先隊列的實作

數組、有序數組

連結清單、有序連結清單

堆：必須是完全二叉樹 且任意一節點是其子樹的最大值或者最小值

3. 堆的操作

* 插入：插入到最後一個元素，然後與父節點（parent/2）作比較，大則交換

* 删除：把最後一個元素替補根的位置，

找出較大的孩子（2parent）（2parent+1）換位置。

* 建堆：1. 順序存入形成完全二叉樹

2. 從最小的子樹開始調整位置，使其左右子樹都變成堆

1. 折半查找與分塊查找

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列 O(log2n)

分塊查找

1. B樹與B+樹，差別

1. B樹：多路平衡查找樹 m路 （5）

   除了根節點外，任何節點至少有m/2個分叉 且關鍵字數要在[m/2-1,m-1] [2,4]

   所有子樹的高度都相同 所有的葉節點都出現在同一層次

2. B樹的操作

   1. 插入：滿了後 從中間裂開，把中間元素提到父節點，剩下元素放左右

   2. 删除：

   * 删非終端節點：把直接前驅或直接後繼替代該元素

   * 删終端節點且左/右兄弟充足 用前驅/後繼和的填補空缺

   * 當兄弟不夠了 合并

3. B+樹 :類似于分塊查找和b樹的結合 根節點指向放的是葉子節點的最大值

1. 哈希函數的構造方法 哈西函數解決沖突的方法 （Java HashSet？）

哈希表：關鍵字與存儲位址直接相關

沖突的處理方法：

1. 拉鍊法

2. 線性探測法

3. 平方探測法0 1 -1 4 -4 9 -9…

4. 再散列法 多個哈希函數

1. 排序有哪些 時空複雜度是多少

   

2. 什麼是分治算法 動态規劃 貪心算法 回溯算法

分治算法：将一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破

分治的技術問題：子問題互相獨立

分治算法的步驟：

1. 劃分

2. 遞歸求解

3. 合并

應用：

1. 二分查找

2. 快速排序

3. 歸并排序

動态規劃：把原始的問題劃分成一系列子問題，每求解一個子問題，将其結果存放在一個表中，以後用到的時候直接存取，不重複計算，自底向上的計算。[子問題的解要被重複利用] 自底向上

動态規劃的條件：

1. 優化子結構：一個問題的優化解包含了子問題的優化解，縮小問題的集合

2. 重疊子問題

應用：

1. 矩陣乘法

2. 最長公共子序列

3. 弗洛伊德Floyd算法

貪心算法：做出目前看來最好的選擇，希望通過做出局部優化達到全局優化

未必産生最優解 是自頂向下

貪心算法的條件：具有貪心選擇性 優化子結構

應用：

1. 克魯斯卡爾 Kruskal 每次選擇一條權值最小的邊，直到所有的點都連通

2. Prim算法： 從某個頂點開始，每次選擇代價最小的新頂點納入

3. 任務安排問題

4. 哈夫曼編碼

回溯算法：把問題的解空間轉化成了圖或者樹的結構表示，然後使用深度優先搜尋政策進行周遊，周遊的過程中記錄和尋找所有可行解或者最優解。

應用：

1. 背包問題

2. 旅行售貨員問題

3. 迷宮問題

1. 遞歸和非遞歸的優缺點

遞歸的好處：代碼相對非遞歸來說，更為簡潔，并且思路清晰。

遞歸的壞處：由于遞歸需要系統堆棧，是以消耗空間要比非遞歸大很多。并且，如果遞歸深度太深，可能會導緻系統奔潰。

非遞歸的優點：效率高，執行時間隻會因為循環的次數增加而增加，沒什麼額外開銷，也不會占用額外空間。

非遞歸的缺點：并不太容易了解，編寫複雜問題時比較困難。

1. 自底向上和自頂向下

↑ 自底向上的分析，是從具體到抽象；

↓ 自頂向下的分析，是從抽象到具體