數(shù)據(jù)結(jié)構(gòu)和算法課程設(shè)計(jì)題目

1、北方民族大學(xué)課程設(shè)課程名稱(chēng):數(shù)據(jù)結(jié)構(gòu)與算法院（部）名 稱(chēng)：信息與計(jì)算科學(xué)學(xué)院組長(zhǎng)姓名學(xué)號(hào)同組人員姓名指導(dǎo)教師姓名：紀(jì) 峰設(shè)計(jì)時(shí)間:201067-2009627一、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)參考題目（一）參考題目一（每位同學(xué)選作一個(gè)，同組人員不得重復(fù)）1編寫(xiě)函數(shù)實(shí)現(xiàn)順序表的建立、查找、插入、刪除運(yùn)算。2、編寫(xiě)函數(shù)分別實(shí)現(xiàn)單鏈表的建立、查找、插入、刪除、逆置算法。3、編寫(xiě)函數(shù)實(shí)現(xiàn)雙向鏈表的建立、插入、刪除算法。4、編寫(xiě)函數(shù)實(shí)現(xiàn)順序棧的進(jìn)棧、退棧、取棧頂?shù)乃惴ā?、編寫(xiě)函數(shù)實(shí)現(xiàn)鏈棧的進(jìn)棧、退棧、取棧頂?shù)乃惴ā?、編寫(xiě)函數(shù)實(shí)現(xiàn)雙向順序棧的判空、進(jìn)棧、出棧算法。7、編寫(xiě)函數(shù)實(shí)現(xiàn)循環(huán)隊(duì)列的判隊(duì)空、取隊(duì)頭元素、

2、入隊(duì)、出隊(duì)算法。8、編寫(xiě)函數(shù)實(shí)現(xiàn)鏈環(huán)隊(duì)列的判隊(duì)空、取隊(duì)頭節(jié)點(diǎn)、入隊(duì)、出隊(duì)算法。9、編寫(xiě)函數(shù)實(shí)現(xiàn)串的，求串長(zhǎng)、連接、求字串、插入、刪除等運(yùn)算。10、分別實(shí)現(xiàn)順序串和鏈串的模式匹配運(yùn)算。11、實(shí)現(xiàn)二叉樹(shù)的建立，前序遞歸遍歷和非遞歸遍歷算法。12、實(shí)現(xiàn)二叉樹(shù)的建立，中序遞歸遍歷和非遞歸遍歷算法。13、實(shí)現(xiàn)二叉樹(shù)的建立，后序遞歸遍歷和非遞歸遍歷算法。14、實(shí)現(xiàn)二叉樹(shù)的中序線(xiàn)索化，查找 *p 結(jié)點(diǎn)中序下的前驅(qū)和后繼結(jié)點(diǎn)。15、分別以臨接表和鄰接矩陣作為存儲(chǔ)就夠?qū)崿F(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索 算法。16、利用線(xiàn)性探測(cè)處理沖突的方法實(shí)現(xiàn)散列表的查找和插入算法。（二）參考題目二（每三人一組，任選三個(gè)題目完

3、成）1. 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)（限 1 人完成）任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)目， 和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1m，女子m+1m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2;哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,*=20）功能要求：1）可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī);2）能統(tǒng)計(jì)各學(xué)?？偡郑?）可以按學(xué)校編號(hào)或名稱(chēng)、學(xué)?？偡?、男女團(tuán)體總分排序輸出;4）可以按學(xué)校編號(hào)查詢(xún)學(xué)校某個(gè)項(xiàng)目的情況;可以按項(xiàng)目編號(hào)查詢(xún)?nèi)〉们叭蚯拔迕?的學(xué)校。5）數(shù)據(jù)存入文件并能隨時(shí)查詢(xún)6）規(guī)定：輸入數(shù)

4、據(jù)形式和范圍：可以輸入學(xué)校的名稱(chēng)，運(yùn)動(dòng)項(xiàng)目的名稱(chēng)輸出形式：有合理的提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān) 的功能要求。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù) 要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫(xiě)方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書(shū) 上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu); 測(cè)試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù); 2、整體非法數(shù)據(jù); 3、局部非法數(shù)據(jù)。進(jìn)行 程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫(xiě)明;2. 飛機(jī)訂票系統(tǒng) 任務(wù)：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 錄入： 可以錄入

5、航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自 定）查詢(xún)： 可以查詢(xún)某個(gè)航線(xiàn)的情況（如，輸入航班號(hào)，查詢(xún)起降時(shí)間，起飛抵達(dá)城市， 航班票價(jià)，票價(jià)折扣，確定航班是否滿(mǎn)倉(cāng)）；可以輸入起飛抵達(dá)城市，查詢(xún)飛機(jī)航班情況； 訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定） 可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班； 退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件； 客戶(hù)資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。 修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 要求： 根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；3. 文章編輯功能：輸入一頁(yè)文字

6、，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò) 80個(gè)字符，共N行；要求（1）分別統(tǒng)計(jì) 出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)； （ 2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn) 的次數(shù)，并輸出該次數(shù)； （ 3）刪除某一子串，并將后面的字符前移。存儲(chǔ)結(jié)構(gòu)使用線(xiàn)性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能； 輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符 號(hào)。輸出形式：（1）分行輸出用戶(hù)輸入的各行字符； （ 2）分 4行輸出 "全部字母數(shù) "、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù) "（

7、3）輸出刪除某一字符串后的文章；4. 宿舍管理查詢(xún)軟件1）任務(wù)：為宿舍管理人員編寫(xiě)一個(gè)宿舍管理查詢(xún)軟件 , 程序設(shè)計(jì)要求：A. 采用交互工作方式B. 建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號(hào)、房號(hào)）進(jìn)行排序（冒泡、選擇、插入排序等任選一種 ）2）查詢(xún)菜單 : （用二分查找實(shí)現(xiàn)以下操作 ）A. 按姓名查詢(xún)B. 按學(xué)號(hào)查詢(xún)C. 按房號(hào)查詢(xún)3）打印任一查詢(xún)結(jié)果（可以連續(xù)操作）5. 校園導(dǎo)航問(wèn)題（限 1 人完成）設(shè)計(jì)要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括 10 個(gè)以上的場(chǎng)所，每?jī)蓚€(gè)場(chǎng)所間可以 有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑。6. 教學(xué)計(jì)劃編制問(wèn)題 設(shè)計(jì)要求：針對(duì)計(jì)算

8、機(jī)系本科課程，根據(jù)課程之間的依賴(lài)關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù) 據(jù)結(jié)構(gòu)之前開(kāi)設(shè)）制定課程安排計(jì)劃，并滿(mǎn)足各學(xué)期課程數(shù)目大致相同。7. 散列法的實(shí)驗(yàn)研究 散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時(shí)對(duì)于同一散列函數(shù)解決沖突的方法也 可以不同。兩者是影響查詢(xún)算法性能的關(guān)鍵因素。對(duì)于幾種典型的散列函數(shù)構(gòu)造方 法，做實(shí)驗(yàn)觀(guān)察，不同的解決沖突方法對(duì)查詢(xún)性能的影響。8. 圖書(shū)借閱管理系統(tǒng)主要分為兩大功能：1）圖書(shū)管理 （增加圖書(shū)、查詢(xún)圖書(shū)、刪除圖書(shū)、圖書(shū)借閱、還書(shū) ）；2）會(huì)員管理 （增加會(huì)員、查詢(xún)會(huì)員、刪除會(huì)員、借書(shū)信息 ）；9. 學(xué)生成績(jī)管 實(shí)現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、

9、排序、退出。10. 活期儲(chǔ)蓄帳目管理 活期儲(chǔ)蓄處理中，儲(chǔ)戶(hù)開(kāi)戶(hù)、銷(xiāo)戶(hù)、存入、支出活動(dòng)頻繁，系統(tǒng)設(shè)計(jì)要求：1）能比較迅速地找到儲(chǔ)戶(hù)的帳戶(hù)，以實(shí)現(xiàn)存款、取款記賬；2）能比較簡(jiǎn)單，迅速地實(shí)現(xiàn)插入和刪除，以實(shí)現(xiàn)開(kāi)戶(hù)和銷(xiāo)戶(hù)的需要。11. 二叉排序樹(shù)的實(shí)現(xiàn) 用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)1）以回車(chē)（'n'）為輸入結(jié)束標(biāo)志，輸入數(shù)列L,生成一棵二叉排 序樹(shù)T;2）對(duì)二叉排序樹(shù) T 作中序遍歷，輸出結(jié)果；3）輸入元素x,查找二叉排序樹(shù)T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn)，并作中序遍歷（執(zhí)行 操作 2）；否則輸出信息 “無(wú) x”；12. 最小生成樹(shù)問(wèn)題設(shè)計(jì)要求：在 n 個(gè)城市之間建設(shè)網(wǎng)絡(luò),只需保證連通

10、即可,求最經(jīng)濟(jì)的架設(shè)方法。 存儲(chǔ)結(jié)構(gòu)采用多種。求解算法多種。13通. 訊錄的制作 設(shè)計(jì)目的：用數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu),結(jié)合 C 語(yǔ)言基本知識(shí)。編 寫(xiě)一個(gè)通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)應(yīng)用到實(shí)際軟件開(kāi)發(fā)中去。 設(shè)計(jì)內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能：1）輸入信息 enter（）;2）顯示信息 display（ ）;3）查找以姓名作為關(guān)鍵字 search（）;4）刪除信息 delete（）;5）存盤(pán) save（ ）;6）裝入 load（ ） ;設(shè)計(jì)要求：1）每條信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）郵編（EIP） 國(guó)家（STAT巳幾項(xiàng)2）作為一個(gè)完整的系

11、統(tǒng)，應(yīng)具有友好的界面和較強(qiáng)的容錯(cuò)能力3）上機(jī)能正常運(yùn)行，并寫(xiě)出課程設(shè)計(jì)報(bào)告14. 哈夫曼編碼/譯碼器【問(wèn)題描述】 設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選 擇退出為止?！净疽蟆?）將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件（文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中）2）分別采用動(dòng)態(tài)和靜態(tài)存儲(chǔ)結(jié)構(gòu)3）初始化：鍵盤(pán)輸入字符集大小 n、n 個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼樹(shù)；4）編碼：利用建好的哈夫曼樹(shù)生成哈夫曼編碼；5）輸出編碼；6）設(shè)字符集及頻度如下表：字符 空格 A BCDEFGHI JK LM頻度 1 8664 1 3 2232 1 03 21 1547571 5

12、3220字符 NOPQRSTUVWXYZ頻度 5763151 4851 80238181 161【進(jìn)一步完成內(nèi)容】1）譯碼功能；2）顯示哈夫曼樹(shù)；3）界面設(shè)計(jì)的優(yōu)化。15. 圖書(shū)管理系統(tǒng)【問(wèn)題描述】 設(shè)計(jì)一個(gè)計(jì)算機(jī)管理系統(tǒng)完成圖書(shū)管理基本業(yè)務(wù)?！净疽蟆?）每種書(shū)的登記內(nèi)容包括書(shū)號(hào)、書(shū)名、著作者、現(xiàn)存量和庫(kù)存量；2）對(duì)書(shū)號(hào)建立索引表（線(xiàn)性表）以提高查找效率；3）系統(tǒng)主要功能如下： *采編入庫(kù)：新購(gòu)一種書(shū)，確定書(shū)號(hào)后，登記到圖書(shū)帳目表中，如果表中已有，則只 將庫(kù)存量增加；*借閱：如果一種書(shū)的現(xiàn)存量大于 0，則借出一本，登記借閱者的書(shū)證號(hào)和歸還期限， 改變現(xiàn)存量；*歸還：注銷(xiāo)對(duì)借閱者的登記，改變

13、該書(shū)的現(xiàn)存量【進(jìn)一步完成內(nèi)容】1）系統(tǒng)功能的進(jìn)一步完善；2）索引表采用樹(shù)表。3）設(shè)計(jì)內(nèi)容4）程序流程圖5）源程序6）軟件測(cè)試報(bào)告（包括所用到的數(shù)據(jù)及結(jié)果） 16.散列表的設(shè)計(jì)與實(shí)現(xiàn)【問(wèn)題描述】 設(shè)計(jì)散列表實(shí)現(xiàn)電話(huà)號(hào)碼查找系統(tǒng)。【基本要求】1）設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話(huà)號(hào)碼、用戶(hù)名、地址；2）從鍵盤(pán)輸入各記錄，分別以電話(huà)號(hào)碼和用戶(hù)名為關(guān)鍵字建立散列表；3）采用一定的方法解決沖突；4）查找并顯示給定電話(huà)號(hào)碼的記錄；5）查找并顯示給定用戶(hù)名的記錄。【進(jìn)一步完成內(nèi)容】1）系統(tǒng)功能的完善；2）設(shè)計(jì)不同的散列函數(shù)，比較沖突率；3）在散列函數(shù)確定的前提下，嘗試各種不同類(lèi)型處理沖突的方法，考察平均查找長(zhǎng)度

14、的變化。17. 順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。設(shè)有一元多項(xiàng)式Am（x）和Bn（x）.Am（X）=A 0+A1X1+A2X2+A3X3+ +AmXm123nBn（X）=BO+BlX +B2X +B3X + +Bnx請(qǐng)實(shí)現(xiàn)求 M（x）= Am（x）+Bn（x）、M（X）= Am（X）-Bn（X）和 M（X）= Am（X）Bn（X）。要求：1）首先判定多項(xiàng)式是否稀疏2）分別采用順序和動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)；3）結(jié)果M（x）中無(wú)重復(fù)階項(xiàng)和無(wú)零系數(shù)項(xiàng)；4）要求輸出結(jié)果的升冪和降冪兩種排列情況18. 簡(jiǎn)易文本編輯器要求：1）具有圖形菜單界面；2）查找，替換（等長(zhǎng)，不等長(zhǎng)），插入（

15、插串，文本塊的插入）、塊移動(dòng)（行塊，列塊 移動(dòng)），刪除3）可正確存盤(pán)、取盤(pán)；4）正確顯示總行數(shù)。19. 二叉樹(shù)的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法 的實(shí)現(xiàn)，應(yīng)包含建樹(shù)的實(shí)現(xiàn)（。限 1 人完成） 要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。樹(shù)與二叉樹(shù)的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹(shù)的前序、后序的遞歸、非遞歸遍歷算法，層次序 的非遞歸遍歷算法的實(shí)現(xiàn)，應(yīng)包含建樹(shù)的實(shí)現(xiàn)。要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。20. 學(xué)生搭配問(wèn)題一班有m個(gè)女生，有n個(gè)男生（m不等于n）,現(xiàn)要開(kāi)一個(gè)舞會(huì).男女生分別編號(hào)坐在舞 池的兩邊的椅子上 .每曲開(kāi)始時(shí) ,依次從男生和女生中各出一人配對(duì)跳舞 , 本曲沒(méi)成功 配對(duì)者坐著等

16、待下一曲找舞伴 .請(qǐng)?jiān)O(shè)計(jì)一系統(tǒng)模擬動(dòng)態(tài)地顯示出上述過(guò)程,要求如下 :1）輸出每曲配對(duì)情況2）計(jì)算出任何一個(gè)男生（編號(hào)為X）和任意女生（編號(hào)為丫）,在第K曲配對(duì)跳舞的情況.至 少求出 K 的兩個(gè)值 .3）盡量設(shè)計(jì)出多種算法及程序 ,可視情況適當(dāng)加分 提示 :用隊(duì)列來(lái)解決比較方便 .21. 猴子吃桃子問(wèn)題有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)，到了第10天就只余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(gè)桃子。 要求：1）采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解2）采用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解3）采用遞歸實(shí)現(xiàn)上述求解22. 數(shù)制轉(zhuǎn)換問(wèn)題任意給定一個(gè) M 進(jìn)制的數(shù) x ，請(qǐng)實(shí)現(xiàn)如

17、下要求1）求出此數(shù) x 的 10進(jìn)制值（用 MD 表示）2）實(shí)現(xiàn)對(duì) x 向任意的一個(gè)非 M 進(jìn)制的數(shù)的轉(zhuǎn)換。3）至少用兩種或兩種以上的方法實(shí)現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解 決）。23.排序綜合利用隨機(jī)函數(shù)產(chǎn)生 N 個(gè)隨機(jī)整數(shù)（ 20000 以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：1）至少采用三種方法實(shí)現(xiàn)上述問(wèn)題求解（提示，可采用的方法有插入排序、希爾排序、 起泡排序、快速排序、選擇排序、堆排序、歸并排序） 。并把排序后的結(jié)果保存在不 同的文件中。2）統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比） ，找出 其中兩種較快的方法。3）如果采用 4種或 4種以上的

18、方法者，可適當(dāng)加分。24.學(xué)生成績(jī)管理系統(tǒng)現(xiàn)有學(xué)生成績(jī)信息文件1 （1.txt）,內(nèi)容如下姓名學(xué)號(hào)語(yǔ)文數(shù)學(xué)英語(yǔ)張明明01677882李成友02789188張輝燦03688256王露04564577陳東明05673847學(xué)生成績(jī)信息文件 2（姓名 學(xué)號(hào) 語(yǔ)文2.txt)數(shù)學(xué),內(nèi)容如下英語(yǔ)陳果31576882李華明32889068張明東33484256李明國(guó)34504587陳道亮35475877試編寫(xiě)一管理系統(tǒng) ,要求如下 :1）實(shí)現(xiàn)對(duì)兩個(gè)文件數(shù)據(jù)進(jìn)行合并 ,生成新文件 3.txt2）抽取出三科成績(jī)中有補(bǔ)考的學(xué)生并保存在一個(gè)新文件 4.txt3）合并后的文件3.txt中的數(shù)據(jù)按總分降序排序（至少采

19、用兩種排序方法實(shí)現(xiàn)）4）輸入一個(gè)學(xué)生姓名后 ,能查找到此學(xué)生的信息并輸出結(jié)果 （至少采用兩種查找方法實(shí) 現(xiàn)）5）要求使用結(jié)構(gòu)體 ,鏈或數(shù)組等實(shí)現(xiàn)上述要求 .6）采用多種方法且算法正確者 ,可適當(dāng)加分.25. 圖的遍歷的實(shí)現(xiàn)要求：1） 先任意創(chuàng)建一個(gè)圖；2）圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)3）要求用有向圖和無(wú)向圖分別實(shí)現(xiàn)4）要求用鄰接矩陣、鄰接表多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)26. 線(xiàn)索二叉樹(shù)的應(yīng)用要求：實(shí)現(xiàn)線(xiàn)索樹(shù)建立、插入、刪除、恢復(fù)線(xiàn)索的實(shí)現(xiàn)27. 稀疏矩陣應(yīng)用要求：實(shí)現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實(shí)現(xiàn)（1）稀疏矩陣的存儲(chǔ)（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉(zhuǎn)置28.樹(shù)的應(yīng)用

20、 要求：實(shí)現(xiàn)樹(shù)與二叉樹(shù)的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹(shù)的前序、后序的遞歸、非遞歸算法， 層次序的非遞歸算法的實(shí)現(xiàn)，應(yīng)包含建樹(shù)的實(shí)現(xiàn)。29. 文本文件單詞的檢索與計(jì)數(shù) 設(shè)計(jì)要求與分析： 要求編程建立一個(gè)文本文件，每個(gè)單詞不包含空格且不跨行，單詞由字符序列構(gòu)成 且區(qū)分大小寫(xiě)；統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個(gè)單詞出現(xiàn) 在文本中的行號(hào)、在該行中出現(xiàn)的次數(shù)以及位置。該設(shè)計(jì)要求可分為三個(gè)部分實(shí)現(xiàn)： 其一，建立文本文件，文件名由用戶(hù)用鍵盤(pán)輸入；其二，給定單詞的計(jì)數(shù)，輸入一 個(gè)不含空格的單詞，統(tǒng)計(jì)輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞， 輸入一個(gè)單詞，檢索并輸出該單詞所在的行號(hào)、該行中出現(xiàn)的次

21、數(shù)以及在該行中的 相應(yīng)位置。（1）.建立文本文件（2）給定單詞的計(jì)數(shù)（3）檢索單詞出現(xiàn)在文本文件中的行號(hào)、次數(shù)及其位置（4）主控菜單程序的結(jié)構(gòu) 頭文件包含 菜單選項(xiàng)包含 建立文件、單詞定位、單詞計(jì)數(shù)、退出程序 選擇 1-4 執(zhí)行相應(yīng)的操作，其他字符為非法。30. 任意長(zhǎng)的整數(shù)加法） 問(wèn)題描述：設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)的求和運(yùn)算。 基本要求：利用雙向循環(huán)鏈表，設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程 序。要求輸入和輸出每四位一組，組間用逗號(hào)隔開(kāi)。如： 1，0000，0000，0000，0000。31. 串的查找和替換 問(wèn)題描述：打開(kāi)一篇英文文章，在該文章中找出所有給定的單詞，然后對(duì)所

22、有給定 的單詞替換為另外一個(gè)單詞，再存盤(pán)。32.約瑟夫環(huán)問(wèn)題描述：編號(hào)為1, 2n的n個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開(kāi)始按順時(shí)針 方向自1開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的 m 值，從他的順時(shí)針?lè)较蛏系南乱粋€(gè)開(kāi)始重新從 1 報(bào)數(shù)，如此下去，直至所有人全 部出列為止，設(shè)計(jì)一個(gè)程序求出出列順序?；疽螅?、利用單循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程；2、鍵盤(pán)輸入總?cè)藬?shù)、初始報(bào)數(shù)上限值 m 及各人密碼；3、按照出列順序輸出各人的編號(hào)。33. 構(gòu)造可以使 n 個(gè)城市連接的最小生成樹(shù)問(wèn)題描述： 給定一個(gè)地

23、區(qū)的 n 個(gè)城市間的距離網(wǎng)，用 Prim 算法或 Kruskal 算法建立 最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。基本要求：1、城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的 定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。 要求在屏幕上顯示得到的最小生成樹(shù)中包括了哪些城市間的道路，并顯示得到的最 小生成樹(shù)的代價(jià)。2、表示城市間距離網(wǎng)的鄰接矩陣（要求至少 6個(gè)城市， 10條邊）3、最小生成樹(shù)中包括的邊及其權(quán)值，并顯示得到的最小生成樹(shù)的代價(jià)。34. 客戶(hù)消費(fèi)積分管理系統(tǒng)問(wèn)題描述： 針對(duì)客戶(hù)的消費(fèi)情況，進(jìn)行客戶(hù)管理，根據(jù)客戶(hù)的消費(fèi)積分對(duì)客戶(hù)實(shí)行

24、不同程度的打折優(yōu)惠?；疽螅?. 采用一定的存儲(chǔ)結(jié)構(gòu)進(jìn)行客戶(hù)信息的存儲(chǔ)；2. 對(duì)客戶(hù)的信息可以進(jìn)行修改、刪除、添加；3. 能夠根據(jù)消費(fèi)情況進(jìn)行客戶(hù)積分的計(jì)算；4. 根據(jù)積分情況實(shí)行不同程度的打折優(yōu)惠；35. 產(chǎn)品進(jìn)銷(xiāo)存管理系統(tǒng) 問(wèn)題描述：針對(duì)某一種行業(yè)的庫(kù)房的產(chǎn)品進(jìn)銷(xiāo)存情況進(jìn)行管理。 基本要求：1. 采用一定的存儲(chǔ)結(jié)構(gòu)對(duì)庫(kù)房的貨品及其數(shù)量進(jìn)行分類(lèi)管理；2. 可以進(jìn)行產(chǎn)品類(lèi)的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加；3. 能夠查詢(xún)庫(kù)房每種產(chǎn)品的總量、進(jìn)貨日期、銷(xiāo)出數(shù)量、銷(xiāo)售時(shí)間等；36. 特殊矩陣的壓縮存儲(chǔ)算法的實(shí)現(xiàn)） 問(wèn)題描述： 對(duì)于特殊矩陣可以通過(guò)壓縮存儲(chǔ)減少存儲(chǔ)空間。 基本要求：1. 針對(duì)多種特

25、殊矩陣進(jìn)行壓縮存儲(chǔ)，并能顯示壓縮后的相關(guān)地址和值；2. 輸入在原來(lái)特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應(yīng)的值；37. 算術(shù)表達(dá)式的求解 問(wèn)題描述：給定一個(gè)算術(shù)表達(dá)式，通過(guò)程序求出最后的結(jié)果?；疽螅?1從鍵盤(pán)輸入要求解的算術(shù)表達(dá)式； 2采用棧結(jié)構(gòu)進(jìn)行算術(shù)表達(dá)式的求解過(guò)程； 3能夠判斷算術(shù)表達(dá)式正確與否； 4對(duì)于錯(cuò)誤表達(dá)式給出提示； 5對(duì)于正確的表達(dá)式給出最后的結(jié)果；38. 實(shí)時(shí)監(jiān)控報(bào)警系統(tǒng) 問(wèn)題描述：建立一個(gè)報(bào)警和出警管理的系統(tǒng) 基本要求：1. 采用一定的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)報(bào)警信息，要求有內(nèi)容、時(shí)間；2. 有一次的出警就應(yīng)該在待處理的信息中刪除這條信息；3. 記錄出警信息；4. 待處理信

26、息過(guò)多時(shí)會(huì)發(fā)出警告；39. 車(chē)廂調(diào)度 問(wèn)題描述：假設(shè)停在鐵路調(diào)度站入口處的車(chē)廂序列的編號(hào)一次為 1，2，3，4。設(shè)計(jì) 一個(gè)程序，求出所有可能由此輸出的長(zhǎng)度為 4 的車(chē)廂序列。40.迷宮問(wèn)題(棧)問(wèn)題描述：以一個(gè) m*n 的長(zhǎng)方陣表示迷宮， 0和 1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程 序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論 。 基本要求：首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的非遞歸程序。 求得的通路以三元組(i,j,d)的形式輸出，其中：(i,j)指示迷宮中的一個(gè)坐標(biāo)，d 表示走到下一坐標(biāo)的方向，如：對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路為：(1,1,1), (1,2,2) ,(3,2,3),(3,1,2),。測(cè)試數(shù)據(jù)： 迷宮的測(cè)試數(shù)據(jù)如下：左下角( 1, 1)為入口,右下角( 8, 9)為出口。實(shí)現(xiàn)提示： 計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法,即從入口出發(fā),順著某個(gè)方向進(jìn)行探 索,若能走通,則繼續(xù)往前進(jìn)；否則沿著原路退回,換一個(gè)方向繼續(xù)探索,直至出 口位置,求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口,則所設(shè)的 迷宮沒(méi)有通路。可以二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù),通常設(shè)定入口點(diǎn)的下標(biāo)為(