【文章內容簡介】 器分配策略和算法、無用單元收集時的標志算法第九章查找（一）目的要求了解靜態(tài)查找表(順序表，有序表，索引順序表)；動態(tài)查找表(二叉排序樹，平衡二叉樹，B樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析；（二）教學內容 本章知識點：、折半查找和索引查找的方法、應用(掌握)；(掌握)；(掌握)；，B+樹和鍵樹的特點以及它們的建立過程（理解）；(掌握)；；(掌握)。（三）重點與難點重點：二叉排序樹的構造方法、二叉平衡樹的建立方法；哈希表的構造、應用；難點：二叉排序樹的構造及應用；哈希表的構造方法；查找的平均長度。第十章內部排序（一）目的要求掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數排序等算法。（二）教學內容 本章知識點：(掌握)； (掌握)；(掌握)。（三）重點與難點重點：各種排序方法的特點及其應用；實現(xiàn)排序的各種算法。難點：各種排序算法的時間復雜度分析。十一章外部排序（一）目的要求理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實現(xiàn)；置換選擇排序；最佳歸并樹。（二）教學內容 本章知識點：(理解)；(掌握)；(掌握)；(掌握)；(掌握)；（熟悉）；，外存讀/寫次數的計算方法(掌握)。（三）重點與難點重點：外部排序過程和實現(xiàn)方法；多路并歸算法及其實現(xiàn)； 難點：最佳并歸樹的構造方法及其應用。實踐教學部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。實驗一停車場管理系統(tǒng)（一）實驗內容 以棧模擬車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數據序列進行模擬管理。棧以順序結構實現(xiàn)，隊列以鏈表結構實現(xiàn)。（二）實驗過程 編程實現(xiàn)實驗內容。（三）實驗教學基本要求通過實例，使學生掌握棧和隊列兩種特殊的線性結構，掌握棧和隊列的特點。實驗后學生提交實驗報告。（四）實驗設備和材料 計算機。（五）實驗學時 4學時實驗二教學計劃編制問題（一）實驗內容假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。編制一個教學計劃程序。（二）實驗過程編程實現(xiàn)實驗內容。（三）實驗教學基本要求通過實例，使學生熟悉圖的各種存儲結構的特性，掌握如何應用圖結構解決具體問題。實驗后學生提交實驗報告。（四）實驗設備和材料 計算機。（五）實驗學時 2學時實驗三最小生成樹問題（一）實驗內容利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權值。（二）實驗過程 編程實現(xiàn)實驗內容（三）實驗教學基本要求通過實例，使學生熟悉圖的各種存儲結構的特性，掌握如何應用圖結構解決具體問題。實驗后學生提交實驗報告。（四）實驗設備和材料 計算機。（五）實驗學時 2學時實驗四哈希表設計（一）實驗內容假設人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數用除留余數法構造，用偽隨機探測再散列法處理沖突。（二）實驗過程 編程實現(xiàn)實驗內容（三）實驗教學基本要求 掌握索引技術的使用。（四）實驗設備和材料 計算機（五）實驗學時 4學時五、課程教學的基本要求和主要環(huán)節(jié)本課程可采用課堂講授、課堂討論、習題課等進行課堂教學。條件允許可采用CAI、電子教案、幻燈片、參觀等進行輔助教學。每章布置3~6道習題以鞏固教學。在課程后半程，安排3~4個上機實驗，讓學生應用數據結構的理論、方法，分組設計幾個較大的軟件，使理論與實際相結合?？荚嚥捎瞄]卷方式。總成績由平時成績和考試成績組成。平時成績占30%，考試成績占70%。六、本課程與其它課程的聯(lián)系與分工先修課包括：集合論，圖論，高級語言（結構或記錄，指針）；后續(xù)課包括：數據庫，編譯原理，操作系統(tǒng)等。七、建議教材與參考教材《數據結構》（C語言版）嚴蔚敏等清華大學出版社1997 《數據結構題集》嚴蔚敏等清華大學出版社1999《數據結構習題與解析》李春葆清華大學出版社2004八、負責人撰稿人：劉景匯、李玉香審稿人：系（院）領導：第四篇：數據結構課程設計教學大綱《數據結構課程設計》教學大綱Data Structure Course Design一、課程的性質、教學目的和要求《數據結構》是計算機軟件的一門基礎課程，計算機科學各領域及有關的應用軟件都要用到各種類型的數據結構。學好數據結構對掌握實際編程能力是很有幫助的。為了學好《數據結構》，必須編寫一些在特定數據結構上的算法，通過上機調試，才能更好地掌握各種數據結構及其特點，同時提高解決計算機應用實際問題的能力。二、設計要點1．設計和調試過程要規(guī)范化。① 需求分析將題目中要求的功能進行敘述分析，并且設計解決此問題的數據存儲結構，（有些題目已經指定了數據存儲的，按照指定的設計），設計或敘述解決此問題的算法，描述算法建議使用流程圖，進行算法分析指明關鍵語句的時間復雜度。給出實現(xiàn)功能的一組或多組測試數據，程序調試后，將按照此測試數據進行測試的結果列出來。對有些題目提出算法改進方案，比較不同算法的優(yōu)缺點。如果程序不能正常運行，寫出實現(xiàn)此算法中遇到的問題，和改進方法。②源程序（可以是一組源程序，即詳細設計部分）源程序要按照寫程序的規(guī)則來編寫。要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。程序能夠運行，要有基本的容錯功能。盡量避免出現(xiàn)操作錯誤時出現(xiàn)死循環(huán)。2．課程設計實習報告的書寫格式① 設計題目（任選其一）②運行環(huán)境（軟、硬件環(huán)境）③算法設計的思想 ④算法的流程圖 ⑤算法設計分析 ⑥源代碼 ⑦運行結果分析 ⑧收獲及體會 3．實施方式可設23人一題，安排在《數據結構》課程開課學期布置題目，然后在期末前兩周完成。三．設計要求學生要發(fā)揮自主學習的能力，充分利用時間，安排好課設的時間計劃，并在課設過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。課程設計按照教學要求需要1周時間完成，1周中每天至少要上68小時的機來調試C語言設計的程序，總共至少要上機調試程序30小時。為保證質量，需要每個學生將每天的上機調試程序的時間記錄下來，作為評判成績的標準之一。四．設計題目校園導游程序[問題描述]用無向網表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題。[基本要求]（1）查詢各景點的相關信息；（2）查詢圖中任意兩個景點間的最短路徑。（3）查詢圖中任意兩個景點間的所有路徑。（4）增加、刪除、更新有關景點和道路的信息。[選作內容]（1）求多個景點的最佳（最短）游覽路徑。（2）區(qū)分機動車道和人行道。（3）實現(xiàn)導游圖的仿真界面。算術表達式求值[問題描述]一個算術表達式是由操作數(operand)、運算符(operator)和界限符(delimiter)組成的。假設操作數是正整數，運算符只含加減乘除等四種運算符，界限符有左右括號和表達式起始、結束符“”，如：（7+15）*（2328/4）。引入表達式起始、結束符是為了方便。編程利用“算符優(yōu)先法”求算術表達式的值。[基本要求]（1）從鍵盤讀入一個合法的算術表達式，輸出正確的結果。（2）顯示輸入序列和棧的變化過程。[選作內容]擴充運算符集合。引入變量操作數。操作數類型擴充到實數。文學研究助手[問題描述]文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手”。[基本要求]英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現(xiàn)次數和出現(xiàn)位置所在行的行號，格式自行設計。[測試數據]以你的源程序模擬英文小說，程序語言保留字集作為待統(tǒng)計的詞匯集。[實現(xiàn)提示]設小說中的詞匯一律不跨行。這樣，每讀入一行，就統(tǒng)計每個詞在這行中的出現(xiàn)次數。出現(xiàn)位置所在行的行號可以用鏈表存儲。若某行中出現(xiàn)了不止一次，不必存多個相同的行號。如果讀者希望達到選作部分（1）和（2）所提出的要求，則首先應把KMP算法改寫成如下的等價形式，再將它推廣到多個模式的情形。[選作內容]（1）模式匹配要基于KMP算法。（2）整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。（3）假設小說中的每個單詞或者從行首開始，或者前置以一個空格符。利用單詞匹配特點另寫一個高效的統(tǒng)計程序，與KMP算法統(tǒng)計程序進行效率比較。（4）推廣到更一般的模式集匹配問題，并設待查模式串可以跨行（提示：定義操作getachar）[問題描述]可以輸入一個任意大小的迷宮數據，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；[基本要求]含有兩個以上的迷宮圖，由用戶選擇哪一張迷宮圖； 實現(xiàn)深度優(yōu)先、廣度優(yōu)先兩種回溯法。在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、算法的時間復雜度、另外可以提出算法的改進方法；[實現(xiàn)提示]可以用一個二維數組存儲迷宮圖，值為1或者0分別表示通路和不通； 搜索路徑可以參考樹的深度優(yōu)先和廣度優(yōu)先算法。[問題描述]假設表達式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即CC或[（[ ] [ ]）]等為正確格式，[（]）或（（（]均為不正確的格式。檢驗括號是否匹配的方法可用“期待的緊迫程度”這個概念來描述。例如：考慮下列的括號序列：[([ ] [ ])]8當計算機接受了第1個括號以后，他期待著與其匹配的第8個括號的出現(xiàn)，然而等來的卻是第2個括號，此時第1個括號“[”只能暫時靠邊，而迫切等待與第2個括號相匹配的 第7個括號“）”的出現(xiàn)，類似的，因只等來了第3個括號“[”，此時，其期待的緊迫程度較第2個括號更緊迫，則第2個括號只能靠邊，讓位于第3個括號，顯然第3個括號的期待緊迫程度高于第2個括號，而第2個括號的期待緊迫程度高于第1個括號；在接受了第4個括號之后，第3個括號的期待得到了滿足，消解之后，第2個括號的期待匹配就成了最急迫的任務了，??，依次類推?？梢娺@個處理過程正好和棧的特點相吻合。[基本要求]設置一個棧，每讀入一個括號，若是左括號，則作為一個新的更急迫的期待壓入棧中，若是右括號，則或者是和當前棧頂的括號相匹配，或者是不合法的情況，輸出“此串括號匹配不合法”。在初始和結束時，棧應該是空的。[測試數據]輸入 （[ ]（）），結果“匹配”輸入 [（）]，結果“此串括號匹配不合法”為起始和結束標志。[問題描述]設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。[測試數據]設n=2,輸入數據為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數據包括三個數據項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，其中，‘A’表示到達；‘D’表示離去，‘E’表示輸入結束