以Niklus Wirth的觀點辰斋，程序等于什么?
程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法算法的重要特性
有窮性 確切性 輸入 輸出 可行性好算法的標(biāo)準(zhǔn)
正確性 可讀性 健壯性 高效率低存儲線性結(jié)構(gòu)的特點
（線性表的邏輯特性）
a. 只有一個表頭元素磨取，表頭元素沒有前驅(qū)
b. 只有一個表尾元素槽棍，表尾元素沒有后繼
c. 除表頭和表尾元素外蜡坊，其他元素只有一個直接前驅(qū)溢谤，也只有一個直接后繼線性結(jié)構(gòu)與非線性結(jié)構(gòu)的區(qū)別
線性結(jié)構(gòu)中的元素具有一對一的關(guān)系挺尾，而非線性結(jié)構(gòu)不是肥隆。
非線性結(jié)構(gòu)中，至少存在一個元素，他具有兩個或者兩個以上的前驅(qū)或后繼搀绣。列出所學(xué)過的線性結(jié)構(gòu)與非線性結(jié)構(gòu)
線性結(jié)構(gòu)：線性表飞袋，棧，隊列链患，串巧鸭，一維數(shù)組。
非線性結(jié)構(gòu)：樹麻捻，圖纲仍，廣義表，多維數(shù)組贸毕。頭指針郑叠、頭結(jié)點、首元結(jié)點的區(qū)別
a.頭指針：指向單鏈表的第一個結(jié)點的指針明棍。如果單鏈表有頭結(jié)點乡革，則頭指針指向頭結(jié)點；如果單鏈表沒有頭結(jié)點摊腋，則頭指針指向第一個首結(jié)點沸版。
b.頭結(jié)點：在單鏈表第一個元素結(jié)點之前設(shè)置的一個結(jié)點，數(shù)據(jù)域可以不存任何信息兴蒸，指針域指向單鏈表的第一個元素結(jié)點视粮。（為了操作方便，單鏈表一般都有）
c.首元結(jié)點：單鏈表中第一個存儲數(shù)據(jù)的結(jié)點橙凳。帶頭結(jié)點和不帶頭結(jié)點的線性鏈表的區(qū)別
A. 帶頭結(jié)點的線性鏈表馒铃，頭指針指向頭結(jié)點；不帶頭結(jié)點的線性鏈表痕惋，頭指針指向首元結(jié)點区宇。
B. 前者判空時，head->next == NULL;后者值戳，head == NULL
C. 在“增刪改查”操作中的區(qū)別：（在首元結(jié)點位置中议谷，存在差異）
a. 增：后者，插入到鏈表的開頭：
x->next = head; head = x;
插入到鏈表其他位置：(其中p為待插入位置的前一位)
x->next = p->next; p->next =x ;
b.刪：后者堕虹，刪除鏈表的開頭：
temp = head; head = head ->next; free(temp);
刪除鏈表的其他位置:(其中p為待刪除位置的前一位)
temp = p->next; p->next = temp ->next; free(temp);
單鏈表卧晓、雙鏈表、循環(huán)鏈表的區(qū)別及各自的優(yōu)缺點
A. 單向鏈表：每個結(jié)點中只包含“同一個方向上的”一個指針域
優(yōu)點：（相較于數(shù)組赴捞，鏈表的優(yōu)點）插入和刪除的時候不需要移動大量元素逼裆。
缺點：指針只能單方向移動。
B.雙向鏈表：每個結(jié)點有兩個指針域赦政，一個指向直接后繼胜宇，一個指向直接前驅(qū)耀怜。
優(yōu)點：查找直接前驅(qū)時桐愉，較單向鏈表方便，因有指針直接指向直接前驅(qū)
缺點：存儲密度低从诲，插入刪除操作需要修改多個指針域。
C.循環(huán)鏈表：最后一個結(jié)點的指針域指向頭結(jié)點
優(yōu)點：
缺點：棧和隊列是什么樣的線性表
棧和隊列是運算受限的線性表系洛，棧得先進后出俊性，隊列得先進先出。指出順序線性表磅废、順序棧荆烈、順序隊列的區(qū)別。
舉出幾個棧和隊列的實例及用棧和隊列所能解決的問題
隊列實例：“排隊買票”竟趾。棧實例：“握式子彈夾”
隊列能解決的問題：樹的層次遍歷憔购；解決主機與外部設(shè)備之間速度不匹配的問題（打印機與緩沖區(qū)）；解決由多用戶引起的資源競爭問題（CPU的資源競爭）玫鸟。
棧能解決的問題：后綴式求值犀勒；函數(shù)調(diào)用棧；指出通常解決隊列贾费，棧的溢出時所能用到的方法
隊列：循環(huán)隊列，鏈隊列
棧：鏈棧押桃，（多棧共享）循環(huán)隊列的循環(huán)是怎樣實現(xiàn)的
用取模運算實現(xiàn)循環(huán)給出對稱矩陣导犹、三角矩陣的節(jié)省內(nèi)存的存貯結(jié)構(gòu)并寫出相應(yīng)的輸入、輸出算法谎痢。
存貯結(jié)構(gòu)： 一維數(shù)組
對稱矩陣(下標(biāo)從1開始)： loc(aij) = loc(a11) +loc(i(i-1)/2 +j -1)L i>=j
loc(aij) = loc(a11) +loc(j(j-1)/2 +i -1)L i<j
下三角矩陣(下標(biāo)從1開始）： loc(aij) = loc(a11) +loc(i*(i-1)/2 +j -1)L i>=j
loc(aij) = 0 i<j
對角矩陣(三對角节猿，下標(biāo)從1開始)：loc(aij) = loc(a11)+(2i + j -3) i-1 <=j <= i+1給出稀疏矩陣的節(jié)省內(nèi)存的存貯結(jié)構(gòu)并寫出相應(yīng)的輸入、輸出算法
三元組表：
十字鏈表：用十字鏈表存貯稀疏矩陣時，矩陣的每個元素同時在幾條鏈上蝎亚，分別被稱為什么鏈先馆？
兩條鏈；行鏈和列鏈梅惯。
18.給出樹的不同的幾種表示形式
（1） 層次表示法 （2）廣義表表示法 （3）嵌套表示法 （4）凹入法表示法
在二叉樹的第i層上至多有多少個結(jié)點仿野，深度為K的二叉樹至多有多少個結(jié)點
2i-1 ; 2k-1在一顆二叉樹中,其葉子結(jié)點數(shù)n0和度為二的結(jié)點數(shù)n2之間的關(guān)系铣减。
n0 = n2 +1有n個結(jié)點的完全二叉樹的深度脚作。
depth = log2(向下取整) +1在二叉樹的順序存貯結(jié)構(gòu)中如何求結(jié)點的雙親、孩子劣针？
下標(biāo)從1開始 雙親： i/2（向下取整）
左孩子 2i
右孩子 2i+1有n個結(jié)點的二叉樹用二叉鏈表存貯時有多少個空鏈域亿扁，用三叉鏈表存貯時有多少個空鏈域。
n+1 襟己； n+2 牍陌；為什么可在不增加指針域的情況下，對二叉樹進行線索化毒涧，線索化的目的是什么链嘀？
因為二叉樹本身具有n+1個空鏈域。線索化是為了方便遍歷樹怀泊。對于已線索化的二叉樹如何識別指針域是指向孩子還是指向其后繼結(jié)點？
增加標(biāo)志域务傲。樹的幾種存貯結(jié)構(gòu)(雙親表示法、孩子表示法看杭、孩子兄弟表示法)的優(yōu)缺點挟伙，各自適應(yīng)的運算。
雙親表示法：便于查找雙親尖阔，但是找孩子難
孩子表示法：涉及孩子的操作容易介却，涉及雙親的難
孩子兄弟表示法：哪種存貯結(jié)構(gòu)可將森林轉(zhuǎn)為二叉樹。此種結(jié)構(gòu)各域的注釋齿坷。說明在這個結(jié)構(gòu)中怎樣找到森林的n棵樹。
孩子兄弟表示法崎场；左指針是第一孩子仰禀，右指針是兄弟（森林中樹的根結(jié)點的右指針為另一棵樹）蚕愤；根結(jié)點的第n代右孩子。樹的先根遍歷悬嗓、后根遍歷對應(yīng)其二叉樹的哪種遍歷裕坊，森林的先根遍歷、中根遍歷對應(yīng)其二叉樹的哪種遍歷周瞎？
樹和森林的先根遍歷對應(yīng)二叉樹的先序遍歷饵蒂；樹和森林的后序遍歷對應(yīng)二叉樹的中序遍歷。（在考研數(shù)據(jù)結(jié)構(gòu)中彼乌，森林的中根遍歷和后序遍歷是一回事）寫算法求樹中結(jié)點的度；樹的度慰照；樹中的葉子結(jié)點數(shù)；樹中的非終端結(jié)點數(shù)稚铣；樹中某結(jié)點的兄弟蝌衔、祖先、子孫曹锨、層次剃允、堂兄弟；樹的高度椒楣；森林中樹的數(shù)目牡肉。
Huffman樹能夠解決的問題是什么？
數(shù)據(jù)通信中的數(shù)據(jù)壓縮編碼問題何為完全圖毛俏、稀疏圖饲窿、稠密圖
完全圖(頂點數(shù)為n)：對有向圖來說，邊數(shù)為n(n-1);對無向圖來說阀溶，邊數(shù)為n(n-1)/2鸦泳；
稀疏圖：邊數(shù)較少的圖（e << n） （題目會規(guī)定額度）
稠密圖：邊數(shù)較多的圖寫算法求無向圖中結(jié)點的度；有向圖中結(jié)點的入度和出度做鹰。
無向圖：鄰接矩陣的一行或一列的數(shù)值和誊垢，代表對應(yīng)定點的度症见。
有向圖：鄰接矩陣的行代表對應(yīng)頂點的出度殃饿，列代表入度圖的數(shù)組表示法、鄰接表存貯結(jié)構(gòu)各自的優(yōu)缺點遵蚜，適應(yīng)的運算
圖的數(shù)組表示法（鄰接矩陣表示法）： 二維數(shù)組存儲圖
優(yōu)點：容易求各個頂點的度
缺點：當(dāng)圖為稀疏圖時浪費空間
圖的鄰接表表示法：
優(yōu)點：容易找到第一個鄰接點和下一個鄰接點-
最小生成樹的實際應(yīng)用背景
image.png
什么圖適合用Prim算法求最小生成樹奈惑，什么圖適合用Kruskal算法求最小生成樹肴甸。
Prim算法適用于稠密圖；Kruskal算法適用于稀疏圖原在。-
圖示用 Prim算法及 Kruskal算法求最小代價生成樹的過程庶柿。
Prim算法
Kruskal算法
舉例簡述“拓?fù)渑判颉彼鉀Q的實際問題
流程圖，施工流程圖梭域，課程決定的優(yōu)先權(quán)维苔。-
請圖示“拓?fù)渑判颉钡倪^程介时。
image.png
舉例簡述“關(guān)鍵路徑”所解決的實際問題沸柔。
一個工程的并行的進行過程
（1） 完成整個工程至少需要多少時間褐澎；
（2） 哪些活動是影響工程的關(guān)鍵工三。順序查找俭正、折半查找、分塊查找算法適合的關(guān)鍵字結(jié)構(gòu)串远。
順序查找對關(guān)鍵字是否有序無要求澡罚，但是基于時間復(fù)雜度問題留搔，關(guān)鍵字?jǐn)?shù)量應(yīng)該盡量小筐喳。（ASL1 = (n+1)/2 ; ASL2 = n）
折半查找要求關(guān)鍵字是有序的。（平均查找長度近似為log2(n+1) -1）
分塊查找要求塊與塊之間必須按照關(guān)鍵字大小有序排列荣月。怎樣從二叉排序樹得到有序表梳毙。
中序遍歷已知長度為n的表，按表中元素順序構(gòu)造二叉平衡樹萌业，圖示構(gòu)造過程奸柬。
在構(gòu)造二叉排序樹的過程中，每當(dāng)插入一個結(jié)點時抱婉，首先檢查是否因插入而破壞了樹的平衡性桌粉，如果是因插入結(jié)點而破壞了樹的平衡性，則找出其中最小不平衡子樹患亿，在保持排序樹特性的前提下押逼，調(diào)整最小不平衡子樹中各結(jié)點之間的連接關(guān)系惦界，以達到新的平衡咙冗。
-
各種查找算法的平均時間復(fù)雜度。
為一組關(guān)鍵字構(gòu)造哈希函數(shù)并建立哈希表瞬逊。
指出希爾排序仪或，歸并排序，快速排序蕾域，堆排序到旦，基數(shù)排序中穩(wěn)定的排序方法，并對不穩(wěn)定的舉出反例采呐。
穩(wěn)定的：歸并排序搁骑，基數(shù)排序。
不穩(wěn)定的反例：-
堆排序算法選用什么樣的存貯結(jié)構(gòu)煤率，按此算法得到的有序表是遞增還是遞減的乏冀。圖示建堆過程。
存貯結(jié)構(gòu)：完全二叉樹昼捍。
若是小頂堆就是遞增的众辨，若是大頂堆就是遞減的舷礼。
建堆過程：
image.png
藉助于“比較”進行排序的算法在最壞情況下能達到的最好的時間復(fù)雜度是什么?
n log2n指出直接插入排序，冒泡排序蛛株，快速排序，堆排序欢摄，基數(shù)排序算法各適合的關(guān)鍵字結(jié)構(gòu)笋粟。
直接插入排序：整個序列已經(jīng)基本有序。
冒泡排序：整個序列已經(jīng)基本有序绿淋。
快速排序：待排序列越接近無序尝盼，本算法效率越高。（越接近有序裁赠，本算法效率低）
堆排序：堆排序適合的場景是關(guān)鍵字?jǐn)?shù)很多的情況赴精，典型的例子是從10 000個關(guān)鍵字中選出前10個最小的。
基數(shù)排序：基數(shù)排序適合的場景是序列中的關(guān)鍵字字?jǐn)?shù)很多失尖，但組成關(guān)鍵字的取值范圍較小掀潮，如數(shù)字0~9是可以接受的。指出各種排序算法的平均時間復(fù)雜度薯鼠、最壞情況的時間復(fù)雜度出皇。
請對學(xué)習(xí)<<數(shù)據(jù)結(jié)構(gòu)>>這門課程進行全面總結(jié)。
