第一篇：《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)教學(xué)大綱（Data Structures & Algorithms）

一、基本信息

課程編號(hào)：E1132107 課程類別：學(xué)科基礎(chǔ)課必修課 適用層次：本科

適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、軟件工程等 開課學(xué)期：3 學(xué) 分：2學(xué)分 學(xué) 時(shí)：2周 考核方式：考查

二、教學(xué)目的

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)不僅是數(shù)據(jù)結(jié)構(gòu)與算法課程的實(shí)踐教學(xué)環(huán)節(jié)，而且是一門綜合性實(shí)驗(yàn)項(xiàng)目。通過這個(gè)實(shí)驗(yàn)，培養(yǎng)學(xué)生綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和程序設(shè)計(jì)基本知識(shí)，解決實(shí)際問題，提高程序設(shè)計(jì)的能力和團(tuán)隊(duì)協(xié)作精神。

本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。

1．學(xué)生通過實(shí)踐掌握線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)； 2．培養(yǎng)學(xué)生利用數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問題的能力;3．使學(xué)生初步具備查閱資料、分析設(shè)計(jì)、上機(jī)實(shí)現(xiàn)和書寫科技 報(bào)告的能力。

三、基本要求

1.指導(dǎo)教師要在選題、設(shè)計(jì)、上機(jī)實(shí)現(xiàn)等諸環(huán)節(jié)上投入精力，加強(qiáng)指導(dǎo)、討論和答疑的力度。尤其在選題上，要充分考慮學(xué)生目前所具有的知識(shí)水平、掌握的開發(fā)工具、以及綜合設(shè)計(jì)能力的現(xiàn)狀，使題目取材合理、大小適中、難易適度，使學(xué)生在完成設(shè)計(jì)工作后，能有所收獲。2.參加課程設(shè)計(jì)的學(xué)生要珍惜機(jī)會(huì)、勤奮工作、勇于創(chuàng)新、勇于探索、勇于實(shí)踐，虛心向指導(dǎo)教師請(qǐng)教，向同學(xué)學(xué)習(xí)，獨(dú)立完成設(shè)計(jì)任務(wù)。

3.學(xué)生需保質(zhì)、保量、保時(shí)間進(jìn)度地提交規(guī)范的課程設(shè)計(jì)報(bào)告，審查由指導(dǎo)教師負(fù)責(zé)。

四、教學(xué)內(nèi)容

1.主要內(nèi)容：應(yīng)用所掌握的線性表、樹、圖等數(shù)據(jù)結(jié)構(gòu)知識(shí)解決實(shí)際問題。2.軟件開發(fā)工具：C/C++、JAVA。

3.課程設(shè)計(jì)題目：指導(dǎo)教師擬定（參考題目見附錄1）

4.具體步驟：指導(dǎo)教師擬定設(shè)計(jì)題目，學(xué)生研究具體問題、進(jìn)行需求分析、選擇合適的數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法、編寫并調(diào)試代碼、書寫文檔材料、提交設(shè)計(jì)報(bào)告，最后，由指導(dǎo)教師驗(yàn)收并評(píng)定成績。

5.設(shè)計(jì)內(nèi)容及時(shí)間安排：第1-3天，選定題目，明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法，并分析算法復(fù)雜度；第4-8天，編寫程序、調(diào)試程序、測試程序；第9-10天，撰寫設(shè)計(jì)報(bào)告，準(zhǔn)備答辯（上機(jī)演示，回答教師提問）。6.設(shè)計(jì)報(bào)告書寫要求：按照軟件開發(fā)規(guī)范的要求書寫設(shè)計(jì)報(bào)告（參見附錄三報(bào)告書寫格式）；要求報(bào)告層次結(jié)構(gòu)清晰、圖表完整、語言通順、字跡工整。7.驗(yàn)收要求：1）運(yùn)行所設(shè)計(jì)的程序；2）回答有關(guān)問題；3）提交課程設(shè)計(jì)報(bào)告（打印或手寫在實(shí)習(xí)報(bào)告冊(cè)上）；4）提交軟盤（源程序）。（鼓勵(lì)學(xué)生創(chuàng)新。對(duì)內(nèi)容有創(chuàng)新者，成績?cè)u(píng)定將適當(dāng)提高）。

五、考核方法

學(xué)習(xí)成績的評(píng)定方式：考查。

課程設(shè)計(jì)成績?cè)u(píng)定 =平時(shí)出勤（20%）+設(shè)計(jì)報(bào)告（40%）+答辯（40%）通過設(shè)計(jì)答辯方式，并結(jié)合學(xué)生的動(dòng)手能力，獨(dú)立分析解決問題的能力和創(chuàng)新精神，總結(jié)報(bào)告和答辯水平以及學(xué)習(xí)態(tài)度綜合考評(píng)。成績分為優(yōu)、良、中、及格和不及格五等。

六、教材與參考資料 1.建議教材：

[1] 數(shù)據(jù)結(jié)構(gòu)(C++)版，王紅梅、胡明、王濤編著，清華大學(xué)出版社，2005.7 [2] 自編教材

2.建議參考書目：

[1] 許卓群，楊冬青，唐世渭，張銘.數(shù)據(jù)結(jié)構(gòu)與算法.高等教育出版社，2004.7 [2] 嚴(yán)蔚敏, 陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程.清華大學(xué)出版社, 2001.2 [3] 朱晉蜀.數(shù)據(jù)結(jié)構(gòu)(第一版).成都: 電子科技大學(xué)出版社, 2000.1 [4] Clifford A.Shaffer著.張銘，劉曉丹譯.數(shù)據(jù)結(jié)構(gòu)與算法分析.電子工業(yè)出版社，1998.8 [5] 殷人昆等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）.清華大學(xué)出版社，1999.7 [6] Ford W., Topp W.DATA STRUCTURES with C++.清華大學(xué)出版社（影印版），1997.3

附錄一

參考題目（可分若干組，每個(gè)學(xué)生選擇其中一個(gè)題目）

1．商廈家電庫存管理 2.排序算法的時(shí)間比較

3．使用哈希表技術(shù)判斷兩個(gè)源程序的相似性 4．以隊(duì)列實(shí)現(xiàn)的仿真技術(shù)預(yù)測理發(fā)館的經(jīng)營狀況 5.某公園導(dǎo)游圖

6．用樹型結(jié)構(gòu)的搜索算法模擬因特網(wǎng)域名的查詢 7．管道鋪設(shè)施工的最佳方案選擇 8．表達(dá)式分析與求值程序 9．安排教學(xué)計(jì)劃

10.設(shè)計(jì)Huffman 編碼器與解碼器 11．在國際象棋盤上馬遍歷問題 12．八皇后問題 13．民航售票系統(tǒng) 14．模擬旅館管理系統(tǒng)中的床位分配和加收 15．銀行業(yè)務(wù)活動(dòng)的模擬

16．文字統(tǒng)計(jì)系統(tǒng)—文字研究助手 17．修道士野人問題 18．考試問題

19．計(jì)算機(jī)輔助考核系統(tǒng) 20．學(xué)籍管理系統(tǒng)

注：學(xué)生可以自選題目或選擇指導(dǎo)老師擬定的題目。

附錄二

開發(fā)步驟

1.分析題目的要求、目的； 2.選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)；

3.抽象數(shù)據(jù)類型的設(shè)計(jì)； 4.抽象數(shù)據(jù)類型的實(shí)現(xiàn)； 5.編寫代碼、上機(jī)調(diào)試； 6.總結(jié)驗(yàn)收、評(píng)價(jià)。

附錄三 報(bào)告書寫格式

1．問題描述

題目內(nèi)容、基本要求 2．需求分析

軟件的基本功能、輸入/輸出形式、測試數(shù)據(jù)要求 3．概要設(shè)計(jì)

所需的ADT及作用、主程序流程及模塊調(diào)用關(guān)系 4．詳細(xì)設(shè)計(jì)

實(shí)現(xiàn)概要設(shè)計(jì)的數(shù)據(jù)類型、每個(gè)操作的偽碼算法、主程序和其它模塊的偽碼算法、函數(shù)調(diào)用關(guān)系圖 5．編碼與調(diào)試分析

編碼與調(diào)試過程中遇到的問題及解決的辦法，還存在哪些沒有解決的問題？ 6．使用說明

簡要說明程序運(yùn)行操作步驟 7．測試結(jié)果

8．課程設(shè)計(jì)心得體會(huì)

第二篇：數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)大綱

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

一、課程基本信息

課程名稱：數(shù)據(jù)結(jié)構(gòu)

總學(xué)時(shí)：64(理論課內(nèi)學(xué)時(shí)48，上機(jī)課內(nèi)學(xué)時(shí)16)課程設(shè)計(jì)：24 課程類型：必修課

考試形式：半開卷考試 講課對(duì)象：計(jì)算機(jī)本科

建議教材：《數(shù)據(jù)結(jié)構(gòu)》(C語言版)陳明 編著 清華大學(xué)出版社

課程簡介：數(shù)據(jù)結(jié)構(gòu)課程介紹如何組織各種數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)、傳遞和轉(zhuǎn)換。內(nèi)容包括：數(shù)組、鏈接表、棧和隊(duì)列、串、樹與森林、圖、排序、查找、索引與散列結(jié)構(gòu)等。課程以結(jié)構(gòu)化程序設(shè)計(jì)語言C語言作為算法的描述工具，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識(shí)和結(jié)構(gòu)化程序設(shè)計(jì)基本能力的雙基訓(xùn)練。為后續(xù)計(jì)算機(jī)專業(yè)課程的學(xué)習(xí)打下堅(jiān)實(shí)的基礎(chǔ)。

二、課程的教學(xué)目標(biāo)

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)相關(guān)專業(yè)的一門重要專業(yè)基礎(chǔ)課，是計(jì)算機(jī)學(xué)科的公認(rèn)主干課。課程內(nèi)容由數(shù)據(jù)結(jié)構(gòu)和算法分析初步兩部分組成。

數(shù)據(jù)結(jié)構(gòu)是針對(duì)處理大量非數(shù)值性程序問題而形成的一門學(xué)科，內(nèi)涵豐富、應(yīng)用范圍廣。它既有完整的學(xué)科體系和學(xué)科深度，又有較強(qiáng)的實(shí)踐性。通過課程的學(xué)習(xí)，應(yīng)使學(xué)生理解和掌握各種數(shù)據(jù)結(jié)構(gòu)(物理結(jié)構(gòu)和邏輯結(jié)構(gòu))的概念及其有關(guān)的算法；熟悉并了解目前常用數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)諸多領(lǐng)域中的基本應(yīng)用。

算法分析強(qiáng)調(diào)最基本的算法設(shè)計(jì)技術(shù)和分析方法。要求學(xué)生從算法和數(shù)據(jù)結(jié)構(gòu)的相互依存關(guān)系中把握應(yīng)用算法設(shè)計(jì)的藝術(shù)和技能。

經(jīng)過上機(jī)實(shí)習(xí)和課程設(shè)計(jì)的訓(xùn)練，使學(xué)生能夠編制、調(diào)試具有一定難度的中型程序；以培養(yǎng)良好的軟件工程習(xí)慣和面向?qū)ο蟮能浖季S方法。

“數(shù)據(jù)結(jié)構(gòu)”的前序課是《離散數(shù)學(xué)》、《C語言程序設(shè)計(jì)與算法初步》。

三、理論教學(xué)內(nèi)容的基本要求及學(xué)時(shí)分配

1、序論(2學(xué)時(shí))學(xué)習(xí)目標(biāo)：熟悉各類文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。

重點(diǎn)與難點(diǎn)：本章無。

知識(shí)點(diǎn)：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型、算法及其設(shè)計(jì)原則、時(shí)間復(fù)雜度、空間復(fù)雜度。

2、線性表(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)了解線性表的邏輯結(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)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表；

(2)熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；

(3)能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合；

(4)結(jié)合線性表類型的定義增強(qiáng)對(duì)抽象數(shù)據(jù)類型的理解。

重點(diǎn)與難點(diǎn)：鏈表是本章的重點(diǎn)和難點(diǎn)。扎實(shí)的指針操作和內(nèi)存動(dòng)態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針 p 和結(jié)點(diǎn) *p 之間的對(duì)應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的不同所指以及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。

知識(shí)點(diǎn)：線性表、順序表、鏈表、有序表。

3、棧和隊(duì)列(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們；

(2)熟練掌握棧類型的兩種實(shí)現(xiàn)方法；

(3)熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法；(4)理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。

重點(diǎn)與難點(diǎn)：棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用。

知識(shí)點(diǎn)：順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列。

4、串(2學(xué)時(shí))

學(xué)習(xí)目標(biāo)：(1)理解串類型定義中各基本操作的特點(diǎn)，并能正確利用它們進(jìn)行串的其它操作；

(2)理解串類型的各種存儲(chǔ)表示方法；(3)理解串匹配的各種算法。

重點(diǎn)和難點(diǎn)：相對(duì)于其它各個(gè)知識(shí)點(diǎn)而言，本章非整個(gè)課程的重點(diǎn)，鑒于串已是多數(shù)高級(jí)語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)類型，因此本章重點(diǎn)僅在于了解串類型定義中各基本操作的定義以及串的實(shí)現(xiàn)方法，并學(xué)會(huì)利用這些基本操作來實(shí)現(xiàn)串的其它操作。本章的難點(diǎn)是理解實(shí)現(xiàn)串匹配的KMP算法的思想。

知識(shí)點(diǎn)：串的類型定義、串的存儲(chǔ)表示、串匹配、KMP算法。

5、數(shù)組和廣義表(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)理解數(shù)組類型的特點(diǎn)及其在高級(jí)編程語言中的存儲(chǔ)表示和實(shí)現(xiàn)方法，并掌握數(shù)組在“以行為主”的存儲(chǔ)表示中的地址計(jì)算方法；

(2)掌握特殊矩陣的存儲(chǔ)壓縮表示方法；

(3)理解稀疏矩陣的兩類存儲(chǔ)壓縮方法的特點(diǎn)及其適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算所采用的處理方法。

重點(diǎn)和難點(diǎn)：本章重點(diǎn)是學(xué)習(xí)數(shù)組類型的定義及其存儲(chǔ)表示。

知識(shí)點(diǎn)：數(shù)組的類型定義、數(shù)組的存儲(chǔ)表示、特殊矩陣的壓縮存儲(chǔ)表示方法、隨機(jī)稀疏矩陣的壓縮存儲(chǔ)表示方法。

6、樹和二叉樹(8學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)領(lǐng)會(huì)樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別；(2)熟記二叉樹的主要特性，并掌握它們的證明方法；

(3)熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作；

(4)理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法；

(5)熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法；(6)學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法；

(7)了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。

重點(diǎn)和難點(diǎn)：二叉樹和樹的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點(diǎn)，而編寫實(shí)現(xiàn)二叉樹和樹的各種操作的遞歸算法也恰是本章的難點(diǎn)所在。

知識(shí)點(diǎn)：樹的類型定義、二叉樹的類型定義、二叉樹的存儲(chǔ)表示、二叉樹的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹、樹和森林的存儲(chǔ)表示、樹和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹和赫夫曼編碼。

7、圖(8學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)領(lǐng)會(huì)圖的類型定義；

(2)熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及其選用原則；

(3)熟練掌握?qǐng)D的兩種遍歷算法；(4)理解各種圖的應(yīng)用問題的算法。

重點(diǎn)和難點(diǎn)：圖的應(yīng)用極為廣泛，而且圖的各種應(yīng)用問題的算法都比較經(jīng)典，因此本章重點(diǎn)在于理解各種圖的算法及其應(yīng)用場合。

知識(shí)點(diǎn)：圖的類型定義、圖的存儲(chǔ)表示、圖的深度優(yōu)先搜索遍歷和圖的廣度優(yōu)先搜索遍歷、無向網(wǎng)的最小生成樹、最短路徑、拓?fù)渑判颉㈥P(guān)鍵路徑。

8、查找(6學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)理解“查找表”的結(jié)構(gòu)特點(diǎn)以及各種表示方法的適用性；(2)熟練掌握以順序表或有序表表示靜態(tài)查找表時(shí)的查找方法；

(3)熟悉靜態(tài)查找樹的構(gòu)造方法和查找算法，理解靜態(tài)查找樹和折半查找的關(guān)系；

(4)熟練掌握二叉查找樹的構(gòu)造和查找方法；(5)理解二叉平衡樹的構(gòu)造過程；

(6)熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別；

(7)掌握描述查找過程的判定樹的構(gòu)造方法，以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長度。

重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于理解查找表的結(jié)構(gòu)特點(diǎn)及其各種表示方法的特點(diǎn)和適用場合。

知識(shí)點(diǎn)：順序表、有序表、索引順序表、靜態(tài)查找樹、二叉查找樹、二叉平衡樹、哈希表。

9、內(nèi)部排序(6學(xué)時(shí))

學(xué)習(xí)目標(biāo)：

(1)理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。排序方法有不同的分類方法，基于“關(guān)鍵字間的比較”進(jìn)行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計(jì)數(shù)排序等五類；

(2)掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類：O(n2)的簡單排序方法，O(n*logn)的高效排序方法和O(d*n)的基數(shù)排序方法；

(3)理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。

重點(diǎn)和難點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效方法是本章的學(xué)習(xí)重點(diǎn)和難點(diǎn)。

知識(shí)點(diǎn)：排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、2-路歸并排序、基數(shù)排序、排序方法的綜合比較。

10、文件(4學(xué)時(shí))

學(xué)習(xí)目標(biāo)：熟悉各類文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。

重點(diǎn)和難點(diǎn)：本章重點(diǎn)在于了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場合。知識(shí)點(diǎn)：順序文件、索引文件、B-樹、B+樹、索引順序文件、VSAM文件、散列文件、多關(guān)鍵字文件。

四、實(shí)驗(yàn)教學(xué)內(nèi)容的基本要求及學(xué)時(shí)分配

1、線性表(1學(xué)時(shí))實(shí)驗(yàn)一 順序表的應(yīng)用 實(shí)驗(yàn)二 鏈表的應(yīng)用

要求：理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義，組織形式，結(jié)構(gòu)特征和類型說明；掌握在這兩種表上實(shí)現(xiàn)的插入，刪除和按值查找的算法；了解循環(huán)鏈表，雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入，刪除等操作。

2、棧(0.5學(xué)時(shí))實(shí)驗(yàn)三 棧的應(yīng)用

要求：理解棧的定義，特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)算的實(shí)現(xiàn)。

3、隊(duì)列(0.5學(xué)時(shí))實(shí)驗(yàn)四 隊(duì)列的應(yīng)用

要求：理解隊(duì)列的定義，特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。

4、串(0.5學(xué)時(shí))實(shí)驗(yàn)五 串的應(yīng)用

要求：了解串的定義；理解和領(lǐng)會(huì)串的存儲(chǔ)方式；掌握常用的串運(yùn)算。

5、數(shù)組和廣義表(0.5學(xué)時(shí))實(shí)驗(yàn)六 稀疏矩陣的應(yīng)用

要求：理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式；理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算；領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡單運(yùn)算；了解廣義表的定義和基本運(yùn)算。

6、樹與二叉樹(4學(xué)時(shí))實(shí)驗(yàn)七 樹與二叉樹的應(yīng)用

要求：理解樹的定義，術(shù)語；領(lǐng)會(huì)并掌握樹的各種存儲(chǔ)結(jié)構(gòu)；熟練掌握森林與二叉樹間的相互轉(zhuǎn)換；領(lǐng)會(huì)樹和森林的遍歷；了解樹的簡單應(yīng)用。深刻理解二叉樹的定義，性質(zhì)及其存儲(chǔ)方法；熟練掌握二叉樹的二叉鏈表存儲(chǔ)方式，結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題。

7、圖(3學(xué)時(shí))實(shí)驗(yàn)八 圖的應(yīng)用

要求：理解圖的基本概念及術(shù)語；掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想，步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；領(lǐng)會(huì)并掌握拓?fù)渑判?，關(guān)鍵路徑，最短路徑的算法思想。

8、查找(3學(xué)時(shí))實(shí)驗(yàn)九 順序查找 實(shí)驗(yàn)十 折半查找 實(shí)驗(yàn)十一 哈希表的應(yīng)用 實(shí)驗(yàn)十二 二叉排序樹的綜合練習(xí)要求：了解查找的基本思想及查找成功和不成功的概念；掌握在順序表，有序表，索引表，散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度；理解并掌握二叉排序樹，平衡二叉樹B-樹的各種算法。

9、排序(3學(xué)時(shí))實(shí)驗(yàn)十三 插入排序 實(shí)驗(yàn)十四 選擇排序 實(shí)驗(yàn)十五 排序綜合練習(xí)

要求：領(lǐng)會(huì)排序的基本思想和基本概念；理解并掌握插入排序，冒泡排序，快速排序，直接選擇排序，堆排序，歸并排序和基數(shù)排序的基本思想，步驟，算法及時(shí)空效率分析；了解外排序的定義和基本方法。

五、大綱說明

1、課堂講述的論題只是核心或有特色的知識(shí)內(nèi)容，還有相當(dāng)數(shù)量的篇章內(nèi)容留給學(xué)生自學(xué)，所確定的自學(xué)部分內(nèi)容亦屬考查范圍。

2、“數(shù)據(jù)結(jié)構(gòu)”課注重上機(jī)訓(xùn)練，所有作業(yè)都必須配有規(guī)范的文檔。上機(jī)訓(xùn)練由平時(shí)的上機(jī)訓(xùn)練和小學(xué)期的實(shí)訓(xùn)課程設(shè)計(jì)兩部分組成。

3、課內(nèi)學(xué)時(shí)安排說明：前8周每周4學(xué)時(shí)全為理論課，從第9周開始理論和上機(jī)為1：1，也即2學(xué)時(shí)理論，2學(xué)時(shí)上機(jī)訓(xùn)練。

4、本課強(qiáng)調(diào)能力的培養(yǎng)，期末采用半開卷考試(允許同學(xué)攜帶一頁A4紙的總結(jié)資料)。本課成績由平時(shí)作業(yè)、上機(jī)成績(30%)和期末考試(70%)合成得到，有獨(dú)到見解的作業(yè)予以適當(dāng)加分。

5、主要參考書：

[1]《數(shù)據(jù)結(jié)構(gòu)與算法教程》鄒永林 周蓓 唐曉陽 楊劍勇 編著 機(jī)械工業(yè)出版社

[2]《數(shù)據(jù)結(jié)構(gòu)(C語言版)》(含CD)嚴(yán)蔚敏 吳為民 編著 清華大學(xué)出版社

[3]《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語言版)》嚴(yán)蔚敏 編著 清華大學(xué)出版社

[4]《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)》張世和 編著 清華大學(xué)出版社

第三篇：《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》任務(wù)書2014

2014/2015學(xué)年第一學(xué)期

《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》任務(wù)書

一、課程設(shè)計(jì)目的

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)是《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)必不可缺的一個(gè)重要環(huán)節(jié)，它可加深學(xué)生對(duì)該課程所學(xué)內(nèi)容的進(jìn)一步的理解與鞏固，是將計(jì)算機(jī)課程與實(shí)際問題相聯(lián)接的關(guān)鍵步驟。通過課程設(shè)計(jì)，能夠提高學(xué)生分析問題、解決問題，從而運(yùn)用所學(xué)知識(shí)解決實(shí)際問題的能力，因而必須給予足夠的重視。

2二、課程設(shè)計(jì)題目

2.1 棋盤覆蓋

【間題描述】

在一個(gè)2k×2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。

【基本要求】

（1）輸入k以及特殊方格所在的行號(hào)dr和特殊方格的列號(hào)dc。

1（2）要求輸出每一步用什么形態(tài)L型骨牌覆蓋，覆蓋后得到的棋盤圖形。（3）如果輸出的結(jié)果只是用矩陣表示則為良好，用圖形表示則為優(yōu)?！緶y試數(shù)據(jù)】 【實(shí)現(xiàn)提示】

使用分治策略，把棋盤劃分成4個(gè)小棋盤，然后用一個(gè)L型骨牌覆蓋將這4個(gè)小棋盤變?yōu)槎季哂刑厥夥礁竦钠灞P。

2.2 Hanoi塔問題（*）

【問題描述】

設(shè)a，b，c是三個(gè)塔座。開始時(shí)，在塔座a上有一疊共n個(gè)圓盤，這些圓盤自下而上，由大到小地疊放在一起，各圓盤從小到大編號(hào)為1,2,?,n，要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則：

規(guī)則（1）每次只能移動(dòng)一個(gè)圓盤；

規(guī)則（2）任何時(shí)刻都部允許將較大的圓盤壓在較小的圓盤之上；

規(guī)則（3）在滿足移動(dòng)規(guī)則（1）和（2）的前提下，可將圓盤移至a，b，c中任一塔座上。

【基本要求】

（1）設(shè)計(jì)出Hannoi塔游戲，供用戶玩；（2）提供正確的搬運(yùn)方法。【實(shí)現(xiàn)說明】

正確的搬運(yùn)方法使用遞歸方法實(shí)現(xiàn)。【測試數(shù)據(jù)】

2.3 矩陣連乘問題

【問題描述】

給定n個(gè)矩陣{A1,A2,...,An},其中Ai和Ai?1是可乘的，i＝1,2,?,n-1。考察這n個(gè)矩陣的連乘積A1A2,...,An，通過加括號(hào)方式，找出矩陣乘積所需的最少計(jì)算量的方法。

【基本要求】

輸入每個(gè)矩陣的行和列，要求輸出最少計(jì)算量的矩陣乘積方法，如(A1(A2(A3A4)))?！緦?shí)現(xiàn)說明】 使用動(dòng)態(tài)規(guī)劃方法。

2.4 多邊形游戲（*）

【問題描述】

多邊形游戲是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“＋”或“*”。所有邊依次用整數(shù)從1到n編號(hào)。

游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：

選擇一條邊E及由E連接著的2個(gè)頂點(diǎn)v1和v2；

用一個(gè)新的頂點(diǎn)取代邊E及用E連接著的2個(gè)頂點(diǎn)v1和v2，將由頂點(diǎn)v1和v2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。

最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。【基本要求】

設(shè)計(jì)該游戲供用戶玩；

對(duì)于給定的多邊形，給出最高得分計(jì)算?！緦?shí)現(xiàn)說明】 使用動(dòng)態(tài)規(guī)劃方法。

2.5 0-1背包問題

【問題描述】

給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為c。問應(yīng)如何選擇裝入背包種的物品，使得裝入背包種物品的總價(jià)值最大。

【基本要求】

使用動(dòng)態(tài)規(guī)劃、回溯法以及分支界限三種方法實(shí)現(xiàn)?！緶y試數(shù)據(jù)】 【實(shí)現(xiàn)提示】

2.6 排序方法

【問題描述】

給定n個(gè)元素，要求對(duì)這n個(gè)元素進(jìn)行排序?！净疽蟆?/p>

使用多種排序方法，越多越好；

比較每種排序方法的時(shí)間復(fù)雜度和空間復(fù)雜度?！緶y試數(shù)據(jù)】 【實(shí)現(xiàn)提示】

2.7 哈夫曼編碼譯碼器

【問題描述】

設(shè)計(jì)一個(gè)哈夫曼編碼/譯碼系統(tǒng)，對(duì)一個(gè)文本文件中的字符進(jìn)行哈夫曼編碼，生成編碼文件

（壓縮文件，后綴名.cod）；反過來，可將一個(gè)壓縮文件譯碼還原為一個(gè)文本文件(.txt)。

【基本要求】

（1）輸入一個(gè)待壓縮的英文文本文件，統(tǒng)計(jì)文本文件中各字符的個(gè)數(shù)作為權(quán)值，生成哈夫曼樹；

（2）將文本文件利用哈夫曼樹進(jìn)行編碼，生成壓縮文件（后綴名cod）（3）輸入一個(gè)待解壓的壓縮文件名稱,并利用相應(yīng)的哈夫曼樹將編碼序列譯碼。【實(shí)現(xiàn)說明】

（1）在構(gòu)造哈夫曼樹時(shí)，可以利用不同的線性表存放二叉樹：用順序表、單鏈表、5 循環(huán)單鏈表、雙向鏈表、循環(huán)雙鏈表；

（2）在構(gòu)造哈夫曼樹時(shí)，可以利用優(yōu)先隊(duì)列存放二叉樹：順序隊(duì)列、鏈隊(duì)列（可以是單鏈表、雙鏈表等，還可以用靜態(tài)結(jié)構(gòu)去實(shí)現(xiàn)），可以分別在入隊(duì)列或出隊(duì)列時(shí)實(shí)現(xiàn)優(yōu)先級(jí)；

（3）二叉樹本身也可以用靜態(tài)數(shù)組模擬；（4）使用貪心算法

2.8 迷宮問題（*）

【問題描述】

設(shè)計(jì)一個(gè)迷宮并給出正確走法。如： *** *** *** *** *** *** *** 其中0表示可以走，1表示不能走，每一步只能向上下左右移動(dòng)?！净疽蟆?/p>

（1）給出迷宮的正確走法，包括沒有解的情況；（2）要求界面友好?！緶y試數(shù)據(jù)】

【實(shí)現(xiàn)提示】 使用回溯的方法。

2.9 繼續(xù)郵資問題

【問題描述】

假設(shè)某國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，在1張信封上貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。

【基本要求】

輸入任意的m和n都能設(shè)計(jì)出最佳的方案，并給出連續(xù)郵資區(qū)間?！緦?shí)現(xiàn)說明】 【測試數(shù)據(jù)】

2.10 圖的m著色問題

【問題描述】

給定一個(gè)地圖，要求給出該地圖的最少著色方案 【基本要求】

（1）把地圖以及最少著色的方案顯示出來則為良好。（2）有友好的界面則為優(yōu) 【實(shí)現(xiàn)說明】

2.11 猜數(shù)字游戲（*）

【問題描述】

孩子想1個(gè)由4種顏色組成的序列（4種顏色不一定完全不同）。每種顏色只能是6種顏色之一。方便起見，我們用數(shù)字1到6表示6種顏色。

計(jì)算機(jī)必須根據(jù)孩子的回答找出孩子所想的顏色序列。計(jì)算機(jī)在屏幕上顯示一個(gè)序列，孩子用鍵盤回答以下兩個(gè)問題：

猜對(duì)的顏色中位置不對(duì)的有幾個(gè)？ 猜對(duì)的顏色中位置對(duì)的有幾個(gè)？ 【基本要求】

編程使至多6次問答后猜出序列，如果辦不到，至多10次問答后猜出序列?！緦?shí)現(xiàn)說明】 【測試數(shù)據(jù)】

如孩子想的是4655 計(jì)算機(jī)猜想 顏色對(duì)位置錯(cuò)的數(shù)目 顏色和位置都對(duì)的數(shù)目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 8 4655 0 4 2.12 大整數(shù)計(jì)算器

【問題描述】

設(shè)計(jì)一個(gè)計(jì)算器實(shí)現(xiàn)兩個(gè)任意長得整數(shù)的加、減、乘、除?！净疽蟆?/p>

設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長的整數(shù)進(jìn)行四則運(yùn)算的演示程序，要求輸入任意長的整數(shù)進(jìn)行四則運(yùn)算，都能得到精確的結(jié)果。

【實(shí)現(xiàn)說明】

2.13 查找搜索技術(shù)

【問題描述】

給定任意的數(shù)組，對(duì)于給定的數(shù)，查找是否在數(shù)組中，如果在，則返回給定數(shù)在數(shù)組的位置，不在則返回不在信息。

【基本要求】

（1）使用多種搜索方法，越多越好，其中二分搜索技術(shù)、線性時(shí)間選擇是必須的；（2）比較每種排序方法的時(shí)間復(fù)雜度和空間復(fù)雜度。【實(shí)現(xiàn)說明】

2.14 Tom,Jerry和奶酪（*）

【問題描述】

貓Tom和鼠Jerry同住在一矩陣地窖中。貓要吃鼠，鼠要吃奶酪。地窖中有2種地磚：有洞磚與無洞磚。一個(gè)洞足以讓鼠鉆入，但貓不能。

以菜單形式完成以下任務(wù)：

隨機(jī)地生成一個(gè)地窖，并給貓、鼠和奶酪安排一個(gè)位置。如： fffffffffffffff fppppppppppppCf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fppppppppppTppf fffffffffffffff 其中c表示貓，j表示鼠，h表示洞，f表示不能通行（2）鼠先行，貓后行。兩者皆滿足以下規(guī)定： 1）必須上、下、左或右移動(dòng) 2）鼠必須走1步（穿過p或h）3）貓必須走1或2步（穿過p）

（3）當(dāng)鼠吃到奶酪或貓抓到鼠時(shí)，游戲結(jié)束?！净疽蟆?【實(shí)現(xiàn)說明】

2.15 布線問題

【問題描述】

印刷電路板將布線區(qū)域劃分成n×m個(gè)方格陣列，精確的電路布線問題要求確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿著直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖標(biāo)記，其他線路不允許穿過被封鎖的方格。

【基本要求】（1）解決題目的問題（2）提供友好的界面 【實(shí)現(xiàn)說明】 使用分支限界法。

2.16 魔方工具包（*）

【問題描述】

一個(gè)魔方是一個(gè)由3×3×3個(gè)小立方體組成的立方體。最初立方體的6個(gè)面分別涂上不同顏色，我們稱之為“最初魔方”。魔方的每一面上的3×3個(gè)小立方體組成它的一層。

魔方所能見到的每一層（6個(gè)面）都能旋轉(zhuǎn)90，180，220或360度。所有層的旋轉(zhuǎn)軸都垂直于面且通過其中心。旋轉(zhuǎn)的結(jié)果是另一個(gè)魔方，它的所有面的顏色都改變了。

現(xiàn)在我們用字符來代替顏色：U=上，D=下，F(xiàn)=前，B=后，L=左，R=右。任何一個(gè)序列的旋轉(zhuǎn)都能表示成{U,R,F,B,L,D}中一些字符組成的字符串，其中每個(gè)字符表示它所 11 指定的面順時(shí)針旋轉(zhuǎn)90度。

【基本要求】

（1）編程完成以下3個(gè)任務(wù)（菜單形式），你可以假設(shè)任何輸入的字串長度都<=35。你的算法能處理非法輸入的情況，如： 輸入 輸出 L L LL LL LLL LLL LLLL “”(空串 LLLLL L LLRRRFFFFRLB LLLB HELLO “error”

（2）判斷輸入的2個(gè)字串的旋轉(zhuǎn)結(jié)果是否相同。如 輸入一 輸入二 輸出 RU UR no RRFFRRFFRRFFRRFF FFRRFFRR yes RRFFRRFFRRFFRRFF RRFFRRFF no（3）求出輸入字符串至少須使用幾次才能將魔方轉(zhuǎn)回到“最初魔方”（一定大于0）輸入 輸出 L 4 12 DD 2 BULB 36 RUF 80 BLUFF 180 【實(shí)現(xiàn)說明】

2.17 圖的建立與輸出

【問題描述】

建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。

【基本要求】

給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動(dòng)態(tài)演示效果 【實(shí)現(xiàn)說明】

無

2.18 圖的建立與輸出

【問題描述】

建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出 13 圖的鄰接矩陣。

【基本要求】

給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動(dòng)態(tài)演示效果?！緦?shí)現(xiàn)說明】

無

2.19 以隊(duì)列實(shí)現(xiàn)的仿真技術(shù)預(yù)測理發(fā)館的經(jīng)營狀況（*）

【問題描述】

理發(fā)館一天的工作過程如下：

1)理發(fā)館有N把理發(fā)椅，可同時(shí)為N位顧客進(jìn)行理發(fā)。

2)理發(fā)師分三個(gè)等級(jí)（一級(jí)、二級(jí)、三級(jí)），對(duì)應(yīng)不同的服務(wù)收費(fèi)。3)當(dāng)顧客進(jìn)門時(shí)，需選擇某級(jí)別理發(fā)師，只要該級(jí)別的理發(fā)師有空椅，則可立即坐下理發(fā)，否則需排隊(duì)等候。

4)一旦該級(jí)別的理發(fā)師有顧客理發(fā)完離去，排在隊(duì)頭的顧客便可開始理發(fā)。5)若理發(fā)館每天連續(xù)營業(yè)T分鐘，求

（1）一天內(nèi)顧客在理發(fā)館內(nèi)的平均逗留時(shí)間；（2）顧客排隊(duì)等候理發(fā)的隊(duì)列長度平均值；

（3）營業(yè)時(shí)間到點(diǎn)后仍需完成服務(wù)的收尾工作時(shí)間；（4）統(tǒng)計(jì)每天的營業(yè)額；

（5）統(tǒng)計(jì)每天不同級(jí)別理發(fā)師的創(chuàng)收。

【基本要求】

1)模擬理發(fā)館一天的工作過程：必須采用事件驅(qū)動(dòng)的離散模型（參考教科書3.5節(jié)離散事件模擬p65）；

2)每個(gè)顧客到達(dá)和下一顧客到達(dá)時(shí)間的間隔應(yīng)是隨機(jī)的； 3)理發(fā)師編號(hào)、理發(fā)師級(jí)別和每天的營業(yè)時(shí)間由用戶輸入；

4)某顧客挑選某一個(gè)級(jí)別的理發(fā)師而不得時(shí)，選第一個(gè)隊(duì)列排隊(duì)等待 ；

5)每個(gè)顧客進(jìn)門時(shí)將生成三個(gè)隨機(jī)數(shù):(1)durtime:進(jìn)門顧客理發(fā)所需服務(wù)時(shí)間（簡稱：理發(fā)時(shí)間）；(2)intertime:下一顧客將到達(dá)的時(shí)間間隔（簡稱：間隔時(shí)間）；(3)select:服務(wù)選項(xiàng)。

6)服務(wù)收費(fèi)：應(yīng)包含服務(wù)時(shí)間和理發(fā)師級(jí)別兩個(gè)因素。

7)除了輸出統(tǒng)計(jì)的數(shù)據(jù)外，還需要顯示理發(fā)館的狀態(tài)，可以采用文本方式（橫向顯示每張椅編號(hào)、理發(fā)師級(jí)別?？v向表示等待該理發(fā)師理發(fā)的排隊(duì)長度）?！緦?shí)現(xiàn)說明】

用戶輸入每位理發(fā)師編號(hào)、級(jí)別號(hào)和營業(yè)的時(shí)間，結(jié)合隨機(jī)數(shù)進(jìn)行測試。

2.20 防抄襲管理系統(tǒng)（*）

【問題描述】

對(duì)于給定的文檔，如word文檔，txt文檔等，找出文檔的相似度。【基本要求】

（1）要求找出給定的兩個(gè)文檔的相似度以及標(biāo)出相似的地方（1:1）；（2）要求找出給定的一個(gè)文檔與給定的文件夾的所有文檔的相似度，以及標(biāo)出相似的地方(1:n)（3）要求找出給定的文件夾下面所有文檔的相似度(n:n)?！緦?shí)現(xiàn)說明】

給定相似文檔進(jìn)行測試。

2.21.設(shè)計(jì)一個(gè)停車場管理系統(tǒng)，模擬停車場的運(yùn)作

設(shè)計(jì)要求：通過此程序具備以下功能：

1、要求以棧模擬停車場，以隊(duì)列模擬車場 15 外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理；

2、要求處理的數(shù)據(jù)元素包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻；

3、該系統(tǒng)完成以下功能：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去，則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）；

4、要求棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表實(shí)現(xiàn)。

2.22． 赫夫曼編碼

設(shè)計(jì)要求：自己找一篇不少于200個(gè)單詞的英文文章，分析該文章中每一個(gè)字符的出現(xiàn)概率（包括標(biāo)點(diǎn)符號(hào)，區(qū)分大小寫），根據(jù)分析結(jié)果對(duì)文章中每一個(gè)字符進(jìn)行赫夫曼編碼，并將編碼原則儲(chǔ)于一個(gè)獨(dú)立的文本文件中。最后，根據(jù)這個(gè)編碼原則，將英文文章轉(zhuǎn)換為01 串存儲(chǔ)于一個(gè)文本文件中，再編寫一個(gè)解碼程序，將編碼解碼為原文件。如：英文文章為 aaabbc 則編碼規(guī)則為 a-----0 b-----10 c-----11 英文文章將被轉(zhuǎn)化為 000101011 2.23.并查集：檢查網(wǎng)絡(luò)

題目要求：給定一個(gè)計(jì)算機(jī)網(wǎng)絡(luò)以及機(jī)器間的雙向連線列表，每一條連線允許兩端的計(jì)算機(jī)進(jìn)行直接的文件傳輸，其他計(jì)算機(jī)間若存在一條連通路徑，也可以進(jìn)行間接的文件傳輸。請(qǐng)寫出程序判斷：任意指定兩臺(tái)計(jì)算機(jī)，它們之間是否可以進(jìn)行文件傳輸？ 輸入要求：輸入若干測試數(shù)據(jù)組成。對(duì)于每一組測試，第1行包含一個(gè)整數(shù)N（≤10000），即網(wǎng)絡(luò)中計(jì)算機(jī)的總臺(tái)數(shù)，因而每臺(tái)計(jì)算機(jī)可用1到N之間的一個(gè)正整數(shù)表示。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺(tái)計(jì)算機(jī)的 16 序號(hào)，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結(jié)束。

當(dāng)N為0時(shí)，表示全部測試結(jié)束，不要對(duì)該數(shù)據(jù)做任何處理。

輸出要求：對(duì)每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。

當(dāng)讀到S時(shí)，檢查整個(gè)網(wǎng)絡(luò)。若網(wǎng)絡(luò)中任意兩機(jī)器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k components.”,其中k是網(wǎng)絡(luò)中連通集的個(gè)數(shù)。

兩組測試數(shù)據(jù)之間請(qǐng)輸出一空行分隔。

2.24.教學(xué)計(jì)劃編制問題（圖的應(yīng)用）

[問題描述] 大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。[實(shí)現(xiàn)提示]

1、輸入?yún)?shù)應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)（可以是固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號(hào)。

2、應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。

3、若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式可以自己設(shè)計(jì)。

4、可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中，則作為錯(cuò)誤處理。

============================= 17 2.25.藥品銷售統(tǒng)計(jì)系統(tǒng)（排序應(yīng)用）

【問題描述】

設(shè)計(jì)一系統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對(duì)銷售各藥品的記錄進(jìn)行統(tǒng)計(jì)，可按藥品的編號(hào)、單價(jià)、銷售量或銷售額做出排名?！緦?shí)現(xiàn)提示】

在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲(chǔ)在順序表中。各藥品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷出數(shù)量、銷售額。藥品編號(hào)共4位，采用字母和數(shù)字混合編號(hào)，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷售量或銷售額進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排序法，對(duì)銷售量的排序采用快速排序法，對(duì)銷售額的排序采用堆排序法。

藥品信息的元素類型定義： typedef struct node { char num[4];/*藥品編號(hào)*/ char name[10];/*藥品名稱*/ float price;/*藥品單價(jià)*/ int count;/*銷售數(shù)量*/ float sale;/*本藥品銷售額*/ }DataType;存儲(chǔ)藥品信息的順序表的定義： typedef struct { DataType r[MaxSize];int length;}SequenList;

2.26梯運(yùn)行仿真程序

[問題描述] 辦公大樓有若干層（例如，十層），每層有電梯，同時(shí)有步行樓梯；

全樓有若干部（例如，不多于10部）電梯同時(shí)供使用，電梯容量為24人，速度每上下一層需5秒，在某一層停下至少15秒。其運(yùn)行狀態(tài)可分：向上、向下、停止，當(dāng)前乘客數(shù)，當(dāng)前所在層數(shù)。它設(shè)有一個(gè)“按鈕數(shù)組”，例如第五層的按鈕按下，意味著有乘客在第5層到達(dá)目標(biāo)層，等等。在樓的每一層，有電梯數(shù)，有按鈕表示有人等待向上或向下，由若干人在等待，有若干電梯在本層停下，等等。

在大樓中（包括進(jìn)出）的總?cè)藬?shù)不超過500 人，每個(gè)人站在電梯前有個(gè)目標(biāo)層，他有一個(gè)最大的忍受等待時(shí)間，因?yàn)樗梢赃x擇電梯或是步行走樓梯，等等。

還有下面若干假設(shè)：在每個(gè)時(shí)間段要進(jìn)大樓的人數(shù)在0～199 之間隨機(jī)取值；

用電梯的每個(gè)人的目標(biāo)層在1～10 之間取值；一個(gè)人在進(jìn)電梯或改走樓梯之前的等待時(shí)間在180～360 秒范圍內(nèi)隨機(jī)發(fā)生；一個(gè)人到達(dá)目標(biāo)層后第二次再乘電梯中間的工作時(shí)間在400～6600 秒間隨機(jī)取值。[基本要求] 編寫一個(gè)程序，模擬辦公大樓中全部電梯的工作過程。這個(gè)仿真程序可以用來監(jiān)測系統(tǒng)運(yùn)行情況，改善大樓管理，它也可以看成是一種游戲程序。

2.27國交通咨詢模擬

[問題描述]

處于不同目的的旅客對(duì)交通工具有不同的要求。例如，因公出差的旅客希望在旅 途中的時(shí)間盡可能的短，出門旅游的游客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個(gè)全國城市間的交通咨詢程序，為旅客提供最優(yōu)決策的交通咨詢。

[基本要求]

（1）提供對(duì)城市信息進(jìn)行編輯（如：添加或刪除）的功能；

（2）城市之間有兩種交通工具：火車或飛機(jī)，提供對(duì)全國城市交通圖和列車時(shí)刻表及飛機(jī)航班表進(jìn)行編輯的功能。（信息的輸入方式可以是文件輸入和鍵盤輸入兩種方式）

（3）提供兩種最優(yōu)決策：最快到達(dá)和最省錢到達(dá)。（選作：旅途中轉(zhuǎn)次數(shù)最少的最優(yōu)決策）

（4）旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。

（5）咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。

a）由用戶輸入起始站、終點(diǎn)站、最優(yōu)決策原則和交通工具；

b）輸出信息：最快需要多長時(shí)間才能到達(dá)或者最少需要多少旅費(fèi)才能到達(dá)，并詳 細(xì)說明依次于何時(shí)乘坐哪一趟列車或哪一次班機(jī)到何地。

三、課程設(shè)計(jì)的基本要求

1．問題分析和任務(wù)定義。根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？

2．邏輯設(shè)計(jì)。對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說明)，各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。

3．詳細(xì)設(shè)計(jì)。定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，20 寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。

4．程序編碼。把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚。

5．程序調(diào)試與測試。采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。

6．結(jié)果分析。程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析。

7．編寫課程設(shè)計(jì)報(bào)告并提交相關(guān)內(nèi)容

設(shè)計(jì)最終需提交的內(nèi)容包括：

A）課程設(shè)計(jì)報(bào)告（1份，A4紙打印，同時(shí)包括一份電子版）報(bào)告要求版面清晰，格式規(guī)范，否則重新編寫。報(bào)告內(nèi)容要求包括：

（1）問題的概述、分析及研究意義；（2）數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)和物理存儲(chǔ)設(shè)計(jì)；（3）重要算法的設(shè)計(jì)、流程描述或偽代碼描述；

（4）數(shù)據(jù)結(jié)構(gòu)的時(shí)空復(fù)雜性分析以及重要算法的復(fù)雜性分析；

（5）程序最終實(shí)現(xiàn)結(jié)果（包括重點(diǎn)結(jié)果界面的抓取，能過說明問題的重要實(shí)驗(yàn)結(jié)果數(shù)據(jù)的打印或其可視化結(jié)果等）。

（6）參考文獻(xiàn)（如果需要）。

（7）附錄部分附上關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的定義及關(guān)鍵算法的源代碼。

B）完整的程序系統(tǒng)（電子方式提交）

能夠?qū)斎氘a(chǎn)生相應(yīng)的輸出，同時(shí)盡量的完成可視化演示。

該部分包括源代碼和可執(zhí)行文件兩個(gè)部分（提交的時(shí)候需清楚的注明個(gè)人姓名，班級(jí)）。

C）源程序文檔（電子方式提交）

源程序代碼要求結(jié)構(gòu)清晰、可讀性好。應(yīng)對(duì)源程序中的類說明（如果采用面向?qū)ο蠓椒ㄔO(shè)計(jì)），函數(shù)說明，接口說明，關(guān)鍵變量說明等進(jìn)行注釋；源程序要進(jìn)行適當(dāng)?shù)目s進(jìn)編排。

D）答辯報(bào)告（編寫Power Point答辯報(bào)告，電子方式提交）要求突出重點(diǎn)，思路清晰。同時(shí)就此報(bào)告準(zhǔn)備答辯。

E）所有以電子方式提交的文件全部存在一個(gè)目錄中，并對(duì)其進(jìn)行壓縮（用Winrar或Winzip均 21 可），壓縮后的文件按規(guī)定格式進(jìn)行命名，命名格式為：學(xué)號(hào)+姓名.rar（如060701014石海杭.rar）。8．每位同學(xué)只能選擇一個(gè)題目并完成

四、評(píng)分標(biāo)準(zhǔn)

1、基本功能：

50分。

通過功能的實(shí)現(xiàn)情況、界面的完成情況、軟件的實(shí)現(xiàn)情況進(jìn)行評(píng)分。

2、設(shè)計(jì)報(bào)告及使用說明書： 20分 按照?qǐng)?bào)告的要求進(jìn)行評(píng)分。

3、回答問題：

4、平時(shí)考勤：

5、核分標(biāo)準(zhǔn)：

15分 15分 100分

（90~100為優(yōu)、80~89為良、70~79為中、60~69為及格、，60以下為不及格）

五、參考書目

嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)》（C語言版）.清華大學(xué)出版社 劉玉龍．《數(shù)據(jù)結(jié)構(gòu)與算法》.電子工業(yè)出版社.嚴(yán)蔚敏等《數(shù)據(jù)結(jié)構(gòu)題集》（C語言版）.清華大學(xué)出版社

徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C/C++描述）.北京:清華大學(xué)出版社.陳慧南.數(shù)據(jù)結(jié)構(gòu)（使用C++語言描述）.南京:東南大學(xué)出版社.殷人昆, 陶永雷, 謝若陽等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）.北京:清華大學(xué)出版社.22

第四篇：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)題目

數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)題目

1．成績管理

問題描述：給出n個(gè)學(xué)生的考試成績表，成績表包括學(xué)生的學(xué)號(hào)、姓名、考試成績（高等數(shù)

學(xué)、英語、物理），設(shè)計(jì)一個(gè)簡單的成績管理程序。

基本要求：

（1）建立成績表，能夠插入、刪除、修改學(xué)生的成績記錄；（2）按任一單科成績排序；(3)計(jì)算每名學(xué)生的平均成績；

(4)統(tǒng)計(jì)任一單科成績不及格的學(xué)生人數(shù), 輸出不及格人數(shù)及不及格的學(xué)生名單(5)根據(jù)平均成績將成績表按由高到低的次序排列，統(tǒng)計(jì)每名學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次，按名次輸出成績表。

(6)成績表保存在文件中, 可以從文件讀取數(shù)據(jù)。

測試數(shù)據(jù)：學(xué)生可以根據(jù)自己班級(jí)的考試成績單，任意截取一部分做為測試數(shù)據(jù) 2．一元多項(xiàng)式簡單計(jì)算

問題描述：設(shè)計(jì)一個(gè)簡單一元多項(xiàng)式計(jì)算器?；疽螅?1)輸入并建立多項(xiàng)式；(2)輸出多項(xiàng)式；

(3)兩個(gè)多項(xiàng)式相加，輸出結(jié)果多項(xiàng)式；(4)兩個(gè)多項(xiàng)式相減，輸出結(jié)果多項(xiàng)式。

提高要求：可以根據(jù)輸入變量的值，計(jì)算出多項(xiàng)式的結(jié)果，且算法的效率高。測試數(shù)據(jù)：可任意選取兩個(gè)一元多項(xiàng)式，可以是一般的多項(xiàng)式，也可以是稀疏多項(xiàng)式。3．舞伴問題

問題描述：一班有m個(gè)女生、n個(gè)男生(m不等于n), 舉辦一場舞會(huì).男女生分別編號(hào)坐在舞池兩邊的椅子上，每曲開始時(shí), 依次從男生和女生中各出一人配對(duì)跳舞, 本曲沒成功配對(duì)者坐著等待下一曲找舞伴，設(shè)計(jì)一個(gè)程序模擬舞伴配對(duì)過程。

基本要求：輸入男、女學(xué)生的姓名、性別，由程序自動(dòng)為男女生編號(hào)，可以順序編號(hào)，也可以隨機(jī)編號(hào)，輸出每曲配對(duì)情況（包括男、女生的姓名、性別和編號(hào)）。原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。

測試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)據(jù) 提高要求：計(jì)算出任意一位男生(編號(hào)為X)和任意一位女生(編號(hào)為Y), 在第K曲配對(duì)跳舞的情況。

4．文學(xué)研究助手（*）

問題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”。基本要求：英文小說存于一個(gè)文本文件中，待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì), 結(jié)果保存到文件中。

提高要求：模式匹配選取KMP算法

測試數(shù)據(jù)：以你的C/C++/JAVA源程序模擬英文小說，相應(yīng)語言的保留字集作為待統(tǒng)計(jì)的詞匯集。

5．哈希表的設(shè)計(jì)與實(shí)現(xiàn)（*）

問題描述：針對(duì)某個(gè)單位電話號(hào)碼簿，設(shè)計(jì)一個(gè)哈希表，并完成相應(yīng)的建表和查表程序?；疽螅涸O(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、住址。從鍵盤輸入各記錄，以用戶名為關(guān)鍵字建立哈希表，哈希函數(shù)用除留取余數(shù)法構(gòu)造，采用線性探測法解決沖突?？梢圆迦搿⒉檎?、刪除并顯示給定用戶名的記錄，并計(jì)算查找長度, 哈希表保存到文件中。

測試數(shù)據(jù)：取某個(gè)單位電話號(hào)碼簿中的30個(gè)記錄。

提高要求：將電話號(hào)碼薄以文件形式保存到盤上，能夠按用戶名和電話號(hào)碼兩種形式建立哈希表并實(shí)現(xiàn)插入、查找、刪除表中元素的功能。

6．管道鋪設(shè)施工的最佳方案（*）

問題描述:需要在某個(gè)城市的n個(gè)小區(qū)鋪設(shè)管道，則在這n個(gè)小區(qū)之間鋪設(shè)n-1條管道即可，假設(shè)任意兩個(gè)居民區(qū)之間都可以架設(shè)管道，但由于地理環(huán)境的不同，所需經(jīng)費(fèi)不同，選擇最優(yōu)的施工方案使總投資盡可能的少。

基本要求：輸入表示小區(qū)間關(guān)系的圖及每條管道的權(quán)值，選擇出n-1條管道, 使總投資最小。圖的信息輸入一次后, 保存到文件中, 選擇的n-1條管道輸出到顯示器的同時(shí), 也保存于文件中。

測試用例：任意選擇一個(gè)圖，模擬小區(qū)間可能鋪設(shè)的管道及費(fèi)用。提高要求：顯示原始圖及選擇n-1條管道后的圖。

7．安排教學(xué)計(jì)劃（**）

問題描述：大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩個(gè)學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排上必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課程恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。

基本要求：輸入?yún)?shù)包括學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課程的課程號(hào)、學(xué)分和直接先修課的課程號(hào)；允許兩種策略，一是使學(xué)生在各學(xué)期的學(xué)習(xí)負(fù)擔(dān)盡量均勻，二是使課程盡量集中在前幾個(gè)學(xué)期；若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔ⅲ駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。教學(xué)計(jì)劃的表格格式自行設(shè)定, 可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結(jié)果保存到文件中。

測試數(shù)據(jù)：學(xué)期總數(shù)為6，學(xué)分上限為10，該專業(yè)共開設(shè)12門。以08級(jí)某專業(yè)必修課與選修課為例，選擇12門課程及相應(yīng)學(xué)分，制定一個(gè)表明各門課程先后約束關(guān)系的有向圖。

提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大。8．停車場管理程序(**)問題描述：設(shè)停車場內(nèi)只有一個(gè)可停放n輛汽車的狹長通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。

基本要求：每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)，單位時(shí)間的停車費(fèi)用由用戶從鍵盤輸入）。

測試數(shù)據(jù)：設(shè)輸入數(shù)據(jù)為：（‘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á)；‘D’表示離去，‘E’表示輸入結(jié)束。

提高要求：設(shè)停車場有南、北兩個(gè)門，每個(gè)門都可以進(jìn)、出車輛。9．計(jì)算表達(dá)式的值(**)問題描述：對(duì)于給定的一個(gè)表達(dá)式，表達(dá)式中可以包括常數(shù)、算術(shù)運(yùn)行符（“+”、“-”、“*”、“/”）和括號(hào)，編寫程序計(jì)算表達(dá)式的值。

基本要求：從鍵盤輸入一個(gè)正確的中綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為對(duì)應(yīng)的后綴表達(dá)式，計(jì)算后綴表達(dá)式的值。

測試數(shù)據(jù)：任意選取一個(gè)符合題目要求的表達(dá)式。提高要求：（1）對(duì)于表達(dá)式中的簡單錯(cuò)誤，能夠給出提示；

（2）表達(dá)式中可以包括單個(gè)字母表示的變量。

10．設(shè)計(jì)Huffman 編碼器與解碼器（***）

問題描述：利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道的利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼；在接受端將傳來的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。

基本要求：根據(jù)某字符文件統(tǒng)計(jì)字符出現(xiàn)頻度，構(gòu)造Huffman 樹，編制Huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進(jìn)制位表示編碼）測試數(shù)據(jù)：英文文件。

提高要求：用二進(jìn)制表示編碼，生成二進(jìn)制的編碼文件。11．銀行業(yè)務(wù)模擬（***）

問題描述：設(shè)銀行有四個(gè)服務(wù)窗口，一個(gè)等待隊(duì)列, 每個(gè)窗口均可以辦理存款、取款、掛失、還貸業(yè)務(wù)，每種業(yè)務(wù)所需的服務(wù)時(shí)間不同，客戶到達(dá)銀行后，先到打號(hào)機(jī)上打號(hào)，號(hào)票上包括到達(dá)時(shí)間、編號(hào)和需要辦理的業(yè)務(wù)，然后在銀行內(nèi)等候, 當(dāng)任一服務(wù)窗口空閑時(shí),處理等候客戶中排在最前面的客戶的業(yè)務(wù)。寫一個(gè)上述銀行業(yè)務(wù)的模擬系統(tǒng),通過模擬方法求出客戶在銀行內(nèi)逗留的平均時(shí)間和每個(gè)窗口辦理的客戶數(shù)及辦理的每種業(yè)務(wù)數(shù)。

基本要求：每個(gè)客戶到達(dá)銀行的時(shí)間和需要辦理的業(yè)務(wù)隨機(jī)產(chǎn)生，輸出一天客戶在銀行的平均逗留時(shí)間和每個(gè)窗口每天辦理的客戶數(shù)和每種業(yè)務(wù)數(shù)。

測試數(shù)據(jù)：營業(yè)時(shí)間為8小時(shí)，其他模擬量自行設(shè)定。12．程序源代碼的相似性（***）

問題描述：對(duì)于兩個(gè)C++語言的源程序代碼，用哈希表的方法分別統(tǒng)計(jì)兩個(gè)程序中使用C++語言關(guān)鍵字的情況，并最終按定量的計(jì)算結(jié)果，得出兩份程序的相似性。

基本要求：建立C++語言關(guān)鍵字的哈希表，統(tǒng)計(jì)在每個(gè)源程序中C++關(guān)鍵字出現(xiàn)的頻度, 得到兩個(gè)向量X1和X2，通過計(jì)算向量X1和X2的相對(duì)距離來判斷兩個(gè)源程序的相似性。

例如: 關(guān)鍵字 Void Int For Char if else while do break class 程序1關(guān)鍵字頻度 4 3 0 4 3 0 7 0 0 2 程序2關(guān)鍵字頻度 4 2 0 5 4 0 5 2 0 1 X1=[4,3,0,4,3,0,7,0,0,2] X2=[4,2,0,5,4,0,5,2,0,1] 設(shè)s是向量X1和X2的相對(duì)距離，s=sqrt(∑(xi1-xi2)2)，當(dāng)X1=X2時(shí)，s=0, 反映出可能是同一個(gè)程序；s值越大，則兩個(gè)程序的差別可能也越大。

測試數(shù)據(jù): 選擇若干組編譯和運(yùn)行都無誤的C++程序，程序之間有相近的和差別大的，用上述方法求s, 對(duì)比兩個(gè)程序的相似性。

提高要求：建立源代碼用戶標(biāo)識(shí)符表，比較兩個(gè)源代碼用戶標(biāo)識(shí)符出現(xiàn)的頻度，綜合關(guān)鍵字頻度和用戶標(biāo)識(shí)符頻度判斷兩個(gè)程序的相似性。

13．小型文本編輯器

問題描述：設(shè)計(jì)一個(gè)行編輯程序，使其具有通常行編輯器(如Vi、Edlin)應(yīng)具備的基本功能。

基本要求：編輯器應(yīng)具備對(duì)文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計(jì)字?jǐn)?shù)，統(tǒng)計(jì)行數(shù)等功能，對(duì)于超過一屏的長文件，應(yīng)能夠分頁顯示，查找功能用字符串匹配算法實(shí)現(xiàn)。設(shè)計(jì)用戶接口命令，實(shí)現(xiàn)對(duì)文本的編輯。具體的編輯命令，可參考數(shù)據(jù)結(jié)構(gòu)算法網(wǎng)絡(luò)教學(xué)平臺(tái)上提供的edlin、Vi的命令集。

測試數(shù)據(jù)：任一文本文件。

提高要求：１.可以支持“* ”、“? ”等通配符；

２.支持復(fù)制、粘貼等功能

3.支持多文檔同時(shí)編輯；

提示：可以考慮用雙向鏈表實(shí)現(xiàn)，每一結(jié)點(diǎn)表示一行字符，注意每行字符不能超過255。14．小型英漢詞典

問題描述：設(shè)計(jì)一個(gè)英漢詞典，支持Member(查找)、Insert(插入)、Delete(刪除)操作。

基本要求：實(shí)現(xiàn)字典的常用方法有：有序線性表（Memeber用二分檢索實(shí)現(xiàn)）、AVL樹（二叉搜索樹）、Patricia Trie、散列表等，任選一種方法實(shí)現(xiàn)字典的操作，查找單詞、插入單詞（插入時(shí)，先查找，找不到插入，找到提示用戶）、刪除單詞（刪除時(shí)，先查找，找到刪除，找不到提示用戶）。

測試數(shù)據(jù)：任一英文單詞。提高要求：選用兩種以上的方法實(shí)現(xiàn)字典的操作，并比較不同實(shí)現(xiàn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。

提示：字典可以自己建立，但必須按字母a~z建立26個(gè)文件，建議從網(wǎng)上下載，文件類型為txt。

備注：

1.每道題目后面的*號(hào)，表示題目的難度系數(shù)；對(duì)應(yīng)的評(píng)定成績等級(jí)為及格（無*號(hào)）、中等（*號(hào)）、良好（**號(hào)）、優(yōu)秀（***號(hào)），學(xué)生完成題目的基本要求，即可得到程序設(shè)計(jì)部分的相應(yīng)等級(jí)成績，完成題目提高要求，成績可以向上浮動(dòng)，如果沒有完成基本要求，成績向下浮動(dòng)，直至不及格。

2.所有題目均需用C++完成，不能用C或MFC。3.實(shí)驗(yàn)班的學(xué)生原則上應(yīng)選擇“*”號(hào)多的題目。4.每道題的選題人數(shù)不能超過3人

第五篇：數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱

教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與算法（Data Structures）

計(jì)算機(jī)技術(shù)已成為現(xiàn)代化發(fā)展的重要支柱和標(biāo)志，并逐步滲透到人類生活的各個(gè)領(lǐng)域。隨著計(jì)算機(jī)硬件的發(fā)展，對(duì)計(jì)算機(jī)軟件的發(fā)展也提出了越來越高的要求。由于軟件的核心是算法，而算法實(shí)際上是對(duì)加工數(shù)據(jù)過程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對(duì)提高編程能力和設(shè)計(jì)高性能的算法是至關(guān)重要的。

非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是傳統(tǒng)的數(shù)學(xué)方程問題，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題的學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法。

一、教學(xué)目的與要求---了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；

教學(xué)要求在每章教學(xué)內(nèi)容給出，大體上為三個(gè)層次：了解、掌握和熟練掌握。他們的含義大致為：了解是正確理解概念，掌握是學(xué)會(huì)所學(xué)知識(shí)，熟練掌握就是運(yùn)用所學(xué)知識(shí)解決實(shí)際問題。

教學(xué)目的為：了解算法對(duì)于程序設(shè)計(jì)的重要性 ； 學(xué)習(xí)掌握基本數(shù)據(jù)結(jié)構(gòu)的描述與實(shí)現(xiàn)方法，熟練掌握典型數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用算法的設(shè)計(jì)。了解算法分析方法。

二、教學(xué)重點(diǎn)與難點(diǎn)--數(shù)據(jù)結(jié)構(gòu)中基本概念和術(shù)語，算法描述和分析方法。

1、鏈表插入、刪除運(yùn)算的算法。算法時(shí)間復(fù)雜度

2、后綴表達(dá)式的算法，數(shù)制的換算

利用本章的基本知識(shí)設(shè)計(jì)相關(guān)的應(yīng)用問題

3、循環(huán)隊(duì)列的特點(diǎn)及判斷溢出的條件

利用隊(duì)列的特點(diǎn)設(shè)計(jì)相關(guān)的應(yīng)用問題

4、串的模式匹配運(yùn)算算法

5、二叉樹遍歷算法的設(shè)計(jì)

利用二叉樹遍歷算法，解決簡單應(yīng)用問題 哈夫曼樹的算法

6、圖的遍歷

最小生成樹

最短路徑

7、二叉排序樹查找

平衡樹二叉樹

8、堆排序

快速排序 歸并排序

三、教學(xué)方法與手段-充分利用多媒體教學(xué)工具，配合黑板上的教學(xué)內(nèi)容較難部分的算法實(shí)現(xiàn)過程演義

四、教學(xué)內(nèi)容、目標(biāo)與學(xué)時(shí)分配

教學(xué)內(nèi)容 教學(xué)目標(biāo) 課時(shí)分配

1、緒論

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)

算法和算法分析

2、線性表

線性表的定義與運(yùn)算

線性表的順序存儲(chǔ)

線性表的鏈?zhǔn)酱鎯?chǔ)

3、棧

棧的定義與運(yùn)算

棧存儲(chǔ)和實(shí)現(xiàn)

棧的應(yīng)用舉例

4、隊(duì)列

隊(duì)列的定義與基本運(yùn)算

隊(duì)列的存儲(chǔ)與實(shí)現(xiàn)

隊(duì)列的應(yīng)用舉例

5、串

串的定義與基本運(yùn)算

串的表示與實(shí)現(xiàn)

串的基本運(yùn)算

6、樹和二叉樹

樹的定義和術(shù)語

二叉樹樹的基本概念和術(shù)語 遍歷二叉數(shù)和線索二叉樹

二叉樹的轉(zhuǎn)換

二叉樹的應(yīng)用

哈夫曼樹及其應(yīng)用

7、圖

圖的定義和術(shù)語

圖的存儲(chǔ)結(jié)構(gòu)

圖的遍歷算法

圖的連通性

8、查找

查找的基本概念與靜態(tài)查找 動(dòng)態(tài)查找

哈希表

了解

了解

掌握

熟練掌握順序表存儲(chǔ)地址的計(jì)算

掌握單鏈表的結(jié)構(gòu)特點(diǎn)和基本運(yùn)算

掌握雙鏈表的結(jié)構(gòu)特點(diǎn)和基本運(yùn)算

掌握棧的定義與運(yùn)算

掌握棧的存儲(chǔ)與實(shí)現(xiàn)

熟練掌握棧的各種實(shí)際應(yīng)用

掌握隊(duì)列的定義與基本運(yùn)算

熟練掌握隊(duì)列的存儲(chǔ)與實(shí)現(xiàn)

掌握循環(huán)隊(duì)列的特征和基本運(yùn)算

了解串的邏輯結(jié)構(gòu)

掌握串的存儲(chǔ)結(jié)構(gòu)

熟練掌握串的基本運(yùn)算

了解

了解二叉樹

熟練掌握二叉樹定義和存儲(chǔ)結(jié)構(gòu)

了解二叉樹的遍歷算法

掌握

掌握哈夫曼的建立及編碼

了解

了解

熟練掌握

熟練掌握

了解

熟練掌握

了解哈希表與哈希方法

4學(xué)時(shí)

1學(xué)時(shí)

1學(xué)時(shí)

2學(xué)時(shí)

8學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

4學(xué)時(shí)

8學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

4學(xué)時(shí)

6學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

6學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

12學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

8學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

8學(xué)時(shí)

4學(xué)時(shí)

2學(xué)時(shí)

2學(xué)時(shí)

9、排序

12學(xué)時(shí) 插入排序

熟練掌握基本思想

3學(xué)時(shí) 快速排序

了解各種內(nèi)部排序方法和特點(diǎn)

3學(xué)時(shí) 選擇排序

掌握

2學(xué)時(shí) 各種排序方法比較

掌握

2學(xué)時(shí)

實(shí)驗(yàn)內(nèi)容 實(shí)驗(yàn)?zāi)繕?biāo) 課時(shí)分配 算法編程實(shí)驗(yàn)：

1、用指針方式編寫程序 復(fù)習(xí)C（C++）語言指針、結(jié)構(gòu)體等的用法

2、對(duì)單鏈表進(jìn)行遍歷

鏈表的描述與操作實(shí)現(xiàn)

3、棧及其操作

描述方法及操作

4、編寫串子系統(tǒng)1 串的特點(diǎn)及順序定長存儲(chǔ)、操作、查找

5、編寫串子系統(tǒng) 2 串的特點(diǎn)及順序定長存儲(chǔ)、操作、查找

6、編寫樹子系統(tǒng)1 二叉樹的特點(diǎn)及存儲(chǔ)方式、創(chuàng)建、顯示、遍歷等

7、編寫樹子系統(tǒng)2 二叉樹的特點(diǎn)及存儲(chǔ)方式、創(chuàng)建、顯示、遍歷等

8、圖子系統(tǒng)

圖的鄰接矩陣的存儲(chǔ)、遍歷、廣度/深度優(yōu)先搜索

9、查找子系統(tǒng)

理解查找基本算法、平均查找長度、靜態(tài)、動(dòng)態(tài)查找等

五、考試范圍與題型

1、考試范圍與分?jǐn)?shù)比例

1)緒論

12% 2)線性表

17% 3)棧

7% 4)隊(duì)列

6% 5)串

4% 6)樹和二叉樹

14% 7)圖

15% 8)查找

4% 9)排序

21%

2、考試題型與分?jǐn)?shù)比例

1)名詞解釋

18% 2)判斷對(duì)錯(cuò)

16% 3)填空

16% 4)單項(xiàng)選擇

18% 5)應(yīng)用

32%

六、教材與參考資料

1、教材： 實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（譚浩強(qiáng)）中國鐵道出版社

2、參考資料： 數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏）清華大學(xué)出版社

數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（徐孝凱）清華大學(xué)出版社

（撰寫人：

，審核人： 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí) 2學(xué)時(shí)）