《哈爾濱工程大學(xué) 數(shù)據(jù)結(jié)構(gòu) 考研筆記》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈爾濱工程大學(xué) 數(shù)據(jù)結(jié)構(gòu) 考研筆記（2頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 線性： 線性表：插入（重點(diǎn)），刪除（重點(diǎn)）。棧，隊(duì)列，數(shù)組，字符串，廣義表。循環(huán)鏈表和不循環(huán)鏈表注意是否帶表頭數(shù)據(jù)結(jié)構(gòu) 以及循環(huán)結(jié)束條件。非線性： 樹型：樹，二叉樹。樹的轉(zhuǎn)換（重點(diǎn)），樹的存儲(chǔ)結(jié)構(gòu)（孩子兄弟表示法）圖： 深度優(yōu)先，廣度優(yōu)先，存儲(chǔ)結(jié)構(gòu)，最小生成樹 順序： 一維數(shù)組：插入，刪除平均移動(dòng)（n-1）/2鄰接矩陣，三元組表。存儲(chǔ)結(jié)構(gòu)非順序結(jié)構(gòu)：線性鏈表，雙向鏈表，十字鏈表，二叉鏈表，逆鄰接表，鄰接多重表。第一章緒論一定要注意黑體字的概念，每年都有幾分的填空！增加分配空間的算法一定要注意成功或者不成功。鏈隊(duì)列設(shè)鏈隊(duì)列指針目的是減少搜索循環(huán)隊(duì)列注意空，滿的判斷。關(guān)于棧的應(yīng)用看表達(dá)式求值。數(shù)

2、組下標(biāo)地址的計(jì)算（重點(diǎn)）：以行序?yàn)橹鞔鎯?chǔ)，以列序?yàn)橹鞔鎯?chǔ)。三對(duì)角列，下三角，上三角。稀疏矩陣的表示方法：三元組表和十字鏈表，但是不要求其算法。廣義表：其定義，頭，尾，注意區(qū)分頭，尾。字符串：其定義，空串和空格串的區(qū)別。注意不要求模式匹配算法！二叉樹的性質(zhì)：5個(gè)結(jié)構(gòu) 一定要看每年都出題！二叉樹的遍歷：先，中，后序。由表達(dá)式變成二叉樹，由二叉樹變成表達(dá)式。由前推表示寫出后推表示。線索二叉樹：三種不同線索樹，要會(huì)畫線索樹（重點(diǎn)），中序遍歷非遞歸算法，后序遍歷非遞歸算法用棧兩次。N個(gè)結(jié)點(diǎn)的二叉樹用N+1個(gè)棧，空指針進(jìn)棧。哈夫曼樹，其編碼注意書中的例子。二叉樹要求寫算法：遍歷，搜索二叉樹某個(gè)結(jié)點(diǎn)，按層遍

3、歷用隊(duì)列（復(fù)試考了） 這些算法一定要會(huì)！深度優(yōu)先遞歸算法變?yōu)榉沁f歸最小生成樹（不是唯一的）：N個(gè)結(jié)點(diǎn)N-1個(gè)邊連通圖。最小生成樹的選邊和選點(diǎn)生成其代價(jià)和相等。拓?fù)渑判颍ㄐ蛄胁晃ㄒ唬╆P(guān)鍵路徑（不唯一）：關(guān)鍵路徑上的活動(dòng)是關(guān)鍵活動(dòng)。拓?fù)渑判蛩惴ú檎遥喉樞虿檎?，平均查找長度（n+1）/2 設(shè)監(jiān)視哨額目的是減少一次比較。折半查找：平均查找長度（成功或者不成功），看書中的例子。分塊查找二叉樹排序：動(dòng)態(tài)生成，查找，刪除平衡二叉樹：四種變換方式，看書中的例子。B樹：5個(gè)定義，第五條葉子在同一層。重點(diǎn)哈希表： 什么是哈希表，哈希表的查找，存取與關(guān)鍵字多少無關(guān)。除留余數(shù)法哈希表構(gòu)造定義好的解決沖突方法：主要的兩

4、種方法：開放地址法，再哈希法。排序：插入排序，希爾排序，縮小增量。選擇排序，堆排序（重點(diǎn)）：算法，思想，建初始堆，次篩選法歸并算法（兩兩合并）基數(shù)，快速排序（關(guān)鍵字已經(jīng)有序，沒有優(yōu)點(diǎn)）。結(jié)束語：筆記我就記這些，這些內(nèi)容都是考試范圍內(nèi)的，把這些內(nèi)容看會(huì)了，你就可以得三位數(shù)的分?jǐn)?shù)，但是，你還需要看教材，把教材上的定義，算法看明白，教材中的第8章和第12章不考，畫星號(hào)的章節(jié)不考，所有遞歸算法不考，切記！04年的數(shù)據(jù)結(jié)構(gòu)與以往的三年相比難度增大了不少，我遇測(cè)05年的試題難度會(huì)維持在這個(gè)水平。還有，你應(yīng)該把近三年的試題做一遍，從試卷中可以發(fā)現(xiàn)你知識(shí)點(diǎn)的疏漏。后記：在復(fù)習(xí)過程中歷年的試題是非常重要的，可以體現(xiàn)出出題老師的思想，哈工程數(shù)據(jù)結(jié)構(gòu)出題老師是 鄂玉章！凡是在試題中不會(huì)的知識(shí)點(diǎn)一定要查教材，弄清楚。近三年的試題都會(huì)有一些重復(fù)的，有的是把選擇題變成了判斷題，有的是把選擇題變成了填空題！請(qǐng)記住一定要把歷年試卷做會(huì)。關(guān)于本筆記的說明： 本人參加了2004年研究生考試并被哈爾濱工程大學(xué)計(jì)算機(jī)系錄取。為了回報(bào)KAOYAN.COM對(duì)我的幫助，一些網(wǎng)友對(duì)我的支持，我把參加專業(yè)課輔導(dǎo)班的筆記打了出來，與廣大的考研戰(zhàn)友分享。 本筆記是由東北林業(yè)大學(xué)蒼松翠柏站創(chuàng)作的，所以，筆記的版權(quán)歸蒼松翠柏站所有，請(qǐng)不要改動(dòng)版權(quán)說明，謝謝合作。2