計(jì)算機(jī)基礎(chǔ)知識(shí) - 岳陽(yáng)電大

1、輔導(dǎo)教師：劉文英數(shù)據(jù)結(jié)構(gòu)（本）期末復(fù)習(xí)和例題選講課程教學(xué)基本要求1掌握常用的數(shù)據(jù)結(jié)構(gòu)的邏輯關(guān)系、存儲(chǔ)結(jié)構(gòu)、操作特點(diǎn)及有關(guān)應(yīng)用。2掌握迭代、遞歸等程序設(shè)計(jì)技術(shù)，了解他們與相關(guān)的數(shù)據(jù)結(jié)構(gòu)的關(guān)系。3掌握常用的查找、排序算法的基本原理和實(shí)現(xiàn)步驟。4能有效合理地利用所學(xué)數(shù)據(jù)結(jié)構(gòu)，程序設(shè)計(jì)技術(shù)和相關(guān)算法解決簡(jiǎn)單實(shí)際應(yīng)用問(wèn)題。5了解數(shù)據(jù)結(jié)構(gòu)在后續(xù)課程中的作用。 登錄三級(jí)平臺(tái)登錄中央電大課程討論打開(kāi)中央電大開(kāi)放教育在線平臺(tái)（）登錄（學(xué)號(hào)為中央電大學(xué)號(hào)，如：20081430060312 ，密碼為生日的8位數(shù)）在課程論壇列表中選擇課程輸入發(fā)貼內(nèi)容。 湖南電大BBS討論省電大BBS討論：登錄省電大在線平臺(tái)（）實(shí)時(shí)交

2、流（頁(yè)面上端）進(jìn)入相應(yīng)的討論室進(jìn)行提問(wèn)。 省電大非實(shí)時(shí)交流：登錄省電大在線平臺(tái)（）選擇相關(guān)課程（頁(yè)面左側(cè)）頁(yè)面右上方點(diǎn)擊“進(jìn)入”，進(jìn)入相應(yīng)的課程論壇點(diǎn)擊“發(fā)新貼”進(jìn)行提問(wèn)。（相關(guān)課程責(zé)任教師將在三天內(nèi)回復(fù)） 岳陽(yáng)電大BBS討論岳陽(yáng)電大BBS討論：登錄岳陽(yáng)電大平臺(tái)（ ）公開(kāi)討論區(qū)（頁(yè)面右側(cè)）公共論壇（頁(yè)面左側(cè)）選擇專業(yè)（計(jì)算機(jī)本科）進(jìn)行提問(wèn)。 岳陽(yáng)電大非實(shí)時(shí)交流：登錄岳陽(yáng)電大平臺(tái)（ ）我的提問(wèn)（頁(yè)面右側(cè)）進(jìn)行提問(wèn)。（相關(guān)課程責(zé)任教師將在三天內(nèi)回復(fù)） 考 核1考核對(duì)象 2007年秋季起入學(xué)的計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)（本科）學(xué)生。2考核依據(jù) 以數(shù)據(jù)結(jié)構(gòu)（本）課程教學(xué)大綱為依據(jù)編制，考核說(shuō)明是本課程形成性

3、考核和終結(jié)性考試命題的基本依據(jù)。3考核方式 采用形成性考核和終結(jié)性考試相結(jié)合的方式。4課程總成績(jī)的記分方法 課程總成績(jī)按百分制記分，其中形成性考核所占的比例為30%，終結(jié)性考試占70。60分為合格，可以獲得課程學(xué)分。本課程的學(xué)位課程學(xué)分為70分，即課程總成績(jī)達(dá)到70分及以上者有資格申請(qǐng)專業(yè)學(xué)位。5形成性考核的要求、形式及手段 形成性考核主要考核學(xué)生形成性作業(yè)和實(shí)驗(yàn)的完成情況，占課程總成績(jī)的30%。形成性考核以作業(yè)冊(cè)的形式下發(fā)，由各地電大根據(jù)學(xué)生作業(yè)和實(shí)驗(yàn)的完成情況進(jìn)行考核。中央電大將不定期隨機(jī)抽檢各地電大學(xué)生的形成性作業(yè)及課程實(shí)驗(yàn)報(bào)告。 考 核6終結(jié)性考試方式考核方式：中央電大統(tǒng)一命題，閉卷考

4、試。 組卷原則：在考核說(shuō)明所規(guī)定的內(nèi)容和要求之內(nèi)命題。在教學(xué)內(nèi)容范圍之內(nèi)，按照理論聯(lián)系實(shí)際原則，考察學(xué)生對(duì)所學(xué)知識(shí)應(yīng)用能力的試題，不屬于超綱。試題的難易程度和題量適當(dāng)，按難易程度分為易、中、難三個(gè)層次：易占25%，中占45%，難占30%。題量安排以大多數(shù)考生能在規(guī)定的考試時(shí)間內(nèi)做完并有一定時(shí)間檢查為原則。 試題類型及試卷結(jié)構(gòu)：試題題型有單項(xiàng)選擇題、填空題、綜合題和程序填空題四種題型。試卷結(jié)構(gòu)如下： 單項(xiàng)選擇題：每小題2分，共30分 填空題：每小題2分，共24分 綜合題：每小題10分，共30分 程序填空題：每空2分，共16分 共100分 答題時(shí)限：答題時(shí)限為90分鐘?？己酥R(shí)點(diǎn)1數(shù)據(jù)結(jié)構(gòu)的基本概

5、念2算法和算法分析的基本概念考核要求1理解數(shù)據(jù)結(jié)構(gòu)的基本概念2掌握邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的概念及相互關(guān)系3掌握本書介紹的四種基本結(jié)構(gòu)的特點(diǎn)4理解算法及其特性5了解算法分析的一般概念第1章 緒論1.數(shù)據(jù)結(jié)構(gòu)：(數(shù)據(jù)元素間的關(guān)系稱為結(jié)構(gòu))，相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合稱為數(shù)據(jù)結(jié)構(gòu)。邏輯結(jié)構(gòu)：元素間的邏輯關(guān)系，與計(jì)算機(jī)無(wú)關(guān)。物理結(jié)構(gòu)：把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的關(guān)系。簡(jiǎn)言之，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示(包括數(shù)據(jù)元素和關(guān)系的表示)，同一種邏輯結(jié)構(gòu)可以對(duì)應(yīng)不同的物理結(jié)構(gòu)。重點(diǎn)掌握的知識(shí)點(diǎn)舉例集合：屬于同一集合。線形：一對(duì)一，數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，線性表除第一個(gè)元素和最后

6、一個(gè)元素外每個(gè)元素有一個(gè)直接前驅(qū)和直接后繼。樹(shù)形：一對(duì)多。圖：多對(duì)多。2.基本的數(shù)據(jù)結(jié)構(gòu)算法：解決特定問(wèn)題的方法算法的5個(gè)特征 有窮、確定、可行、零個(gè)或多個(gè)輸入、一個(gè)或多個(gè)輸出時(shí)間復(fù)雜度 基本操作、頻度、問(wèn)題規(guī)模、數(shù)量級(jí)、時(shí)間復(fù)雜度與實(shí)現(xiàn)算法的軟、硬件無(wú)關(guān)。 n個(gè)矩陣的乘積算法的基本操作為乘法，時(shí)間復(fù)雜度為O(n3) 要在n個(gè)數(shù)據(jù)元素中找最大元素，基本操作為比較，比較次數(shù)為n-1，時(shí)間復(fù)雜度為O(n)3.算法：考核知識(shí)點(diǎn)1線性表的定義、邏輯結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上的基本操作和應(yīng)用 3雙向鏈表、循環(huán)鏈表的原理和相關(guān)操作考核要求1理解線性表的定義及兩種存儲(chǔ)結(jié)構(gòu)

7、2理解線性表順序存儲(chǔ)的特點(diǎn)、實(shí)現(xiàn)方法和應(yīng)用。3掌握順序表的基本操作（包括建立鏈表、遍歷鏈表、刪除、插入、查找）和應(yīng)用。特別要求能夠利用鏈表的操作和相關(guān)的程序設(shè)計(jì)技術(shù)編制有一定難度的程序。4了解雙向鏈表、循環(huán)鏈表的原理和相關(guān)操作。第2章 線性表1.線性表的定義：屬于同一個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)元素的有限序列。2.順序存儲(chǔ)(順序表)：邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)一致，可用數(shù)組或指針實(shí)現(xiàn)，能隨機(jī)訪問(wèn)，如果線性表存儲(chǔ)后最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，采用順序表較方便，但順序表插入刪除操作平均而言移動(dòng)元素次數(shù)較多，效率很低. 插入位置i，移動(dòng)元素次數(shù)為n-i+1.刪除位置是i，移動(dòng)次數(shù)n-i。3.鏈?zhǔn)酱鎯?chǔ)(鏈表)：以

8、結(jié)構(gòu)變量存儲(chǔ)結(jié)點(diǎn)，動(dòng)態(tài)生成結(jié)點(diǎn)，以指針鏈接結(jié)點(diǎn)，能有效利用存儲(chǔ)空間，插入刪除方便，但不能隨機(jī)訪問(wèn).單向鏈表可從某結(jié)點(diǎn)訪問(wèn)到后繼結(jié)點(diǎn)。重點(diǎn)掌握的知識(shí)點(diǎn)舉例建立鏈表的頭插法：指針變量p開(kāi)辟單元，生成結(jié)點(diǎn)，指針變量q始終指向頭結(jié)點(diǎn)，操作為： p-next=q-next; q-next=p; 尾插法：指針變量q始終指向尾結(jié)點(diǎn)，p指針開(kāi)辟單元，生成結(jié)點(diǎn). q-next=p; q=p; 4.單向鏈表操作的關(guān)鍵步驟：插入：p所指向結(jié)點(diǎn)的后面插入新結(jié)點(diǎn)s所指結(jié)點(diǎn) s-next=p-next; p-next=s; 刪除：p，q指向相鄰結(jié)點(diǎn)，q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的后繼，刪除q所指結(jié)點(diǎn)， p-next=q-nex

9、t;遍歷：p=p-next; 插入、刪除、遍歷：?jiǎn)蜗蜴湵碇校绻衟-next=NULL，令 p-next=head；則成為單向循環(huán)鏈表，可從某結(jié)點(diǎn)訪問(wèn)到任一結(jié)點(diǎn)，但訪問(wèn)前驅(qū)要通過(guò)頭結(jié)點(diǎn).單向循環(huán)鏈表中，若p指向尾結(jié)點(diǎn)，則p-next=head5.單向循環(huán)鏈表：6.雙向鏈表：每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接后繼，一個(gè)指向直接前驅(qū).頭結(jié)點(diǎn)的prio指向尾結(jié)點(diǎn)，尾結(jié)點(diǎn)的next指向頭結(jié)點(diǎn)，從任一結(jié)點(diǎn)可訪問(wèn)前驅(qū)和后繼7.單向鏈表為空的判斷條件是head=NULL,但帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件為head-next=NULL 8.鏈?zhǔn)酱鎯?chǔ)的線性表都不能隨機(jī)訪問(wèn)考核知識(shí)點(diǎn)1棧的定義、棧的存儲(chǔ)結(jié)構(gòu)（

10、順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）和基本操作、棧的應(yīng)用2隊(duì)列的定義、隊(duì)列的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)）、隊(duì)列的應(yīng)用3循環(huán)隊(duì)列的概念和實(shí)現(xiàn)方法考核要求1掌握棧和隊(duì)列的操作特點(diǎn)2理解順序棧、順序隊(duì)列的基本操作3了解在實(shí)際編程中棧和隊(duì)列的不同應(yīng)用。理解循環(huán)隊(duì)列的概念、實(shí)現(xiàn)方法。掌握循環(huán)隊(duì)列判空、判滿的條件4能按照后續(xù)章節(jié)（例如二叉樹(shù)、排序等）的要求利用遞歸程序設(shè)計(jì)技術(shù)實(shí)現(xiàn)相關(guān)算法。第3章 棧和隊(duì)列1.棧和隊(duì)列是運(yùn)算受限制的線性表。2.棧：后進(jìn)先出(LIFO)，棧的插入刪除操作在棧頂進(jìn)行 例:進(jìn)棧順序?yàn)閎, c, d, e, f .出?？赡転?f, e, d, c, b; b, c, d, e, f ; c, b

11、, e, d, f 但不可能是e, d, f, b, c3.順序棧：相當(dāng)于線性表的順序存儲(chǔ)結(jié)構(gòu)，可用一維數(shù)組實(shí)現(xiàn)設(shè)置棧頂指針top，在棧頂進(jìn)行操作(插入、刪除等)重點(diǎn)掌握的知識(shí)點(diǎn)舉例4.鏈棧：相當(dāng)于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，設(shè)頭指針變量為top 出棧：用x保存被刪結(jié)點(diǎn)的值，在棧中刪除結(jié)點(diǎn). x=top-data; top=top-next; 進(jìn)棧：設(shè)棧頂指針為h，要插入s所指結(jié)點(diǎn)，操作為s-next=h;h=s;相當(dāng)于在單向鏈表的頭插法5.隊(duì)列：（FIFO） 入隊(duì)：1,2,3,4,5 出隊(duì)：1,2,3,4,56.順序隊(duì)列：可以用一維數(shù)組來(lái)實(shí)現(xiàn)設(shè)置指針front、rear分別指向隊(duì)列的隊(duì)頭元素和隊(duì)尾

12、元素7.鏈隊(duì)列：是在表頭刪除在表尾插入的單鏈表設(shè)置頭指針front,尾指針rear在鏈隊(duì)中插入s所指結(jié)點(diǎn)的操作為： rear-next=s; rear=s;在鏈隊(duì)中刪除結(jié)點(diǎn)相當(dāng)于刪除鏈表中的第一個(gè)結(jié)點(diǎn)（若要保存被刪結(jié)點(diǎn)，可先保留，再刪除）考核知識(shí)點(diǎn)1串類型定義、C語(yǔ)言中字符串的特點(diǎn)和處理方法2串的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3串的基本運(yùn)算和實(shí)現(xiàn)方法考核要求1理解串的定義和存儲(chǔ)方法2了解串的基本操作和相關(guān)算法3掌握用C語(yǔ)言處理字符串的語(yǔ)法規(guī)則第4章 串1.每個(gè)字符占一個(gè)字節(jié),串的最基本的存儲(chǔ)方式是順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)。字符串的特點(diǎn)是在串尾自動(dòng)加一個(gè)結(jié)束符。3.有關(guān)串的運(yùn)算的函數(shù)（求串長(zhǎng)、復(fù)制、連接、

13、比較、查找字符、查找子串），要求能掌握函數(shù)的功能.例StrCmp (“a”,“A”)的值為1，上述函數(shù)是字符串比較函數(shù).兩個(gè)串相等的充要條件是串長(zhǎng)相等，對(duì)應(yīng)位置字符相等.例StrCat (“ab”,“cd”)的功能是串連接。4.從字符串中查找子串的方法稱為模式匹配算法，例求串q在p中首先出現(xiàn)的位置。重點(diǎn)掌握的知識(shí)點(diǎn)舉例考核知識(shí)點(diǎn)1數(shù)組的定義和存儲(chǔ)結(jié)構(gòu)2特殊矩陣和稀疏矩陣的存儲(chǔ)結(jié)構(gòu)3廣義表的定義和存儲(chǔ)結(jié)構(gòu)考核要求1了解數(shù)組的存儲(chǔ)結(jié)構(gòu)。2掌握特殊矩陣進(jìn)行壓縮存儲(chǔ)的下標(biāo)轉(zhuǎn)換公式。3理解稀疏矩陣的壓縮存儲(chǔ)原理。4掌握利用三元組表示稀疏矩陣的方法。5了解廣義表的概念和存儲(chǔ)結(jié)構(gòu)。第章 數(shù)組和廣義表1.特殊

14、矩陣,如對(duì)稱矩陣的壓縮存儲(chǔ)結(jié)構(gòu)，矩陣元素與一維數(shù)組元素的對(duì)應(yīng)。 設(shè)數(shù)組下標(biāo)從開(kāi)始,矩陣元素， ，(1+2+3)+3=9,， 對(duì)應(yīng)一維數(shù)組下標(biāo)為9.7，6對(duì)應(yīng)一維數(shù)組下標(biāo)為(1+2+3+6)+6=27.i，j對(duì)應(yīng)下標(biāo)為i(i-1)/2+j。2.稀疏矩陣的三元組存儲(chǔ)結(jié)構(gòu)（行，列，非零元）重點(diǎn)掌握的知識(shí)點(diǎn)舉例考核知識(shí)點(diǎn)1樹(shù)的基本概念2二叉樹(shù)的性質(zhì)和存儲(chǔ)結(jié)構(gòu)3二叉樹(shù)的遍歷和線索二叉樹(shù)4哈夫曼樹(shù)及其應(yīng)用考核要求1了解樹(shù)和二叉樹(shù)的定義2掌握二叉樹(shù)的基本性質(zhì)，能利用相關(guān)性質(zhì)解決簡(jiǎn)單計(jì)算問(wèn)題3了解二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)4掌握二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、相關(guān)操作5掌握二叉樹(shù)的有關(guān)算法并能編程實(shí)現(xiàn)6掌握利用遍歷序歷構(gòu)造二

15、叉樹(shù)的規(guī)則和具體步驟7掌握哈夫曼樹(shù)的定義、性質(zhì)和構(gòu)造方法8了解哈夫曼樹(shù)的應(yīng)用第6章 樹(shù)和二叉樹(shù)1.樹(shù)的定義： 連通不含回路的圖 樹(shù)的邊數(shù)m和頂點(diǎn)數(shù)n有關(guān)系n=m+1，頂點(diǎn)數(shù)等于邊數(shù)加1重點(diǎn)掌握的知識(shí)點(diǎn)舉例2. 二叉樹(shù)的性質(zhì)：二叉樹(shù)上終端結(jié)點(diǎn)數(shù)(葉結(jié)點(diǎn)數(shù))等于雙分子結(jié)點(diǎn)數(shù)(度數(shù)為的結(jié)點(diǎn)數(shù))加.例有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，每個(gè)結(jié)點(diǎn)度數(shù)為2，則有2n-1個(gè)結(jié)點(diǎn)二叉樹(shù)第i層上至多有2i-1個(gè)結(jié)點(diǎn)深度為h的二叉樹(shù)至多有2h-1個(gè)結(jié)點(diǎn)二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)，左孩子結(jié)點(diǎn)編號(hào)為2i，右孩子結(jié)點(diǎn)為2i+1滿二叉樹(shù)、完全二叉樹(shù) 設(shè)有一棵完全二叉樹(shù)有18個(gè)結(jié)點(diǎn),最高層有18-(1+2+4+8)=3個(gè)結(jié)點(diǎn)。 例有一棵二叉

16、樹(shù)，有2n-2條邊，每一個(gè)非葉結(jié)點(diǎn)度數(shù)都為2，則共有2n-2+1=2n-1個(gè)頂點(diǎn)，有n個(gè)葉結(jié)點(diǎn)，n-1個(gè)非葉結(jié)點(diǎn)。1354213542673.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)： 對(duì)結(jié)點(diǎn)編號(hào)，以編號(hào)為下標(biāo)把結(jié)點(diǎn)存儲(chǔ)到一維數(shù)組中鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)的空指針域： 設(shè)結(jié)點(diǎn)數(shù)為n，共有2n個(gè)指針域，有n-1個(gè)指針域指向n-1個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）所以有2n-(n-1)個(gè)指針沒(méi)有指向（空指針域），即n+1個(gè)空指針域。二叉樹(shù)的遍歷： 訪問(wèn)每個(gè)結(jié)點(diǎn)一次且只一次leftdataright值域、左指針、右指針遍歷樹(shù)的三個(gè)子問(wèn)題：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)。規(guī)定先左后右，以根結(jié)點(diǎn)的訪問(wèn)順序分為先、中、后序遍歷.另外還有

17、層次遍歷，共四種遍歷方法 二叉樹(shù)的遞歸遍歷算法.遞歸調(diào)用、輸出結(jié)點(diǎn)信息結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長(zhǎng)度： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積 第6章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的帶權(quán)路徑長(zhǎng)度： 樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和 WPL= WiLi第6章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)哈夫曼樹(shù)(最優(yōu)樹(shù))： n個(gè)帶權(quán)葉結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)構(gòu)造Huffman樹(shù)的算法： 設(shè)n個(gè)權(quán)值w1,w2,wn, (1)在權(quán)值集合中取權(quán)值最小的作為結(jié)點(diǎn)，以它們的權(quán)值之和作為它們的父結(jié)點(diǎn)的權(quán)值第6

18、章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)構(gòu)造Huffman樹(shù)的算法： (2)在剩余的權(quán)值集合中，加入上述父結(jié)點(diǎn)的權(quán)值得到新權(quán)值集合，重復(fù)步驟(1),直到權(quán)值集合中只剩下一個(gè)權(quán)值，生成一棵有n個(gè)結(jié)點(diǎn)的Huffman樹(shù)第6章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)哈夫曼編碼： 在Huffman樹(shù)中，讓每個(gè)分支結(jié)點(diǎn)的左、右分支分別用0、1編碼，從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑上所經(jīng)分支的0、1編碼序列為該葉結(jié)點(diǎn)的二進(jìn)制編碼，所有葉結(jié)點(diǎn)的編碼集合為哈夫曼編碼第6章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)哈夫曼編碼： Huffman樹(shù)的特點(diǎn)之一：除葉結(jié)點(diǎn)外，每一個(gè)結(jié)點(diǎn)度數(shù)都為

19、2.設(shè)一棵哈夫曼樹(shù)有n個(gè)非葉結(jié)點(diǎn)，則有n+1個(gè)葉結(jié)點(diǎn)，共有2n+1個(gè)結(jié)點(diǎn)第6章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例 例1 ： (1)以1，2，5，6，7，8作為葉結(jié)點(diǎn)的 權(quán)，構(gòu)造一棵哈夫曼樹(shù)，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。 (2) 一棵哈夫曼樹(shù)有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由？第6章 樹(shù)和二叉樹(shù)重點(diǎn)掌握的知識(shí)點(diǎn)舉例 答案： (1)1：0000 2：0001 5：001 6：10 7：11 8：01 (2)2n-1個(gè)，因?yàn)榉侨~結(jié) 點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。29132176538816重點(diǎn)掌握的知識(shí)點(diǎn)舉例例2 ：如圖所示的二叉樹(shù)（1）給出中序遍歷序列（2）給出先序遍歷序列（3）給出后序遍歷序

20、列 (1)abcdjefhgi (2)eadcbjfghi (3)bcjdahigfeefhbgjcdai考核知識(shí)點(diǎn)1圖的基本概念2圖的存儲(chǔ)結(jié)構(gòu)3圖的遍歷4最小生成樹(shù)和最短路徑?？己艘?了解圖的基本概念2掌握?qǐng)D的存儲(chǔ)方法（鄰接矩陣、鄰接表）3掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷的規(guī)則和步驟4理解在連通圖中求最小生成樹(shù)的方法。了解求圖的最短路徑等相關(guān)算法及其應(yīng)用第7章 圖重點(diǎn)掌握的知識(shí)點(diǎn)舉例1.圖的存儲(chǔ)結(jié)構(gòu)2.圖的遍歷：圖的廣度優(yōu)先遍歷的規(guī)則和步驟： (1)訪問(wèn)vi ,訪問(wèn)vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn) vi1、vi2、vit2.圖的遍歷：圖的廣度優(yōu)先遍歷的規(guī)則和步驟： (2)按照vi1、vi2、vi

21、t的次序，訪問(wèn)每一個(gè)頂點(diǎn)所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，依次類推直到和vi有路徑相通的頂點(diǎn)都訪問(wèn)過(guò)為止第7章 圖重點(diǎn)掌握的知識(shí)點(diǎn)舉例2.圖的遍歷：圖的深度優(yōu)先遍歷的規(guī)則和步驟： 訪問(wèn)vi(初始點(diǎn))，從vi的任一個(gè)未被訪問(wèn)過(guò)的鄰接點(diǎn)出發(fā)繼續(xù)深度優(yōu)先搜索遍歷，若搜索過(guò)程中某一結(jié)點(diǎn)的鄰接點(diǎn)全被訪問(wèn)過(guò)，則退回上一個(gè)結(jié)點(diǎn)，繼續(xù)深度搜索遍歷，直到退回到初始點(diǎn)且沒(méi)有未被訪問(wèn)過(guò)的鄰接點(diǎn)第7章 圖重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.圖的最小生成樹(shù)生成樹(shù)： 設(shè)有連通圖G，取G的全部頂點(diǎn)和部分邊構(gòu)成子圖G,若G連通且不含有回路，則G是生成樹(shù)第7章 圖重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.圖的最小生成樹(shù)帶權(quán)圖： 邊上帶有權(quán)的圖連通圖一定存在生成樹(shù)，且

22、不一定唯一樹(shù)權(quán)： 樹(shù)中所有邊的權(quán)值之和第7章 圖重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.圖的最小生成樹(shù)最小生成樹(shù)： 連通圖中具有最小權(quán)的生成樹(shù)帶權(quán)連通圖一定存在最小生成樹(shù)，且不一定唯一第7章 圖 重點(diǎn)掌握的知識(shí)點(diǎn)舉例 例1 已知如圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7 CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7v1V2V3V8V4V5答案：A 重點(diǎn)掌握的知識(shí)點(diǎn)舉例 例2 已知如圖所示的一個(gè)圖，若從頂點(diǎn)V1出發(fā)，按廣優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂

23、點(diǎn)序列為（ ）。 AV1V2V3V6V7V4 V5V8 BV1V2V3V4V5V8V6V7 CV1V2V3V4V5V6V7V8 DV1V2V3V4V8V5V6V7V6V7v1V2V3V8V4V5答案：C考核知識(shí)點(diǎn)1線性表的查找（順序查找、折半查找、分塊查找）。2二叉排序樹(shù)的查找。3哈希表（哈希表的定義、哈希函數(shù)的構(gòu)造、處理沖突的方法、哈希表的查找和分析）?？己艘?了解查找的相關(guān)概念。2掌握順序表的查找方法、步驟、程序?qū)崿F(xiàn)、時(shí)間復(fù)雜度和平均查找長(zhǎng)度。3掌握在有序的順序表上進(jìn)行折半查找的方法、步驟、程序?qū)崿F(xiàn)。4掌握折半查找的判定樹(shù)的構(gòu)造方法。能利用判定樹(shù)求平均查找長(zhǎng)度。5掌握二叉排序樹(shù)的確切定義

24、，掌握建立二叉排序樹(shù)的步驟和方法。理解在二叉排序樹(shù)中進(jìn)行輸入、刪除操作的規(guī)則。6了解哈希表的相關(guān)概念和原理，了解常用哈希函數(shù)的構(gòu)造和處理沖突的方法。理解哈希函數(shù)和哈希表的關(guān)系及在查找中的應(yīng)用。第8章 查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例1.查找表、關(guān)鍵字：主關(guān)鍵字2.線性表的查找：順序查找：從表的某一端開(kāi)始逐次進(jìn)行比較折半查找：針對(duì)有序的順序表，設(shè)置low、high，令mid=( low+high)/23.折半查找對(duì)應(yīng)的判定樹(shù)： 樹(shù)中結(jié)點(diǎn)相應(yīng)于查找表中的記錄，結(jié)點(diǎn)值相應(yīng)于記錄在查找表中的位置4.利用折半查找的判定樹(shù)，求成功查找到某一元素、查不到某一元素的比較次數(shù)、等概率條件下成功查找的平均查找長(zhǎng)度第8章

25、查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例5.分塊查找的數(shù)據(jù)結(jié)構(gòu) 查找表分塊索引表(塊內(nèi)最大關(guān)鍵字值、塊起始地址)第8章 查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例6.二叉排序樹(shù)二叉排序樹(shù)定義： 若左子樹(shù)非空，則左子樹(shù)所有結(jié)點(diǎn)的值小于根結(jié)點(diǎn)的值； 若右子樹(shù)非空，則右子樹(shù)所有結(jié)點(diǎn)的值大于根結(jié)點(diǎn)的值；第8章 查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例6.二叉排序樹(shù)二叉排序樹(shù)定義： 左、右子樹(shù)也分別是一棵二叉排序樹(shù)(每個(gè)結(jié)點(diǎn)的值都大于它的左子樹(shù)上所有結(jié)點(diǎn)的值，小于它的右子樹(shù)上所有結(jié)點(diǎn)的值)二叉排序樹(shù)中任一棵子樹(shù)也是二叉排序樹(shù)。第8章 查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例6.二叉排序樹(shù)二叉排序樹(shù)的建立： 實(shí)際上是從空樹(shù)逐次插入的過(guò)程二叉排序樹(shù)的查找二叉排序樹(shù)的插入

26、第8章 查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例6.二叉排序樹(shù)7.哈希函數(shù)： 記錄的關(guān)鍵字值與該記錄存儲(chǔ)地址之間構(gòu)造的對(duì)應(yīng)關(guān)系第8章 查找重點(diǎn)掌握的知識(shí)點(diǎn)舉例例1 設(shè)查找表為( 8,16,22,23,50,59,69,81,89, 90, 121 ),元素的下標(biāo)依次為1,2,3,11.(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的 判定樹(shù)（樹(shù)中結(jié)點(diǎn)用下標(biāo)表示）(2)說(shuō)明成功查找到元素50需要經(jīng)過(guò)多少次比 較？(3)求在等概率條件下，成功查找的平均比較 次數(shù)？重點(diǎn)掌握的知識(shí)點(diǎn)舉例例1 答案：(1)(2)4次(3)ASL=(1+2*2 +3*4+4*4)/11=34711852101396重點(diǎn)掌握的知識(shí)點(diǎn)舉例 例2

27、設(shè)查找表為 (51,61,76,86,97,99,106,111,121, 131) , (1)說(shuō)出成功查找到元素121需要進(jìn)行多少 次元素間的比較？ (2)為了查找元素95，經(jīng)過(guò)多少次元素間的 比較才能確定不能查到？ (3)畫出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng) 的判定樹(shù)(要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn))重點(diǎn)掌握的知識(shí)點(diǎn)舉例例2 答案：(1)3次(2)4次(3)如圖 977699131106865111112161例3 設(shè)查找表為(17,16,21,54,65,8), (1)用冒泡法對(duì)該表進(jìn)行排序(要求升序排列),要求寫出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次

28、元素間的比較？ (2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù).(要求以數(shù)據(jù)元素作為樹(shù)結(jié)點(diǎn)) (3)求在等概率條件下,對(duì)上述有序表成功查找 的平均查找長(zhǎng)度.例3 答案：(1)原序列 17 16 21 54 65 8 16 17 21 54 8 65 n-1趟 16 17 21 8 54 65 n-j次 16 17 8 21 54 65 16 8 17 21 54 65 8 16 17 21 54 65 (2)如右圖(3)平均查找長(zhǎng)度=（1*1+2*2+3*3）/6=14/681621651754 例4（1）如果二叉樹(shù)中任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值，則該樹(shù)

29、為二叉排序樹(shù)，這種說(shuō)法是否正確？若認(rèn)為正確，則回答正確，若認(rèn)為不正確，則舉例說(shuō)明。（2）設(shè)有數(shù)據(jù)集合41，30，8，74，102，5，56，3，82，93，40，依次取集合中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。 例4 答案： (1)不正確，例 (2) 如右圖15424056938215102834107430 例5 （1）對(duì)給定數(shù)列8,17,5,9,21,10,7,19,6,依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。 (2 )對(duì)一個(gè)給定的查找值,簡(jiǎn)述針對(duì)二叉排序樹(shù)進(jìn)行查找的算法步驟,在上述二叉樹(shù)中查找元素21共要進(jìn)行多少次元素的比較? 例5 答案： (1)如右圖： (2)先將給定值與根結(jié)點(diǎn)比較，若相等則

30、查找成功，否則若小于根結(jié)點(diǎn)則在左子樹(shù)中繼續(xù)查找，大于根結(jié)點(diǎn)在右子樹(shù)中查找，查找20共進(jìn)行3次比較。 5791068172119 例6 (1)“一棵二叉樹(shù)若它的根結(jié)點(diǎn)的值大于左子樹(shù)所有結(jié)點(diǎn)的值，小于右子樹(shù)所有結(jié)點(diǎn)的值，則該樹(shù)一定是二叉排序樹(shù)”。該說(shuō)法是否正確，若認(rèn)為正確，則回答正確，若認(rèn)為不正確則說(shuō)明理由？ (2)設(shè)有查找表6，15，3，7，19，8，5，17，4，依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù). 對(duì)上述二叉樹(shù)給出后序遍歷的結(jié)果。 例6 答案： (1)不正確，二叉排序樹(shù)要求其子樹(shù)也是二叉排序樹(shù)。 (2) 4,5,3,8,7,17,19,15,6357841961517考核知識(shí)點(diǎn)1插入排序（直接

31、插入排序、希爾排序）2交換排序（冒泡排序、快速排序）3選擇排序（簡(jiǎn)單選擇排序、堆排序）4歸并排序考核要求1掌握教材中介紹的各種排序算法的基本原理、步驟。2能針對(duì)小規(guī)模具體實(shí)例，按相關(guān)排序算法的規(guī)則人工完成排序；能通過(guò)分析排序的中間結(jié)果判斷所用的排序算法。3能正確理解相關(guān)排序算法的程序?qū)嵗⒅攸c(diǎn)掌握算法中的關(guān)鍵步驟和關(guān)鍵語(yǔ)句。4掌握堆和特殊的完全二叉樹(shù)的對(duì)應(yīng)關(guān)系。掌握建堆、篩選算法和完全二叉樹(shù)相關(guān)操作的對(duì)應(yīng)關(guān)系。第9章 排序重點(diǎn)掌握的知識(shí)點(diǎn)舉例1.插入排序：直接插入： 第i趟插入是指前i-1個(gè)已有序，第i個(gè)元素逐次與前i-1個(gè)元素比較找到插入位置.插入后得到有i個(gè)元素的有序序列。折半插入： 采

32、用折半查找法找到插入位置，加快了查找速度第9章 排序重點(diǎn)掌握的知識(shí)點(diǎn)舉例2.交換排序：冒泡排序： n個(gè)元素通常需要n-1趟冒泡 第i趟冒泡要進(jìn)行n-i次元素比較 某趟冒泡中若沒(méi)有進(jìn)行元素的交換，則表 明已排好序，可設(shè)立標(biāo)志位結(jié)束冒泡過(guò)程第9章 排序重點(diǎn)掌握的知識(shí)點(diǎn)舉例2.交換排序：快速排序： 一趟劃分執(zhí)行步驟：設(shè)置分割元素(第一個(gè)元素)，逐次輪換從后向前、從前向后掃描，必要時(shí)交換記錄位置，最終使劃分元素到位，完成一次分割，遞歸調(diào)用一趟劃分函數(shù)，實(shí)現(xiàn)快速排序 第9章 排序重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.選擇排序：簡(jiǎn)單選擇排序： 逐次從n個(gè)元素、n-1個(gè)元素，查找最小元素的位置，并逐一排序到位 第9章 排

33、序重點(diǎn)掌握的知識(shí)點(diǎn)舉例3.選擇排序：堆排序： 大根堆、小根堆 堆與特殊完全二叉樹(shù)的對(duì)應(yīng) 篩選：輸出堆頂元素(存入到最后一個(gè)元素的位置)，以最后一個(gè)元素替換，并自頂向下重新調(diào)整為堆 建初始堆：從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始直到第一個(gè)結(jié)點(diǎn)，從下到上逐次篩選 第9章 排序重點(diǎn)掌握的知識(shí)點(diǎn)舉例4.歸并排序：歸并：把兩個(gè)有序序列合成一個(gè)有序序列(逐次比較)一趟歸并算法對(duì)待排序列逐次施行(1,1)歸并、(2,2)歸并， 最終完成排序 第9章 排序例1設(shè)一組記錄的關(guān)鍵字序列為（59，93，69，51，53，57），采用堆排序算法完成以下操作：（要求小根堆，并畫出中間過(guò)程）（1）以二叉樹(shù)描述6個(gè)元素的初始堆（2）以

34、二叉樹(shù)描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的5個(gè)元素、4個(gè)元素的堆例1 答案：(1) 596993515357935751536959595157935369595153439383594957699353515357935969例1 答案：(2)695751599353535751699359695751539359575193695359575153935969例2 一組記錄的關(guān)鍵字序列為（47，80，57，39，41，85）（1）利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過(guò)程，要求以升序排列）（2）對(duì)上述序列用堆排序的方法建立大根堆，要求以二叉樹(shù)逐次描

35、述建堆過(guò)程。例2 答案：(1)初始序列 47，80，57，39，41，85 47 41，80，57，39，41，85 41，80，57，39，80，85 41，39，57，39，80，85 41，39，57，57，80，85 41，39，47，57，80，85 例2 答案：(2) 5780394185478580394147575780394147803941858557471.能閱讀書中給出的相關(guān)程序2.重點(diǎn)掌握單向鏈表的頭插法、尾插法、靜態(tài)法建鏈表的程序、單向鏈表的插入和刪除程序、順序表的插入、刪除程序、二分查找程序、冒泡排序程序、棧的出棧、進(jìn)棧程序.隊(duì)列的出隊(duì)、入隊(duì)程序、二叉樹(shù)的前序、中

36、序、后序遍歷程序（遞歸法）等第10章 有關(guān)程序的要求一、單項(xiàng)選擇題（每小題2分，共30分）1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù) （ ）結(jié)構(gòu)。 A. 邏輯 B. 物理 C. 存儲(chǔ) D. 邏輯與物理 答案：A2.下述各類表中可以隨機(jī)訪問(wèn)的是（ ）。 A. 單向鏈表 B. 雙向鏈表 C.單向循環(huán)鏈表 D.順序表 答案：D習(xí)題選講3.在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開(kāi)始從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（ ）。 A. 21 B. 20 C. 19 D. 25 答案：B4.元素2，4，6按順序依次進(jìn)棧，則該棧的不可能的輸出序列是（ ）。 A. 6 4 2 B

37、. 6 2 4 C. 4 2 6 D. 2 6 4 答案：B5.一個(gè)隊(duì)列的入隊(duì)序列是5，6，7，8，則隊(duì)列的輸出序列是（ ）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多種情況 答案：A6. 串函數(shù)StrCmp（“d”，“D”）的值為（ ）。 A0 B1 C-1 D3 答案：B7在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn),且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q所指結(jié)點(diǎn),可用語(yǔ)句（ ）。 Ap=q-next ; BP-next=q ; CP-next=q-next ; D. q-next=NULL ; 答案：C8.設(shè)一棵哈夫曼樹(shù)共有n個(gè)非葉結(jié)點(diǎn)，

38、則該樹(shù)一共有（ ）個(gè)結(jié)點(diǎn)。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 答案：B9.對(duì)如圖1所示二叉樹(shù)進(jìn)行中序遍歷,結(jié)果是( ) A. dfebagc B. defbagc C. defbacg D. dbaefcg 答案：Aadgbfec10 . 任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（ ）。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 答案：A11設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始）,則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（ ）。 A33 B32 C85 D41 答案：A

39、12 . 一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（ ）。 A31，29，37，85，47，70 B29，31，37，47，70，85 C31，29，37，70，47，85 D31，29，37，47，70，85 答案：D13 . 對(duì)n個(gè)元素進(jìn)行冒泡排序，要求按升序排列，程序中設(shè)定某一趟冒泡沒(méi)有出現(xiàn)元素交換，就結(jié)束排序過(guò)程。對(duì)某n個(gè)元素的排序共進(jìn)行了3n-6次元素間的比較就完成了排序，則（ ）。 A.原序列是升序排列 B.原序列是降序排列 C.對(duì)序列只進(jìn)行了2趟冒泡 D. 對(duì)序列只進(jìn)行了3趟冒泡 答案：D14在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用x保存被刪除的結(jié)點(diǎn),應(yīng)執(zhí)行（ ）。 =top-data;top=top-next; B. top=top-next ; x=top; =top;top=top-next ; D. x=top-data; 答案：A15在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。 A2i B2i-1 C2i+2 D2i