B131000920數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課題要求201612計15008物15002

1、-0-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實施方案（201612）（部分）-課題要求3 教學(xué)內(nèi)容及基本要求3-1 總體設(shè)計要求1、 采用 C/C+編程語言，推薦使用 C+勺類來完成綜合訓(xùn)練題目，使用 C+啲模板類（STL）,來完成研究性學(xué)習(xí)與創(chuàng)新性設(shè)計題目。2、 軟件采用模塊化結(jié)構(gòu)，劃分功能模塊，確定模塊間勺聯(lián)系，實現(xiàn)模塊勺算法。3、 軟件測試與調(diào)試，給出必要勺測試用例數(shù)據(jù)。4、 軟件要完成界面設(shè)計，推薦設(shè)計可視化界面。5、 完成設(shè)計要求中規(guī)定勺基本功能。6、 在完成基本設(shè)計要求勺基礎(chǔ)上，可以增加和完善功能。7、 對所完成勺課題勺算法進行時間和空間勺性能評價。8、 針對創(chuàng)新性應(yīng)用課題，在數(shù)據(jù)結(jié)構(gòu)或算法設(shè)計中有所創(chuàng)

2、新。9、 學(xué)生在軟件開發(fā)中要體現(xiàn)團隊協(xié)作精神和程序設(shè)計勺調(diào)試能力。3-2 綜合訓(xùn)練性題目（ A 類）綜合訓(xùn)練性題目勺設(shè)計考慮到與課堂講授勺內(nèi)容相銜接，以問題為中心，體現(xiàn)數(shù)據(jù)結(jié)構(gòu) 的綜合應(yīng)用。本次課程設(shè)計共安排 15 個綜合訓(xùn)練性 A 類可選題目。1、立體化停車場管理【問題描述】設(shè)停車場有地上和地下兩層，統(tǒng)一管理。地下停車場采用單入口和單出口。地上停車場 采用南北方向的雙口，每個口都有一個入口和出口。停車順序先地上，后地下。地上入口處 各有一個單車道的等候通道，并允許等候的車輛因急事從等候通道直接開走?！驹O(shè)計要求】設(shè)計停車場模擬管理程序。（ 1 ）采用棧、隊列和有序表等數(shù)據(jù)結(jié)構(gòu)。（ 2）可以隨機

3、、文件及人工輸入數(shù)據(jù)。（ 3 ）等候車輛的管理。（ 4 ）地下、地上停車位的管理。（ 5）停車計費功能。（ 6）其它完善性或擴展性功能。2、運動會競賽成績統(tǒng)計【問題描述】東北大學(xué)第 54 屆運動大會成功舉行。共有 N 個學(xué)院的學(xué)生男女代表隊和教工代表隊參 賽。大會共設(shè) M 個學(xué)生男子項目和 W 個學(xué)生女子項目、 R 個教工團體項目。大會即將閉幕， 準(zhǔn)備公布成績。【設(shè)計要求】 設(shè)計運動會競賽成績統(tǒng)計程序。（ 1 ）采用順序表、集合等數(shù)據(jù)結(jié)構(gòu)。（ 2）可以隨機、文件及人工輸入數(shù)據(jù)。（ 3）統(tǒng)計各代表隊的男女總分和團體總分。（4）采用堆排序，公布各單項成績的前六名和團體成績的前三名。（5）可以查詢和

4、更新數(shù)據(jù)。-1-（6）其它完善性或擴展性功能。3、銀行業(yè)務(wù)模擬 【問題描述】 銀行有 N 個窗口對外接待客戶。從早晨銀行營業(yè)開始到晚間營業(yè)終止不斷有客戶辦理業(yè) 務(wù)。銀行門口設(shè)有取號機，分為一般業(yè)務(wù)和特殊業(yè)務(wù)，設(shè)每個一般業(yè)務(wù)不超過5 分鐘，每個特殊業(yè)務(wù)不超過 15 分鐘?？蛻粼诘群騾^(qū)內(nèi)等候叫號?！驹O(shè)計要求】 設(shè)計銀行客戶業(yè)務(wù)的模擬程序。（1）采用有序鏈表、隊列等數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）分類統(tǒng)計一天內(nèi)客戶在銀行逗留的平均時間和人數(shù)。（4）若特殊業(yè)務(wù)窗口空閑，可辦理一般業(yè)務(wù)。（5）可以查詢和更新數(shù)據(jù)。（6）其它完善性或擴展性功能。4、電梯運行模擬 【問題描述】 東北大學(xué)綜

5、合辦公樓有 14 層，設(shè)有 4 部自動電梯。每梯最多載客12 人。從上班到下班 不斷有乘客使用電梯。電梯運行每上下一層需 5 秒，空閑時，在某一層最多停留 10 秒，否則 返回 1 層待命。乘客等待電梯時間不超過 T 時間?！驹O(shè)計要求】 設(shè)計電梯工作運行的模擬程序。（1）采用有序鏈表、隊列、數(shù)組等數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）實時顯示電梯的工作運行狀況。（4）統(tǒng)計一天內(nèi)每樓層電梯的使用人次數(shù)。（5）可以查詢和更新數(shù)據(jù)。（6）其它完善性或擴展性功能。5、哈夫曼壓縮軟件設(shè)計 【問題描述】 采用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。利用哈夫曼編碼對文本或 圖像進行數(shù)

6、據(jù)壓縮，設(shè)計數(shù)據(jù)壓縮軟件?！驹O(shè)計要求】 設(shè)計基于哈夫曼編碼的文本和圖像壓縮軟件。（1）采用靜態(tài)鏈表的二叉樹等數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）創(chuàng)建哈夫曼樹，生成哈夫曼編碼和譯碼。（4）源碼、編碼和壓縮后的信息均以文件形式保存。（5）可以查詢和更新數(shù)據(jù)。（6）其它完善性或擴展性功能。6、教務(wù)課程計劃安排 【問題描述】 拓?fù)浼系膭澐挚梢越鉀Q教務(wù)課程安排問題。高校每學(xué)年含兩學(xué)期，每學(xué)期的教學(xué)周數(shù) 和學(xué)分均有上限。在教學(xué)計劃一定的情況下，開設(shè)的課程必須滿足次序關(guān)系。拓?fù)浼系膭?分與拓?fù)渑判虻乃惴愃啤！驹O(shè)計要求】設(shè)計基于拓?fù)浼蟿澐值慕虅?wù)課程編排模擬程序。（1）采用圖鄰接表、棧等

7、數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）計算課程安排的最優(yōu)劃分，盡量使學(xué)期最短。（4）可以統(tǒng)計數(shù)據(jù)并滿足必要的約束條件。（5）可以查詢和更新數(shù)據(jù)。（6）其它完善性或擴展性功能。7、城市旅游購物交通咨詢模擬 【問題描述】 沈陽城內(nèi)有若干旅游觀光景點和商業(yè)區(qū)。游客主要以公交車為交通工具出游。假設(shè)往返 于每個景點和商業(yè)區(qū)的公交線路不少于 6 路。旅客希望中轉(zhuǎn)次數(shù)最少、時間最短、費用最省?！驹O(shè)計要求】 設(shè)計城市交通咨詢模擬程序。-2-（1）采用圖結(jié)構(gòu)、集合等數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）可以完成旅游、購物一日游的最佳線路。（4）可以統(tǒng)計數(shù)據(jù)并滿足必要的約束條件。（5）

8、可以查詢和更新數(shù)據(jù)。（6）其它完善性或擴展性功能。8、校園光纖網(wǎng)絡(luò)鋪設(shè) 【問題描述】 東北大學(xué)鋪設(shè)校園光纖網(wǎng)絡(luò)。假設(shè)有 N 個學(xué)院和辦公樓，只需要鋪設(shè) N-1 條光纜通道 采用最小生成樹的算法，給出一個最佳鋪設(shè)方案。【設(shè)計要求】 設(shè)計基于最小生成樹的校園光纜鋪設(shè)程序。（ 1 ）采用圖結(jié)構(gòu)、并集樹等數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3） 采用克魯斯卡爾算法設(shè)計最小代價生成樹（4） 可以采用堆排序算法選擇權(quán)值最小的邊。（5） 采用并集樹完成樹邊的查詢和合并。（6） 其它完善性或擴展性功能。9、汽車牌照的快速查詢 【問題描述】 在汽車數(shù)據(jù)的信息模型中，汽車牌照是具有結(jié)構(gòu)特點的一類關(guān)鍵字

9、。汽車牌照是字母和數(shù)字混編的，例如 01B7238。利用查找和排序算法，實現(xiàn)遼寧省內(nèi)汽車牌照的快速查找。 【設(shè)計要求】 設(shè)計汽車牌照的快速查詢程序。（1） 采用順序表、靜態(tài)鏈表等數(shù)據(jù)結(jié)構(gòu)。（2） 可以隨機、文件及人工輸入數(shù)據(jù)。（3） 利用靜態(tài)鏈表對汽車牌照進行鏈?zhǔn)交鶖?shù)排序。（4） 采用折半查找汽車牌照。（5） 可以按城市進行分塊索引查找。（6） 其它完善性或擴展性功能。10、十進制四則運算計算器 【問題描述】 由輸入的四則運算表達式字符串，動態(tài)生成算術(shù)表達式所對應(yīng)的二叉樹，通過表達式二叉樹自動求值并輸出?！驹O(shè)計要求】 設(shè)計十進制整數(shù)四則運算計算器。（1）采用二叉樹、棧等數(shù)據(jù)結(jié)構(gòu)。（2）可以隨機

10、、文件及人工輸入數(shù)據(jù)。（3）給定表達式字符串，生成二叉鏈表的表達式二叉樹。（4）對表達式二叉樹采用后序遍歷求值并輸出。（5）具有計算整數(shù)和復(fù)數(shù)四則運算的功能。（6）其它完善性或擴展性功能。11、互聯(lián)網(wǎng)域名信息管理系統(tǒng) 【問題描述】 互聯(lián)網(wǎng)域名系統(tǒng)是一個典型的樹形層次結(jié)構(gòu)。從根節(jié)點往下的第一層是頂層域，如cn、com 等，最底層（第四層）是葉子結(jié)點，如 www 等?！驹O(shè)計要求】 設(shè)計互聯(lián)網(wǎng)域名信息管理的模擬程序。（1）采用樹的孩子兄弟鏈表等存儲結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）實現(xiàn)域名的創(chuàng)建、分類、插入、刪除、修改等管理功能。（4）實現(xiàn)域名的查詢和統(tǒng)計功能。（5）考慮采用優(yōu)化的查詢

11、和排序算法。（6）其它完善性或擴展性功能。12、無向圖的關(guān)節(jié)點問題 【問題描述】 對無向連通圖，若刪除某個結(jié)點使其成為非連通圖，則稱-3-該結(jié)點為關(guān)節(jié)點。假設(shè)某一地 區(qū)公路交通網(wǎng)，求解關(guān)節(jié)點?！驹O(shè)計要求】 設(shè)計求解無向連通圖關(guān)節(jié)點的模擬程序。（1）采用鄰接表或鄰接矩陣存儲結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）采用深度優(yōu)先遍歷求解關(guān)節(jié)點。（4）實現(xiàn)關(guān)節(jié)點的查詢和統(tǒng)計功能。（5）實現(xiàn)將關(guān)節(jié)點改造為非關(guān)節(jié)的功能。（6）其它完善性或擴展性功能。13、手機個人通訊錄信息管理系統(tǒng) 【問題描述】 對手機個人通訊錄的創(chuàng)建和查詢等信息管理作一個簡單的模擬?！驹O(shè)計要求】 設(shè)計手機個人通訊錄管理的模擬程序

12、。（1）采用順序表或結(jié)構(gòu)體鏈表存儲結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）實現(xiàn)通訊錄的創(chuàng)建、修改、插入、刪除、分組等管理功能。（4）實現(xiàn)通訊錄的各種查詢和統(tǒng)計功能。（5）實現(xiàn)人機交互界面功能。（6）其它完善性或擴展性功能。14、超市商品庫存信息管理系統(tǒng) 【問題描述】對一個中小型超市的庫存商品信息管理作一個簡單的模擬。 【設(shè)計要求】 設(shè)計超市庫存商品信息維護管理的模擬程序。（1）采用順序表或結(jié)構(gòu)體鏈表存儲結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）實現(xiàn)超市商品的創(chuàng)建、分類、出庫、入庫、修改等管理功能。（4）實現(xiàn)庫存商品的各種查詢和統(tǒng)計功能。（5）實現(xiàn)人機交互界面功能。（6）其它完善性

13、或擴展性功能。15、圖書館圖書借閱信息管理系統(tǒng)【問題描述】 對圖書館的圖書借閱業(yè)務(wù)管理作一個簡單的模擬?！驹O(shè)計要求】設(shè)計圖書借閱信息管理的模擬程序。（1）采用順序表或結(jié)構(gòu)體鏈表存儲結(jié)構(gòu)。（2）可以隨機、文件及人工輸入數(shù)據(jù)。（3）實現(xiàn)圖書的創(chuàng)建、分類、插入、刪除、修改、借閱等管理功能。（4）實現(xiàn)圖書的各種借閱查詢和統(tǒng)計功能。（5）實現(xiàn)人機交互界面功能。（6）其它完善性或擴展性功能。3-3 研究性學(xué)習(xí)與創(chuàng)新性設(shè)計題目（ B 類） 研究性學(xué)習(xí)與創(chuàng)新性設(shè)計題目的設(shè)計重點是在鞏固基本數(shù)據(jù)結(jié)構(gòu)知識的基礎(chǔ)上，激發(fā)學(xué) 生的自主性學(xué)習(xí)熱情和創(chuàng)造性思維能力，擴充數(shù)據(jù)結(jié)構(gòu)課程的知識量。一方面可以將課堂上 及書本上的

14、內(nèi)容做應(yīng)用擴展；另一方面可以設(shè)計基于STL 框架的數(shù)據(jù)結(jié)構(gòu)應(yīng)用程序。本次課程設(shè)計共安排 15 個研究性學(xué)習(xí)與創(chuàng)新性設(shè)計 B 類可選題目。1、 二進制堆及其應(yīng)用【問題描述】 堆是設(shè)計很巧妙的數(shù)據(jù)結(jié)構(gòu)，堆排序的算法也有很多應(yīng)用。但當(dāng)堆比較龐大時，選取堆 頂元素及重新建堆的工作量也較大。利用堆的定義構(gòu)建二進制堆，應(yīng)用于優(yōu)先隊列有很大的-4-優(yōu)勢。二進制堆是在二進制樹 Bk上建立的數(shù)據(jù)結(jié)構(gòu)。一個整數(shù)可以表示為二進制數(shù)，一組關(guān) 鍵字組成的序列可以由一組二進制堆表示?！驹O(shè)計要求】 設(shè)計基于 STL 框架的二進制堆的抽象數(shù)據(jù)類型及其實現(xiàn)。（1）實現(xiàn)二進制堆 Hk的 ADT。（2）應(yīng)用基本運算，實現(xiàn)二進制堆的

15、簡單應(yīng)用。2、 線段樹及其應(yīng)用【問題描述】 在實際應(yīng)用中，常遇到與區(qū)間有關(guān)的操作，比如統(tǒng)計若干矩形并集的面積，記錄一個區(qū) 間的最大最小值及總量，并在區(qū)間的插入、刪除和修改中維護這些數(shù)據(jù)。線段樹的定義是利用樹形二分結(jié)構(gòu)所建立的一種數(shù)據(jù)結(jié)構(gòu)，能夠高效的完成這些操作。【設(shè)計要求】 設(shè)計基于 STL 框架的線段樹的抽象數(shù)據(jù)類型及其實現(xiàn)。（ 1 ）實現(xiàn)線段樹的 ADT 。（2）應(yīng)用基本運算，實現(xiàn)線段樹的簡單應(yīng)用。3、郵局選址問題 【問題描述】 n 個居民小區(qū)規(guī)則的坐落在城市中，用 x 表示東西向，用 y 表示南北向。如何選擇郵局 的最佳位置，才能使 n 個居民小區(qū)到郵局的費用為最省。【設(shè)計要求】 采用最

16、短路徑算法求解。(1)采用 STL 數(shù)據(jù)結(jié)構(gòu)或設(shè)計基于 STL 框架的數(shù)據(jù)結(jié)構(gòu)。( 2)應(yīng)用基本運算，設(shè)計算法求解。4、男女運動員最佳組合 【問題描述】 設(shè)有 N 個男羽毛球運動員和 N 個女羽毛球運動員，現(xiàn)組成N 對男女混合最佳組合。 每 個男運動員對每個女運動員都有一個滿意度排序， 用矩陣 mf0:n-10:n-1表示。 mfij 表示 第 i 個男運動員對第 j 個女運動員的滿意度，滿意度值越高，滿意程度越高。同理，每個女運 動員對每個男運動員也有一個滿意度排序，用矩陣 fm0:n-10:n-1 表示。男女運動員之間的 一個完全匹配稱為一個組合。【設(shè)計要求】 設(shè)計對于給定的滿意度，求最佳

17、組合的程序，使得滿意度總和達到最大。(1)采用 STL 的一維向量類構(gòu)造構(gòu)造二維向量矩陣。 ( 2)應(yīng)用基本運算，設(shè)計算法求解。5、最佳任務(wù)分配方案 【問題描述】 設(shè)有 n 個人，準(zhǔn)備承擔(dān) m 項課題任務(wù)，每個人只能承擔(dān)其中的1 項。一般情況下 nm, 可以有多種任務(wù)分配方案。假設(shè)每個人完成不同的課題所需的經(jīng)費不同，則一定存在一種最 佳方案，使得完成所有課題的總的費用最省。【設(shè)計要求】 設(shè)計對于給定的任務(wù)分配方案，求最佳任務(wù)分配方案，使得費用最省。( 1 )采用 STL 一維向量類構(gòu)造二維向量矩陣。 ( 2)應(yīng)用基本運算，通過搜索狀態(tài)空間樹實現(xiàn)問題求解。6、 排隊購票問題【問題描述】 世界杯足

18、球亞洲區(qū)預(yù)選賽正在激烈進行。決賽門票處于熱賣。為使門票公平、安全的銷 售，售票處決定采用如下售票規(guī)則：( 1 )購票者到購票處領(lǐng)取一個隨機編號。購票者按隨機編號從小到大排序。 ( 2)隨機編號處于最小編號與最大編號之間的購票者，可直接到窗口排隊購票。( 3)售票窗口空閑時隨機發(fā)出 0 或 1 指令，指令為 0 時，最小編號者到窗口購票，指令 為 1時，最大編號者到窗口購票?！驹O(shè)計要求】 設(shè)計算法實現(xiàn)按上述規(guī)則的排隊售票程序。(1)采用 STL 的雙端隊列類等數(shù)據(jù)結(jié)構(gòu)。 ( 2)應(yīng)用基本運算，設(shè)計算法求解。7、 投票選舉問題【問題描述】 在一次投票選舉中，要從 n 個候選人中選出 1 個優(yōu)勝者。

19、每個候選人有一張選票，只能 投給一位候選者，超過半數(shù)選票的候選人為優(yōu)勝者。用一個長度為 n 的選舉向量 v 表示收集 到的 n 張選票。投票選舉問題要求根據(jù)選舉向量 v 計算選舉產(chǎn)生的優(yōu)勝者?！驹O(shè)計要求】 設(shè)計算法實現(xiàn)投票選舉問題的程序。（1）采用 STL 的向量等數(shù)據(jù)結(jié)構(gòu)。 （2）應(yīng)用基本運算，設(shè)計算法求解。-5-8、學(xué)生成績條形圖統(tǒng)計問題 【問題描述】 條形圖問題描述：給定 n 個數(shù)據(jù)，繪出表示這 n 個數(shù)據(jù)的條形統(tǒng)計圖。即統(tǒng)計出這 n 個 數(shù)據(jù)中有多少個不同的值， 以及每個值出現(xiàn)的頻率是多少。 條形圖常用于表示數(shù)據(jù)分布情況。 例如，學(xué)生考試成績統(tǒng)計、居民收入分布情況等。假設(shè)輸入數(shù)據(jù)為正整

20、數(shù)，利用二叉排序樹 完成輸入數(shù)據(jù)頻率統(tǒng)計?！驹O(shè)計要求】 設(shè)計基于二叉排序樹的學(xué)生成績條形圖統(tǒng)計程序。（1）采用 STL 的二叉排序樹等數(shù)據(jù)結(jié)構(gòu)。 （2）應(yīng)用基本運算，設(shè)計算法求解。9、紅黑平衡二叉樹及其應(yīng)用 【問題描述】 一棵紅黑樹本身就是一棵二叉排序樹。紅黑樹中的結(jié)點顏色是黑色或紅色。從紅黑樹的 根結(jié)點到葉子結(jié)點的路徑上的黑色結(jié)點數(shù)目相同，最短的路徑就是所有結(jié)點都是黑色。根據(jù) 紅黑樹的性質(zhì)，紅黑樹在平衡類二叉排序樹中有許多應(yīng)用?！驹O(shè)計要求】 設(shè)計紅黑平衡二叉樹實現(xiàn)動態(tài)查找表及其應(yīng)用。（1）采用 STL 紅黑平衡二叉樹數(shù)據(jù)結(jié)構(gòu)。 （2）應(yīng)用基本運算，實現(xiàn)紅黑樹的簡單應(yīng)用。10、動態(tài)選擇求第 k

21、 小元素問題 【問題描述】集合中的元素是動態(tài)構(gòu)成的。要求對集合中的n 個元素求解第 k 小的元素。【設(shè)計要求】設(shè)計應(yīng)用紅黑平衡二叉樹實現(xiàn)動態(tài)查找第 k 小的元素。（1） 實現(xiàn)動態(tài)查找表的三種基本功能：查找、插入、刪除。（2） 應(yīng)用基本運算，設(shè)計算法求解。11、 基于緊縮圖的鄰接表的拓?fù)渑判騿栴} 【問題描述】 緊縮鄰接表將圖的每個頂點的鄰接表緊湊的存儲在兩個向量 list 和 h 中。其中向量 list依次存儲頂點 0, 1,，n-1 的鄰接頂點。向量單元 hi存儲頂點 i 的鄰接表在向量 list 中的 起始位置。【設(shè)計要求】 設(shè)計基于緊縮圖的鄰接表的拓?fù)渑判虺绦?。?） 采用 STL 的圖、緊縮鄰接表、棧等數(shù)據(jù)結(jié)構(gòu)。（2） 應(yīng)用基本運算，設(shè)計算法求解。12、 教務(wù)排課表的二分圖問題 【問題描述】 如果一個無向圖的頂點集合可以分為兩個互不相交的子集，并且圖中每條邊的兩個頂點都屬于兩個不同的頂點集。則稱該圖為一個二分圖?？梢杂靡粋€二分圖表示教師與課程的排 課關(guān)系