數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目及說明201420151

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計序號題 目說 明第一組1-1一元多項式乘法1) 問題描述已知A(x)=a0+a1x+a2x2+anxn和B(x)=b0+b1x+b2x2+bmxm，并且在A(x)和B(x)中指數(shù)相差很多，求A(x)=A(x)*B(x)。2) 基本要求(1)設(shè)計存儲結(jié)構(gòu)表示一元多項式；(2)設(shè)計算法實現(xiàn)一元多項式乘法；(3)分析算法的時間復雜度和空間復雜度。1-2迷你計算器功能要求：（1）計算任意一個算術(shù)表達式的加法、減法、除法以及乘法。（2）運算數(shù)為整數(shù)和小數(shù)（3）人機界面自定義，要友好。如用戶輸入錯誤在計算之前可以修改。1-3排序算法演示系統(tǒng)1）問題描述設(shè)計一個測試程序比較幾種內(nèi)部排序算法的

2、關(guān)鍵字比較次數(shù)和移動次數(shù)以取得直觀感受。2）基本要求(1)實現(xiàn)各種內(nèi)部排序。包括冒泡排序，直接選擇排序，希爾排序，快速排序，堆排序。(2) 待排序的元素的關(guān)鍵字為整數(shù)。其中的數(shù)據(jù)要用隨機數(shù)產(chǎn)生(如10000個)，至少用5組不同的數(shù)據(jù)做比較，再使用各種算法對其進行排序，記錄其排序時間，再匯總比較。(3) 演示程序以人機對話的形式進行。每次測試完畢顯示各種比較指標值的列表，比較各種排序的優(yōu)劣。(4) 界面友好，易與操作。采用菜單方式進行選擇。1-4通訊錄管理1）問題描述編寫一個簡單的通訊錄管理程序。通訊錄記錄有姓名、地址、電話號碼、電子郵箱等4項。2）基本要求程序應(yīng)提供的基本管理功能如下：（1）添

3、加：增加一個人的記錄到通訊錄中；（2）顯示：在屏幕上顯示所以通訊錄中的人員信息，應(yīng)能分屏顯示；（3）存儲：將通訊錄信息保存在一個文件中；（4）裝入：即將文件中的信息讀入程序；（5）查詢：可根據(jù)姓名查找某人的相關(guān)信息，若找到顯示其姓名、地址、電話號碼、電子郵箱；（6）修改：可修改一個人的除姓名之外的其他信息；3）測試數(shù)據(jù)程序應(yīng)輸入不少于10個人員的通訊錄信息，應(yīng)考慮到人員可以同名的情況。1-5圖書管理系統(tǒng)功能要求：（1）界面友好，易于操作。可采用菜單或其它人機對話方式進行選擇。(2) 每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量； (3) 對書號建立索引表（線性表）以提高查找效率；(4

4、) 系統(tǒng)主要功能如下： *采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量1-6多項式運算功能要求：（1）輸入并建立多項式；（2）輸出多項式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,cn,en,其中n是多項式的 項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；（3）多項式a和b相加，建立多項式a+b；輸出相加的多項式（4）多項式a和b相減，建立多項式a-b。輸出相加的多項式（5）用帶表頭結(jié)點的單鏈表存儲

5、多項式。1-7公園主要游覽景點之間最短距離問題問題描述：圖的最短路徑問題是指從指定的某一點v開始，求得從該地點到圖中其它各地點的最短路徑。并且給出求得的最短路徑的長度及途徑的地點。除了完成最短路徑的求解外，還能對該圖進行修改，如頂點以及邊的增刪、邊上權(quán)值的修改等。公園最短路徑問題中的數(shù)據(jù)元素有：（1）頂點數(shù)（2）邊數(shù)（3）邊的長度功能需求：要求完成以下功能：(1) 輸出頂點信息：將公園內(nèi)各景點輸出。（2）輸出邊的信息：將公園內(nèi)每兩個位置（若兩個位置之間有直接路徑）的距離輸出。(3) 修改：修改兩個位置（若兩個位置之間有直接路徑）的距離，并重新輸出每兩個位置（若兩個位置之間有直接路徑）的距離；(

6、4) 求最短路徑：輸出給定兩點之間的最短路徑的長度及途經(jīng)的地點，輸出任意一點與其他各點的最短路徑。（5）刪除：刪除任意一條邊。（6）插入：插入任意一條邊。1-8最少換車次數(shù)問題1)問題描述：設(shè)某城市有n個車站，并有m條公交線路連接這些車站。設(shè)這些公交車站都是單向的，這n個車站被順序編號為0n-1。編程序，輸入該城市的公交線路數(shù)，車站個數(shù)，以及各公交線路上的各站編號。2)基本要求：求得從站0出發(fā)乘公交車至站n-1的最少換車次數(shù)。3)設(shè)計思路：利用輸入信息構(gòu)建一張有向圖G（鄰接矩陣存儲），有向圖的頂點表示車站，若某條公交線路經(jīng)i站能到達j站，就在圖G中存在一條有向邊<i,j>，權(quán)值為1

7、。因此，從站x至站y的最少上車次數(shù)對應(yīng)于圖G中從頂點x到頂點y的最短路徑長度。第2組2-1文章編輯1)問題描述輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。2) 基本要求靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"

8、、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"（3）輸出刪除某一字符串后的文章；2-2哈希表設(shè)計1)問題描述針對某個集體中人名設(shè)計一個哈希表，使得平均查找長度不超過R，并完成相應(yīng)的建表和查表程序。2)基本要求假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。3)測試數(shù)據(jù)取讀者周圍較熟悉的30個人名。4)選作內(nèi)容（1）從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計幾個不同的哈希函數(shù)，比較他們的地址沖突率（可以用更大的名字集合作

9、實驗）。（2）研究這30個人名的特點，努力找一個哈希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。（3）在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希表中關(guān)鍵字的聚集性。2-3二叉排序樹的遍歷1)問題描述輸入樹的各個結(jié)點，建立二叉排序樹，對建立的二叉排序樹進行層次、先序、中序和后序遍歷并統(tǒng)計該二叉樹中葉子結(jié)點的數(shù)目。 2)基本要求 (1)用菜單實現(xiàn) (2)輸入樹的各個結(jié)點，建立二叉排序樹，并能夠輸出用不同方法遍歷的遍歷序列和葉子結(jié)點的數(shù)目。2-4個人帳簿管理系統(tǒng)設(shè)計1)問題描述個人帳簿管理系統(tǒng)記錄某人每月的全部收入及各項開支情況，包括食品消費，房租，子女教

10、育費用，水電費，醫(yī)療費，儲蓄等。進入系統(tǒng)后可以輸入和修改某月的收支情況，可以對每月的開支從小到大進行排序，可以根據(jù)輸入的月份查詢每月的收支情況。2) 基本要求（1）初步完成總體設(shè)計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；（2）完成最低要求：建立一個文件，包括某人5個月的收支情況，能對文件中的信息進行擴充（追加），修改和刪除；（3）進一步要求：完成對每月的開支排序，以及完成系統(tǒng)查詢功能。有興趣的同學可以自己擴充系統(tǒng)功能。2-5學分管理程序1) 問題描述請設(shè)計一個學生的學分管理程序。假設(shè)每位學生必須完成基礎(chǔ)課50學分、專業(yè)課50學分、選修課24學分、人文類課程8學分、實驗性課程20學分才能夠

11、畢業(yè)。因此在管理學分時，要考慮每個學分所屬于的課程類別。學分信息應(yīng)該包括學號、姓名、課程類別、學分等。2) 基本要求該程序應(yīng)該具有下列功能：(1) 通過鍵盤輸入多個學生的學分，存入數(shù)據(jù)文件中； (2) 給定學號，顯示某位學生的學分完成情況；(3) 給定某個班級的班號，顯示該班所有學生學分完成情況；(4) 給定某位學生的學號，修改該學生的學分信息；(5) 按照某類課程的學分高低進行排序；(6) 提供一些統(tǒng)計各類信息的功能。2-6學生作業(yè)完成情況管理程序1)問題描述請設(shè)計一個學生作業(yè)完成情況管理程序。假設(shè)某門課程一學期要留10次作業(yè)，每次老師要進行批改，給出分數(shù)后還要進行登記。學期期末要根據(jù)每次作

12、業(yè)的成績計算出最終的平時成績（滿分100）。作業(yè)登記信息應(yīng)該包含：學號、姓名、10次作業(yè)的完成情況。2) 基本要求該程序應(yīng)該具有下列功能：(1) 通過鍵盤輸入某位學生某次作業(yè)的分數(shù)；(2) 給定學號，顯示某位學生作業(yè)完成情況；(3) 給定某個班級的班號，顯示該班所有學生的作業(yè)完成情況；(4) 給定某位學生的學號，修改該學生的作業(yè)完成信息；(5) 給定某位學生的學號，刪除該學生的信息；(6) 按學生的最終平時成績進行排序；(7) 輸出平均分數(shù)。（8）用數(shù)據(jù)文件保存作業(yè)登記信息。2-7學生籍貫管理系統(tǒng)1)問題描述編制一個學生籍貫信息記錄簿，每個學生信息包括：學號、姓名、籍貫、通信地址。2) 基本要

13、求該程序應(yīng)該具有下列功能：（1）輸入學生信息并以磁盤文件保存；（2）讀取磁盤文件并顯示輸出所有學生的籍貫信息；（3）按學號或姓名查詢其籍貫；（4）按籍貫查詢并輸出該籍貫的所有學生；（5）能添加、刪除和修改學生的籍貫信息；（6）顯示輸出天津籍和非天津籍學生的信息并可分別存盤；（7） 按學號進行排序。2-8通信錄管理系統(tǒng)1)問題描述設(shè)計出模擬手機通信錄管理系統(tǒng)，實現(xiàn)對手機中的通信錄進行管理。2) 基本要求功能要求：（1）查看功能：選擇此功能時，列出下列三類選擇。A 工作類 B 家庭類 C 朋友類 ，當選中某類時，顯示出此類所有數(shù)據(jù)中的姓名和電話號碼）（2）增加功能：能錄入新數(shù)據(jù)（一個結(jié)點包括：姓名

14、、電話號碼、分類（可選項有：A 工作類 B 家庭類 C 朋友類）、家庭住址）。例如 楊春商務(wù)類 南開區(qū)當錄入了重復的姓名和電話號碼時，則提示數(shù)據(jù)錄入重復并取消錄入；當通信錄中超過10條信息時，存儲空間已滿，不能再錄入新數(shù)據(jù)；錄入的新數(shù)據(jù)能按遞增的順序自動進行條目編號。（3）修改功能：選中某個人的姓名時，可對此人的相應(yīng)數(shù)據(jù)進行修改（4） 刪除功能：選中某個人的姓名時，可對此人的相應(yīng)數(shù)據(jù)進行刪除，并自動調(diào)整后續(xù)條目的編號。第3組3-1串的查找和替換1） 問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。2） 基本要求編寫字符串的模式匹配程序，

15、實現(xiàn)字符串的查找替換功能3-2迷宮問題1)問題描述迷宮求解是實驗心理學中的一個經(jīng)典問題，心理學家把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮，迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。2) 基本要求(1) 設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲迷宮；(2) 設(shè)計存儲結(jié)構(gòu)保存從入口到出口的通路；(3) 設(shè)計算法完成迷宮問題的求解；(4) 分析算法的時間復雜度。3-3TSP問題（回溯法求解）1) 問題描述所謂TSP問題是指旅行家要旅行n個城市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員

16、問題，是圖問題中最廣為人知的問題。2) 基本要求(1) 上網(wǎng)查找TSP問題的應(yīng)用實例；(2) 分析求TSP問題的全局最優(yōu)解的時間復雜度；(3) 設(shè)計一個求近似解的算法；(4) 分析算法的時間復雜度。3-4醫(yī)院選址問題1)問題描述n個村莊之間的交通圖可以用有向網(wǎng)圖來表示，圖中邊<vi, vj>上的權(quán)值表示從村莊i到村莊j的道路長度?，F(xiàn)在要從這n個村莊中選擇一個村莊新建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使所有的村莊離醫(yī)院都比較近？2) 基本要求(1) 建立模型，設(shè)計存儲結(jié)構(gòu)；(2) 設(shè)計算法完成問題求解；(3) 分析算法的時間復雜度。3-5機器調(diào)度問題1)問題描述機器調(diào)度是指有m

17、臺機器需要處理n個作業(yè)，設(shè)作業(yè)i的處理時間為ti，則對n個作業(yè)進行機器分配，使得：(1) 一臺機器在同一時間內(nèi)只能處理一個作業(yè)；(2) 一個作業(yè)不能同時在兩臺機器上處理；(3) 作業(yè)i一旦運行，則需要ti個連續(xù)時間單位。設(shè)計算法進行合理調(diào)度，使得在m臺機器上處理n個作業(yè)所需要的處理時間最短。2) 基本要求(1) 建立問題模型，設(shè)計數(shù)據(jù)結(jié)構(gòu)；(2) 設(shè)計調(diào)度算法，為每個作業(yè)分配一臺可用機器；(3) 給出分配方案。3-6個人電話號碼查詢系統(tǒng)1) 問題描述人們在日常生活中經(jīng)常需要查找某個人或某個單位的電話號碼，本實驗將實現(xiàn)一個簡單的個人電話號碼查詢系統(tǒng)，根據(jù)用戶輸入的信息（例如姓名等）進行快速查詢。

18、2) 基本要求(1)使用文件保存電話號碼信息；(2)設(shè)計數(shù)據(jù)結(jié)構(gòu)存儲電話號碼信息；(3) 提供查詢功能：根據(jù)姓名實現(xiàn)快速查詢；(4) 提供其他維護功能：例如插入、刪除、修改等；(5) 按電話號碼進行排序。3-7數(shù)制轉(zhuǎn)換任意給定一個M進制的數(shù)x ，請實現(xiàn)如下要求1)求出此數(shù)x的10進制值（用MD表示）2)實現(xiàn)對x向任意的一個非M進制的數(shù)的轉(zhuǎn)換。3)至少用兩種或兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。3-8學生搭配1) 問題描述一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會. 男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞,

19、 本曲沒成功配對者坐著等待下一曲找舞伴。2) 基本要求請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下:(1)輸出每曲配對情況(2)計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個值(3)盡量設(shè)計出多種算法及程序,可視情況適當加分 提示:用隊列來解決比較方便.第4組4-1庫存管理系統(tǒng)的目的是實現(xiàn)貨物的入庫和出庫，以及存儲情況1、 系統(tǒng)管理員可以實現(xiàn)貨物的入庫和出庫管理一般用戶可以查詢貨物的出庫個數(shù)和存儲個數(shù)，和貨物的信息（比如產(chǎn)地、生產(chǎn)日期等）4-2公交線路調(diào)配管理系統(tǒng)系統(tǒng)的目的可以實現(xiàn)對公交車輛的統(tǒng)一管理，以及實時監(jiān)控各公交線路的情況。1、 可以查

20、詢每條線路的出車情況2、 根據(jù)線路的回執(zhí)，可以根據(jù)具體情況，增加車輛3、 車輛故障處理4 車輛定期維修4-3超市商品管理系統(tǒng) 系統(tǒng)目的是可以實現(xiàn)對商品信息的查詢，以及商品的入庫和出庫管理。系統(tǒng)管理員可以實現(xiàn)商品的入庫和出庫管理一般用戶可以查詢商品的售出和存儲個數(shù)，和商品的信息（比如價格、產(chǎn)地、生產(chǎn)日期等）4-4考試系統(tǒng) 要求能識別考生，自動隨機抽取試題，考試時間到自動交卷，交卷時自動評分。教師能根據(jù)教學內(nèi)容生成或維護試題庫，能了解學生學生的考試情況。該考試系統(tǒng)只限單選題、多選題和判斷題，它由二個子系統(tǒng)組成：1、報名系統(tǒng)：（1）考生信息錄入。（2）準考證號生成。（3）考生信息查詢與維護。2、考試

21、系統(tǒng)：考生只需輸入準考證，與登錄考生信息相符即可開始考試，否則拒絕登錄，考試開始時將自動抽取試題，考試時間到自動交卷，交卷時自動評分。3、數(shù)據(jù)管理：將報名表中的考生信息導入登錄表。4、查詢與統(tǒng)計：查詢已考人員成績及統(tǒng)計人數(shù)。查詢零分人員及統(tǒng)計人數(shù)。查詢未考人員及統(tǒng)計人數(shù)。交卷后可查詢本考試各題的用戶答案與正確答案（注意不同用戶的權(quán)限）4-5人事工資管理系統(tǒng) 要求對某單位的人事和工資進行管理。1數(shù)據(jù)管理：職工信息錄入、數(shù)據(jù)更新-包括人員調(diào)動、職稱、工資和退休等2查詢：查個人信息、部門信息、職稱情況、入伍時間、工資情況、是否在職等3統(tǒng)計：各部門人數(shù)、各類職稱人數(shù)、統(tǒng)計各類工資總和、科研成果統(tǒng)計等4

22、工資管理5.生成報表：生成各類統(tǒng)計報表、生成每月工資表、生成各類統(tǒng)計報表4-6人口信息管理系統(tǒng) 要求對某一城市的人口情況進行管理1、 常住人口管理（登記、刪除、遷入、移出）外來暫住人口管理（登記、信息管理）4-7稀疏矩陣的加法運算輸入任意兩個系數(shù)矩陣A和B，求出它們的和矩陣C。要求：1、輸入兩個稀疏矩陣的行數(shù)、列數(shù)以及非零元素，創(chuàng)建稀疏矩陣；2、實現(xiàn)兩個系數(shù)矩陣的加法運算；3、輸出系數(shù)矩陣；4、要求分別使用三元組表和十字鏈表兩種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。4-8大整數(shù)計算器實現(xiàn)大整數(shù)（200位以內(nèi)的整數(shù)）的加、減、乘、除運算。說明：由于整型數(shù)據(jù)存儲位數(shù)的有限，因此引入串的概念，將整型數(shù)據(jù)用字符串進行存儲，利

23、用字符串的一個字符存儲大整數(shù)的一位數(shù)值，然后根據(jù)四則運算規(guī)則，對相應(yīng)位依次進行相應(yīng)運算，同時保存進位，從而實現(xiàn)大整數(shù)的精確運算。第5組5-1電力收費綜合管理系統(tǒng) 要求可以對個用戶進行電力收費管理1、用電指數(shù)查詢及收費2、欠費用戶管理3、電力故障報警5-2安徽省內(nèi)汽運公路交通系統(tǒng)系統(tǒng)目的是實現(xiàn)通用查詢，主要功能：1、系統(tǒng)管理員管理汽車基本信息。一般用戶：只具有查詢權(quán)限，不具有系統(tǒng)管理權(quán)限。2、可搜索從起始站到終點站（用戶輸入站名拼音或漢字）的所有汽車，向用戶發(fā)布相關(guān)信息（車次、發(fā)車和到站時間、里程、票價）。3、可根據(jù)給出的區(qū)間（用戶輸入）查詢出車次的基本信息（包括發(fā)車時間，剩余票數(shù)，到站時間、票價等）。5-3多項式求導要求實現(xiàn)一元多項式求導運算，有效字符為變量x，數(shù)字0-9，運算符、+、-、*、/，輸入的多項式以#結(jié)尾。輸出結(jié)果也為多項式。例如：輸入：6x4-32x，輸出結(jié)果為：24x3-32。5-4馬踏棋盤所謂馬踏棋盤問題，是指將馬隨機放在國際象棋的8×8棋盤的某個方格中，馬按走棋規(guī)則（馬走日字）進行移動。要求每個