動態存儲管理

新用戶請求分配內存：一，系統繼續從地址的空閑中分配地址，直到無法分配，才回收不在使用的空閑塊。二，運行結束，就把它所占的內存釋放成空閑塊。

分配策略：***擬合發，***擬合法（適用最廣），最差擬合法。

[[238295]]

查找

（面試筆試重點：

筆試選擇題、簡答題都有，要會畫查找的哈希表、會計算平均查找時間；

面試編程：折半查找；

面試經常考：可能因為我研究生的方向是與數據查詢有關的，經常被問到解決哈希沖突的方法，問的細了，還問各個的優缺點，一般何時用）

基本術語：文件，記錄、字段（數據的最小單位）、關鍵字、主關鍵字、次關鍵字

靜態查找表：查詢某個特定的元素是否在表中；檢索某個特定的元素的各種屬性。查找方法為順序查找、折半查找、索引順序表查找

動態查找表：若在查找的同時對表做修改運算（如插入和刪除）

二叉排序樹，有序表，和折半查找類似；中序遍歷此樹得到有序序列

平衡二叉樹，二叉排序樹中每個結點的左、右子樹的高度至多相差1。

B樹：多路平衡查找樹，一種組織和維護外存文件系統非常有效的數據結構。B-樹的查找過程是一個順指針查找結點和在結點的關鍵字中進行查找交叉進行的過程。B+樹是B-樹的一種變形，應用更普遍。

平均查找長度ASL：確定數據元素在表中的位置，需和給定值進行比較的關鍵字個數的期望值。

哈希表：

別名：散列法，雜湊法或關鍵字地址計算法等，稱為哈希表或散列表。

基本思想，p=H(key),H稱為哈希函數，是從關鍵字空間到存儲地址空間的一種映射。

構造方法：直接定地址法、數字分析法、平方取中法、折疊法、除留余數法、偽隨機數法

處理沖突的方法：開放地址法（線性探測再散列，二次探測再散列，隨機探測在散列）、在hash法、建立公共溢出區、鏈地址法

排序

（面試筆試重點，重中之重呀！！！！！：

筆試選擇題：一般偏概念，要熟練各個排序算法的步驟、時間復雜度、空間復雜度、穩定性、會算移動次數等；

面試經常考：現場編程，讓寫過遞歸與非遞歸的快排、遞歸與非遞歸的歸并排序、堆排序，所以這章真的真的很重要）

概念：將一組雜亂無章的數據按一定的規律順序排列起來，使之按關鍵字遞增（0或遞減）有序排列。了解穩定排序的意義

排序時間開銷：算法執行中關鍵字比較次數和記錄移動次數來衡量。

內部排序：待排序記錄存放在計算機隨機存儲中進行的排序過程。

外部排序：待排序記錄數量大，在排序過程中尚需對外存進行訪問的排序過程。

方法分類：

插入排序：將待排序記錄按其關鍵字大小插入到前面已經排好序的子表中的適當位置，知道全部插入完全為止。包括：直接插入排序、折半插入排序、2-路插入排序、表插入排序、希爾排序（縮小增量排序，多趟）。主要應用“比較”和“移動”。

交換排序：通過不斷比較相鄰元素大小，進行交換來實現排序。冒泡排序、快排。

選擇排序：每一趟都選出一個***或最小的元素，并放在合適的位置。有簡單選擇排序、樹形選擇排序、堆排序。

歸并排序：將2個或兩個以上的有序表合成一個新的有序表。

基數排序：通過“分配”和“收集”過程來實現排序，是一種借助于多關鍵字排序的思想對單關鍵字排序的方法。包括多關鍵字排序，鏈式基數排序，

各個排序算法比較：