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

1、 線(xiàn)性： 線(xiàn)性表：插入（重點(diǎn)），刪除（重點(diǎn)）。棧，隊(duì)列，數(shù)組， 字符串，廣義表。循環(huán)鏈表和不循環(huán)鏈表注意是否帶表頭 數(shù)據(jù)結(jié)構(gòu) 以及循環(huán)結(jié)束條件。 非線(xiàn)性： 樹(shù)型：樹(shù)，二叉樹(shù)。樹(shù)的轉(zhuǎn)換（重點(diǎn)），樹(shù)的存儲(chǔ)結(jié)構(gòu)（孩子兄弟表示法） 圖： 深度優(yōu)先，廣度優(yōu)先，存儲(chǔ)結(jié)構(gòu)，最小生成樹(shù) 順序： 一維數(shù)組：插入，刪除平均移動(dòng)（n-1）/2 鄰接矩陣，三元組表。 存儲(chǔ)結(jié)構(gòu) 非順序結(jié)構(gòu)：線(xiàn)性鏈表，雙向鏈表，十字鏈表，二叉鏈表，逆鄰接表，鄰接多重表。 第一章緒論一定要注意黑體字的概念，每年都有幾分的填空?。?！

2、 增加分配空間的算法一定要注意成功或者不成功。 鏈隊(duì)列設(shè)鏈隊(duì)列指針目的是減少搜索 循環(huán)隊(duì)列注意空，滿(mǎn)的判斷。 關(guān)于棧的應(yīng)用看表達(dá)式求值。 數(shù)組下標(biāo)地址的計(jì)算（重點(diǎn)）：以行序?yàn)橹鞔鎯?chǔ)，以列序?yàn)橹鞔鎯?chǔ)。三對(duì)角列，下三角，上三角。 稀疏矩陣的表示方法：三元組表和十字鏈表，但是不要求其算法。 廣義表：其定義，頭，尾，注意區(qū)分頭，尾。 字符串：其定義，空串和空格串的區(qū)別。注意不要求模式匹配算法！ 二叉樹(shù)的性質(zhì)：5個(gè)結(jié)構(gòu) 一定要看每年都出題！?。? 二叉樹(shù)的遍歷：先，中，后序。由表達(dá)式變成二叉樹(shù)，由二叉樹(shù)變成表達(dá)式。 由前推表示寫(xiě)出后推表示。 線(xiàn)索二叉樹(shù)：三種不同線(xiàn)索樹(shù)，要會(huì)畫(huà)線(xiàn)索樹(shù)（

3、重點(diǎn)），中序遍歷非遞歸算法，后序遍歷非遞歸算法用棧兩次。 N個(gè)結(jié)點(diǎn)的二叉樹(shù)用N+1個(gè)棧，空指針進(jìn)棧。 哈夫曼樹(shù)，其編碼注意書(shū)中的例子。 二叉樹(shù)要求寫(xiě)算法：遍歷，搜索二叉樹(shù)某個(gè)結(jié)點(diǎn)，按層遍歷用隊(duì)列（復(fù)試考了） 這些算法一定要會(huì)！ 深度優(yōu)先遞歸算法變?yōu)榉沁f歸 最小生成樹(shù)（不是唯一的）：N個(gè)結(jié)點(diǎn)N-1個(gè)邊連通圖。最小生成樹(shù)的選邊和選點(diǎn)生成其代價(jià)和相等。 拓?fù)渑判颍ㄐ蛄胁晃ㄒ唬╆P(guān)鍵路徑（不唯一）：關(guān)鍵路徑上的活動(dòng)是關(guān)鍵活動(dòng)。 拓?fù)渑判蛩惴? 查找：順序查找，平均查找長(zhǎng)度（n+1）/2 設(shè)監(jiān)視哨額目的是減少一次比較。 折半查找：平均查找長(zhǎng)度（成功或者不成功），看書(shū)中的例子。 分塊查找

4、 二叉樹(shù)排序：動(dòng)態(tài)生成，查找，刪除 平衡二叉樹(shù)：四種變換方式，看書(shū)中的例子。 B－樹(shù)：5個(gè)定義，第五條葉子在同一層。重點(diǎn) 哈希表： 什么是哈希表，哈希表的查找，存取與關(guān)鍵字多少無(wú)關(guān)。 除留余數(shù)法――哈希表構(gòu)造 定義好的解決沖突方法：主要的兩種方法：開(kāi)放地址法，再哈希法。 排序：插入排序，希爾排序，縮小增量。選擇排序， 堆排序（重點(diǎn)）：算法，思想，建初始堆，次篩選法 歸并算法（兩兩合并）基數(shù)，快速排序（關(guān)鍵字已經(jīng)有序，沒(méi)有優(yōu)點(diǎn)）。 結(jié)束語(yǔ)：筆記我就記這些，這些內(nèi)容都是考試范圍內(nèi)的，把這些內(nèi)容看會(huì)了，你就可以得三位數(shù)的分?jǐn)?shù)，但是，你還需要看教材，把教材上的定義，算法看明白，教

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