南信大數(shù)據(jù)結構課程設計要求和評分標準

1、南京信息工程大學課程設計形式期末考試要求和評分標準2018-2019 學年第 1 學期課程名稱：數(shù)據(jù)結構課程設計1、系統(tǒng)選題質(zhì)量所占分值 20。（每位同學根據(jù)學號最后一位選擇對應的附后的課程設計題目，如學號為 20178303001 的同學可以在題號 1、11、21、31、41 中選擇，學號為 20171398010 的同學可以在題號 10、20、30、40 中選擇）2、數(shù)據(jù)結構定義和實現(xiàn)所占分值 15。3、代碼質(zhì)量所占分值 20。4、界面風格所占分值 20。5、抄襲和回答問題所占分值 25。凡是有抄襲資料的，要扣分；嚴重抄襲的，比如直接拿別人的代碼或者從網(wǎng)上直接下載的代碼而沒有消化吸收并修改

2、的，給予不及格。任課教師:備注：本表作為不以試卷考試形式進行期末考試的課程使用。附：數(shù)據(jù)結構課程設計題目1.排序算法的性能分析問題描述設計一個測試程序，比較幾種內(nèi)部排序算法的關鍵字比較次數(shù)和移動次數(shù)以取得直觀感受。基本要求(1)對冒泡排序、直接排序、選擇排序、箱子排序、堆排序、快速排序及歸并排序算法進行比較。(2)待排序表的表長不小于 100,表中數(shù)據(jù)隨機產(chǎn)生，至少用 5 組不同數(shù)據(jù)作比較，比較指標：關鍵字參加比較次數(shù)和關鍵字的移動次數(shù)(關鍵字交換記為 3 次移動)。(3)輸出比較結果。選做內(nèi)容(1)對不同表長進行比較。(2)驗證各算法的穩(wěn)定性。(3)輸出界面的優(yōu)化。2 .排序算法思想的可視化

3、演示一1基本要求排序數(shù)據(jù)隨機產(chǎn)生，針對隨機案例，對冒泡排序、箱子排序、堆排序、歸并算法，提供排序執(zhí)行過程的動態(tài)圖形演示。3 .排序算法思想的可視化演示一2基本要求排序數(shù)據(jù)隨機產(chǎn)生，針對隨機案例，對插入排序、選擇排序、基數(shù)排序、快速排序算法，提供排序執(zhí)行過程的動態(tài)圖形演示。4 .線性表的實現(xiàn)與分析基本要求設計并實現(xiàn)線性表。線性表分別采取數(shù)組(公式化描述)、單鏈表、雙向鏈表、間接尋址存儲方式針對隨機產(chǎn)生的線性表實例，實現(xiàn)線性表的插入、刪除、搜索操作動態(tài)演示(圖形演示)。5 .等價類實現(xiàn)及其應用問題描述：某工廠有一臺機器能夠執(zhí)行 n 個任務，任務 i 的釋放時間為 m(是一個整數(shù))最后期限為 di(

4、也是整數(shù))。在該機上完成每個任務都需要一個單元的時間。一種可行的調(diào)度方案是為每個任務分配相應的時間段，使得任務 i 的時間段正好位于釋放時間和最后期限之間。一個時間段不允許分配給多個任務?；疽螅菏褂玫葍r類實現(xiàn)以上機器調(diào)度問題。等價類分別采取兩種數(shù)據(jù)結構實現(xiàn)。6 .一元稀疏多項式計算器問題描述設計一個一元稀疏多項式簡單計算器?；疽笠辉∈瓒囗検胶唵斡嬎闫鞯幕竟δ苁牵?1)輸入并建立多項式；(2)輸出多項式，輸出形式為整數(shù)序列：n,Ci,ei,C2,02,Cn,en,其中 n 是多項式的項數(shù)，G,九分別是第 i 項的系數(shù)和指數(shù)，序列按指數(shù)降序排序；(3)多項式 a 和 b 相加，建立多項

5、式 a+b;(4)多項式 a 和 b 相減，建立多項式 a-b;(5)計算多項式在 x 處的值；(6)計算器的仿真界面(選做)7 .長整數(shù)的代數(shù)計算問題描述應用線性數(shù)據(jù)結構解決長整數(shù)的計算問題。設計數(shù)據(jù)結構完成長整數(shù)的表示和存儲，并編寫算法來實現(xiàn)兩長整數(shù)的加、減、乘、除等基本代數(shù)運算。基本要求1長整數(shù)長度在一百位以上。2實現(xiàn)兩長整數(shù)在取余操作下的加、減、乘、除操作，即實現(xiàn)算法來求解 a+bmodn,a-bmodn,abmodn,abmodn。輸入輸出均在文件中。4分析算法的時空復雜性。8 .敢死隊問題。有 M 個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪個戰(zhàn)士去執(zhí)

6、行任務。如果前一個戰(zhàn)士沒完成任務，則要再派一個戰(zhàn)士上去?，F(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當數(shù)到 5 時，對應的戰(zhàn)士就去執(zhí)行任務，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務，再從下一個戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第 5 時，此戰(zhàn)士接著去執(zhí)行任務。以此類推，直到任務完成為止。排長是不愿意去的，假設排長為 1 號，請你設計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務。要求：至少采用兩種不同的數(shù)據(jù)結構的方法實現(xiàn)。9 .簡單計算器基本要求：輸入：不含變量的數(shù)學表達式的中綴形式，可以接受的操作符包括+、-、*、/、騎口(、)。輸出：如果表達式正確，則

7、輸出表達式的結果，如果表達式非法，則輸出錯誤信息。同時輸出堆棧的狀態(tài)變化過程。注：輸入/輸出形式可采取終端設備輸入/輸出，也可采用文件輸入/輸出，一個文件中可包含多個表達式10 .迷宮問題-1問題描述以一個 m*n 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙。 設計一個程序， 對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。基本要求(1)實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路一三元組(i,j,d)的形式輸出，其中：(i,j)指示迷宮中的一個坐標，d 表示走到下一坐標的方向。(2)編寫遞歸形式的算法，求得迷宮中所有可能的

8、通路；(3)以方陣形式輸出迷宮及其通路(4)輸出堆棧的變化過程及探測的過程11 .迷宮問題-2程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處。要求：(1)老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動；(2)迷宮的墻足夠結實，老鼠不能穿墻而過；(3)正確檢測結果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，否則提示失??；(4)添加編輯迷宮功能，可修改當前迷宮，修改內(nèi)容：墻變路、路變墻；(5)找出走出迷宮的所有路徑，以及最短路徑；利用序列化功能實現(xiàn)迷宮地圖文件的存盤和讀出等功能。12 .應用等價類生成隨機迷宮弁

9、尋找迷宮路徑問題描述：使用等價類來構造一個 NMN 的從左上角到右下角只有一條路徑的隨機迷宮，然后在這一迷宮上尋找迷宮路徑。該設計共包含如下四個部分：等價類數(shù)據(jù)結構的設計和實現(xiàn)構建隨機迷宮尋找迷宮路徑將迷宮和路徑用圖形方式畫出用圖形方式將上述算法獲得的隨機迷宮及其上的最短路徑畫出。用線段來表示迷宮中的墻，用在每個方格中心的點來表示路徑。13、跳表（SkipList）的實現(xiàn)與分析基本要求4構造并實現(xiàn)跳表（SkipList）的 ADTADT 中應包括初始化、查找、插入、刪除等基本操作。5分析各基本操作的時間復雜性。6針對一個實例實現(xiàn) SkipList 的動態(tài)演示（圖形演示）。14 .LZW壓縮算法

10、及應用基本要求1在一個文本文件上實現(xiàn) LZW 壓縮和解壓縮，其中每個字符就是該文本的 8 位 ASCII 碼。2在實現(xiàn) LZW 過程中需要仔細考慮如何在編譯表中找到匹配或找不到匹配，需要注意匹配算法的時間、空間開銷。（選彳）應用 LZW 算法實現(xiàn) 256 色灰度 BMP 圖像文件的壓縮和解壓縮。15 .二叉樹的實現(xiàn)及分析基本要求（1）設計實現(xiàn)鏈表存儲的二叉樹 ADT（2）實現(xiàn)基本操作實現(xiàn)過程（前序遍歷、中序遍歷、后序遍歷、層序遍歷等）的動態(tài)演示（圖形演示）。（3）應用二叉樹，實現(xiàn)信號放大器的設置。16 .應用堆實現(xiàn)一個優(yōu)先隊列并實現(xiàn)作業(yè)的優(yōu)先調(diào)度問題描述優(yōu)先隊列 priorityqueupri

11、orityqueu 曜一種可以用于很多場合的數(shù)據(jù)結構，應用堆結構設計并實現(xiàn)一個優(yōu)先隊列。應用該優(yōu)先隊列實現(xiàn)作業(yè)的優(yōu)先調(diào)度：一個作業(yè) ti=（s,e）,si 為作業(yè)的開始時間（進入時間），e 為作業(yè)的結束時間（離開時間）。作業(yè)調(diào)度的基本任務是從當前在系統(tǒng)中的作業(yè)中選取一個來執(zhí)行，如果沒有作業(yè)則執(zhí)行 nop 操作。本題目要求的作業(yè)調(diào)度是基于優(yōu)先級的調(diào)度，每次選取優(yōu)先級最高的作業(yè)來調(diào)度，優(yōu)先級用優(yōu)先數(shù)（每個作業(yè)一個優(yōu)先數(shù) pi）表征，優(yōu)先數(shù)越小，優(yōu)先級越高。作業(yè) ti進入系統(tǒng)時，即 si時刻，系統(tǒng)給該作業(yè)指定其初始優(yōu)先數(shù) pi=ei-si,從而使越短的作業(yè)優(yōu)先級越高。該優(yōu)先數(shù)在作業(yè)等待調(diào)度執(zhí)行的過程

12、中會不斷減小，調(diào)整公式為：pi=pi-Wi,其中的 Wi為作業(yè) ti的等待時間：Wi=當前時間-si。一旦作業(yè)被調(diào)度，該作業(yè)就一直執(zhí)行，不能被搶占，只有當前執(zhí)行作業(yè)指向完成時，才產(chǎn)生下一輪調(diào)度。所以可以在每次調(diào)度前動態(tài)調(diào)整各作業(yè)的優(yōu)先數(shù)。編程實現(xiàn)這樣一個作業(yè)調(diào)度系統(tǒng)?；疽笠远呀Y構實現(xiàn)優(yōu)先隊列。作業(yè)集合中的各作業(yè)隨機生成，根據(jù)作業(yè)的 s屬性和 e 屬性動態(tài)調(diào)整作業(yè)隊列，不斷加入作業(yè)，作業(yè)結束刪除作業(yè)。要對作業(yè)調(diào)度的結果給出清晰的輸出信息， 包括： 何時作業(yè)進入， 何時調(diào)度哪個作業(yè)， 何時離開，每個作業(yè)等待多長時間，優(yōu)先數(shù)的動態(tài)變化情況等。17 .哈夫曼編/譯碼器問題描述利用哈夫曼編碼進行信息

13、通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼；在接收端將傳來的數(shù)據(jù)進行譯碼(復原)。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編譯碼系統(tǒng)?；疽笠粋€完整的系統(tǒng)應具有以下功能：(1)1:初始化(Initialization)。從終端讀入字符集大小 n 及 n 個字符和 m 個權值，建立哈夫曼樹，并將它存于文件 hfmtree 中。(2) C:編碼(Coding)。利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件 hfmtree 中讀入)，對文件 tobetran

14、s 中的正文進行編碼，然后將結果存入文件 codefile 中。(3) D：解碼(Decoding)。利用已建好的哈夫曼樹將文件 codefile 中的代碼進行譯碼，結果存入文件 texfile 中。(4) P:打印代碼文件(Print)。將文件 codefile 以緊湊格式顯示在終端上，每行 50 個代碼。同時，將此字符形式的編碼文件寫入文件 codeprint 中。(5) T:打印哈夫曼樹(Treeprinting)o將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件 treeprint 中。18.AVL樹的實現(xiàn)及分析基本要求1編寫 AVL

15、 樹判別程序，并判別一個二叉搜索樹是否為 AVL 樹。二叉搜索樹用其先序遍歷結果表示，如：5,2,1,3,7,8。2實現(xiàn) AVL 樹，其上的基本操作包括：Search,Insert,Delete,和 Ascend;3實現(xiàn)基本操作的動態(tài)演示(圖形演示)。擴展：a.實現(xiàn)帶索引的 AVL 搜索樹，實現(xiàn)其上的基本操作：Search,Insert,Delete,IndexSearch,IndexDelete 和 Ascend。前 5 種函數(shù)的時間復雜性應為 O(logn),最后一種函數(shù)的時間復雜性應為 O(n)。b.搜索樹中有一些元素的關鍵值相同。19 .直方圖問題問題描述：在直方圖問題中，從一個具有

16、n 個關鍵值的集合開始，要求輸出不同關鍵值的列表以及每個關鍵值在集合中出現(xiàn)的次數(shù)(頻率)。下圖給出了一個含有 10 個關鍵值的例子。圖 a 給出了直方圖的輸入，直方圖的表格形式如圖 b 所示，直方圖的圖形形式如圖 c 所示。直方圖一般用來確定數(shù)據(jù)的分布，例如，考試的分數(shù)、圖象中的灰色比例、在生產(chǎn)商注冊的汽車和居住在洛杉磯的人所獲得的最高學位都可以用直方圖來表示。n=10;關能值=2.4,2,2,3.4,2t&4,2基本要求：分別使用三種結構(數(shù)組、鏈表散列、二叉搜索樹)，寫出求解直方圖問題的程序，通過圖形顯示運行時間的比較。20 .箱子裝載問題問題描述：在箱子裝載問題中，有若干個容量為

17、 c 的箱子和 n 個待裝載入箱子中的物品。物品 i 需占 si個單元(0siwc)。所謂成功裝載(feasiblepacking),是指能把所有物品都裝入箱子而不溢出，而最優(yōu)裝載(optimalpacking)則是指使用了最少箱子的成功裝載?；疽螅褐辽俳o出求解箱子裝載問題的三種方案，并進行性能比較。21 .B-樹的實現(xiàn)及分析基本要求1實現(xiàn)在 B-樹上的查找，并分析其時間復雜性。2實現(xiàn) B-樹的 ADT,包括其上的基本操作：結點的加入和刪除。要求 B-樹結構中的 M=3 或 5,實現(xiàn)其中的一種即可。4實現(xiàn)基本操作的動態(tài)演示(圖形演示)。22 .圖的實現(xiàn)與分析-1問題描述分別對有向圖、無向圖

18、、帶權有向圖、帶權無向圖實現(xiàn)對圖的基本操作(創(chuàng)建、求頂點的度數(shù)、增加/刪除邊、判斷邊是否存在、DFS、BFS、判斷是否連通、連通構件的標識，求生成樹等)?；疽髨D使用鄰接矩陣存儲。提供隨機案例，對任意隨機案例，實現(xiàn) DFS 和 BFS 實現(xiàn)過程的動態(tài)演示（圖形演示）。對 DFS 提供遞歸與非遞歸兩種方法的實現(xiàn)，并通過輸出進行性能比較。23 .圖的實現(xiàn)與分析-2問題描述分別對有向圖、無向圖、帶權有向圖、帶權無向圖實現(xiàn)對圖的基本操作（創(chuàng)建、求頂點的度數(shù)、增加/刪除邊、判斷邊是否存在、DFS、BFS、判斷是否連通、連通構件的標識，求生成樹等）?；疽髨D使用鄰接鏈表存儲。提供隨機案例，對任意隨機案

19、例，實現(xiàn) DFS 和 BFS 實現(xiàn)過程的動態(tài)演示（圖形演示）。對 DFS 提供遞歸與非遞歸兩種方法的實現(xiàn)，并通過輸出進行性能比較。24 .校園導游3、用無向網(wǎng)表示校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題?；疽螅?查詢?nèi)我饩包c的相關信息；2查詢圖中任意兩個景點間的最短路徑。3查詢圖中任意兩個景點間的所有路徑。增加、刪除、更新有關景點和道路的信息。（選作）*求多個景點的最佳（最短）游覽路徑。25 .全國交通咨詢模擬問題描述處于不同目的的旅客對交通工具有不同的要求。例如，因公出差

20、的旅客希望在旅途中的時間盡可能地短，出門旅游的旅客則期望旅費盡可能省，而老年旅客則要求中轉次數(shù)最少。編織一個全國城市間的交通資訊程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。設計要求（1）提供對城市信息進行編輯（如添加或刪除）的功能。（2）城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班進行編輯（增設或刪除）的功能。（3）提供兩種最優(yōu)決策：最快到達和最省錢到達。全程只考慮一種交通工具。（4）旅途中耗費的總時間應該包括中轉站的等候時間。（5）咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具。輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能

21、到達，并詳細說明依次于何時乘坐哪一趟列車或那一次班機到何地。實現(xiàn)提示（1）對全國城市交通圖和列車時刻表及飛機航班表進行編輯，應該提供文件形式輸入和鍵盤輸入兩種方式。飛機航班表的信息應包括：起始站的出發(fā)時間、終點站的到達時間和票價；列車時刻表則需根據(jù)交通圖給出各個路段的詳細信息，例如：對從北京到上海的火車，需給出北京至天津、天津至徐州及徐州至上海各段的出發(fā)時間、到達時間及票價等信息。（2）以鄰接表座交通圖的存儲結構，表示邊的結構內(nèi)除含有鄰接點的信息外，還應包括交通工具、路程中耗費的時間和花費以及出發(fā)和到達的時間等多種屬性。（3）增加旅途中轉次數(shù)最少的最優(yōu)決策。26 .公交線路上優(yōu)化路徑的查詢問題

22、描述最短路徑問題是圖論中的一個經(jīng)典問題，其中的 Dijkstra 算法一直被認為是圖論中的好算法，但有的時候需要適當?shù)恼{(diào)整 Dijkstra 算法才能完成多種不同的優(yōu)化路徑的查詢。對于某城市的公交線路，乘坐公交的顧客希望在這樣的線路上實現(xiàn)各種優(yōu)化路徑的查詢。設該城市的公交線路的輸入格式為：線路編號：起始站名（該站坐標）；經(jīng)過的站點 1 名（該站坐標）；經(jīng)過的站點 2 名（該站坐標）；經(jīng)過的站點 n 名（該站坐標）；終點站名（該站坐標）。該線路的乘坐價錢。該線路平均經(jīng)過多少時間來一輛。車速。例如：63:A（32,45）;B（76,45）;C（76,90）;；N（100,100）。1 元。的鐘。1

23、/每分鐘。假定線路的乘坐價錢與乘坐站數(shù)無關，假定不考慮公交線路在路上的交通堵塞。對這樣的公交線路，需要在其上進行的優(yōu)化路徑查詢包括：任何兩個站點之間最便宜的路徑；任何兩個站點之間最省時間的路徑等等?；疽?根據(jù)上述公交線路的輸入格式，定義并建立合適的圖模型。2針對上述公交線路，能查詢獲得任何兩個站點之間最便宜的路徑，即輸入站名 S,T 后，可以輸出從 S 到 T 的最便宜的路徑，輸出格式為：線路 x：站名 S,，站名 M1;換乘線路 x：站名 M1,，站名M2;；換乘線路 x：站名 MK,，站名 To 共花費 x 元。針對上述公交線路，能查詢獲得任何兩個站點之間最省時間的路徑（不考慮在中間站

24、等下一輛線路的等待時間），即輸入站名 S,T 后，可以輸出從 S 到 T 的考慮在中間站等下一輛線路的等待時間的最省時間的路徑，輸出格式為：線路 x：站名 S,，站名 M1;換乘線路 x：站名 M1,，站名 M2;；換乘線路 x：站名 MK,，站名 To 共花費 x 時間。針對上述公交線路，能查詢獲得任何兩個站點之間最省時間的路徑（要考慮在中間站等下一輛線路的等待時間），即輸入站名 S,T 后，可以輸出從 S 到 T 的考慮在中間站等下一輛線路的等待時間的最省時間的路徑，輸出格式為：線路 x：站名 S,，站名 M1;換乘線路 x：站名 M1,，站名 M2;；換乘線路 x：站名 MK,，站名 T

25、o 共花費 x 時間。（4）實現(xiàn)提不需深入考慮，應根據(jù)不同的應用目標，即不同的優(yōu)化查詢來建立合適的圖模型。27 .多叉路口交通燈的管理問題通常，在十字交叉路口只需設紅、綠兩色的交通燈便可保持正常的交通秩序，而在多叉路口需設幾種顏色的交通燈才能既使車輛相互之間不碰撞，又能達到車輛的最大流通。假設有一個如圖（a）所示的五叉路口，其中 C 和 E 為單行道。在路口有 13 條可行的通路，其中有的可以同時通行，如AfB 和 EfC,而有的不能同時通行，如 EfB 和 A-D。那么，在路口應如何設置交通燈進行車輛的管理呢？AM28 .文檔集合上的查詢（i）問題描述設計數(shù)據(jù)結構完成在一個文檔集合的存儲，并

26、構造算法實現(xiàn)其內(nèi)容的查詢。該設計包括三個部分：（一）應用數(shù)據(jù)結構完成文檔集合的內(nèi)容（基于單詞的）存儲，并為下一步的查詢建立索引。（二）就單個單詞的查詢請求，設計算法進行查詢。（三）對多個單詞通過 AN 于口 OR 勾造的復雜查 tU 進行處理（此處可只做兩個單詞的情況）。具體情形如下面的例子：ExampleExampleDoci:Iliketheclassondatastructuresandalgorithms.Doc2:Ihatetheclassondatastructuresandalgorithms.Doc3:Interestingstatisticaldatamayresultfro

27、mthissurvey.Herearetheanswerstosomequeries:Query1:dataDoc1,Doc2,Doc3Query2:dataANDstructuresDoc1,Doc2Query3:likeORsurveyDoc1,Doc3文檔集合上的查詢實例基本要求文檔集合中的文檔數(shù)不能少于 20 個。數(shù)據(jù)結構的設計以及查找算法的構造應考慮如何最大程度的提高查詢效率。查詢效率的提高應是綜合多種查詢的，而不是只針對一種查詢的優(yōu)化。給出查詢效率的模擬實驗數(shù)據(jù)。實現(xiàn)提示AND 和 OR 查詢可轉變?yōu)閱蝹€單詞查詢結果的組合。29 .教學計劃編制問題問題描述大學的每個專業(yè)都要制訂教學

28、計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。基本要求(1)輸入?yún)?shù)包括：學期總數(shù)，一學期的學分上限，每門課的課程號(固定占 3 位的字母數(shù)字串)、學分和直接先修課的課程號。(2)允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是是課程盡可能地集中在前幾個學期中。(3)若根據(jù)給定的條件問題無解，則報告適當?shù)男畔?；否則，將教學計劃輸出到用戶指定的文件中。計劃的表格格式自行設計。30 .最小生成樹一Prim

29、算法設計實現(xiàn)無向網(wǎng)結構，針對隨機無向網(wǎng)實例和隨機起點,有的最小生成樹，并給出求解過程的動態(tài)圖形演示?？煽紤]實現(xiàn)不同存儲結構上的實現(xiàn)。31 .最小生成樹一Kruskal算法設計實現(xiàn)無向網(wǎng)結構，針對隨機無向網(wǎng)實例和隨機起點，用 Kruskal 算法的基本思想求解出所有的最小生成樹，并給出求解過程的動態(tài)圖形演示?？煽紤]實現(xiàn)不同存儲結構上的實現(xiàn)。32 .最短路徑一Dijkstra算法設計實現(xiàn)有向網(wǎng)結構，針對隨機有向網(wǎng)實例和隨機源點，用 Dijkstra 算法求解出單源點到其他各頂點的最短路徑，給出求解過程的動態(tài)演示?？煽紤]實現(xiàn)不同存儲結構上的實現(xiàn)。33 .拓撲排序對給定的 AOV 網(wǎng)，產(chǎn)生所有的拓撲序

30、列，給出求解過程的動態(tài)演示。34 .成績分析問題問題描述錄入、保存一個班級學生多門課程的成績，并對成績進行分析?；疽?1)通過鍵盤輸入個學生的多門課程的成績，建立相應的文件 input.dat。(2)對文件 input.dat 中的數(shù)據(jù)進行處理，要求具有以下功能：用 PRIM 算法的基本思想求解出所1)按各門課程成績排序，并生成相應的文件輸出。2）計算每人的平均成績，按平均成績排序，并生成文件。3）求出各門課程的平均成績、最高分、最低分、不及格人數(shù)、6069 分人數(shù)、7079 分人數(shù)、8089 分人數(shù)、90 分以上人數(shù)。4）根據(jù)姓名或學號查詢某人的各門課成績，重名情況也能處理（3）界面美觀

31、35 .檢查網(wǎng)絡給定一個計算機網(wǎng)絡以及機器間的雙向連線列表，每一條連線與允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。要求實現(xiàn)功能：任意指定兩臺計算機，判斷它們之間是否可以進行文件傳輸？判斷整個網(wǎng)絡中是否任意兩臺機器間都可以文件傳輸？若不可以，請給出當前網(wǎng)絡中連通分量的個數(shù)及各個連通分量中的機器。增加兩臺計算機之間的連線?；疽螅褐辽偈褂脙煞N結構實現(xiàn)。36 .調(diào)度問題（1）機器調(diào)度現(xiàn)有 n n 件任務和無限多臺的機器，任務可以在機器上得到處理。每件任務的開始時間為 s si,完成時間為 f fi,s sif fi。s si,f fi為處理任務

32、i i 的時間范圍。兩個任務 i,j j 重疊是指兩個任務的時間范圍區(qū)間有重疊，而并非是指 i i, ,j j 的起點或終點重合。每臺機器在任何時刻最多只處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方案。要求：輸入任務個數(shù)及每個任務的名稱，開始時間，完成時間給出最優(yōu)分配方案。（2 2）任務調(diào)度現(xiàn)在有 n 項作業(yè)，Ji,J2,Jn,要求按順序執(zhí)行，已知各作業(yè)對應的運行所需時間分別為tl,t2,tn,要求這些作業(yè)在一個處理器上運行，并且要求完成這 n 個作業(yè)的平均完成時間最小。注：每個作業(yè)的完成時間等于作業(yè)的等待時間與它的執(zhí)行時間的和，這里假設一旦開始運行一個作業(yè)，那么在該作業(yè)完成之前，其他

33、作業(yè)都只能等待。要求：輸入作業(yè)個數(shù)及每個作業(yè)的名稱，執(zhí)行時間給出最優(yōu)調(diào)度方案。37 .學校超市選址問題（帶權有向圖的中心點）?；疽螅簩τ谀骋粚W校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。38 .設計散列表實現(xiàn)電話號碼查找系統(tǒng)基本要求：(1)設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；(2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表;(3)查找并顯示給定電話號碼的記錄；(4)查找并顯示給定用戶名的記錄。(5)嘗試不同類型處理沖突的方法，考察平均查找長度的變化。一班有 m 個女生，有 n 個男生(m 不等于 n),現(xiàn)要

34、開一個舞會。男女生分別編號坐在舞池的兩邊的椅子上。每曲開始時，依次從男生和女生中各出一人配對跳舞，本曲沒成功配對者坐著等待下一曲找舞伴。請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程，要求如下：(1)輸出每曲配對情況；(2)計算出任何一個男生(編號為 X)和任意女生(編號為 Y),在第 K 曲配對跳舞的情況。至少求出 K 的兩個值；(3)盡量設計出多種算法及程序。提示：用隊列來解決比較方便。40.掃雷游戲實現(xiàn)一個 N*M 的掃雷游戲。41馬的遍歷問題：設計程序完成如下要求：在中國象棋盤上，對任意位置上放置一個馬，均能選擇一個合適的路線，使得該棋子能夠按照象棋的規(guī)則不重復的走過棋盤上的每一位置。要求：(1)依次輸出走過的各位置的坐標(2)最好能畫出棋盤的圖形形式，并在其上動態(tài)的標注行走過程(3)程序能方便的移植到其他規(guī)格的棋盤上。42.在 8X8 的國際象棋棋盤上，如果放置若干個馬后，使得整