軟件算法綜合設(shè)計(jì)任務(wù)書(shū)

1、軟件算法綜合設(shè)計(jì)任務(wù)書(shū)一、軟件算法綜合設(shè)計(jì)基本信息1、課程設(shè)計(jì)編號(hào):2、課程設(shè)計(jì)名稱:軟件算法綜合設(shè)計(jì)3、課程設(shè)計(jì)周數(shù)(學(xué)時(shí):1周(40學(xué)時(shí)4、課程設(shè)計(jì)授課單位:計(jì)算機(jī)科學(xué)與技術(shù)系5、指導(dǎo)方式:集體輔導(dǎo)和個(gè)別輔導(dǎo)相結(jié)合6、適用專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)7、課程設(shè)計(jì)教材及主要參考資料:1 嚴(yán)蔚敏,吳偉民編著.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版.清華大學(xué)出版社, 1997.42 嚴(yán)蔚敏,吳偉民編著.數(shù)據(jù)結(jié)構(gòu)習(xí)題集 . 清華大學(xué)出版社,1997.4二、教學(xué)目的和基本要求1、了解并掌握數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)的方法,具備初步的獨(dú)立分析和設(shè)計(jì)能力。2、初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析分析、系統(tǒng)設(shè)計(jì)、程序編碼和測(cè)試等基本方法和技能。

2、3、提高綜合運(yùn)用所學(xué)的理論只是和方法,獨(dú)立分析和解決問(wèn)題的能力。4、訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件的開(kāi)發(fā),培養(yǎng)軟件工作著所具備的科學(xué)工作方法和作風(fēng)。三、軟件算法綜合設(shè)計(jì)的內(nèi)容和安排1、問(wèn)題分和任務(wù)定義:根據(jù)設(shè)計(jì)題目的要求,充分地分析和理解問(wèn)題,明確問(wèn)題要求做什么,限制的條件是什么。2、邏輯設(shè)計(jì):對(duì)問(wèn)題中涉及到的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型,并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊,定義主程序和各抽象數(shù)據(jù)類型,邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說(shuō)明,各個(gè)主要模塊的算法,并畫(huà)出模塊之間的調(diào)用關(guān)系圖。3、物理設(shè)計(jì):定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出個(gè)函數(shù)的

3、偽碼算法。在這個(gè)過(guò)程中,要綜合考慮系統(tǒng)功能,使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試,抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝,基本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作做出進(jìn)一步的求精,寫出數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)的類型定義,寫出函數(shù)形式的算法框架。4、程序編碼:把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言。同時(shí)加入一些注解和斷言,使程序中邏輯概;念清晰。5、程序調(diào)試和測(cè)試:采用自底向上,分模塊進(jìn)行,即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能,設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn),通過(guò)修改程序來(lái)證實(shí)它或繞過(guò)它。調(diào)試正確后,認(rèn)真整理源程序和注釋,形成格式和風(fēng)格良好的源程序清單和結(jié)果。6、結(jié)果分

4、析:程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果、含有錯(cuò)誤的輸入和輸出結(jié)果、算法時(shí)間復(fù)雜度和空間復(fù)雜度分析。7、撰寫課程設(shè)計(jì)報(bào)告:總結(jié)和提升上述過(guò)程和步驟,寫出結(jié)構(gòu)嚴(yán)謹(jǐn)、表述清楚、符合設(shè)計(jì)規(guī)范的報(bào)告。四、軟件算法綜合設(shè)計(jì)的題目本課程設(shè)計(jì)題目共34個(gè),每個(gè)同學(xué)可以根據(jù)自身實(shí)際情況進(jìn)行選擇。最后需要對(duì)所做系統(tǒng)書(shū)寫實(shí)驗(yàn)報(bào)告一份,格式見(jiàn)附頁(yè)。五、考核的方法和成績(jī)的評(píng)定考核成績(jī)分為兩個(gè)部分:(1驗(yàn)收程序部分:占50%。按照以下幾個(gè)指標(biāo)進(jìn)行驗(yàn)收:程序的正確性;程序的運(yùn)行和存儲(chǔ)效率;程序代碼編寫規(guī)范程度,代碼的可讀性高;界面是否友好;程序設(shè)計(jì)的創(chuàng)新性;(2實(shí)驗(yàn)報(bào)告(50%實(shí)驗(yàn)報(bào)告結(jié)構(gòu)是否清晰,問(wèn)題敘述是否具有邏輯

5、性;關(guān)鍵代碼設(shè)計(jì)是否正確無(wú)誤;程序設(shè)計(jì)的時(shí)間、空間復(fù)雜性分析是否正確。六、時(shí)間的安排共1周,5天。題目共10個(gè),每個(gè)同學(xué)可以根據(jù)自身實(shí)際情況掌握進(jìn)度,最后一天驗(yàn)收程序,也可以分部分驗(yàn)收。七、軟件算法綜合設(shè)計(jì)報(bào)告的格式(1問(wèn)題的概述、分析和研究意義;(2數(shù)據(jù)結(jié)構(gòu)的邏輯設(shè)計(jì)和物理存儲(chǔ)設(shè)計(jì);(3重要算法的設(shè)計(jì)、流程描述和代碼描述;(4數(shù)據(jù)結(jié)構(gòu)的時(shí)間、空間復(fù)雜性分析和重要算法的復(fù)雜度分析;(5程序的最終實(shí)現(xiàn)結(jié)果(包括重點(diǎn)界面的抓取,能說(shuō)明問(wèn)題的重要實(shí)驗(yàn)結(jié)果數(shù)據(jù)的打印或其可視化結(jié)果;(6參考文獻(xiàn);(7附錄:關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的定義及關(guān)鍵算法的源代碼。八、軟件算法綜合設(shè)計(jì)結(jié)果的提交(1課程設(shè)計(jì)報(bào)告(一份、A4紙

6、打印,同時(shí)包括一份電子文檔。(2完整的程序系統(tǒng)(電子方式提交,能夠?qū)斎氘a(chǎn)生相應(yīng)的輸出,同時(shí)盡量完成可視化演示。(3源程序文檔(電子方式提交,源程序代碼要求適當(dāng)縮進(jìn)編排、結(jié)構(gòu)清晰、可讀性好,對(duì)源程序的類說(shuō)明(如采用面向?qū)ο蠓椒ㄔO(shè)計(jì)、函數(shù)說(shuō)明、接口說(shuō)明、關(guān)鍵變量說(shuō)明等要進(jìn)行注釋。(4答辯報(bào)告(制作PPT報(bào)告,電子方式提交,要求重點(diǎn)突出,思路清晰,同時(shí)就此報(bào)告準(zhǔn)備答辯。所有電子方式提交的文件全部存放在一個(gè)目錄中,并對(duì)其進(jìn)行壓縮,壓縮后的文件按規(guī)定格式進(jìn)行命名,命名格式為:班級(jí)號(hào)+學(xué)號(hào)+姓名。九、軟件算法綜合設(shè)計(jì)題目說(shuō)明1.運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)(限3人完成任務(wù):參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校,學(xué)校編號(hào)為1n。比賽分

7、成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,n=20功能要求:1可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī);2能統(tǒng)計(jì)各學(xué)?？偡?3可以按學(xué)校編號(hào)或名稱、學(xué)校總分、男女團(tuán)體總分排序輸出;4可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況;可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校;5數(shù)據(jù)存入文件并能隨時(shí)查詢;6規(guī)定:輸入數(shù)據(jù)形式和范圍:可以輸入學(xué)校的名稱,運(yùn)動(dòng)項(xiàng)目的名稱。輸出形式:有合理的提示,各學(xué)校分?jǐn)?shù)為整形。界面要求:有合理的提示,

8、每個(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ù)讀寫方法等相關(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料中寫明。2.飛機(jī)訂票系統(tǒng)(限3人完成通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能:錄入:可以錄入航班情況(數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中,數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定;查詢:可以查詢某個(gè)航線的情況(如,輸入航班號(hào),查詢起降時(shí)間,起飛抵達(dá)

9、城市,航班票價(jià),票價(jià)折扣,確定航班是否滿倉(cāng);可以輸入起飛抵達(dá)城市,查詢飛機(jī)航班情況;訂票:(訂票情況可以存在一個(gè)數(shù)據(jù)文件中,結(jié)構(gòu)自己設(shè)定可以訂票,如果該航班已經(jīng)無(wú)票,可以提供相關(guān)可選擇航班;退票:可退票,退票后修改相關(guān)數(shù)據(jù)文件;客戶資料有姓名,證件號(hào),訂票數(shù)量及航班情況,訂單要有編號(hào);修改航班信息:當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件。要求:根據(jù)以上功能說(shuō)明,設(shè)計(jì)航班信息,訂票信息的存儲(chǔ)結(jié)構(gòu),設(shè)計(jì)程序完成功能。3.文章編輯(限3人完成功能:輸入一頁(yè)文字,程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù);靜態(tài)存儲(chǔ)一頁(yè)文章,每行最多不超過(guò)80個(gè)字符,共N行。要求:(1分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總

10、字?jǐn)?shù);(2統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù),并輸出該次數(shù);(3刪除某一子串,并將后面的字符前移。存儲(chǔ)結(jié)構(gòu)使用線性表,分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能。輸入數(shù)據(jù)的形式和范圍:可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式:(1分行輸出用戶輸入的各行字符;(2分4行輸出全部字母數(shù)、數(shù)字個(gè)數(shù)、空格個(gè)數(shù)、文章總字?jǐn)?shù)(3輸出刪除某一字符串后的文章。4.宿舍管理查詢軟件(限3人完成為宿舍管理人員編寫一個(gè)宿舍管理查詢軟件, 程序設(shè)計(jì)要求:A.采用交互工作方式;B.建立數(shù)據(jù)文件,數(shù)據(jù)文件按關(guān)鍵字(姓名、學(xué)號(hào)、房號(hào)進(jìn)行排序(冒泡、選擇、插入排序等任選一種。查詢菜單:(用二分查找實(shí)現(xiàn)以下操作A.按姓名查

11、詢;B.按學(xué)號(hào)查詢;C.按房號(hào)查詢。打印任一查詢結(jié)果(可以連續(xù)操作5.校園導(dǎo)航問(wèn)題(限3人完成設(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)題(限3人完成設(shè)計(jì)要求:針對(duì)計(jì)算機(jī)系本科課程,根據(jù)課程之間的依賴關(guān)系(如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開(kāi)設(shè)制定課程安排計(jì)劃,并滿足各學(xué)期課程數(shù)目大致相同。7.散列法的實(shí)驗(yàn)研究(限3人完成散列法中,散列函數(shù)構(gòu)造方法多種多樣,同時(shí)對(duì)于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對(duì)于幾種典型的散列函數(shù)構(gòu)造方法,做實(shí)驗(yàn)觀

12、察,不同的解決沖突方法對(duì)查詢性能的影響。8.圖書(shū)借閱管理系統(tǒng)(限3人完成主要分為兩大功能:1圖書(shū)管理(增加圖書(shū)、查詢圖書(shū)、刪除圖書(shū)、圖書(shū)借閱、還書(shū);2會(huì)員管理(增加會(huì)員、查詢會(huì)員、刪除會(huì)員、借書(shū)信息。9.學(xué)生成績(jī)管理(限3人完成實(shí)現(xiàn)功能:輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計(jì)、退出。10.二叉排序樹(shù)的實(shí)現(xiàn)(限3人完成用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)1以回車(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”。1

13、1.最小生成樹(shù)問(wèn)題(限3人完成設(shè)計(jì)要求:在n個(gè)城市之間建設(shè)網(wǎng)絡(luò),只需保證連通即可,求最經(jīng)濟(jì)的架設(shè)方法。存儲(chǔ)結(jié)構(gòu)采用多種。求解算法多種。12.通訊錄的制作(限3人完成設(shè)計(jì)目的:用數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu),結(jié)合C語(yǔ)言基本知識(shí)。編寫一個(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存盤save ( ;6裝入load( 。設(shè)計(jì)要求:1每條信息至包含:姓名(NAME 街道(STREET城市(CITY郵編(EIP國(guó)家(STA

14、TE幾項(xiàng);2作為一個(gè)完整的系統(tǒng),應(yīng)具有友好的界面和較強(qiáng)的容錯(cuò)能力;3上機(jī)能正常運(yùn)行,并寫出課程設(shè)計(jì)報(bào)告。13.哈夫曼編碼/譯碼器(限3 人完成【問(wèn)題描述】設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng),重復(fù)地顯示并處理以下項(xiàng)目,直到選擇退出為止。【基本要求】1將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt,位于執(zhí)行程序的當(dāng)前目錄中 ;2分別采用動(dòng)態(tài)和靜態(tài)存儲(chǔ)結(jié)構(gòu);3初始化:鍵盤輸入字符集大小n、n個(gè)字符和n個(gè)權(quán)值,建立哈夫曼樹(shù);4編碼:利用建好的哈夫曼樹(shù)生成哈夫曼編碼;5輸出編碼;6設(shè)字符集及頻度如下表:字符空格 A B C D E F G H I J K L M頻度 186 64 13 22 3

15、2 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【進(jìn)一步完成內(nèi)容】1譯碼功能;2顯示哈夫曼樹(shù);3界面設(shè)計(jì)的優(yōu)化。14.圖書(shū)管理系統(tǒng)(限3人完成【問(wèn)題描述】設(shè)計(jì)一個(gè)計(jì)算機(jī)管理系統(tǒng)完成圖書(shū)管理基本業(yè)務(wù)。【基本要求】1每種書(shū)的登記內(nèi)容包括書(shū)號(hào)、書(shū)名、著作者、現(xiàn)存量和庫(kù)存量;2對(duì)書(shū)號(hào)建立索引表(線性表以提高查找效率;3系統(tǒng)主要功能如下:采編入庫(kù):新購(gòu)一種書(shū),確定書(shū)號(hào)后,登記到圖書(shū)帳目表中,如果表中已有,則只將庫(kù)存量增加;借閱:如果一種書(shū)的現(xiàn)存量大于0,則借出一本,登記

16、借閱者的書(shū)證號(hào)和歸還期限,改變現(xiàn)存量;歸還:注銷對(duì)借閱者的登記,改變?cè)摃?shū)的現(xiàn)存量?！具M(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é)果。15.散列表的設(shè)計(jì)與實(shí)現(xiàn)(限3人完成【問(wèn)題描述】設(shè)計(jì)散列表實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)?！净疽蟆?設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng):電話號(hào)碼、用戶名、地址;2從鍵盤輸入各記錄,分別以電話號(hào)碼和用戶名為關(guān)鍵字建立散列表;3采用一定的方法解決沖突;4查找并顯示給定電話號(hào)碼的記錄;5查找并顯示給定用戶名的記錄?！具M(jìn)一步完成內(nèi)容】1系統(tǒng)功能的完善;2設(shè)計(jì)不同的散列函數(shù),比較沖突率;3在散列函數(shù)確定的前

17、提下,嘗試各種不同類型處理沖突的方法,考察平均查找長(zhǎng)度的變化。16.順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。(限3人完成設(shè)有一元多項(xiàng)式A m(x和B n(x.A m(x=A0+A1x1+A2x2+A3x3+ +A m x mB n(x=B0+B1x1+B2x2+B3x3+ +B n x n請(qǐng)實(shí)現(xiàn)求M(x= A m(x+B n(x、M(x= A m(x-B n(x和M(x= A m(xB n(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é)果的升冪和降冪兩種排列情況。17.利用棧求表達(dá)式的值,可供小學(xué)生

18、作業(yè),并能給出分?jǐn)?shù)。(限3人完成要求:建立試題庫(kù)文件,隨機(jī)產(chǎn)生n個(gè)題目;題目涉及加減乘除,帶括弧的混合運(yùn)算;隨時(shí)可以退出;保留歷史分?jǐn)?shù),能回顧歷史,給出與歷史分?jǐn)?shù)比較后的評(píng)價(jià)。18.二叉樹(shù)的中序、前序、后序的遞歸、非遞歸遍歷算法,層次序的非遞歸遍歷算法的實(shí)現(xiàn),應(yīng)包含建樹(shù)的實(shí)現(xiàn)。(限3人完成要求:遍歷的內(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)的。19.學(xué)生搭配問(wèn)題(限3人完成一班有m個(gè)女生,有n個(gè)男生(m不等于n,現(xiàn)要開(kāi)一個(gè)舞會(huì). 男女生分別編號(hào)坐在舞池的兩邊的椅子上.每曲開(kāi)

19、始時(shí),依次從男生和女生中各出一人配對(duì)跳舞, 本曲沒(méi)成功配對(duì)者坐著等待下一曲找舞伴。請(qǐng)?jiān)O(shè)計(jì)一系統(tǒng)模擬動(dòng)態(tài)地顯示出上述過(guò)程,要求如下:1輸出每曲配對(duì)情況;2計(jì)算出任何一個(gè)男生(編號(hào)為X和任意女生(編號(hào)為Y,在第K曲配對(duì)跳舞的情況.至少求出K的兩個(gè)值;3盡量設(shè)計(jì)出多種算法及程序,可視情況適當(dāng)加分。提示:用隊(duì)列來(lái)解決比較方便。20.猴子吃桃子問(wèn)題(限3人完成有一群猴子摘了一堆桃子,他們每天都吃當(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)上述求解。21.數(shù)制轉(zhuǎn)換

20、問(wèn)題(限3人完成任意給定一個(gè)M進(jìn)制的數(shù)x ,請(qǐng)實(shí)現(xiàn)如下要求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ù)組解決,其它方法解決。22.排序綜合(限3人完成利用隨機(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種以上

21、的方法者,可適當(dāng)加分。23.學(xué)生成績(jī)管理系統(tǒng)(限3人完成現(xiàn)有學(xué)生成績(jī)信息文件1(1.txt,內(nèi)容如下姓名學(xué)號(hào)語(yǔ)文數(shù)學(xué)英語(yǔ)張明明 01 67 78 82李成友 02 78 91 88張輝燦 03 68 82 56王露 04 56 45 77陳東明 05 67 38 47. . . . 學(xué)生成績(jī)信息文件2(2.txt,內(nèi)容如下:姓名學(xué)號(hào)語(yǔ)文數(shù)學(xué)英語(yǔ)陳果 31 57 68 82李華明 32 88 90 68張明東 33 48 42 56李明國(guó) 34 50 45 87陳道亮 35 47 58 77. . . . 試編寫一管理系統(tǒng),要求如下:1實(shí)現(xiàn)對(duì)兩個(gè)文件數(shù)據(jù)進(jìn)行合并,生成新文件3.txt;2抽取出三

22、科成績(jī)中有補(bǔ)考的學(xué)生并保存在一個(gè)新文件4.txt;3合并后的文件3.txt中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實(shí)現(xiàn);4輸入一個(gè)學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實(shí)現(xiàn);5要求使用結(jié)構(gòu)體,鏈或數(shù)組等實(shí)現(xiàn)上述要求;6采用多種方法且算法正確者,可適當(dāng)加分。 24.圖的遍歷的實(shí)現(xiàn)（ 人完成） 24.圖的遍歷的實(shí)現(xiàn)（限 3 人完成） 圖的遍歷的實(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)。 25.線索二叉樹(shù)的應(yīng)用（ 人完成） 25.線索二叉樹(shù)的應(yīng)用（限

23、 3 人完成） 線索二叉樹(shù)的應(yīng)用 要求：實(shí)現(xiàn)線索樹(shù)建立、插入、刪除、恢復(fù)線索的實(shí)現(xiàn)。 26.稀疏矩陣應(yīng)用（限 3 人完成） 26.稀疏矩陣應(yīng)用（ 人完成） 稀疏矩陣應(yīng)用 要求：實(shí)現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實(shí)現(xiàn)。 （1）稀疏矩陣的存儲(chǔ)； （2）稀疏矩陣加法； （3）矩陣乘法； （4）矩陣轉(zhuǎn)置。 27.樹(shù)的應(yīng)用（限 3 人完成） 27.樹(shù)的應(yīng)用（ 人完成） 樹(shù)的應(yīng)用 要求：實(shí)現(xiàn)樹(shù)與二叉樹(shù)的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹(shù)的前序、后序的遞歸、非遞歸 算法，層次序的非遞歸算法的實(shí)現(xiàn)，應(yīng)包含建樹(shù)的實(shí)現(xiàn)。 28.任意長(zhǎng)的整數(shù)加法（限 3 人完成） 8.任意長(zhǎng)的整數(shù)加法（ 人完成） 任意長(zhǎng)的整數(shù)加法 問(wèn)

24、題描述：設(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。 29.二叉平衡排序樹(shù)（限 3 人完成） 29.二叉平衡排序樹(shù)（ 人完成） 二叉平衡排序樹(shù) 問(wèn)題描述：從一棵空樹(shù)開(kāi)始創(chuàng)建，在創(chuàng)建過(guò)程中，保證樹(shù)的有序性，同時(shí)還要 針對(duì)樹(shù)的平衡性做些調(diào)整。最終要把創(chuàng)建好的二叉排序樹(shù)轉(zhuǎn)換為二叉平衡排序 樹(shù)。 基本要求：1.創(chuàng)建（插入、調(diào)整、改組） 2.輸出 30.串的查找和替換 （限 3 人完成） 30.串的查找和替換 人完成） 問(wèn)題描述：打開(kāi)

25、一篇英文文章，在該文章中找出所有給定的單詞，然后對(duì)所 有給定的單詞替換為另外一個(gè)單詞，再存盤。 31.約瑟夫環(huán) （限 3 人完成） 31.約瑟夫環(huán) 人完成） 問(wèn)題描述：編號(hào)為 1，2 n 的 n 個(gè)人按順時(shí)針?lè)较驀蝗?，每人持有?個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值 m，從第一個(gè)人開(kāi) 始按順時(shí)針?lè)较蜃?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è)程序求出出列順序。 基本要求： 1利用單循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程； 2鍵盤輸入總?cè)藬?shù)、初始報(bào)數(shù)上限值 m 及各人密碼； 3按照出列順序輸出各人的編號(hào)。 32.構(gòu)造可以使 n 個(gè)城市連接的最小生成樹(shù) （限 3 人完成） 32.構(gòu)造可以使 個(gè)城市連接的最小生成樹(shù) 人完成） 問(wèn)題描述：給定一個(gè)地區(qū)的 n 個(gè)城市間的距離網(wǎng)，用 Prim 算法或 Kruskal 算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。 基本要求： 1、城市間的距離