為幫助大家備考軟考軟件設(shè)計(jì)師考試，希賽小編整理了軟件設(shè)計(jì)師考試知識(shí)點(diǎn)100條（9），希望對(duì)大家備考有幫助。

81、最優(yōu)二叉樹的概念

最優(yōu)二叉樹：又稱為哈弗曼樹，它是一類帶權(quán)路徑長度最短的樹。

路徑是從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的通路，路徑上的分支數(shù)目稱為路徑長度。

樹的路徑長度是從樹根到每一個(gè)葉子之間的路徑長度之和。結(jié)點(diǎn)的帶權(quán)路徑長度為從該結(jié)點(diǎn)到樹根之間的路徑長度與該結(jié)點(diǎn)權(quán)值的乘積。

樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。

82、二叉樹的遍歷操作

前序遍歷：又稱為先序遍歷，按根?左?右的順序進(jìn)行遍歷。

后序遍歷：按左?右?根的順序進(jìn)行遍歷。

中序遍歷：按左?根?右的順序進(jìn)行遍歷。

層次遍歷：按層次順序進(jìn)行遍歷。

83、圖的概念

完全圖

在無向圖中，若每對(duì)頂點(diǎn)之間都有一條邊相連，則稱該圖為完全圖（complete graph）。

在有向圖中，若每對(duì)頂點(diǎn)之間都有二條有向邊相互連接，則稱該圖為完全圖。

強(qiáng)連通圖：在有向圖中，對(duì)于每一對(duì)頂點(diǎn)，從頂點(diǎn)vi到頂點(diǎn)vj和從頂點(diǎn)vj到頂點(diǎn)vi都存在路徑，則稱為強(qiáng)連通圖。

84、圖的遍歷特點(diǎn)

深度優(yōu)先遍歷：

當(dāng)以鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n2)

當(dāng)以鄰接表作為存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度為O(n+e)

廣度優(yōu)先遍歷和深度優(yōu)先搜索遍歷圖的運(yùn)算時(shí)間復(fù)雜度相同，其不同之處僅僅在于對(duì)頂點(diǎn)的訪問次序不同。

85、算法特性

有窮性：執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。

確定性：算法中每一條指令都必須有確切的含義，不能含糊不清。

輸入（>=0）

輸出（>=1）

有效性(可行性)：算法的每個(gè)步驟都能有效執(zhí)行并能在執(zhí)行有限次后得到確定的結(jié)果。例如a=0，b/a就無效

86、常見算法策略

87、常見的對(duì)算法執(zhí)行所需時(shí)間的度量

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

88、常見排序算法對(duì)比

89、常見排序算法適用常見對(duì)比1

若待排序列的記錄數(shù)目n較小，可采用直接插入排序和簡單選擇排序。由于直接插入排序所需的記錄移動(dòng)操作較簡單選擇排序多，因而當(dāng)記錄本身信息量大時(shí)，用簡單選擇排序方法較好。

若待排記錄按關(guān)鍵字基本有序，宜采用直接插入排序或冒泡排序。

當(dāng)n很大且關(guān)鍵字位數(shù)較少時(shí)，采用基數(shù)排序較好。

若n很大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法，例如快速排序、堆排序或歸并排序：

快速排序目前被認(rèn)為是內(nèi)部排序中最好的方法，當(dāng)待排序的關(guān)鍵字為隨機(jī)分布時(shí)，快速排序的平均運(yùn)行時(shí)間最短；

堆排序只需要一個(gè)輔助空間，并且不會(huì)出現(xiàn)在快速排序中可能出現(xiàn)的最快情況。

快速排序和堆排序都是不穩(wěn)定的排序方法，若要求排序穩(wěn)定，可選擇歸并排序。

90、編譯與解釋的區(qū)別

編譯方式下機(jī)器上運(yùn)行的是與源程序等價(jià)的目標(biāo)程序，源程序和編譯程序都不再參與目標(biāo)程序的執(zhí)行過程，因此執(zhí)行時(shí)效率較高；

解釋方式下解釋程序和源程序（或某種等價(jià)表示）要參與到程序的運(yùn)行過程中，邊解釋邊執(zhí)行，執(zhí)行效率較低。

即：解釋方式，翻譯程序不生成獨(dú)立的目標(biāo)程序，而編譯方式則生成獨(dú)立保持的目標(biāo)程序。