《數(shù)據(jù)結(jié)構(gòu)與算法》理論教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)與算法理論教學(xué)大綱(2004年制訂)課程編號(hào)：210142英 文 名：Data Structure and Algorithm課程類別：文化技能課前 置 課：計(jì)算機(jī)導(dǎo)論、C程序設(shè)計(jì)基礎(chǔ)、高等數(shù)學(xué)、線性代數(shù)、離散數(shù)學(xué)后 置 課： 學(xué) 分：4學(xué)分課 時(shí)：72課時(shí)(其中理論教學(xué)36課時(shí)，實(shí)驗(yàn)教學(xué)36課時(shí))主講教師：曹驄、楊小寧等選定教材：課程概述： 隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，軟件需求量也不斷增大，程序設(shè)計(jì)知識(shí)普及率也隨之增高。在這種情況下，數(shù)據(jù)結(jié)構(gòu)與算法課程，已經(jīng)由原來(lái)計(jì)算機(jī)專業(yè)的特有課程，逐步發(fā)展成為眾多理工專業(yè)的文化基礎(chǔ)課。本課程面向數(shù)學(xué)專業(yè)學(xué)生講授。本課程內(nèi)容的選取，定位于以數(shù)據(jù)結(jié)

2、構(gòu)知識(shí)為主，同時(shí)介紹算法設(shè)計(jì)和分析方法的內(nèi)容，這對(duì)那些在非計(jì)算機(jī)專業(yè)不開(kāi)設(shè)算法設(shè)計(jì)課程，而又需要了解和掌握一部分算法設(shè)計(jì)和分析基本技能的學(xué)生群是非常合適的。本課程內(nèi)容包括：第一部分緒論；第二部分線性表；第三部分棧和隊(duì)列；第四部分串；第五部分?jǐn)?shù)組和廣義表；第六部分樹(shù)和二叉樹(shù)；第七部分圖；第八部分查找；第九部分排序。第二至四部分集中介紹基礎(chǔ)順序結(jié)構(gòu)是本課程的基礎(chǔ)。第六、七部分是本課程重點(diǎn)，也是難點(diǎn)。第八、九部分為算法設(shè)計(jì)奠定基礎(chǔ)。教學(xué)目的： 數(shù)據(jù)結(jié)構(gòu)與算法的教學(xué)目的是培養(yǎng)學(xué)生在問(wèn)題的分析中抽象出數(shù)據(jù)、數(shù)據(jù)集合和數(shù)據(jù)關(guān)系，并以此為基礎(chǔ)設(shè)計(jì)算法，把算法分解成為對(duì)數(shù)據(jù)集上的數(shù)據(jù)結(jié)構(gòu)和各種運(yùn)算。在語(yǔ)言支持

3、下，實(shí)現(xiàn)算法和數(shù)據(jù)集上的運(yùn)算。因此要求學(xué)生學(xué)會(huì)從問(wèn)題入手，分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的操作算法，并初步掌握時(shí)間和空間分析技術(shù)。為此本課程從基本數(shù)據(jù)結(jié)構(gòu)入手，講授基本數(shù)據(jù)結(jié)構(gòu)：線性表、棧、隊(duì)列、矩陣、字符串、廣義表并予以基本操作和實(shí)驗(yàn)，以增加學(xué)生對(duì)基礎(chǔ)知識(shí)的理解和認(rèn)識(shí)。講授遞歸知識(shí)，為算法設(shè)計(jì)提供一種思路。樹(shù)、圖的講授使線性表應(yīng)用、變形得以充分?jǐn)U展，為分析、解決和處理問(wèn)題的思路和方法奠定了基礎(chǔ)。查找、排序是全課程內(nèi)容的高潮，精彩、經(jīng)典的算法不失為學(xué)生的算法設(shè)計(jì)入門和創(chuàng)新思維的平臺(tái)。本課程在講述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)方法、實(shí)現(xiàn)算法和

4、應(yīng)用基礎(chǔ)上，著重培養(yǎng)學(xué)生對(duì)數(shù)據(jù)對(duì)象的特性及組織方式的學(xué)習(xí)和分析，提高對(duì)有關(guān)數(shù)據(jù)的存儲(chǔ)操作、算法及應(yīng)用的技能。教學(xué)方法： 本課程采用立體化教學(xué)模式。課堂教學(xué)以講授教材內(nèi)容為主線，同時(shí)講授實(shí)驗(yàn)方法和內(nèi)容，適時(shí)安排作業(yè)分析和習(xí)題課，還結(jié)合程序設(shè)計(jì)基礎(chǔ)與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)講述有關(guān)課程設(shè)計(jì)的知識(shí)和重點(diǎn)。鑒于數(shù)學(xué)系專業(yè)特性，考慮到數(shù)學(xué)系學(xué)生的課程設(shè)置，本課程的理論課時(shí)與實(shí)驗(yàn)課時(shí)適時(shí)增加，同時(shí)加強(qiáng)學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)知識(shí)理性認(rèn)識(shí)與感性認(rèn)識(shí)的有機(jī)結(jié)合。為后續(xù)課程奠定基礎(chǔ)。各章教學(xué)要求及教學(xué)要點(diǎn)第一章 緒論課時(shí)分配：2課時(shí)教學(xué)要求：本章是課程的入門，主要介紹數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和概念。掌握數(shù)據(jù)結(jié)構(gòu)及其相關(guān)概念。熟悉數(shù)據(jù)的

5、四種基本結(jié)構(gòu)類型。熟悉四種不同存儲(chǔ)結(jié)構(gòu)。熟悉算法的五個(gè)重要特征。掌握算法的設(shè)計(jì)要求。掌握算法的兩種效率量度。了解大O表示法及大O運(yùn)算規(guī)則。本章要注意算法的時(shí)間復(fù)雜度和空間復(fù)雜度、大O表示法這兩個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容：第一節(jié) 什么是數(shù)據(jù)結(jié)構(gòu)一、什么是數(shù)據(jù)結(jié)構(gòu)。第二節(jié) 基本概念和術(shù)語(yǔ)一、數(shù)據(jù)結(jié)構(gòu)的基本概念。二、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)。三、數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)。第三節(jié) 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)一、數(shù)據(jù)結(jié)構(gòu)中的C語(yǔ)法和常用表示方法。二、基本操作。第四節(jié) 算法和算法分析一、算法的定義。二、算法的重要特性。三、算法設(shè)計(jì)的要求。四、算法效率的度量。五、大O表示法及大O運(yùn)算規(guī)則。六、算法的存儲(chǔ)空間需求。思考

6、題： 1.數(shù)據(jù)結(jié)構(gòu)由哪幾部分組成？2.數(shù)據(jù)的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)分別包括哪幾種類型？3.算法的五個(gè)重要特性是什么？第二章 線性表課時(shí)分配：6課時(shí)教學(xué)要求： 了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系。理解在計(jì)算機(jī)中，表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡(jiǎn)稱為順序表，用后者表示的線性表簡(jiǎn)稱為鏈表。熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法，以及線性表的各種基本操作的實(shí)現(xiàn)。了解從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合。本章要注意線性鏈表的基本運(yùn)算、循環(huán)鏈表的實(shí)現(xiàn)、雙向鏈表的實(shí)現(xiàn)這三個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容： 第一節(jié) 線

7、性表的類型定義一、線性表的類型定義。二、線性表的操作。第二節(jié) 線性表的順序表示和實(shí)現(xiàn)一、線性表的順序存儲(chǔ)結(jié)構(gòu)及基本概念。二、線性表的元素、位置的確定與計(jì)算。三、線性表的C語(yǔ)言描述。四、線性表的基本操作。五、線性表的引入操作。六、線性表操作的應(yīng)用。第三節(jié) 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、線性鏈表的定義。二、線性鏈表的相關(guān)概念。三、線性鏈表結(jié)構(gòu)的C語(yǔ)言定義。四、單鏈表的操作實(shí)現(xiàn)。五、靜態(tài)鏈表的定義和基本操作。六、循環(huán)鏈表的定義和基本操作。七、雙向鏈表的定義和基本操作。思考題： 1.線性表的邏輯結(jié)構(gòu)特征是什么？當(dāng)順序表和鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，線性表中結(jié)點(diǎn)之間的關(guān)系分別用什么來(lái)表示？2.順序表中插入和刪除一

8、個(gè)結(jié)點(diǎn)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)，具體移動(dòng)的結(jié)點(diǎn)個(gè)數(shù)取決于哪兩個(gè)參數(shù)？3.寫出從順序表中刪除所有值為x值的算法。4.從順序表中刪除重復(fù)的元素，并使剩余元素的相對(duì)次序保持不變，試寫出算法。5.編寫一個(gè)在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)最小節(jié)點(diǎn)的算法。第三章 棧和隊(duì)列課時(shí)分配：4課時(shí)教學(xué)要求：本章在線性表的基礎(chǔ)上，進(jìn)一步介紹限定性操作的線性結(jié)構(gòu)及其之上的操作運(yùn)算。掌握棧和隊(duì)列類型的特點(diǎn)，了解在相應(yīng)的應(yīng)用問(wèn)題中如何正確選用它們。熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法。熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法。了解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化

9、過(guò)程。本章要注意遞歸算法、遞歸與非遞歸過(guò)程的轉(zhuǎn)換這兩個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容：第一節(jié) 棧一、棧的定義和棧的抽象數(shù)據(jù)類型。二、棧的相關(guān)概念。三、棧的兩種存儲(chǔ)表示方法順序棧。四、棧的兩種存儲(chǔ)表示方法鏈棧。第二節(jié) 棧與遞歸的實(shí)現(xiàn)一、遞歸的概念。二、遞歸實(shí)現(xiàn)的例子。三、遞歸算法與非遞歸算法的轉(zhuǎn)換。第三節(jié) 隊(duì)列一、隊(duì)列的抽象數(shù)據(jù)類型定義。二、隊(duì)列的性質(zhì)。三、鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。四、循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn)。思考題：1.編寫一個(gè)算法，利用棧的基本運(yùn)算，將指定棧中的內(nèi)容進(jìn)行逆轉(zhuǎn)。2.編寫一個(gè)算法，利用棧的基本運(yùn)算，返回指定棧中的棧底元素。3.編寫一個(gè)算法，利用隊(duì)列和棧的基本算法，將指定隊(duì)列

10、中的內(nèi)容進(jìn)行逆轉(zhuǎn)。4.在HQ的鏈隊(duì)中，編寫求該鏈隊(duì)中結(jié)點(diǎn)個(gè)數(shù)的算法思路與描述。5.已知一遞歸函數(shù)，分別寫出一個(gè)遞歸算法和一個(gè)非遞歸算法。第四章 串課時(shí)分配：2課時(shí)教學(xué)要求： 本章的目的是介紹串的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及串上的基本運(yùn)算。熟悉串的七種基本操作的定義，并能利用這些基本操作來(lái)實(shí)現(xiàn)串的其它各種操作的方法。掌握在串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法。了解串的堆存儲(chǔ)結(jié)構(gòu)以及在其上實(shí)現(xiàn)串操作的基本方法。了解串的匹配操作。本章要注意串的模式匹配這個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容： 第一節(jié) 串類型的定義一、串的相關(guān)概念及其定義。二、串的抽象數(shù)據(jù)類型定義。第二節(jié) 串的表示和實(shí)現(xiàn)一、定長(zhǎng)順序存儲(chǔ)表示

11、。二、串聯(lián)接操作。三、求子串操作。四、堆分配存儲(chǔ)表示。五、串的塊鏈存儲(chǔ)表示。思考題：1.順序串表示串位有哪兩種表示方法？2.鏈串的優(yōu)點(diǎn)、缺點(diǎn)各是什么？3.編寫一個(gè)算法計(jì)算一個(gè)子串在一個(gè)字符串中出現(xiàn)的次數(shù)，如果該子串不出現(xiàn)則為0。第五章 數(shù)組和廣義表課時(shí)分配：2課時(shí)教學(xué)要求：掌握數(shù)組的兩種存儲(chǔ)表示方法。掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。了解對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。了解稀疏矩陣的兩類壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍。領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法。了解一種結(jié)構(gòu)的鏈表。了解對(duì)非空廣義表進(jìn)行分解的方法：即將一個(gè)非空廣義

12、表分解為表頭和表尾兩部分。本章要注意二維數(shù)組的以行序?yàn)橹餍虼鎯?chǔ)的方式與以列序?yàn)橹餍虻拇鎯?chǔ)方式、廣義表的存儲(chǔ)結(jié)構(gòu)、矩陣的壓縮存儲(chǔ)方式這三個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容：第一節(jié) 數(shù)組的定義一、數(shù)組的抽象數(shù)據(jù)類型定義。二、數(shù)組和線性表的對(duì)比。三、數(shù)組的操作。第二節(jié) 數(shù)組的順序表示和實(shí)現(xiàn)一、數(shù)組的存儲(chǔ)結(jié)構(gòu)。二、數(shù)組元素存儲(chǔ)位置的計(jì)算。三、數(shù)組的順序表示和實(shí)現(xiàn)。第三節(jié) 廣義表的類型定義一、廣義表的類型定義。二、廣義表的相關(guān)概念。三、廣義表的基本操作。思考題：1.設(shè)二維數(shù)組A58的每個(gè)元素占8個(gè)字節(jié)，存儲(chǔ)器按字節(jié)編址，已知A的基地址為100，則A的終端節(jié)點(diǎn)A47的存儲(chǔ)地址是多少？若按行存儲(chǔ)時(shí)A25的地址是

13、多少？按列存儲(chǔ)時(shí)A25的存儲(chǔ)地址是多少？2.假定數(shù)組An的n個(gè)元素中有多個(gè)零元素，將A中的所有非零元素依次移到A的前端，設(shè)計(jì)算法的基本思路和步驟。3.分別按行優(yōu)先和列優(yōu)先的順序，編寫輸出數(shù)組的轉(zhuǎn)值函數(shù)。4.廣義表的長(zhǎng)度、深度、極表頭、標(biāo)尾如何確定？5.寫一個(gè)算法，判斷廣義表中左右括號(hào)是否配對(duì)，可將廣義表視為一個(gè)字符串。第六章 樹(shù)和二叉樹(shù)課時(shí)分配：8課時(shí)教學(xué)要求：熟練掌握二叉樹(shù)的結(jié)構(gòu)特性。了解相應(yīng)的證明方法。熟悉二叉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。掌握各種遍歷策略的遞歸算法，運(yùn)用遍歷算法，實(shí)現(xiàn)二叉樹(shù)的其它操作。遍歷二叉樹(shù)是二叉樹(shù)各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。層

14、次遍歷是按另一種搜索策略進(jìn)行的遍歷。理解二叉樹(shù)線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系。了解二叉樹(shù)的線索化過(guò)程以及在中序線索化樹(shù)上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。熟悉樹(shù)的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)。掌握樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，要求掌握一至二種建立二叉樹(shù)和樹(shù)的存儲(chǔ)結(jié)構(gòu)的方法。理解編寫實(shí)現(xiàn)樹(shù)的各種操作的算法。了解最優(yōu)樹(shù)的特性，掌握建立最優(yōu)樹(shù)和哈夫曼編碼的方法。本章要注意二叉樹(shù)的遍歷的非遞歸算法、Huffman樹(shù)及Huffman編碼、二叉樹(shù)的線索化、線索二叉樹(shù)這四個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容：第一節(jié) 樹(shù)的定義和基本術(shù)語(yǔ)一、樹(shù)的定義。二、樹(shù)的抽象

15、數(shù)據(jù)類型定義。三、樹(shù)的基本操作。四、樹(shù)的基本術(shù)語(yǔ)。第二節(jié) 二叉樹(shù)一、二叉樹(shù)的定義。二、二叉樹(shù)的抽象數(shù)據(jù)類型定義。三、二叉樹(shù)的基本操作。四、二叉樹(shù)的基本形態(tài)。五、二叉樹(shù)的性質(zhì)。六、二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)。七、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。第三節(jié) 遍歷二叉樹(shù)和線索二叉樹(shù)一、遍歷的定義。二、遍歷二叉樹(shù)的定義。三、先序遍歷二叉樹(shù)。四、中序遍歷二叉樹(shù)。五、后序遍歷二叉樹(shù)。六、遍歷二叉樹(shù)的非遞歸算法。第四節(jié) 樹(shù)和森林一、樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法。二、樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子表示法。三、樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉鏈表法。四、樹(shù)、森林、二叉樹(shù)的相互轉(zhuǎn)換。五、樹(shù)的遍歷。六、森林的遍歷。第五節(jié) 哈夫曼樹(shù)及其應(yīng)用一、最優(yōu)二叉樹(shù)（哈夫曼樹(shù)）的定義

16、。二、哈夫曼樹(shù)的構(gòu)建方法。三、哈夫曼編碼的定義。四、哈夫曼編碼的設(shè)計(jì)。五、哈夫曼編碼的算法。思考題：1.假設(shè)二叉樹(shù)采用鏈接存儲(chǔ)方式存儲(chǔ)，編寫一個(gè)二叉樹(shù)先序遍歷的非遞歸算法。2.假設(shè)二叉樹(shù)采用鏈接存儲(chǔ)方式存儲(chǔ)，編寫一個(gè)二叉樹(shù)中序遍歷的非遞歸算法。3.如何判斷二叉樹(shù)是否為滿二叉樹(shù)。4.高度為h的嚴(yán)格二叉樹(shù)至少有多少個(gè)結(jié)點(diǎn)？最多有多少個(gè)結(jié)點(diǎn)（設(shè)根的層數(shù)為1）？5.一棵2n+1個(gè)結(jié)點(diǎn)的二叉樹(shù)中，若無(wú)1度結(jié)點(diǎn)，則它有多少個(gè)度為2的結(jié)點(diǎn)？6.已知5個(gè)字符的哈夫曼編碼中，3個(gè)字符編碼分別為01、10、11，其余兩個(gè)字符的編碼長(zhǎng)度為3，則這兩個(gè)字符的編碼分別是多少？7.若某二叉樹(shù)的先序序列和中序序列分別為AB

17、DGHCEFI和GDHBAECIF，請(qǐng)畫出這棵樹(shù)。第七章 圖課時(shí)分配：4課時(shí)教學(xué)要求：熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法。了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。掌握?qǐng)D的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹(shù)的遍歷算法之間的類似和差異。了解應(yīng)用圖的遍歷算法求解各種簡(jiǎn)單路徑問(wèn)題。了解教科書中討論的各種圖的算法。本章要注意深度優(yōu)先搜索的非遞歸方法、廣度優(yōu)先搜索算法這兩個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容：第一節(jié) 圖的定義和術(shù)語(yǔ)一、圖的抽象數(shù)據(jù)類型。二、圖的基本操作。三、圖的定義及相關(guān)概念。第二節(jié) 圖的存儲(chǔ)結(jié)構(gòu)一、圖的數(shù)組表示法

18、。二、圖的鄰接表表示法。三、圖的逆鄰接表表示法。第三節(jié) 圖的遍歷一、圖的遍歷定義。二、圖的深度優(yōu)先搜索。三、圖的廣度優(yōu)先搜索。思考題：1.圖有哪幾種表示方法？給出一個(gè)圖用不同的方法表示出來(lái)。2.使用普里姆算法構(gòu)造出圖的一棵最小生成樹(shù)。3.使用克魯斯卡爾算法構(gòu)造出圖的一棵最小生成樹(shù)。4.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的多少倍？5.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是多少？6.編寫一個(gè)算法將一個(gè)無(wú)向圖的鄰接矩陣轉(zhuǎn)換成鄰接表。第八章 查找課時(shí)分配：4課時(shí)教學(xué)要求： 理解順序表和有序表的查找方法及其平均查找長(zhǎng)度的計(jì)算方法。掌握靜態(tài)查找樹(shù)的構(gòu)造方法和查找算法。理

19、解靜態(tài)查找樹(shù)和折半查找的關(guān)系。熟練掌握二叉排序樹(shù)的構(gòu)造和查找方法，以及插入刪除操作。掌握哈希表的構(gòu)造方法。理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。了解按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。本章要注意二叉排序樹(shù)的插入和刪除、二叉排序樹(shù)的查找分析這兩個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容：第一節(jié) 靜態(tài)查找表一、靜態(tài)查找表的定義。二、順序表的查找。三、查找操作的性能分析。四、有序表的查找。第二節(jié) 動(dòng)態(tài)查找表一、動(dòng)態(tài)查找表的定義。二、二叉排序樹(shù)的定義。三、二叉排序樹(shù)的插入和刪除操作。第三節(jié) 哈希表一、什么是哈希表。二、哈希函數(shù)的構(gòu)造方法直接定址法。三、哈希函數(shù)的構(gòu)造方法數(shù)字分析法。四、

20、哈希函數(shù)的構(gòu)造方法平方取數(shù)法。五、哈希函數(shù)的構(gòu)造方法折疊法。六、哈希函數(shù)的構(gòu)造方法除留余數(shù)法。七、哈希函數(shù)的構(gòu)造方法隨機(jī)數(shù)法。八、處理沖突的方法開(kāi)放地址法。九、處理沖突的方法再哈希法。十、處理沖突的方法鏈地址法。十一、處理沖突的方法建立一個(gè)公共溢出區(qū)。十二、哈希表的查找及其分析。思考題：1.順序查找在成功時(shí)的平均查找長(zhǎng)度為多少？在失敗時(shí)的關(guān)鍵字比較次數(shù)為多少？2.在分塊查找中，若用折半查找確定塊，則查找成功時(shí)的平均查找長(zhǎng)度約為多少？若用順序查找確定塊，則查找成功時(shí)的平均查找長(zhǎng)度為多少？3.設(shè)計(jì)一個(gè)二叉查找的遞歸算法思路。4.判定給定的二叉樹(shù)是否是二叉排序樹(shù)。5.設(shè)計(jì)一個(gè)算法，求出指定的結(jié)點(diǎn)在二

21、叉排序樹(shù)中的層次。第九章 內(nèi)部排序課時(shí)分配：4課時(shí)教學(xué)要求：了解排序的定義和各種排序方法的特點(diǎn)。熟悉各種方法的排序過(guò)程及其依據(jù)的原則?；凇瓣P(guān)鍵字間的比較”進(jìn)行排序的方法可以按排序過(guò)程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序等五類。掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類：O(n2)的簡(jiǎn)單排序方法，O(nlogn)的高效排序方法 和 O(dn)的基數(shù)排序方法。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。了解外部排

22、序的基本過(guò)程及其時(shí)間分析。本章要注意希爾排序的算法、各種排序算法在不同情況下的算法復(fù)雜度這兩個(gè)教學(xué)難點(diǎn)的分散化解。教學(xué)內(nèi)容： 第一節(jié) 概述一、排序的定義。二、排序的穩(wěn)定性和不穩(wěn)定性定義。三、排序過(guò)程所需的兩種基本操作。第二節(jié) 插入排序一、直接插入排序。二、折半插入排序。三、希爾排序。第三節(jié) 快速排序一、冒泡排序算法。二、快速排序算法。 第四節(jié) 各種內(nèi)部排序方法的比較一、各種排序算法在性能方面的比較。二、各種排序算法在穩(wěn)定性方面的比較。思考題：1.已知序列17，18，60，40，7，32，73，65，85，請(qǐng)給出采用冒泡排序法對(duì)該序列作升序排序時(shí)的每一趟結(jié)果。2.已知序列503，87，512，61，908，170，897，275，653，462，請(qǐng)給出采用快速排序法對(duì)該序列作升序時(shí)的每一趟結(jié)果。3.已知序列17，18