自考數(shù)據(jù)結(jié)構(gòu)02331知識點(diǎn)

《自考數(shù)據(jù)結(jié)構(gòu)02331知識點(diǎn)》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、1、二叉樹并非是樹的特殊情形，它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。2、在有序樹中，雖然一個結(jié)點(diǎn)的孩子之間是有左右次序的，但是若該結(jié)點(diǎn)只有一個孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個孩子也有左右之分。3、在直接插入排序中，每次取出的未排序數(shù)字是從后往前依次比較的。如：對于記錄(54,38,96,23,15,72,60,45,83)，當(dāng)把第7個記錄60插入時，需比較3次。解：前6個已排序好記錄15,23,38,54,72,96，所以從后往前要比較96,72和54。在快速排序中，前后的i和j是從后面的j開始比較的，比較者不動，被替換者后(前)移如：對于記錄(51,22,83,46,75,18,6

2、8,30)解：第一趟劃分：哨兵R[0]=i=51,先從j=30比較，30<51,30替換51，i=22，i≯51，后移i=83,83>51,83替換30，j=68，依次繼續(xù)。冒泡排序中，最好與最壞時間復(fù)雜度不相同。無論待排序列是否有序(即不受數(shù)據(jù)初始狀態(tài)影響)，時間復(fù)雜度都是O(n2)的排序算法是直接選擇排序。記錄關(guān)鍵字比較次數(shù)與記錄的初始排列次序無關(guān)的是直接選擇排序。在待排序的記錄關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是直接插入排序，效率最低的是快速排序。2013.1.23對同一個基本有序的待排序序列分別進(jìn)行堆排序、快速排序和冒泡排序，最省時間的是4、對于哈夫曼編碼，應(yīng)該先構(gòu)造哈夫

3、曼樹：每次取權(quán)值最小的兩個結(jié)點(diǎn)(包含新生成的結(jié)點(diǎn))放一起生成新結(jié)點(diǎn)。至于左右孩子之分，按照編碼字出現(xiàn)的先后順序去決定(還是左小右大)。關(guān)于哈夫曼樹的一些解釋：哈夫曼樹不唯一，和你左右子樹的編碼有關(guān)。但最小帶權(quán)路徑長度唯一。你記住每次都是從集合中尋找兩個最小元素，權(quán)值相加之后形成的那個元素得重新放入集合參與新的比較。遞歸下去生成的樹才沒有問題，否則弄不好就是一個單枝樹上去了。你最好采取我建議的規(guī)則，自己設(shè)置一個優(yōu)先級。譬如你新生成的節(jié)點(diǎn)的權(quán)值和原集合的某各節(jié)點(diǎn)的權(quán)值相等的時候。新生成的節(jié)點(diǎn)具有高結(jié)合優(yōu)先級。這樣便于做出和標(biāo)準(zhǔn)答案一致的解。5、堆排序中的初始堆就是第一次將最大值放在根上的堆，然后

4、才是第一次、第二次重建堆。線性探查法的散列表6、對稱矩陣中的上三角是右上三角，下三角是左下三角。如果二叉樹的每個非葉結(jié)點(diǎn)都有非空的左子樹和右子樹，那么這樣的二叉樹稱為嚴(yán)格二叉樹。7、三元組表的行表：每一行矩陣的非零元素在三元組表的起始位置。8、隊列的隊尾指針rear指向隊尾元素的下一個位置。9、采用鄰接矩陣存儲有向圖，則結(jié)點(diǎn)k對應(yīng)的入度等于A中結(jié)點(diǎn)k對應(yīng)的列元素之和。10、棧頂指針指的是棧頂元素，順序循環(huán)隊列的隊尾指針始終指向隊尾元素的下一個位置。鏈隊列不區(qū)分普通和循環(huán)，鏈隊列的尾指針指的就是隊尾的元素。注意頭結(jié)點(diǎn)和隊頭結(jié)點(diǎn)的區(qū)別，p78頁。鏈隊列一般是不帶頭結(jié)點(diǎn)的，但和單鏈表類似，為了簡化

5、邊界條件的處理，在隊頭結(jié)點(diǎn)之前也附加一個頭結(jié)點(diǎn)，并設(shè)隊頭指針指向此結(jié)點(diǎn)。鏈?zhǔn)酱鎯Φ臈?，其鏈頭即為棧頂。11、循環(huán)隊列當(dāng)前元素個數(shù)公式（rear-front+m）%m，其中+m的意義是有可能rear已經(jīng)跑到了front前面的小數(shù)字，所以要+m。12、哈夫曼樹編碼樹上的0和1是在分支上，不是在結(jié)點(diǎn)上，一定要記住，不然就會陷入迷茫。13、前序遍歷一棵樹等價于前序遍歷該樹對應(yīng)的二叉樹，后序遍歷一棵樹等價于中序遍歷該樹對應(yīng)的二叉樹。14、兩個算法沒有什么太多的聯(lián)系，只能說是想法類似，都用了一定程度的貪心思維。最短路徑是要求一點(diǎn)到另外的點(diǎn)的最短路徑，只要最短的長度到達(dá)就好，除了出發(fā)點(diǎn)和終點(diǎn)外一概不管。如

6、果不求一點(diǎn)到所有點(diǎn)的最短路，甚至可以不管所有點(diǎn)是否都聯(lián)通。最小生成樹則要保證第一所有點(diǎn)都是聯(lián)通的，不然就稱不上是樹了，而后保證樹的邊長度之和最小。15、任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。16、為了克服順序存儲分配固定空間所產(chǎn)生的溢出和空間浪費(fèi)問題?？刹捎面?zhǔn)酱鎯Y(jié)構(gòu)來存儲棧。鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。其插入和刪除操作進(jìn)限制在表頭（棧頂）位置。17、用普里姆算法和克魯斯卡爾算法構(gòu)造的最小生成樹，所得到的最小生成樹可能相同，也可能不同。這是由于最小生成樹不唯一。18、二叉排序樹的插入一定是個葉子節(jié)點(diǎn)。19、線索二叉樹中的

7、線索是指指針。20、一個圖的鄰接矩陣表示唯一，鄰接表表示不唯一。21、稀疏矩陣在用三元組表示時，還必須將稀疏矩陣的總行數(shù)、總列數(shù)和非零元素個數(shù)作為三元組的輔助屬性加以說明。所以它的存儲還要在加上三個整數(shù)的位置。