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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)序號(hào)：403040002課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)學(xué)分：1適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)課程設(shè)計(jì)的目的、任務(wù)與基本要求：課程設(shè)計(jì)的目的是培養(yǎng)學(xué)生綜合程序設(shè)計(jì)的能力， 訓(xùn)練學(xué)生靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)和編程實(shí)現(xiàn) 等軟件開(kāi)發(fā)全過(guò)程的綜合實(shí)踐能力。鞏固、深化學(xué)生的理論知識(shí)，提高編程水平，并在此過(guò) 程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的學(xué)習(xí)作風(fēng)。為今后學(xué)習(xí)其他計(jì)算機(jī)課程打下基礎(chǔ)。課 程設(shè)計(jì)為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將書本上的理論知識(shí)和工作、生 產(chǎn)實(shí)際有機(jī)地結(jié)合起來(lái)，從而鍛煉學(xué)生分析問(wèn)題、解決實(shí)際問(wèn)題的能力，提高學(xué)生的編程序

2、能力和創(chuàng)新意識(shí)。在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、 構(gòu)思算法、通過(guò)算法的設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題 目，最終寫出完整的課程設(shè)計(jì)與程序分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī) 調(diào)試工作的效率。課題要求：一人一機(jī)，二至三人一組。課程設(shè)計(jì)結(jié)束，要求學(xué)生提供可運(yùn)行的軟件及源程序，打印課程設(shè)計(jì)報(bào)告與其電子版。課程設(shè)計(jì)內(nèi)容：【課程設(shè)計(jì)題目一】一元稀疏多項(xiàng)式加法、乘法器【問(wèn)題描述】利用單鏈表實(shí)現(xiàn)設(shè)計(jì)一個(gè)一元多項(xiàng)式的的計(jì)算器，用于完成兩個(gè)多項(xiàng)式P(x)、Q(x)的 加法、減法、乘法及求導(dǎo)運(yùn)算。例如(x2+4x5+2x9)+(x+3xQ 或

3、(7x4+4x6+2x9)*(x4+3x【基本要求】輸入并建立兩個(gè)多項(xiàng)式P(x)和。(x)；輸出每個(gè)多項(xiàng)式，要求輸出時(shí)按指數(shù)從小到大輸出。兩個(gè)多項(xiàng)式完成加法、減法、乘法、求導(dǎo)運(yùn)算。輸出兩個(gè)多項(xiàng)式的加法、減法、乘法、求導(dǎo)的結(jié)果。寫出課程設(shè)計(jì)報(bào)告【實(shí)現(xiàn)提示】用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式?！緶y(cè)試數(shù)據(jù)】分別選定三組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目二】局域網(wǎng)的架設(shè)問(wèn)題【問(wèn)題描述】若要在8個(gè)城市(A、B、C、D、E、F、G、H)之間架設(shè)局域網(wǎng)，如何以最低的經(jīng)濟(jì)代價(jià) 架設(shè)這個(gè)局域網(wǎng)，并求出A城市到其他各城市之間的最短距離?！净疽蟆浚?）利用二種方法（Prim算法和克魯斯卡爾（Krus

4、kual）算法生成局域網(wǎng)的架設(shè)方 案（2）利用迪杰斯特拉算法求最短距離。（3）寫出課程設(shè)計(jì)報(bào)告?！緶y(cè)試數(shù)據(jù)】分別對(duì)每種方法選定兩組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目三】校園網(wǎng)架設(shè)的方案與設(shè)計(jì)問(wèn)題【問(wèn)題描述】若要在揚(yáng)州大學(xué)的七個(gè)校區(qū)（江陽(yáng)路南校區(qū)、江陽(yáng)路北校區(qū)、瘦西湖校區(qū)、農(nóng)學(xué)院校區(qū)、 工學(xué)院校區(qū)、水利學(xué)院校區(qū)、醫(yī)學(xué)院校區(qū)）之間架設(shè)校園網(wǎng)，如何以最低的經(jīng)濟(jì)代價(jià)架設(shè)這 個(gè)校園網(wǎng)，（任意兩校區(qū)之間距離估計(jì)一下）。并求出江陽(yáng)路南校區(qū)到其他各校區(qū)之間的最短 距離。【基本要求】（1）利用二種方法（Prim算法和克魯斯卡爾（Kruskual）算法生成校園網(wǎng)的架設(shè)方案（2）利用迪杰斯特拉算法求

5、出江陽(yáng)路校區(qū)到其他各校區(qū)之間的最短距離。（3）寫出課程設(shè)計(jì)報(bào)告。【測(cè)試數(shù)據(jù)】對(duì)每種方法設(shè)定一組模擬測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目四】城市景點(diǎn)導(dǎo)游咨詢系統(tǒng)【問(wèn)題描述】設(shè)計(jì)一個(gè)你所在城市景點(diǎn)導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)?！净疽蟆浚?）設(shè)計(jì)你所在城市平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示城市各景點(diǎn)， 存放景點(diǎn)名稱，地址，景點(diǎn)簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（2）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。（3）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查出任意兩個(gè)景點(diǎn)之間的一條最 短的簡(jiǎn)單路徑。（4）寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定一組模擬測(cè)

6、試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目五】通信網(wǎng)絡(luò)的架設(shè)問(wèn)題【問(wèn)題描述】若要在n（N10）個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可，如何以最低 的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹(shù)問(wèn)題?！净疽蟆浚?）利用二種方法（Prim算法和克魯斯卡爾（Kruskual）生成網(wǎng)中的最小生成樹(shù)。（2）求出任意兩個(gè)城市之間通信的最短距離。（3）將n個(gè)城市設(shè)計(jì)為一個(gè)有向圖，求出一組拓?fù)渑判?。?）寫出課程設(shè)計(jì)報(bào)告。【測(cè)試數(shù)據(jù)】分別對(duì)每種方法選定三組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性。【課程設(shè)計(jì)題目六】?jī)?nèi)部排序的比較【問(wèn)題描述】比較內(nèi)部排序一一冒泡排序、直接插入排序、二分插入排序、

7、選擇排序、快速排序的運(yùn) 行時(shí)間。給出算法執(zhí)行的時(shí)間階或每個(gè)程序的運(yùn)行時(shí)間，精確到秒。【基本要求】（1）比較下列幾種內(nèi)部排序：冒泡排序、插入排序、二分插入排序、選擇排序、快速 排序的運(yùn)行時(shí)間。要求隨機(jī)生成20000個(gè)測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，并輸出每個(gè)程序的運(yùn)行時(shí)間， 精確到秒。（2）驗(yàn)證每個(gè)排序程序的穩(wěn)定性（3）寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性并對(duì)計(jì)算時(shí)間進(jìn)行比較。【課程設(shè)計(jì)題目七】二叉樹(shù)及其遍歷方法【問(wèn)題描述】用遞歸和非遞歸兩種方法創(chuàng)建一棵二叉樹(shù)，并對(duì)它們進(jìn)行先序遍歷、中序遍歷、后序遍 歷及層次遍歷，并求出該二叉樹(shù)的深度和葉子結(jié)點(diǎn)數(shù)、輸入一個(gè)結(jié)點(diǎn)查找該結(jié)點(diǎn)的雙親、祖

8、 先及左右孩子結(jié)點(diǎn)?！净疽蟆浚?）用遞歸和非遞歸兩種方法創(chuàng)建一棵二叉樹(shù)。（2）用遞歸和非遞歸兩種方法，對(duì)二叉樹(shù)進(jìn)行先序遍歷、中序遍歷、后序遍歷及層 次遍歷。（3）求出該二叉樹(shù)的深度和葉子結(jié)點(diǎn)數(shù)。（4）輸入一個(gè)結(jié)點(diǎn)查找該結(jié)點(diǎn)的雙親、祖先及左右孩子結(jié)點(diǎn)。（5）寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定兩組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目八】表達(dá)式的求值演算【問(wèn)題描述】以字符序列的形式從終端輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的 算符優(yōu)先關(guān)系，加上乘方廠）和求除（）運(yùn)算符，實(shí)現(xiàn)對(duì)算術(shù)混合運(yùn)算表達(dá)式的求值?！净疽蟆浚?）表達(dá)式中含有乘方廠）、加（+）、減（-）、乘（*）

9、、除（/）、求除（%）運(yùn)算；并含有 括號(hào)。（2）分別以五組不同的表達(dá)式作為測(cè)試實(shí)例，每個(gè)實(shí)例中含有上述所有運(yùn)算符，測(cè)試 其結(jié)果的正確性。寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】選定五組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目九】設(shè)計(jì)一個(gè)矩陣運(yùn)算器【問(wèn)題描述】設(shè)計(jì)一個(gè)矩陣運(yùn)算器，對(duì)矩陣進(jìn)行乘方廠)、加(+)、減(-)、乘(*)、轉(zhuǎn)置等運(yùn)算；【基本要求】參見(jiàn)數(shù)據(jù)結(jié)構(gòu)題集P136頁(yè)4.1求含有乘方廠)、加(+)、減(-)、乘(*)運(yùn)算；。寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】分別選定一組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目十】自來(lái)水管理架設(shè)問(wèn)題【問(wèn)題描述】若要在揚(yáng)州大學(xué)的八個(gè)居民區(qū)(A區(qū)、B區(qū)、C

10、區(qū)、D區(qū)、E區(qū)、F區(qū)、G區(qū)、H區(qū))之間 架設(shè)自來(lái)水管道，如何以最低的經(jīng)濟(jì)代價(jià)架設(shè)這個(gè)自來(lái)水管道?！净疽蟆坷枚N方法(Prim算法和克魯斯卡爾(Kruskual)算法生成自來(lái)水管道的架設(shè)寫出課程設(shè)計(jì)報(bào)告?！緶y(cè)試數(shù)據(jù)】分別對(duì)每種方法選定三組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目十一】哈夫曼樹(shù)與哈夫曼碼【問(wèn)題描述】創(chuàng)建一棵哈夫曼樹(shù)并實(shí)現(xiàn)哈夫曼編碼的輸出?！净疽蟆枯斎胍粋€(gè)文本，統(tǒng)計(jì)各字符出現(xiàn)的頻度，輸出結(jié)果使用字符出現(xiàn)的頻度構(gòu)造哈夫曼樹(shù)輸出各字符按上述頻度所構(gòu)造的哈夫曼編碼輸入一個(gè)由0和1組成的代碼序列，翻譯并輸出與之對(duì)應(yīng)的文本，若最后的代碼 子序列不能譯為文本，則輸出相關(guān)出錯(cuò)信

11、息寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】分別對(duì)選定兩組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性?！菊n程設(shè)計(jì)題目十二】二叉排序樹(shù)【問(wèn)題描述】輸入一個(gè)數(shù)列創(chuàng)建一棵二叉排序樹(shù)T,對(duì)二叉排序樹(shù)T按遞增、遞減兩種序列輸出，計(jì) 算該二叉排序樹(shù)T的平均查找長(zhǎng)度并輸出，在二叉排序樹(shù)T上刪除指定結(jié)點(diǎn)，并輸出二叉排 序樹(shù)T中指定結(jié)點(diǎn)的平衡因子。【基本要求】輸入一個(gè)數(shù)列L，生成一棵二叉排序樹(shù)T對(duì)二叉排序樹(shù)T作遞增、遞減輸出計(jì)算二叉排序樹(shù)T的平均查找長(zhǎng)度，輸出結(jié)果在二叉排序樹(shù)T上刪除指定結(jié)點(diǎn)輸出二叉排序樹(shù)T中指定結(jié)點(diǎn)的平衡因子寫出課程設(shè)計(jì)報(bào)告【測(cè)試數(shù)據(jù)】分別對(duì)選定兩組測(cè)試數(shù)據(jù)進(jìn)行測(cè)試，驗(yàn)證程序的正確性。【課程設(shè)計(jì)題目十三】雙向鏈表的操作【問(wèn)題描述】創(chuàng)建一個(gè)雙向鏈表，并實(shí)現(xiàn)雙向鏈表的基本操作?！净疽?/p>