動態(tài)存儲管理

新用戶請求分配內(nèi)存：一，系統(tǒng)繼續(xù)從地址的空閑中分配地址，直到無法分配，才回收不在使用的空閑塊。二，運(yùn)行結(jié)束，就把它所占的內(nèi)存釋放成空閑塊。

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

[[238295]]

查找

（面試筆試重點(diǎn)：

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

面試編程：折半查找；

面試經(jīng)常考：可能因?yàn)槲已芯可姆较蚴桥c數(shù)據(jù)查詢有關(guān)的，經(jīng)常被問到解決哈希沖突的方法，問的細(xì)了，還問各個(gè)的優(yōu)缺點(diǎn)，一般何時(shí)用）

基本術(shù)語：文件，記錄、字段（數(shù)據(jù)的最小單位）、關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字

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

動態(tài)查找表：若在查找的同時(shí)對表做修改運(yùn)算（如插入和刪除）

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

平衡二叉樹，二叉排序樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差1。

B樹：多路平衡查找樹，一種組織和維護(hù)外存文件系統(tǒng)非常有效的數(shù)據(jù)結(jié)構(gòu)。B-樹的查找過程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過程。B+樹是B-樹的一種變形，應(yīng)用更普遍。

平均查找長度ASL：確定數(shù)據(jù)元素在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。

哈希表：

別名：散列法，雜湊法或關(guān)鍵字地址計(jì)算法等，稱為哈希表或散列表。

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

構(gòu)造方法：直接定地址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、偽隨機(jī)數(shù)法

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

排序

（面試筆試重點(diǎn)，重中之重呀！！！！！：

筆試選擇題：一般偏概念，要熟練各個(gè)排序算法的步驟、時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性、會算移動次數(shù)等；

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

概念：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順序排列起來，使之按關(guān)鍵字遞增（0或遞減）有序排列。了解穩(wěn)定排序的意義

排序時(shí)間開銷：算法執(zhí)行中關(guān)鍵字比較次數(shù)和記錄移動次數(shù)來衡量。

內(nèi)部排序：待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲中進(jìn)行的排序過程。

外部排序：待排序記錄數(shù)量大，在排序過程中尚需對外存進(jìn)行訪問的排序過程。

方法分類：

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

交換排序：通過不斷比較相鄰元素大小，進(jìn)行交換來實(shí)現(xiàn)排序。冒泡排序、快排。

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

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

基數(shù)排序：通過“分配”和“收集”過程來實(shí)現(xiàn)排序，是一種借助于多關(guān)鍵字排序的思想對單關(guān)鍵字排序的方法。包括多關(guān)鍵字排序，鏈?zhǔn)交鶖?shù)排序，

各個(gè)排序算法比較：