數據結構課程設計題目
《數據結構》方向選題
|
序号
|
數據結構（選題）
|
适用專業
|
題目類型
|
課題來源與性質
|
供題
教師
|
題目簡介與要求
|
|
1
|
PC機泡泡堂遊戲
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫一個應用程序實現泡泡堂遊戲，要求有遊戲菜單，選擇不同的菜單會出現不同的效果，遊戲方式為人與人之間的對戰，實現泡泡堂遊戲的所有規則，有不同的道具，不同的道具讓玩家有不同的增益或減益；遊戲勝利或失敗後能重新開始。
|
|
2
|
坦克大戰
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫應用程序實現坦克大戰遊戲，人機對戰，模拟紅白機上坦克大戰遊戲，一次出現四輛NPC坦克，有簡單的AI，能發射子彈攻擊，實現不同的道具，不同的道具有不責罵的增益或減益效果，實現不同的障礙，不同的障礙有不同的效果，比如水面，坦克不可通行，但子彈能通行；遊戲勝利過關，失敗結束退回遊戲菜單。
|
|
3
|
俄羅斯方塊
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫應用程序實現俄羅斯方塊遊戲，實現俄羅斯方塊遊戲所有的規則，實現下一個方塊的提示，實現過關後速度的增加，顯示得分，有遊戲界面。
|
|
4
|
貪吃蛇遊戲
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫應用程序實現貪吃蛇遊戲，實現蛇的移動，比如按蛇在往右過程中按左鍵操作不能有反應，食物的不同的種類，不同的食物會對蛇産生不同的效果，比如有一種食物能讓蛇臨時增加速度，實現關卡的切換，有随機的出現的障礙，會對蛇産生阻礙，有遊戲界面。
|
|
5
|
2D地圖編輯器
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫走格子類型遊戲的2D地圖編輯器，要求實現地圖編輯和地圖預覽，能實現數據的存儲和讀取，數據的任意修改。
|
|
6
|
約瑟夫生死遊戲
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
約瑟夫生死遊戲：30個人圍成一個圈由第一個人數起，依次報數，數到第九個人，便把他剔除，然後再從他的下一個人數起，數到第九個人，再将他剔除剩下15個乘客為止，問那些位置将是被扔下大海的位置。
|
|
7
|
彩票開獎問題
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
寫出6＋1彩票開獎的情況，當前6個号碼和特别号都對的時候，這個時候是特等獎。如果前面6個号碼都對的時候，中的是一等獎。在前面6個數字中連續的對了5個的時候，中的是二等獎。在前面6個數字中連續的對了4個的時候，中的是三等獎。請編寫程序，實現連續多個輸入，并在每次輸入以後顯示号碼中獎的情況。
|
|
8
|
日曆系統的設計
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫一程序實現對輸入的任一年份中所有月份日期對應星期計算的萬年日曆系統。1、輸入任一年将顯示出該年的所有月份日期，對應的星期；2、注意閏年情況；
|
|
9
|
八皇後遊戲
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
八皇後是個古老而有趣的遊戲，是由高斯于1850年首先提出的。要求在國際象棋的棋盤上放置八個皇後，使其不能相互攻擊，即任意兩個皇後不能處于棋盤的同一行、同一列和同一條對角線上。試問有多少種放法？
|
|
10
|
比較同學的年齡
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
編寫類student，其中包含生日（年、月、日）的私有變量，要求能比較兩位學生的年齡差距（精确到多少天），用重載“－”運算符實現年齡差的計算。
|
|
11
|
比我疆土
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
四位分别來自中國、美國、俄羅斯、加拿大的小學生都以自己的國土面積大而驕傲不已，但是他們想知道到底誰的國土最大，誰的最小，他們的判斷如下：加拿大學生：加拿大最大，美國最小，俄羅斯第三。美國學生：美國最大，加拿大最小，俄羅斯第二，中國第三。中國學生：美國最小，加拿大第三。他們互不相讓，最後老師下定結論：對于上述四國面積的判斷，他們每人隻判斷對了一個國家。對于老師的提示，四位小學生還是絞盡腦汁推斷不出到底是誰的國土最大，誰的最小！現請編制程序告訴四位小學生正确順序。
|
|
12
|
漢諾塔遊戲
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
傳說婆羅門廟裡有一個塔台，台上有3根标号為A,B,C的用鑽石做成的柱子，在A柱子上放着64個金盤，每一個都比下面的略小一些。把A柱子上的金盤子全部移到C柱上的那一天就是世界末日。移到的條件是：一次隻能移到一個金盤，移到過程中大金盤不能放在小金盤上面。廟裡的僧人一直在移個不停。因為全部的移動是264－1次，如果每秒移動一次的話需要500億年。
|
|
13
|
文本文件複制
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
将一個文本文件複制到另一個文件中（要求用兩種方法實現：一個一個字符複制及按行進行複制）。
|
|
14
|
石頭剪刀布遊戲
|
計算機及相關專業
|
設計
|
生産/社會實際模拟題
|
鄒飚/王志高
|
編寫一個小遊戲實現石頭，剪刀，布的遊戲規則，人機對戰，能輸入遊戲次數，能統計玩家和電腦的總比分，最終判斷玩家勝利還是電腦勝利。
|
|
15
|
深度尋路算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求根據當前的不同地圖情況，采用深度遍曆的方法尋找出一條可通行的路徑。
|
|
16
|
廣度尋路算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求根據當前的不同地圖情況，采用廣度遍曆的方法尋找出一條可通行的路徑。
|
|
17
|
A*尋路算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求根據當前的不同地圖情況，采用智能型尋路算法（A*）尋找出一條可通行的路徑。
|
|
18
|
泡泡堂遊戲泡泡爆算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求根據當前地圖上泡泡的釋放情況，實現地圖上所有泡泡在某一時刻的爆炸狀态，已方便NPC完成自動尋路過程。
|
|
19
|
泡泡龍遊戲的消除算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求根據當前遊戲地圖中泡泡的存在情況，實時檢測當前可能消除的泡泡，要求應用遞歸算法完成。
|
|
20
|
飛機遊戲中的跟蹤導彈算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求以數據的形式，完成對豎版飛機遊戲中的跟蹤導彈算法。
|
|
21
|
飛機遊戲中的旋轉保護罩算法
|
計算機及相關專業
|
設計
|
人工智能模拟題
|
鄒飚/王志高
|
要求以數據的形式，完成對豎版飛機遊戲中的旋轉保護罩算法。
|
1. 運動會分數統計
任務：參加運動會有n個學校，學校編号為1……n。比賽分成m個男子項目，和w個女子項目。項目編号為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分别為：7、5、3、2、1，前三名的積分分别為：5、3、2；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20,）
功能要求：
1) 可以輸入各個項目的前三名或前五名的成績；
2) 能統計各學校總分，
3) 可以按學校編号或名稱、學校總分、男女團體總分排序輸出；
4) 可以按學校編号查詢學校某個項目的情況；可以按項目編号查詢取得前三或前五名的學校。
5) 數據存入文件并能随時查詢
6) 規定：輸入數據形式和範圍：可以輸入學校的名稱，運動項目的名稱
輸出形式：有中文提示，各學校分數為整形
界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。
存儲結構：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。（數據文件的數據讀寫方法等相關内容在c語言程序設計的書上，請自學解決）請在最後的上交資料中指明你用到的存儲結構；
測試數據：要求使用1、全部合法數據；2、整體非法數據；3、局部非法數據。進行程序測試，以保證程序的穩定。測試數據及測試結果請在上交的資料中寫明；
2. 飛機訂票系統
任務：通過此系統可以實現如下功能：
錄入：
可以錄入航班情況（數據可以存儲在一個數據文件中，數據結構、具體數據自定）
查詢：
可以查詢某個航線的情況（如，輸入航班号，查詢起降時間，起飛抵達城市，航班票價，票價折扣，确定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；
訂票：（訂票情況可以存在一個數據文件中，結構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班；
退票：可退票，退票後修改相關數據文件；
客戶資料有姓名，證件号，訂票數量及航班情況，訂單要有編号。
修改航班信息：當航班信息改變可以修改航班數據文件
要求：
根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；
3. 文章編輯
功能：輸入一頁文字，程序可以統計出文字、數字、空格的個數。
靜态存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分别統計出其中英文字母數和空格數及整篇文章總字數；（2）統計某一字符串在文章中出現的次數，并輸出該次數；（3）删除某一子串，并将後面的字符前移。
存儲結構使用線性表，分别用幾個子函數實現相應的功能；
輸入數據的形式和範圍：可以輸入大寫、小寫的英文字母、任何數字及标點符号。
輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數"、"數字個數"、"空格個數"、"文章總字數"（3）輸出删除某一字符串後的文章；
4. 紙牌遊戲
任務：編号為1-52張牌，正面向上，從第2張開始，以2為基數，是2的倍數的牌翻一次，直到最後一張牌；然後，從第3張開始，以3為基數，是3的倍數的牌翻一次，直到最後一張牌；然後…從第4張開始，以4為基數，是4的倍數的牌翻一次，直到最後一張牌；...再依次5的倍數的牌翻一次，6的，7的直到以52為基數的翻過，輸出：這時正面向上的牌有哪些？
5. 宿舍管理查詢軟件
1) 任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求：
A. 采用交互工作方式
B. 建立數據文件，數據文件按關鍵字（姓名、學号、房号）進行排序(冒泡、選擇、插入排序等任選一種)
2) 查詢菜單: (用二分查找實現以下操作)
A. 按姓名查詢
B. 按學号查詢
C. 按房号查詢
3) 打印任一查詢結果（可以連續操作）
6. 地圖着色問題
設計要求：已知中國地圖，對各省進行着色，要求相鄰省所使用的顔色不同，并保證使用的顔色總數最少（4種）。
要求：
1、地圖數據的輸入采取從文件中讀取。
2、結果輸出方式可以采用圖形方式或者文本方式。
7. 校園導航問題
設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。
1、 基本要求：
1） 設計校園平面圖，在校園景點選10個左右景點。以圖中頂點表示校園内各景點，存放景點名稱、代号、簡介等信息；以邊表示路徑，存放路徑長度等有關信息。
2） 為來訪客人提供圖中任意景點相關信息的查詢。
3） 為來訪客人提供任意景點的問路查詢，即查詢任意兩個景點之間的一條最短路徑。
2、 實現提示：一般情況下，校園的道路是雙向通行的，可設計校園平面圖是一個無向網。頂點和邊均含有相關信息。
8、建立二叉樹，層序、先序、中序、後序遍曆（分别用遞歸和非遞歸的方法實現）
任務：能按一定方式（鍵盤、文件）輸入樹的各個結點，并能輸出用不同方法遍曆的遍曆序列；
要求：提供良好的菜單操作界面（可以是文本模式或圖形模式）
9、赫夫曼樹的建立
任務：按給定的數據建立赫夫曼樹
要求：可以建立函數輸入二叉樹，并輸出其赫夫曼樹。在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數據和結果。提供良好的菜單操作界面
10、紙牌遊戲
任務：編号為1-52張牌，正面向上，從第2張開始，以2為基數，是2的倍數的牌翻一次，直到最後一張牌；然後，從第3張開始，以3為基數，是3的倍數的牌翻一次，直到最後一張牌；然後…從第4張開始，以4為基數，是4的倍數的牌翻一次，直到最後一張牌；...再依次5的倍數的牌翻一次，6的，7的，直到以52為基數的翻過，輸出：這時正面向上的牌有哪些？
要求：提供良好的菜單操作界面
11、圖的建立及輸出
任務：建立圖的存儲結構（圖的類型可以是有向圖、無向圖），輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而後輸出圖的鄰接矩陣。（提高部分：以圖形模式輸出實際圖形）
要求：提供良好的菜單操作界面。
12、實現兩個鍊表的合并
基本功能要求：
（1） 建立兩個鍊表A和B，鍊表元素個數分别為m和n個。
（2） 假設元素分别為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個線形表C，使得：
當m>=n時，C=x1,y1,x2,y2,…xn,yn,…,xm
當n>m時，C=y1,x1,y2,x2,…ym,xm,…,yn
輸出線形表C
（3） 用直接插入排序法對C進行升序排序，生成鍊表D，并輸出鍊表D。
測試數據：
（1） A表（30，41，15，12，56，80）
B表（23，56，78，23，12，33，79，90，55）
（2） A表（30，41，15，12，56，80，23，12，34）
B表（23，56，78，23，12）
13、超大整數加法與乘法運算器設計。
任務：實現兩個超大整數（成千上萬位數的大整數）的加法和乘法運算，并能精确的按位輸出。
要求：采用合理的存儲結構，盡量節省存儲空間。
14、超大整數減法與除法運算器設計。
任務：實現兩個超大整數（成千上萬位數的大整數）的減法和除法運算，并能精确的按位輸出。（除不盡時輸出整數商和餘數）
要求：采用合理的存儲結構，盡量節省存儲空間。
15、超大整數進制轉換器設計。
任務：将10進制的超大整數（成千上萬位數的大整數）轉換為其他任意進制的數，并能精确的按位輸出。
要求：采用合理的存儲結構，盡量節省存儲空間。
16. 最小生成樹問題
設計要求：在n個城市之間建設網絡，隻需保證連通即可，求最經濟的架設方法。存儲結構采用多種。求解算法多種。
17. 通訊錄的制作
模塊要求：
第一個模塊——主函數main()的功能是：根據選單的選項調用各函數，并完成相應的功能。
第二個模塊——Menu()的功能是：顯示英文提示選單。
第三個模塊——Quit()的功能是：退出選單。
第四個模塊——Create()的功能是：創建新的通訊錄。
第五個模塊——Add()的功能是：在通訊錄的末尾，寫入新的信息，并返回選單。
第六個模塊——Find()的功能是：查詢某人的信息，如果找到了，則顯示該人的信息，如果未找到，則提示通訊錄中沒有此人的信息，并返回選單。
第七個模塊——Alter()的功能是：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。
第八個模塊——Delete()的功能是：删除某人的信息，如果未找到要删除的人，則提示通訊錄中沒有此人的信息，并返回選單。
第九個模塊——List()的功能是：顯示通訊錄中的所有記錄。;
設計要求：
1) 每條信息至包含：姓名（NAME ）、性别(GENDER)、電話（TEL）、城市（CITY）郵編（EIP）幾項。
2) 作為一個完整的系統，應具有友好的界面和較強的容錯能力
18. 哈夫曼編碼/譯碼器
[問題描述]
利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端将傳來的數據進行譯碼（複原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼編/譯碼系統。
[基本要求]
一個完整的系統應具有以下功能：
（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并将它存于文件hfmTree中。
（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在内存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行編碼，然後将結果存入文件CodeFile中。
（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹将文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。
（4）P：印代碼文件（Print）。将文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時将此字符形式的編碼寫入文件CodePrint中。
（5）T：印哈夫曼樹（Tree Printing）。将已在内存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時将此字符形式的哈夫曼樹寫入文件TreePrint中。
[測試數據]
（1）數據一：已知某系統在通信聯絡中隻可能出現8種字符，其概率分别為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此設計哈夫曼編碼。利用此數據對程序進行調試。
（2）用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。
|
字符
|
[空格]
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
J
|
K
|
L
|
M
|
|
頻度
|
186
|
64
|
13
|
22
|
32
|
103
|
21
|
15
|
47
|
57
|
1
|
5
|
32
|
20
|
|
字符
|
N
|
O
|
P
|
Q
|
R
|
S
|
T
|
U
|
V
|
W
|
X
|
Y
|
Z
|
|
|
頻度
|
57
|
63
|
15
|
1
|
48
|
51
|
80
|
23
|
8
|
18
|
1
|
16
|
1
|
|
[實現提示]
（1）文件CodeFile的基類型可以設為子界型bit = 0..1。
（2）用戶界面可以設計為“菜單”方式：顯示上述功能符号，再加上“Q”，表示運行Quit。請用戶鍵入一個先把功能符，些功能執行完畢後再經菜單，直至某次用戶先把了“E”為止。
（3）在程序的一次執行過程中，第一次執行I、D或C命令之後，哈夫曼樹已經在内存了，不必再讀入。每次執行中不一定執行I命令，因為文件hfmTree可能早已建好。
19. 圖書管理系統
【問題描述】
設計一個計算機管理系統完成圖書管理基本業務。
【基本要求】
1) 每種書的登記内容包括書号、書名、著作者、現存量和庫存量；
2) 對書号建立索引表（線性表）以提高查找效率；
3) 系統主要功能如下：
*采編入庫：新購一種書，确定書号後，登記到圖書帳目表中，如果表中已有，則隻将庫存量增加；
*借閱：如果一種書的現存量大于0，則借出一本，登記借閱者的書證号和歸還期限，改變現存量；
*歸還：注銷對借閱者的登記，改變該書的現存量。
【進一步完成内容】
1) 系統功能的進一步完善；
2) 索引表采用樹表。
3) 設計内容
4) 程序流程圖
5) 源程序
6) 軟件測試報告（包括所用到的數據及結果）
20. 散列表的設計與實現
【問題描述】
設計散列表實現電話号碼查找系統。
【基本要求】
1) 設每個記錄有下列數據項：電話号碼、用戶名、地址；
2) 從鍵盤輸入各記錄，分别以電話号碼和用戶名為關鍵字建立散列表；
3) 采用一定的方法解決沖突；
4) 查找并顯示給定電話号碼的記錄；
5) 查找并顯示給定用戶名的記錄。
【進一步完成内容】
1) 系統功能的完善；
2) 設計不同的散列函數，比較沖突率；
3) 在散列函數确定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。
21. 走迷宮遊戲
程序開始運行時顯示一個迷宮地圖，迷宮中央有一隻老鼠，迷宮的右下方有一個糧倉。遊戲的任務是使用鍵盤上的方向鍵操縱老鼠在規定的時間内走到糧倉處。
要求：
1) 老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動；
2) 迷宮的牆足夠結實，老鼠不能穿牆而過；
3) 正确檢測結果，若老鼠在規定時間内走到糧倉處，提示成功，否則提示失敗；
4) 添加編輯迷宮功能，可修改當前迷宮，修改内容：牆變路、路變牆；
5) 找出走出迷宮的所有路徑，以及最短路徑。
利用序列化功能實現迷宮地圖文件的存盤和讀出等功能
22.一元多項式的運算。（限1 人完成）
設有一元多項式Am(x)和Bn(x).
Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm
Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn
請實現求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。
要求：
1) 首先判定多項式是否稀疏
2) 分别采用順序和動态存儲結構實現；
3) 結果M(x)中無重複階項和無零系數項；
4) 要求輸出結果的升幂和降幂兩種排列情況
23. 學生選修課程系統設計
假定有n門課程，每門課程有課程編号，課程名稱，課程性質，總學時，授課學時，實驗或上機學時，學分，開課學期等信息，學生可按要求（如總學分不得少于60）自由選課。試設計一選修課程系統，使之能提供以下功能：
課程信息錄入功能(課程信息用文件保存)
課程信息浏覽功能
查詢功能：(至少一種查詢方式)
按學分查詢
按課程性質查詢
學生選修課程
24. 中心對稱字符串問題
(1)問題描述
有n個字符的字符串，用c或c++語言編寫程序判斷該字符串是否中心對稱。例如，abbccdccbba與abba都是中心對稱的字符串。
（2）要求
采用單鍊表數據結構或棧數據結構的方法實現上述問題的求解。如果采用兩種或兩種以上數據結構實現者，可加分。
25、利用棧求表達式的值
(1)問題描述
用c或c++語言編寫程序實現表達式求值，即驗證某算術表達式的正确性，若正确，則計算該算術表達式的值。表達式從鍵盤輸入後，按以下方法對該表達式中成份逐個進行分析：
（a）若是數字，則判斷該數字的合法性。若合法，則壓入數據到堆棧中。
（b）若是規定的運算符，則根據規則進行處理。在處理過程中，将計算該表達式的值。
（c）若是其它字符，則返回錯誤信息。
若上述處理過程中沒有發現錯誤，則認為該表達式合法，并打印處理結果。
(2)要求
（a)用棧數據結構實現，且程序中應主要編寫如下幾個功能函數：
void initstack()：初始化堆棧。
int Make_str()：語法檢查并計算。
int push_operate(int operate)：将操作碼壓入堆棧。
int push_num(double num)：将操作數壓入堆棧。
int procede(int operate)：處理操作碼。
int change_opnd(int operate)：将字符型操作碼轉換成優先級。
int push_opnd(int operate)：将操作碼壓入堆棧。
int pop_opnd()：将操作碼彈出堆棧。
int caculate(int cur_opnd)：簡單計算+，-，*，/。
double pop_num()：彈出操作數。
（b)如果采用兩種或兩種以上數據結構實現者，可加分。
26、簡易文本編輯器
(1)問題描述
用c或c++語言編寫一個具有簡單的文字或圖形菜單界面的文本編輯器。
（2）要求
（a) 具有簡單的文字或圖形菜單界面。
（b)能實現串或文本塊的查找、替換、插入、移動、删除操作。
（c)能實現文本文件的存盤和讀取功能。
（d)如果采用兩種或兩種以上數據結構實現者，可加分。
27、二叉樹操作
（1）問題描述
用c或c++語言編寫程序實現二叉樹的創建，以及中序、前序、後序遍曆的遞歸算法與非遞歸算法。
（2）要求
（a) 創建的二叉樹以樹形結構顯示出來，結點需帶上序号和數據值兩項。
（b) 遍曆的方法可以選擇，遍曆的結果應顯示結點序号和數據值。
（c)如果采用兩種或兩種以上數據結構實現者，可加分。
28、舞伴問題
（1）問題描述
假設一個班有m個女生,有n個男生(m不等于n),現要開一個舞會。男女生分别編号坐在舞池的兩邊的椅子上，每曲開始時,依次從男生和女生中各出一人配對跳舞，本曲沒成功配對者坐着等待下一曲找舞伴。用c或c++語言編寫程序模拟動态地顯示出上述過程。
（2）要求
（a)輸出每曲男女配對情況。
（b)計算出任何一個男生(編号為X)和任意女生(編号為Y),在第K曲配對跳舞的情況,至少求出K的兩個值。
(c)采用隊列數據結構或其他數據結構實現上述問題的求解。如果采用兩種或兩種以上數據結構實現者，可加分。
29、敢死隊問題
(1)問題描述
有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數數的辦法來決定哪個戰士去執行任務。如果前一個戰士沒完成任務，則要再派一個戰士上去。現給每個戰士編一個号，大家圍坐成一圈，随便從某一個戰士開始計數，當數到5時，對應的戰士就去執行任務，且此戰士不再參加下一輪計數。如果此戰士沒完成任務，再從下一個戰士開始數數，被數到第5時，此戰士接着去執行任務。以此類推，直到任務完成為止。
排長是不願意去的，假設排長為1号，用c或c++語言編寫程序，求出從第幾号戰士開始計數才能讓排長最後一個留下來而不去執行任務。
（2)要求
采用數組數據結構、鍊數據結構或遞歸的方法實現上述問題的求解。如果采用兩種或兩種以上數據結構實現者，可加分。
30、猴子吃桃子問題
(1)問題描述
有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就隻餘下一個桃子。用c或c++語言編寫程序實現求出原來這群猴子共摘了多少個桃子。
（3）要求
采用數組數據結構或鍊數據結構或遞歸的方法實現上述問題的求解。如果采用兩種或兩種以上數據結構實現者，可加分。
31、數制轉換問題
(1)問題描述
用c或c++語言編寫程序，實現從鍵盤任意輸入一個M進制（2、8、10、16）的數，對其轉換為其他三種進制的功能。
（2）要求
（a)要轉換的數制可以選擇，轉換的結果以（轉換前為XXXX，轉換後為XXXX）的形式應顯示。若輸入的是2進制數，則通過選擇可将其轉換為8、10、16三種進制的數。
（b) 采用數組數據結構或棧數據結構或遞歸的方法實現上述問題的求解。如果采用兩種或兩種以上數據結構實現者，可加分。
32. 排序綜合
利用随機函數産生N個随機整數（20000以上），對這些數進行多種方法進行排序。
要求：
1) 至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序後的結果保存在不同的文件中。
2) 統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。
3) 如果采用4種或4種以上的方法者，可适當加分。
33. 學生成績管理系統
現有學生成績信息文件1（1.txt），内容如下
姓名 學号 語文 數學 英語
張明明 01 67 78 82
李成友 02 78 91 88
張輝燦 03 68 82 56
王露 04 56 45 77
陳東明 05 67 38 47
…. .. .. .. …
學生成績信息文件2（2.txt）,内容如下:
姓名 學号 語文 數學 英語
陳果 31 57 68 82
李華明 32 88 90 68
張明東 33 48 42 56
李明國 34 50 45 87
陳道亮 35 47 58 77
…. .. .. .. …
試編寫一管理系統,要求如下:
1) 實現對兩個文件數據進行合并,生成新文件3.txt
2) 抽取出三科成績中有補考的學生并保存在一個新文件4.txt
3) 對合并後的文件3.txt中的數據按總分降序排序(至少采用兩種排序方法實現)
4) 輸入一個學生姓名後,能查找到此學生的信息并輸出結果(至少采用兩種查找方法實現)
5) 要求至少使用結構體實現上述要求,若增加其他實現方式更好.
6) 采用多種方法且算法正确者,可适當加分.
34. 圖的遍曆和生成樹求解實現
要求：
1) 先任意創建一個圖；
2) 圖的DFS,BFS的遞歸和非遞歸算法的實現
3) 最小生成樹（兩個算法）的實現，求連通分量的實現
4) 要求至少用鄰接矩陣結構存儲實現。若增加鄰接表、十字鍊表多種其他的存儲結構實現更好
5) 采用多種方法且算法正确者,可适當加分.
35. 線索二叉樹的應用
要求：實現線索樹建立、插入、删除、恢複線索的實現。
36. 稀疏矩陣實現與應用
要求：實現三元組，十字鍊表下的稀疏矩陣的加、轉置、乘的實現。
37. 樹的應用
要求：實現樹與二叉樹的轉換的實現。以及樹的前序、後序的遞歸、非遞歸算法，層次序的非遞歸算法的實現，應包含建樹的實現。
38.簡單的職工管理系統
1）問題描述
對單位的職工進行管理，包括插入、删除、查找、排序等功能。
2）.要求
職工對象包括姓名、性别、出生年月、工作年月、學曆、職務、住址、電話等信息。
（1）新增一名職工：将新增職工對象按姓名以字典方式職工管理文件中。
（2）删除一名職工：從職工管理文件中删除一名職工對象。
（3）查詢：從職工管理文件中查詢符合某些條件的職工。
（4）修改：檢索某個職工對象，對其某些屬性進行修改。
（5）排序：按某種需要對職工對象文件進行排序。
3）.實現提示
職工對象數不必很多，便于一次讀入内存，所有操作不經過内外存交換。
（1）由鍵盤輸入職工對象，以文件方式保存。程序執行時先将文件讀入内存。
（2）對職工對象中的"姓名"按字典順序進行排序。
（3）對排序後的職工對象進行增、删、查詢、修改、排序等操作。
4）選做内容
将職工對象按散列法存儲，并設計解決沖突的方法。在此基礎上實現增、删、查詢、修改、排序等操作。
39.鐵路運輸網火車站管理
1）問題背景描述
這是上海鐵路局目前仍在使用的行包托運軟件中的一部分内部算法。該題目采用1995年年底我國鐵路運輸網的真實數據進行編程和運行驗證。
鐵路運輸網絡中由鐵路線和火車站的兩個主要概念，譬如：1号鐵路線表示京廣線，2号鐵路線表示京滬線等。
鐵路線對象包括鐵路線編号,鐵路線名稱，起始站編号,終點站編号,該鐵路線長度，通行标志(00B客貨運禁行,01B貨運通行專線，10B客運通行專線，11B客貨運通行)。
火車站對象包括所屬鐵路線編号，車站代碼，車站名，車站簡稱，離該鐵路線起點站路程及終點站路程。
2）題目要求
寫一個火車站管理程序，添加、删除火車站，修改火車站的各項數據，按照車站名查詢火車站的各項數據。
40. 鐵路運輸網鐵路線管理
1）問題背景描述
這是上海鐵路局目前仍在使用的行包托運軟件中的一部分内部算法。該題目采用1995年年底我國鐵路運輸網的真實數據進行編程和運行驗證。
鐵路運輸網絡中由鐵路線和火車站的兩個主要概念，譬如：1号鐵路線表示京廣線，2号鐵路線表示京滬線等。
鐵路線對象包括鐵路線編号,鐵路線名稱，起始站編号,終點站編号,該鐵路線長度，通行标志(00B客貨運禁行,01B貨運通行專線，10B客運通行專線，11B客貨運通行)。
火車站對象包括所屬鐵路線編号，車站代碼，車站名，車站簡稱，離該鐵路線起點站路程及終點站路程。
2）題目要求
寫一個鐵路線管理程序，添加、删除鐵路線，修改鐵路線的各項數據，給鐵路線添加火車站，查詢鐵路線的各項數據。
41.旅遊交通線路問題
有一些城鎮和公路，由于沿途路況和其他因素的影響，每條旅行線路所需的旅行費用也不同，要求設計一種數據結構，能夠存儲各個城鎮之間的公路費用與長度（若存在的話），在此基礎上設計相關算法，使得用戶任意輸入起始城鎮名稱和終點城鎮名稱後，可以給出一條最便宜的線路以及總裡程最短的線路，并給出途徑的每一個城鎮和總共所需的費用和總長度。
42.某銀行營業廳共有6個營業窗口，設有排隊系統廣播叫号，該銀行的業務分為公積金、銀行卡、理财卡等三種。公積金業務指定1号窗口，銀行卡業務指定2、3、4号窗口，理财卡業務指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空閑時，理财卡業務也可以在空閑的2、3、4号窗口之一辦理。
客戶領号、業務完成可以作為輸入信息，要求可以随時顯示6個營業窗口的狀态。
43. 課程設置問題
某專業計劃進行課程設置調整，請專家确定要在m個學期中開設的n門課程，并給出每門課程的先修課程列表，專業負責人把這些數據交給你，并告訴你每個學期能開設的課程的數目。請問能否按照要求完成課程設置任務，如果可行，輸出一種排課計劃。
