【正文】 102實驗預(yù)研報告清晰、正確、圖表齊全、質(zhì)量高103態(tài)度認(rèn)真，作風(fēng)嚴(yán)謹(jǐn)，并按規(guī)定的進(jìn)度開展實驗工作104能很好地完成任務(wù)書規(guī)定的工作量105在實驗中，學(xué)生使用和操作儀器的能力、觀察和分析實驗現(xiàn)象的能力、主動排除故障的能力106對實驗結(jié)果有自己獨立見解107答辯簡明扼要、重點突出地闡述課題的主要內(nèi)容108準(zhǔn)確流利地回答各種問題，能否闡明自己的觀點109課程設(shè)計報告，內(nèi)容充實、圖表齊全、數(shù)據(jù)處理正確、結(jié)構(gòu)合理、書面整潔1010文字表達(dá)能力強(qiáng)，準(zhǔn)確地表達(dá)自己的思想。要求：按“課程設(shè)計教學(xué)大綱”的要求完成不“數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告”。⑵ 深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計技術(shù)，提高分析和解決實際問題的能力。（2）程序的運行時間應(yīng)盡可能少。合肥學(xué)院計算機(jī)科學(xué)與技術(shù)系課程設(shè)計報告20 ～20 學(xué)年第 學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱學(xué)生姓名高蘇廣學(xué)號020202086專業(yè)班級03計科(1)指導(dǎo)教師20 年 月計算機(jī)科學(xué)與技術(shù)系課程設(shè)計評分表學(xué)生/學(xué)號： （5號字、宋體） 專業(yè)/班級：計算機(jī)科學(xué)與技術(shù)06級1班設(shè)計題目二元多項式加減運算問題成績 課程設(shè)計主要內(nèi)容一、內(nèi)容設(shè)計程序以實現(xiàn)降冪建立、輸出、加、減任意兩個二元多項式。紙質(zhì)文檔包括：《課程設(shè)計報告》1份（用塑料拉桿夾裝訂好）；《課程設(shè)計評分表》1份；《課程設(shè)計任務(wù)書》1份（可以雙面打?。?；《課程設(shè)計的心得體會》1份；紙質(zhì)文檔裝入“課程設(shè)計資料袋”上交?！墩n程設(shè)計報告》文檔規(guī)范及注意事項一、按照《實驗指導(dǎo)書》中“課程設(shè)計示例”模式寫；即：應(yīng)包括題目、問題分析和任務(wù)定義、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計、詳細(xì)設(shè)計和編碼、上機(jī)調(diào)試過程、測試結(jié)果及其分析、用戶使用說明、參考文獻(xiàn)、附錄這幾個部分和順序；二、文檔格式為A4紙、宋體、5號字、一級標(biāo)題加粗、單倍行距；三、圖、表應(yīng)有標(biāo)號和名稱，且圖名位于圖下，表名位于表格上方；四、參考文獻(xiàn)格式為：序號 作者．書名．出版地：出版社名稱，出版社年份序號 作者．論文題名．期刊名稱，年份，卷號（期號）：起至頁碼五、附錄中的源代碼應(yīng)有適當(dāng)?shù)淖⑨?；六、按照格式要求填寫《課程設(shè)計報告封面》、《課程設(shè)計評分表》中學(xué)生應(yīng)填寫的內(nèi)容。5 號同學(xué)接完水，即所有人完成接水?！　〉? 秒，3 人接水。第3 秒結(jié)束時，2 號同學(xué)每人的已接水量為3，4 號同學(xué)的已接　　水量為2。第2 秒結(jié)束時，2 號同學(xué)每人的已接水量為2，4 號同學(xué)的已接　　水量為1。第1 秒結(jié)束時，3 號同學(xué)每人的已接水量為1，3 號同學(xué)接完　　水，4 號同學(xué)接替3 號同學(xué)開始接水。輸出格式　　輸出只有一行，1 個整數(shù)，表示接水所需的總時間。輸入格式　　第1 行2 個整數(shù)n 和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。若當(dāng)前接水人數(shù)n’不足m， 則只有n’個龍頭供水，其它m?n’個龍頭關(guān)閉。這個換人的過程是瞬間完成的，且沒有任何水的浪費。接水開始時，1 到m 號同學(xué)各占一個水龍頭，并同時打 開水龍頭接水。 現(xiàn)在有n 名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。50 接水問題 輸出格式　　輸出一行，包含一個整數(shù)，表示小朋友的不高興程度和的最小值。輸入格式　　輸入的第一行包含一個整數(shù)n，表示小朋友的個數(shù)?！　≌垎枺屗行∨笥寻磸牡偷礁吲抨?，他們的不高興程度之和最小是多少?！　∪绻硞€小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類推?！　∶總€小朋友都有一個不高興的程度。問題描述　　n 個小朋友站成一排。樣例輸入151 2 21 3 12 4 52 5 4樣例輸出1135輸出格式大臣J從城市4到城市5要花費135的路費。接下來n1行，描述T國的高速路（T國的高速路一定是n1條）每行三個整數(shù)Pi, Qi, Di，表示城市Pi和城市Qi之間有一條高速路，長度為Di千米。也就是說走1千米花費11，走2千米要花費23。他有一個錢袋，用于存放往來城市間的路費。J是T國重要大臣，他巡查于各大城市之間，體察民情。為節(jié)省經(jīng)費，T國的大臣們經(jīng)過思考，制定了一套優(yōu)秀的修建方案，使得任何一個大城市都能從首都直接或者通過其他大城市間接到達(dá)。問題描述很久以前，T王國空前繁榮。（約定樹結(jié)點用不同的大寫字母表示，長度=8）。問題描述　　給出一棵二叉樹的中序與后序排列。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。樣例輸入44 99 1113 1910 17樣例輸出21 3[1] 字典序指在字典中排列的順序，如果序列l(wèi)1是序列l(wèi)2的前綴，或者對于l1和l2的第一個不同位置j，l1[j]l2[j]，則l1比l2小。數(shù)據(jù)規(guī)模和約定　　對于50%的輸入，N≤3000。輸出格式　　輸出的第一行應(yīng)有一個整數(shù)M，表示最多可以租借給多少家公司。第i+1行的整數(shù)表示第i家公司申請租借的起始和終止日期。輸入格式　　輸入的第一行有一個整數(shù)N，表示發(fā)出租借會堂申請的公司的個數(shù)。而在字典序中(1,3)(1,4)(2,3)。最后，選出其中字典序最小[1]的候選策略作為最終的策略?！　′N售主管為了公平起見，決定按照如下的程序來確定選擇何種租借策略：首先，將租借給客戶數(shù)量最多的策略作為候選，將所有的公司按照他們發(fā)出請求的順序編號。租借策略分別是租給公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。他們對租借會堂發(fā)出了請求，并提出了他們所需占用會堂的起止日期（如下表所示）。　　例如下面的例子。會議中心的銷售主管認(rèn)為：最好的策略應(yīng)該是將會堂租借給盡可能多的客戶。許多公司對租借會議中心的會堂很感興趣，他們希望能夠在里面舉行會議。Sample OutputYESNO44 會議中心 輸出：如果序列相同則輸出YES，否則輸出NO接下去一行是一個序列，序列長度小于10，包含(0~9)的數(shù)字，沒有重復(fù)數(shù)字，根據(jù)這個序列可以構(gòu)造出一顆二叉搜索樹。輸入格式　　一行，為導(dǎo)彈依次飛來的高度輸出格式　　兩行，分別是最多能攔截的導(dǎo)彈數(shù)與要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)樣例輸入389 207 155 300 299 170 158 65樣例輸出6243 二叉搜索樹判斷兩序列是否為同一個二叉搜索樹序列由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。42 攔截導(dǎo)彈 若網(wǎng)絡(luò)中任意兩機(jī)器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k ponents.”,其中k是網(wǎng)絡(luò)中連通集的個數(shù)。 【輸出要求】 1 5 4 2 3 9 8 7 6 500m 200m 200m 100m 200m 50m 100m 500m 700m 100m 100m 對每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺計算機(jī)的序號，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結(jié)束。請寫出程序判斷：任意指定兩臺計算機(jī)，它們之間是否可以進(jìn)行文件傳輸？【輸入要求】 輸入若干測試數(shù)據(jù)組成。41 最短路 對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。 可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（n,n）。實現(xiàn)提示： 計算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向，如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 選做內(nèi)容：（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。為處理方便起見，可在迷宮的四周加一圈障礙。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)的迷宮沒有通路。測試數(shù)據(jù)： 迷宮的測試數(shù)據(jù)如下：左下角（1，1）為入口，右下角（8，9）為出口。要求： 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。39迷宮問題（棧） 以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。至少用兩種或兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。2):1)任意給定一個M進(jìn)制的數(shù)x要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。排長是不愿意去的，假設(shè)排長為1號，請你設(shè)計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。現(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當(dāng)數(shù)到5時，對應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計數(shù)。有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪個戰(zhàn)士去執(zhí)行任務(wù)。盡量設(shè)計出多種算法及程序。（2）計算出任何一個男生（編號為X）和任意女生（編號為Y），；請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程，要求如下：每曲開始時，依次從男生和女生中各出一人配對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴。一班有m個女生,有n個男生（m不等于n），現(xiàn)要開一個舞會。36 學(xué)生搭配問題。 /*選手得分*/ int tax。 /*選手姓名*/ int num。將選手的編號和姓名依此存入順序表單元中，觀眾通過按鍵進(jìn)行投票，按’1’為1號選手投票，按’2’為2號選手投票，以此類推，以按’0’作為投票結(jié)束標(biāo)志。現(xiàn)在要求編寫一程序模擬實現(xiàn)上述系統(tǒng)的功能。讀取一個稀疏矩陣建立其完全鏈表表示輸出一個稀疏矩陣的內(nèi)容刪除一個稀疏矩陣兩個稀疏矩陣相加兩個稀疏矩陣相減兩個稀疏矩陣相乘稀疏矩陣的轉(zhuǎn)置（4）實現(xiàn)提示鏈表上的操作。實現(xiàn)一個完全鏈表系統(tǒng)進(jìn)行稀疏矩陣運算，并分析下列操作函數(shù)的計算時間和額外存儲空間的開銷。另外，增加一個包含矩陣維數(shù)的結(jié)點。使得第二個表即列表，把所有結(jié)點按照列序（同一列內(nèi)按行序）用down鏈接起來。用單獨一個結(jié)點表示一個非零項，并將所有結(jié)點連接在一起，形成兩個循環(huán)鏈表。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽車的牌照號碼和進(jìn)入停車場的時刻。[實現(xiàn)提示]需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實現(xiàn)。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達(dá)”或“離去”信息、汽車牌照號碼及到達(dá)或離去的時刻，其中，‘A’表示到達(dá)；‘D’表示離去，‘E’表示輸入結(jié)束。試為停車場編制按上述要求進(jìn)行管理的模擬程序。33 停車場管理[問題描述]設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。[測試數(shù)據(jù)]由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定。[基本要求]針對一種特定商品，實現(xiàn)上述管理過程。32 商品貨架管理[問題描述]商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。退出系統(tǒng)：退出程序。插入元素：在哈希表中，插入一個元素，分為插入成功和失敗。顯示元素：顯示已經(jīng)創(chuàng)建的哈希表。設(shè)計思想：哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列處理沖突。31 哈希表應(yīng)用　【問題描述】 利用哈希表進(jìn)行存儲。測試數(shù)據(jù)：　　m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？　　 要求： 輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n ，輸入每個人的密碼，建立單循環(huán)鏈表。設(shè)計一個程序來求出出列順序。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找成功與否的信息、插入和刪除后的中序遍歷結(jié)果(排序結(jié)果)?！緶y試數(shù)據(jù)】由隨機(jī)數(shù)產(chǎn)生器生成29 動態(tài)查找表【問題描述】 利用二叉排序樹完成動態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點。2) 待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)程序產(chǎn)生