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

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

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

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

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

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

82、二叉樹的遍歷操作

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

后序遍歷：按左?右?根的順序進行遍歷。

中序遍歷：按左?根?右的順序進行遍歷。

層次遍歷：按層次順序進行遍歷。

83、圖的概念

完全圖

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

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

強連通圖：在有向圖中，對于每一對頂點，從頂點vi到頂點vj和從頂點vj到頂點vi都存在路徑，則稱為強連通圖。

84、圖的遍歷特點

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

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

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

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

85、算法特性

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

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

輸入（>=0）

輸出（>=1）

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

86、常見算法策略

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

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

88、常見排序算法對比

89、常見排序算法適用常見對比1

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

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

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

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

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

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

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

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

編譯方式下機器上運行的是與源程序等價的目標程序，源程序和編譯程序都不再參與目標程序的執(zhí)行過程，因此執(zhí)行時效率較高；

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

即：解釋方式，翻譯程序不生成獨立的目標程序，而編譯方式則生成獨立保持的目標程序。