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

課程大綱西北大學(xué)《數(shù)據(jù)結(jié)構(gòu)》-13-國(guó)家精品課程西北大學(xué)《數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱2012-2013學(xué)年第1學(xué)期含課堂教學(xué)大綱、實(shí)訓(xùn)大綱、實(shí)驗(yàn)大綱等，以綱要形式規(guī)定課程的教學(xué)內(nèi)容，具體應(yīng)包括課程的教學(xué)目的、教學(xué)任務(wù)、教學(xué)內(nèi)容的結(jié)構(gòu)、模塊或單元教學(xué)目標(biāo)與任務(wù)、教學(xué)活動(dòng)以及教學(xué)方法上的基本要求等。

目錄1課程大綱 -1-1.1課程描述 -1-1.2課程目標(biāo) -2-1.3先修課程 -2-1.4后續(xù)課程 -2-1.5教學(xué)時(shí)數(shù) -2-1.6教學(xué)方式 -2-1.7教學(xué)內(nèi)容 -3-1.8學(xué)時(shí)分配表 -9-1.9參考文獻(xiàn) -9-2實(shí)驗(yàn)大綱 -10-2.1實(shí)驗(yàn)?zāi)康?-10-2.2實(shí)驗(yàn)要求 -10-2.3實(shí)驗(yàn)內(nèi)容 -11-2.4實(shí)驗(yàn)考核方式 -12-

1課程大綱1.1課程描述數(shù)據(jù)結(jié)構(gòu)及其處理算法是設(shè)計(jì)與實(shí)現(xiàn)系統(tǒng)軟件和大型應(yīng)用軟件的重要基礎(chǔ)，“數(shù)據(jù)結(jié)構(gòu)與算法”課程是計(jì)算機(jī)專業(yè)重要的專業(yè)技術(shù)基礎(chǔ)課程。該課程的內(nèi)容對(duì)于培養(yǎng)學(xué)生的計(jì)算思維、系統(tǒng)分析與設(shè)計(jì)、算法設(shè)計(jì)與分析、程序設(shè)計(jì)與實(shí)現(xiàn)等學(xué)科基本能力非常重要。本課程系統(tǒng)地介紹了軟件開(kāi)發(fā)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的存儲(chǔ)結(jié)構(gòu)和操作算法，包括常用的查找技術(shù)、排序技術(shù)、遞歸技術(shù)等。1.2課程目標(biāo)掌握“數(shù)據(jù)結(jié)構(gòu)”中的基本概念、合理組織數(shù)據(jù)的基本方法、高效處理數(shù)據(jù)的基本算法、常用的經(jīng)典算法、通用的程序設(shè)計(jì)技術(shù)，以及面對(duì)實(shí)際問(wèn)題時(shí)選擇恰當(dāng)數(shù)據(jù)結(jié)構(gòu)并設(shè)計(jì)高效算法的能力，培養(yǎng)學(xué)生用計(jì)算思維分析問(wèn)題的能力，提高學(xué)生上機(jī)解決較大規(guī)模實(shí)際問(wèn)題的能力，為進(jìn)一步的軟件開(kāi)發(fā)打下堅(jiān)實(shí)的基礎(chǔ)。1.3先修課程離散數(shù)學(xué)，計(jì)算機(jī)導(dǎo)論，高級(jí)語(yǔ)言程序設(shè)計(jì)。1.4后續(xù)課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)。1.5教學(xué)時(shí)數(shù)72小時(shí)課堂教學(xué)和18小時(shí)實(shí)驗(yàn)教學(xué)；1.6教學(xué)方式“數(shù)據(jù)結(jié)構(gòu)與算法”是理論與實(shí)踐并重的課程，采用理論教學(xué)和上機(jī)訓(xùn)練相結(jié)合的教學(xué)方式。在理論教學(xué)方面，以課堂講授為主，同時(shí)借助網(wǎng)絡(luò)教學(xué)平臺(tái)，拓展課堂講授的相關(guān)知識(shí)，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。課堂講授采用多媒體課件，用FLASH動(dòng)畫(huà)形象地展示抽象算法的處理過(guò)程。書(shū)面作業(yè)是消化掌握課堂知識(shí)的重要環(huán)節(jié)，是培養(yǎng)計(jì)算思維的重要手段，是上機(jī)訓(xùn)練的前提條件。每章應(yīng)布置一定數(shù)量的書(shū)面作業(yè)，其難度和覆蓋面應(yīng)該恰當(dāng)?？筛鶕?jù)學(xué)生作業(yè)情況，組織若干次獨(dú)立的習(xí)題課，針對(duì)學(xué)生作業(yè)中出現(xiàn)的典型問(wèn)題進(jìn)行綜合講評(píng)。另外，還可以不定期地進(jìn)行課堂小測(cè)驗(yàn)（15分鐘左右）。在上機(jī)訓(xùn)練方面，根據(jù)教學(xué)目標(biāo)，設(shè)計(jì)出規(guī)模適當(dāng)、難度適中，實(shí)用性和趣味性兼顧的上機(jī)題目。上機(jī)題目分為三類：第一類是為了驗(yàn)證當(dāng)前所學(xué)知識(shí)點(diǎn)的驗(yàn)證性實(shí)驗(yàn)，第二類是為了運(yùn)用多個(gè)相關(guān)知識(shí)點(diǎn)解決問(wèn)題的綜合性實(shí)驗(yàn)，第三類是為了靈活運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的設(shè)計(jì)性實(shí)驗(yàn)（后續(xù)課程：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)）。要求學(xué)生完成數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的設(shè)計(jì)，并上機(jī)調(diào)試實(shí)現(xiàn)，最后提交規(guī)范的實(shí)驗(yàn)報(bào)告。針對(duì)不同基礎(chǔ)的學(xué)生，教師應(yīng)該提供不同的上機(jī)指導(dǎo)。1.7教學(xué)內(nèi)容緒論本章討論數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)，包括相關(guān)概念、算法基礎(chǔ)與問(wèn)題求解方法。1.1相關(guān)概念一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度數(shù)據(jù)數(shù)據(jù)元素，數(shù)據(jù)對(duì)象掌握數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，運(yùn)算熟練掌握數(shù)據(jù)類型基本數(shù)據(jù)類型，抽象數(shù)據(jù)類型掌握1.2算法基礎(chǔ)一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度算法概念與描述方法算法定義，算法設(shè)計(jì)要求，算法描述方式，算法描述規(guī)范要點(diǎn)，用高級(jí)語(yǔ)言實(shí)現(xiàn)抽象數(shù)據(jù)類型，算法設(shè)計(jì)風(fēng)格，高級(jí)語(yǔ)言中參數(shù)傳遞和結(jié)果返回的相關(guān)技術(shù)掌握算法設(shè)計(jì)基本方法窮舉法，分治法，回溯法，貪心法，動(dòng)態(tài)規(guī)劃法了解算法分析大O表示法，漸進(jìn)分析，最佳、最差和平均時(shí)間復(fù)雜度，時(shí)間和空間的折衷掌握1.3問(wèn)題求解方法一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度問(wèn)題分析與抽象問(wèn)題抽象，數(shù)據(jù)結(jié)構(gòu)抽象，算法抽象掌握系統(tǒng)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)掌握線性結(jié)構(gòu)本章討論線性結(jié)構(gòu)的定義、存儲(chǔ)結(jié)構(gòu)、基本操作及其應(yīng)用。2.1線性表一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度線性表順序表（數(shù)組）的存儲(chǔ)結(jié)構(gòu)與基本操作熟練掌握單鏈表的存儲(chǔ)結(jié)構(gòu)與基本操作熟練掌握雙鏈表的存儲(chǔ)結(jié)構(gòu)與基本操作熟練掌握循環(huán)鏈表的存儲(chǔ)結(jié)構(gòu)與基本操作熟練掌握靜態(tài)鏈表的存儲(chǔ)結(jié)構(gòu)與基本操作了解順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)比較熟練掌握2.2棧和隊(duì)列一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度棧順序棧、鏈棧棧的應(yīng)用（表達(dá)式求值和轉(zhuǎn)換）熟練掌握棧與遞歸（遞歸實(shí)現(xiàn)機(jī)制、遞歸到非遞歸轉(zhuǎn)換）初步掌握隊(duì)列鏈隊(duì)列、循環(huán)隊(duì)列的實(shí)現(xiàn)，利用隊(duì)列進(jìn)行排隊(duì)問(wèn)題求解熟練掌握字符串字符串存儲(chǔ)結(jié)構(gòu)與簡(jiǎn)單匹配操作實(shí)現(xiàn)掌握字符串的快速模式匹配算法（KMP算法）初步掌握2.3字符串一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度字符串字符串存儲(chǔ)結(jié)構(gòu)與簡(jiǎn)單匹配操作實(shí)現(xiàn)掌握字符串的快速模式匹配算法（KMP算法）初步掌握2.4擴(kuò)展線性結(jié)構(gòu)一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度多維數(shù)組多維數(shù)組的順序存儲(chǔ)掌握特殊矩陣（三角矩陣、對(duì)稱矩陣、對(duì)角矩陣、稀疏矩陣）的壓縮存儲(chǔ)掌握稀疏矩陣的三元組存儲(chǔ)和十字鏈表存儲(chǔ)了解廣義表廣義表的存儲(chǔ)結(jié)構(gòu)，廣義表的簡(jiǎn)單操作了解二叉樹(shù)、樹(shù)與森林本章討論樹(shù)結(jié)構(gòu)的定義、存儲(chǔ)結(jié)構(gòu)、基本操作及其應(yīng)用。3.1二叉樹(shù)一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度二叉樹(shù)概念二叉樹(shù)的遞歸定義，二叉樹(shù)的性質(zhì)，二叉樹(shù)的有關(guān)術(shù)語(yǔ)熟練掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)熟練掌握二叉鏈表熟練掌握三叉鏈表，靜態(tài)三叉鏈表熟練掌握二叉樹(shù)的遍歷方法及其應(yīng)用前序遍歷，中序遍歷，后序遍歷，層次優(yōu)先遍歷；由遍歷序列確定二叉樹(shù)等熟練掌握遞歸遍歷算法到非遞歸遍歷算法的轉(zhuǎn)換方法，非遞歸遍歷算法掌握線索二叉樹(shù)線索二叉樹(shù)的建立與使用了解二叉樹(shù)應(yīng)用Huffman樹(shù)（貪心法構(gòu)造）利用Huffman樹(shù)進(jìn)行編碼解碼熟練掌握3.2樹(shù)與森林一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的鏈?zhǔn)酱鎯?chǔ)（孩子兄弟鏈表，孩子鏈表，父指針表示法）掌握樹(shù)、森林與二叉樹(shù)的關(guān)系樹(shù)與森林的遞歸定義，森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系及其轉(zhuǎn)換方法掌握樹(shù)的遍歷（先根遍歷、后根遍歷、廣度優(yōu)先遍歷）森林的遍歷（前序遍歷、中序遍歷、后序遍歷）掌握K叉樹(shù)了解圖結(jié)構(gòu)本章討論圖結(jié)構(gòu)的定義、存儲(chǔ)結(jié)構(gòu)、基本操作及其應(yīng)用。4.1圖的概念一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度圖的概念頂點(diǎn)，邊，權(quán)，入度，出度，有向圖，無(wú)向圖，稀疏圖，稠密圖，子圖，路徑，簡(jiǎn)單路徑，簡(jiǎn)單回路，無(wú)環(huán)圖，有向無(wú)環(huán)圖（DAG），連通圖，強(qiáng)連通圖，帶權(quán)圖掌握4.2圖的存儲(chǔ)結(jié)構(gòu)一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度圖的存儲(chǔ)結(jié)構(gòu)鄰接矩陣熟練掌握鄰接表熟練掌握逆鄰接表，十字鏈表，鄰接多重表了解4.3圖的遍歷方法一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度圖的遍歷圖的深度優(yōu)先遍歷熟練掌握?qǐng)D的寬度優(yōu)先遍歷熟練掌握?qǐng)D的生成樹(shù)，生成森林掌握4.4圖的經(jīng)典算法一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度有向無(wú)環(huán)圖拓?fù)渑判蛘莆贞P(guān)鍵路徑掌握最小生成樹(shù)Prim算法（貪心法）掌握Kruskal算法（貪心法）掌握最短路徑Dijkstra算法（貪心法）掌握Floyd算法(動(dòng)態(tài)規(guī)劃法)掌握查找技術(shù)本章討論常用的查找技術(shù)。5.1查找基本概念與基于線性表的查找一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度查找基本概念查找某個(gè)結(jié)點(diǎn)的比較次數(shù)，平均查找長(zhǎng)度掌握順序表查找采用監(jiān)視哨的順序查找熟練掌握折半查找，折半判定樹(shù)熟練掌握分塊查找索引表查找和塊內(nèi)查找的二級(jí)查找掌握5.2基于樹(shù)結(jié)構(gòu)的查找一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度二叉搜索樹(shù)二叉搜索樹(shù)的定義與查找過(guò)程，二叉搜索樹(shù)結(jié)點(diǎn)的插入與刪除；熟練掌握擴(kuò)展二叉搜索樹(shù)平衡二叉樹(shù)（AVL）初步掌握紅黑樹(shù)了解多路查找樹(shù)m路查找樹(shù)掌握B樹(shù)的定義B樹(shù)的查找、插入、刪除操作初步掌握B+樹(shù)的定義B+樹(shù)的查找、插入簡(jiǎn)介字符樹(shù)了解5.3散列查找一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度散列查找散列函數(shù)(除留余數(shù)法)沖突處理方法(線性探測(cè)法、同義詞鏈表法)散列表的查找、構(gòu)建算法，平均查找性能分析熟練掌握同義詞，碰撞，二次聚集散列函數(shù)(平方取中法、折疊法)沖突處理方法(二次探測(cè)法、偽隨機(jī)探測(cè)法、雙散列函數(shù))掌握內(nèi)部排序本章討論常用的排序技術(shù)。一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度基本概念數(shù)據(jù)記錄，關(guān)鍵字，正序，逆序，穩(wěn)定性，待排序表的結(jié)構(gòu)（向量、鏈表、地址表結(jié)構(gòu)）掌握插入排序法直接插入排序熟練掌握Shell排序掌握交換排序法冒泡排序熟練掌握快速排序（分治法）熟練掌握選擇排序法直接選擇排序熟練掌握堆排序掌握歸并排序二路歸并（分治法）掌握分配排序桶排序，基數(shù)排序（鏈?zhǔn)?、順序）初步掌握排序算法分析時(shí)間代價(jià)：記錄的比較和移動(dòng)次數(shù)空間代價(jià)：輔助數(shù)據(jù)空間大小排序問(wèn)題的下限掌握外部排序一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度概念主存儲(chǔ)器，外存儲(chǔ)器，緩沖區(qū)，順串了解排序算法置換選擇排序多路歸并(勝方樹(shù)、敗方樹(shù))最佳歸并樹(shù)多路歸并的讀盤(pán)和寫(xiě)盤(pán)次數(shù)了解文件組織技術(shù)一級(jí)知識(shí)點(diǎn)二級(jí)知識(shí)點(diǎn)掌握程度索引文件ISAM,VSAM初步掌握散列文件桶，基桶，溢出桶初步掌握倒排表次關(guān)鍵字，倒排索引，基于屬性的檢索初步掌握1.8學(xué)時(shí)分配表序號(hào)內(nèi)容授課學(xué)時(shí)上機(jī)學(xué)時(shí)1概論基礎(chǔ)32線性表633棧和隊(duì)列534字符串225數(shù)組和廣義表526樹(shù)形結(jié)構(gòu)及其應(yīng)用1047圖結(jié)構(gòu)及其應(yīng)用848查找技術(shù)639內(nèi)部排序6310外部排序與文件組織301.9參考文獻(xiàn)耿國(guó)華等，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學(xué)出版社，2002.2。耿國(guó)華等，《數(shù)據(jù)結(jié)構(gòu)（第2版）》，西安電子科技大學(xué)出版社，2008.7。耿國(guó)華等，《數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述》及隨附教學(xué)光盤(pán)，高等教育出版社，2005.7。耿國(guó)華等，《數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述(第2版)》及隨附教學(xué)光盤(pán)，高等教育出版社，2011.6。嚴(yán)蔚敏等，《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，清華大學(xué)出版社，2007.3。RobertL.Kruse，《DataStructuresandProgramDesigninC++》，高等教育出版社（影印版），2001.5。MarkWeiss，《DataStructuresandAlgorithmAnalysisinC(3rdedition)》，AddisonWesley，2005.11。SartaSahni，《DataStructures,Algorithms,andApplicationsinC++》，McGraw-Hill，2003。EllisHorowitz，《FundamentalsofDataStructuresinC》，SiliconPress，2007.8。張銘，王騰蛟，趙海燕，《數(shù)據(jù)結(jié)構(gòu)與算法》，高等教育出版社，2008.6。北京大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》國(guó)家精品課程網(wǎng)站，/pkujpk/course/sjjg/殷人昆，數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcＣ＋＋描述），清華大學(xué)出版社，2007.6。D.E.Knuth,theartofcomputerprogrammingvolume1/fundamewfalalgorithms,ThirdEdition(Reading,Massachusetts:Addison-Wesley,1997);volume3/sortingandsearching,SecondEdition(Reading,Massachusetts:Addison-Wesley,1998)格里斯，程序設(shè)計(jì)方法技巧，第三卷。2實(shí)驗(yàn)大綱2.1實(shí)驗(yàn)?zāi)康摹皵?shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)專業(yè)一門(mén)重要的專業(yè)技術(shù)基礎(chǔ)課程，由于本課程的技術(shù)性與實(shí)踐性，課程實(shí)驗(yàn)的設(shè)置十分必要。上機(jī)實(shí)習(xí)是對(duì)學(xué)生的一種全面綜合訓(xùn)練，通過(guò)分析、設(shè)計(jì)、編碼、調(diào)試等各環(huán)節(jié)的訓(xùn)練，使學(xué)生深刻理解、牢固掌握所用到的技術(shù)，提高計(jì)算思維能力。在掌握基本數(shù)據(jù)結(jié)構(gòu)和基本算法的基礎(chǔ)上，提高學(xué)生的分析、設(shè)計(jì)、編碼和調(diào)試能力，為進(jìn)一步的軟件開(kāi)發(fā)打下堅(jiān)實(shí)基礎(chǔ)。2.2實(shí)驗(yàn)要求根據(jù)教學(xué)目標(biāo)，設(shè)計(jì)出規(guī)模適當(dāng)、難度適中，實(shí)用性和趣味性兼顧的上機(jī)題目。上機(jī)題目分為三類：第一類是為了驗(yàn)證當(dāng)前所學(xué)知識(shí)點(diǎn)的驗(yàn)證性實(shí)驗(yàn)，第二類是為了運(yùn)用多個(gè)相關(guān)知識(shí)點(diǎn)解決問(wèn)題的綜合性實(shí)驗(yàn)，第三類是為了靈活運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的設(shè)計(jì)性實(shí)驗(yàn)（課程設(shè)計(jì)）。針對(duì)不同基礎(chǔ)的學(xué)生，教師應(yīng)該提供不同的上機(jī)指導(dǎo)。要求學(xué)生在認(rèn)真分析問(wèn)題的基礎(chǔ)上，完成數(shù)據(jù)結(jié)構(gòu)和相關(guān)算法的概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)，然后編碼并上機(jī)調(diào)試，最后提交規(guī)范、統(tǒng)一的實(shí)驗(yàn)報(bào)告。在實(shí)驗(yàn)結(jié)束前，教師要注意現(xiàn)場(chǎng)驗(yàn)收學(xué)生設(shè)計(jì)實(shí)現(xiàn)的系統(tǒng)，并給出現(xiàn)場(chǎng)評(píng)定。評(píng)定級(jí)別分優(yōu)秀、良好、合格、不合格，最后結(jié)合實(shí)驗(yàn)報(bào)告給出實(shí)驗(yàn)成績(jī)。實(shí)驗(yàn)學(xué)時(shí)為18機(jī)時(shí)。2.3實(shí)驗(yàn)內(nèi)容要求完成以下六個(gè)題目：實(shí)習(xí)一約瑟夫環(huán)問(wèn)題（2機(jī)時(shí)）用循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題，熟悉鏈表結(jié)構(gòu)的使用。實(shí)習(xí)二停車(chē)場(chǎng)管理（4機(jī)時(shí)） 利用棧和隊(duì)列模擬停車(chē)場(chǎng)管理，學(xué)習(xí)利用棧和隊(duì)列解決實(shí)際問(wèn)題。實(shí)習(xí)三二叉樹(shù)基本操作（2機(jī)時(shí)）創(chuàng)建、遍歷、插入、刪除、顯示二叉樹(shù)，通過(guò)二叉樹(shù)的基本操作，掌握樹(shù)結(jié)構(gòu)的處理方法。實(shí)習(xí)四圖的基本操作（4機(jī)時(shí)）分別用鄰接矩陣和鄰接表實(shí)現(xiàn)以下操作：圖的創(chuàng)建、遍歷、插入、刪除、最短路徑。熟悉圖的常用存儲(chǔ)結(jié)構(gòu)和基本操作。實(shí)習(xí)五哈希表設(shè)計(jì)（3機(jī)時(shí)）給定30個(gè)人的姓名，用除留余數(shù)法構(gòu)造哈希函數(shù)，用線性探測(cè)再散列法處理沖突，構(gòu)造哈希表，掌握哈希表的設(shè)計(jì)與使用。實(shí)習(xí)六常用排序算法的對(duì)比分析（3機(jī)時(shí)）分別實(shí)現(xiàn)直接插入排序、冒泡排序、簡(jiǎn)單選擇排序、希爾排序、快速排序、堆排序，并隨機(jī)生成50個(gè)數(shù)，比較各算法的時(shí)、空性能和穩(wěn)定性。掌握常用排序算法的特點(diǎn)，以便根據(jù)實(shí)際情況選擇使用。2.4實(shí)驗(yàn)考核方式實(shí)驗(yàn)考核采用上機(jī)表現(xiàn)、程序質(zhì)量、實(shí)驗(yàn)報(bào)告質(zhì)量相結(jié)合