數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫課程設(shè)計指導(dǎo)書

1、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫課程設(shè)計指導(dǎo)書數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫課程設(shè)計指導(dǎo)書一、課程設(shè)計的目的、要求和任務(wù)本課程設(shè)計通過設(shè)計完整的程序,使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫等根本方法.掌握數(shù)據(jù)庫應(yīng)用程序設(shè)計的步驟和方法.1 .課程的目的(1)使學(xué)生進一步理解和掌握課堂上所學(xué)各種根本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法,以及它們在程序中的使用方法.(2)使學(xué)生掌握數(shù)據(jù)庫設(shè)計的根本內(nèi)容和設(shè)計方法,并培養(yǎng)學(xué)生進行標(biāo)準(zhǔn)化軟件設(shè)計的水平.(3)使學(xué)生掌握使用各種計算機資料和有關(guān)參考資料,提升學(xué)生進行程序設(shè)計的根本水平；2 .課程的根本要求與任務(wù)(1)穩(wěn)固和加深對數(shù)據(jù)結(jié)構(gòu)根本知識的理解,提升綜合運用所學(xué)課程知識

2、的水平.(2)培養(yǎng)學(xué)生自學(xué)參考書籍,查閱手冊、圖表和文獻資料的水平.(3)通過實際課程設(shè)計,初步掌握簡單軟件的分析方法和設(shè)計方法.(4)了解與課程有關(guān)的工程技術(shù)標(biāo)準(zhǔn),能正確解釋和分析實驗結(jié)果.(5)題目具有足夠的工作量.(6)有水平的同學(xué)可以根據(jù)數(shù)據(jù)庫的原理設(shè)計數(shù)據(jù)庫表邏輯結(jié)構(gòu),通過數(shù)據(jù)結(jié)構(gòu)的方法用C+/Java/C語言編寫程序?qū)崿F(xiàn)表中數(shù)據(jù)的插入、刪除、查找等操作.二、課程設(shè)計的一般步驟選題與搜集資料：分析與概要設(shè)計：根據(jù)搜集的資料,進行程序功能與數(shù)據(jù)結(jié)構(gòu)分析,并選擇適宜的數(shù)據(jù)結(jié)構(gòu)、并在此根底上進行實現(xiàn)程序功能的算法設(shè)計.程序設(shè)計：運用掌握C+/Java/C語言編寫程序,實現(xiàn)程序的各個模塊功能

3、調(diào)試與測試：調(diào)試程序,并記錄測試情況.完成課程設(shè)計報告.驗收與評分：指導(dǎo)教師對每個同學(xué)的開發(fā)的系統(tǒng)進行綜合驗收.三、課程設(shè)計報告的標(biāo)準(zhǔn)課程設(shè)計報告(3000字以上,數(shù)據(jù)結(jié)構(gòu)題目1000字以上,數(shù)據(jù)庫題目2000字以上)數(shù)據(jù)結(jié)構(gòu)題目要求標(biāo)準(zhǔn)書寫,應(yīng)當(dāng)包括如下8個局部：(1)問題描述：描述要求編程解決的問題.(2)根本要求：給出程序要到達的具體的要求.(3)算法思想：描述解決相應(yīng)問題算法的設(shè)計思想.(4)模塊劃分：描述所設(shè)計程序的各個模塊(即函數(shù))功能.(5)數(shù)據(jù)結(jié)構(gòu)：給出所使用的根本抽象數(shù)據(jù)類型,所定義的具體問題的數(shù)據(jù)類型,以及新定義的抽象數(shù)據(jù)類型.(6)源程序：給出所有源程序清單,要求程序有充

4、分的注釋語句,至少要注釋每個函數(shù)參數(shù)的含義和函數(shù)返回值的含義.(7)測試數(shù)據(jù)：設(shè)計測試數(shù)據(jù),或具體給出測試數(shù)據(jù).要求測試數(shù)據(jù)能全面地測試所設(shè)計程序的功能.(8)測試情況：給出程序的測試情況,并分析運行結(jié)果(9)總結(jié)和體會數(shù)據(jù)庫要求標(biāo)準(zhǔn)書寫,應(yīng)當(dāng)包括如下6個局部：(1)系統(tǒng)概述(2)需求分析(3)概念結(jié)構(gòu)設(shè)計(4)邏輯設(shè)計(5)物理設(shè)計(6)實現(xiàn)數(shù)據(jù)庫(7)總結(jié)和體會四、成績評定標(biāo)準(zhǔn)學(xué)生成績以優(yōu)、良、中、及格和不及格5個等級評定.(1)學(xué)生編寫的實際軟件和運行結(jié)果,占總成績50%;(2)設(shè)計報告,占總成績50%o五、數(shù)據(jù)庫題目及要求一、題目根據(jù)學(xué)號的尾號選擇以下系統(tǒng)之一：1、工資治理系統(tǒng)2、藥品

5、治理系統(tǒng)3、學(xué)生宿舍治理系統(tǒng)4、圖書治理系統(tǒng)5、網(wǎng)上銷售治理系統(tǒng)6、酒店治理系統(tǒng)7、物業(yè)治理系統(tǒng)8、人事治理系統(tǒng)9、學(xué)生成績治理系統(tǒng)10、教室排課治理系統(tǒng)二、要求(一)數(shù)據(jù)庫設(shè)計1、對系統(tǒng)進行需求分析.2、對系統(tǒng)進行概念結(jié)構(gòu)設(shè)計.(畫出局部和全局E_R圖)3、對系統(tǒng)進行邏輯結(jié)構(gòu)設(shè)計(轉(zhuǎn)換成關(guān)系模型)4、對系統(tǒng)進行物理結(jié)構(gòu)設(shè)計：(1)用T-SQL語句創(chuàng)立數(shù)據(jù)庫2用T-SQL語句創(chuàng)立所有的表及設(shè)置主鍵3用T-SQL語句給需要設(shè)外鍵的表設(shè)置外鍵4用T-SQL語句給表加上check約束、UNIQU邑勺束、DEFAULT勺束5、使用insert語句初始化數(shù)據(jù)庫給每個表至少插入5條記錄二任務(wù)描述需求分析、

6、概念結(jié)構(gòu)設(shè)計、邏輯結(jié)構(gòu)設(shè)計物理設(shè)計、初始化數(shù)據(jù)插入記錄流程限制語句與函數(shù)、視圖、索引、游標(biāo)數(shù)據(jù)查詢存儲過程、觸發(fā)器、數(shù)據(jù)備份、課程設(shè)計報告的整理和編寫六、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計參考題目類型一線性表、棧、隊列與遞歸算法設(shè)計1 .約瑟夫環(huán)問題描述約瑟夫Joeph問題的一種描述是：編號為1,2,n的n個人按順時針方向圍坐一圈,每人持有一個密碼正整數(shù).一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個人開始按順時針方向自1開始順序報數(shù),報到m時停止報數(shù).報m的人出列,將他的密碼作為新的m值,從他在順時針方向上的下一個人開始重新從1報數(shù),如此下去,直至所有人全部出列為止.試設(shè)計一個程序求出出列順序.根本要求利用單

7、向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程,按照出列的順序印出各人的編號.測試數(shù)據(jù)m的初值為20;密碼：3,1,7,2,4,8,4正確的結(jié)果應(yīng)為6,1,4,7,2,3,5.實現(xiàn)提示程序運行后首先要求用戶指定初始報數(shù)上限值,然后讀取各人的密碼.設(shè)n030.2、長整數(shù)運算問題描述設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算.根本要求利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲,每個結(jié)點含一個整型變量.任何整型變量的范圍是-215-1215-1.輸入和輸出形式：按中國對于長整數(shù)的表示習(xí)慣,每四位一組,組間用逗號隔開測試數(shù)據(jù)(1) 0;0;應(yīng)輸出“0.(2) -2345,6789;-7654,3211;應(yīng)輸出“-1,0000,00

8、00'.(3) -9999,9999;1,0000,0000,0000;應(yīng)輸出“9999,0000,0001%(4) 1,0001,000;-1,0001,0001;應(yīng)輸出“0.(5) 1,0001,0001;-1,0001,0000;應(yīng)輸出實現(xiàn)提示(1)每個結(jié)點中可以存放的最大整數(shù)為215-1=32767,才能保證兩數(shù)相加不會溢出.但假設(shè)這樣存,即相當(dāng)于按32768進制數(shù)存,在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不方便.故可以在每個結(jié)點中僅存十進制數(shù)的4位,即不超過9999的非負整數(shù),整個鏈表視為萬進制數(shù).(2)可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號.用其絕對值表示元素結(jié)點數(shù)

9、目.相加過程中不要破壞兩個操作數(shù)鏈表兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法.不能給長整數(shù)位數(shù)規(guī)定上限.選作內(nèi)容修改上述程序,使它在整型量范圍是-(2n-1)(2n-1)的計算機上都能有效地運行.其中,n是由程序讀入的參量.輸入數(shù)據(jù)的分組方法可以另行規(guī)定.3、多項式鏈?zhǔn)酱鎯Y(jié)構(gòu)及其代數(shù)運算問題描述設(shè)計并建立一個鏈?zhǔn)酱鎯Ψ峙湎到y(tǒng)來表示和操作多項式.為了防止對零和非零多項式進行不同的處理,使用帶頭結(jié)點的循環(huán)鏈表.為了充分利用多項式中不再使用的結(jié)點,維護一個可用空間表avail,把不再使用的多項式的結(jié)點鏈入其中.當(dāng)需要一個新結(jié)點時,就查看這個單鏈表avail.如果表非空,那么可以使用它

10、的一個結(jié)點.只有當(dāng)該表為空時,才使用動態(tài)存儲分配來創(chuàng)立新結(jié)點.根本要求設(shè)計多項式的存儲結(jié)構(gòu),編寫并測試以下函數(shù):a) get_node和ret_node)從/向可用空間表申請和插入一個多項式結(jié)點.b) pread,讀取一個多項式,并將其轉(zhuǎn)換成循環(huán)存儲表示.返回指向該多項式的頭結(jié)點的指針.c) pwrite)輸出多項式)采用能夠清楚顯示的形式.d) padd)計算d=a+b.不改變a和b.e) psub,計算d=a-bo不改變a和b.f) pmult)計算d=a*b.不改變a和b.g) eval,計算多項式在某點a的值,其中a是一個浮點型常量.返回結(jié)果為浮點數(shù).h) perase,把存儲表示為循

11、環(huán)鏈表的多項式返還給可用空間表.實現(xiàn)提示為了進一步簡化加法算法,把多項式的頭結(jié)點的指數(shù)域設(shè)為-1.4、稀疏矩陣的完全鏈表表示及其運算問題描述稀疏矩陣的每個結(jié)點包含down)right)row,col和value五個域.用單獨一個結(jié)點表示一個非零項,并將所有結(jié)點連接在一起,形成兩個循環(huán)鏈表.使得第一個表即行表,把所有結(jié)點根據(jù)行序(同一行內(nèi)按列序)用right域鏈接起來.使得第二個表即列表,把所有結(jié)點根據(jù)列序(同一列內(nèi)按行序)用down鏈接起來.這兩個表共用一個頭結(jié)點.另外,增加一個包含矩陣維數(shù)的結(jié)點.稀疏矩陣的這種存儲表示稱為完全鏈表表式.實現(xiàn)一個完全鏈表系統(tǒng)進行稀疏矩陣運算,并分析以下操作函數(shù)

12、的計算時間和額外存儲空間的開銷.(2)設(shè)計目的熟悉和掌握稀疏矩陣的完全鏈表表示；能夠建立并運用這種存儲結(jié)構(gòu)(3)根本要求建立一個用戶友好、菜單式系統(tǒng)進行以下操作,并使用合當(dāng)?shù)臏y試數(shù)據(jù)測試該系統(tǒng).讀取一個稀疏矩陣建立其完全鏈表表示輸出一個稀疏矩陣的內(nèi)容刪除一個稀疏矩陣兩個稀疏矩陣相加兩個稀疏矩陣相減兩個稀疏矩陣相乘稀疏矩陣的轉(zhuǎn)置(4)實現(xiàn)提示鏈表上的操作.5、實現(xiàn)簡單數(shù)字圖像處理問題描述一幅圖像就是一個從位置集到顏色集的變換.考慮二維圖像,位置集實際上就是一個矩陣,此時一幅圖像實際上就是一個內(nèi)容為顏色矩陣.如果顏色為0-255間的整數(shù),表示該位置的灰度等級,0為黑色,255為白色,此時的圖像稱為

13、灰度圖.而圖像的處理就是在該矩陣進行相關(guān)計算.一種常見的計算就是通過一點和周圍8個點的信息共同決定該點的新值：如一點的新值為該點和周圍8點顏色值之和的均值,這一操作可用下圖表不1/91/91/91/91/91/91/91/91/9圖像平滑模板顯然這樣處理后,圖像會變得平滑,因此稱為平滑操作.顯然將上述操作變?yōu)橐韵聢D時,就成為銳化操作.-1-1-1-19-1-1-1-1圖像銳化模板要求實現(xiàn)假設(shè)干根本的圖像處理操作.根本要求熟悉Windows下BMP文件的格式,能夠?qū)崿F(xiàn)其讀寫只考慮灰度圖像.實現(xiàn)圖像的平滑和銳化操作,其它處理操作選做.需用VC+作為語言.6、回文判斷問題描述試寫一個算法,判斷依次讀

14、入的一個以為結(jié)束符的字母序列,是否為形如序列1&序列2,模式的字符序列.其中序列1和序列2中都不含字符'&且序列2是序列1的逆序列.例如,'a+b&b+a'是屬該模式的字符序列,而T+3&31'那么不是.實現(xiàn)提示首先,序列1進棧,然后序列1出棧并與序列2比擬.測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定.注意測試邊界數(shù)據(jù),如序列1和序列2均為空串.7、商品貨架治理問題描述商品貨架可以看成一個棧,棧頂商品的生產(chǎn)日期最早,棧底商品的生產(chǎn)日期最近.上貨時,需要倒貨架,以保證生產(chǎn)日期較近的商品在較下的位置.根本要求針對一種特定商品,實現(xiàn)上

15、述治理過程.實現(xiàn)提示用棧模擬貨架和周轉(zhuǎn)空間.測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定.注意測試邊界數(shù)據(jù),如空棧.8、停車場治理問題描述設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道,且只有一個大門可供汽車進出.汽車在停車場內(nèi)按車輛到達時間的先后順序,依次由北向南排列(大門在最南端,最先到達的第一輛車停放在車場的最北端),假設(shè)車場內(nèi)已停滿n輛汽車,那么后來的汽車只能在門外的便道上等候,一旦有車開走,那么排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時,在它之后開入的車輛必須先退出車場為它讓路,待該輛車開出大門外,其它車輛再按原次序進入車場,每輛停放在車場的車在它離開停車場時必須按它停留的時

16、間長短交納費用.試為停車場編制按上述要求進行治理的模擬程序.測試數(shù)據(jù)設(shè)n=2,輸入數(shù)據(jù)為：('A',1,5),('A',2,10),(D,1,15),(,A3,20),(,A4,25),('A',5,30),('D',2,35),('D',4,40),('E',0,0).每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達或“離去信息、汽車牌照號及到達或離去的時刻,其中,'A'表示到達；'D'表示離去,'E'表示輸入結(jié)束.根本要求以棧模擬停車場,以隊列模擬車場外的

17、便道,根據(jù)從終端讀入的輸入數(shù)據(jù)序列進行模擬管理.每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達或“離去信息、汽車牌照號及到達或離去的時刻,對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：假設(shè)是車輛到達,那么輸出汽車在停車場內(nèi)或便道上的停車位置；假設(shè)是車離去；那么輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用(在便道上停留的時間不收費).棧以順序結(jié)構(gòu)實現(xiàn),隊列以鏈表實現(xiàn).實現(xiàn)提示需另設(shè)一個棧,臨時停放為給要離去的汽車讓路而從停車場退出來的汽車,也用順序存儲結(jié)構(gòu)實現(xiàn).輸入數(shù)據(jù)按到達或離去的時刻有序.棧中每個元素表示一輛汽車,包含兩個數(shù)據(jù)項：汽車的牌照號和進入停車場的時刻.9、電梯運行仿真程序問題描述辦公大樓有假設(shè)干

18、層例如,十層,每層有電梯,同時有步行樓梯；全樓有假設(shè)干部例如,不多于10部電梯同時供使用,電梯容量為24人,速度每上下一層需5秒,在某一層停下至少15秒.其運行狀態(tài)可分：向上、向下、停止,當(dāng)前乘客數(shù),當(dāng)前所在層數(shù).它設(shè)有一個“按鈕數(shù)組,例如第五層的按鈕按下,意味著有乘客在第5層到達目標(biāo)層,等等.在樓的每一層,有電梯數(shù),有按鈕表示有人等待向上或向下,由假設(shè)干人在等待,有假設(shè)干電梯在本層停下,等等.在大樓中包括進出的總?cè)藬?shù)不超過500人,每個人站在電梯前有個目標(biāo)層,他有一個最大的忍受等待時間,由于他可以選擇電梯或是步行走樓梯,等等.還有下面假設(shè)干假設(shè)：在每個時間段要進大樓的人數(shù)在0199之間隨機取

19、值；用電梯的每個人的目標(biāo)層在110之間取值；一個人在進電梯或改走樓梯之前的等待時間在180360秒范圍內(nèi)隨機發(fā)生；一個人到達目標(biāo)層后第二次再乘電梯中間的工作時間在4006600秒間隨機取值.根本要求編寫一個程序,模擬辦公大樓中全部電梯的工作過程.這個仿真程序可以用來監(jiān)測系統(tǒng)運行情況,改善大樓治理,它也可以看成是一種游戲程序.FLoois4535740%-000:08:000：07;000;0E:1000:Ik05:000:4也q4：一oqqEJSEI.*R*+*0口F""*口1皿,W."*Ba-9"*F4bM+fcflk*k*gappa«

20、87;i*tiFIt*.,一4«.03:-000：:02;-OQO:01:*000UEU.00:U-069ElevatcrSimulationfromLearnircC+byTomSwanTQtalInL/ft命口g#Avq#TookHunHumSwq白nd百lapsedPaopleSideBlds隔itincRidineSt&irElrFirLeftTimt0G2Z100221000000Q0&0009000001010.3503.0：01:36屏幕顯示的布局設(shè)計類型二串及其應(yīng)用1、文學(xué)研究助手問題描述文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置.試

21、寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng),稱為“文學(xué)研究助手.根本要求英文小說存于一個文本文件中.待統(tǒng)計的詞聚集合要一次輸入完畢,即統(tǒng)計工作必須在程序的一次運行之后就全部完成.程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號,格式自行設(shè)計.測試數(shù)據(jù)以你的源程序模擬英文小說,程序語言保存字集作為待統(tǒng)計的詞聚集.實現(xiàn)提示設(shè)小說中的詞匯一律不跨行.這樣,每讀入一行,就統(tǒng)計每個詞在這行中的出現(xiàn)次數(shù).出現(xiàn)位置所在行的行號可以用鏈表存儲.假設(shè)某行中出現(xiàn)了不止一次,不必存多個相同的行號類型三樹、圖及其應(yīng)用1、二叉樹的建立與遍歷問題描述建立一棵二叉樹,并對其進行遍歷先序、中序、后序,打印輸出遍歷結(jié)果.根本要求從

22、鍵盤接受輸入先序,以二叉鏈表作為存儲結(jié)構(gòu),建立二叉樹以先序來建立,并采用遞歸算法對其進行遍歷先序、中序、后序,將遍歷結(jié)果打印輸出.測試數(shù)據(jù)abciiDEiGiiFiii其中小表示空格字符那么輸出結(jié)果為：先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA選作內(nèi)容采用非遞歸算法實現(xiàn)二叉樹遍歷.2、打印二叉樹結(jié)構(gòu)問題描述按凹入表形式橫向打印二叉樹結(jié)構(gòu),即二叉樹的根在屏幕的最左邊,二叉樹的左子樹在屏幕的下邊,二叉樹的右子樹在屏幕的上邊.測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定.注意測試邊界數(shù)據(jù),如空二叉樹.3、打印樹結(jié)構(gòu)問題描述按凹入表形式打印樹形結(jié)構(gòu).測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技

23、術(shù)自己確定.注意測試邊界數(shù)據(jù),如空樹.實現(xiàn)提示(1)利用樹的先根遍歷方法；(2)利用結(jié)點的深度限制橫向位置.4、圖遍歷的演示問題描述很多涉及圖上操作的算法都是以圖的遍歷操作為根底的.試寫一個程序,演示無向圖的遍歷操作.根本要求以鄰接表為存儲結(jié)構(gòu),實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷.以用戶指定的結(jié)點為起點,分別輸出每種遍歷下的結(jié)點訪問序列和相應(yīng)生成樹的邊集.測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定.注意測試邊界數(shù)據(jù),如單個結(jié)點.實現(xiàn)提示設(shè)圖的結(jié)點不超過30個,每個結(jié)點用一個編號表示如果一個圖有n個結(jié)點,那么它們的編號分別為1,2,n.通過輸入圖的全部邊輸入一個圖,每個邊為一個數(shù)對,可以對

24、邊的輸入順序作出某種限制.注意,生成樹的邊是有向邊,端點順序不能顛倒.5、學(xué)生選課系統(tǒng)問題描述大學(xué)里實行學(xué)分制.每門課都有一定的學(xué)分.每個學(xué)生均需要修滿規(guī)定數(shù)量的課程才能畢業(yè).其中有些課程可以直接修讀,有些課程需要一定的根底知識,必須在選了其他一些課程的基礎(chǔ)上才能修讀.例如,?數(shù)據(jù)結(jié)構(gòu)?必須在選修了?程序設(shè)計根底?之后才能選修.我們稱?程序設(shè)計根底?是?數(shù)據(jù)結(jié)構(gòu)?的“先修課.假定每門課的直接先修課至多只有一門,兩門課可能存在相同的先修課.例如：課程號先修課號學(xué)分1 012 113 234 035 24上例中,1是2的先修課,即如果要選修2,那么1必定被選.根本要求學(xué)生不可能學(xué)完大學(xué)里開設(shè)的所有

25、課程,因此每個學(xué)生必須在入學(xué)時選定自己要學(xué)的課程.每個學(xué)生所修的學(xué)分?jǐn)?shù)的下限是給定的.現(xiàn)在編寫一個“學(xué)生選課系統(tǒng),任意給定一種課程體系總課程數(shù),課程之間的修讀先后制約關(guān)系,學(xué)生畢業(yè)要求修的課程學(xué)分?jǐn)?shù),該系統(tǒng)能幫助學(xué)生找出一種選課方案,使得他所選課程數(shù)目最少,并獲得畢業(yè)所需學(xué)分,并且必須滿足先修課程優(yōu)先的原那么.具體功能如下：1 .將課程體系存放為課程體系文件CourseHierarchy.txt;2 .將課程體系文件CourseHierarchy.txt轉(zhuǎn)換左孩子右兄弟二叉樹表示；3 .在此根底上對二叉樹進行先序、中序、后序遍歷.4 .給出選課方案.6、設(shè)計一個哈夫曼碼的編/譯碼系統(tǒng)根本要求該

26、系統(tǒng)應(yīng)具有以下功能：(1) I：初始化(Initialization).從終端讀入字符集大小n,以及n個字符和n個權(quán)值,建立哈夫曼樹,并將它存于文件hfmTree中.(2) E:編碼(Encoding).利用已建好的哈夫曼樹(如不在內(nèi)存,那么從文件hfmTree中讀入),對文件ToBeTran中的正文進行編碼,然后將結(jié)果存入文件CodeFile中.(3) D:譯碼(Decoding).利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼,結(jié)果存入文件TextFile中.(4) P:打印代碼文件(Print).將文件CodeFile以緊湊格式顯示在終端上,每行50個代碼.同時將此字符形式的

27、編碼文件寫入文件CodePrin中.(5) T:打印哈夫曼樹(Treeprinting).將已在中的哈夫曼樹以直觀的方式(樹或凹入表形式)顯示在終端上,同時將此字符形式的哈夫曼樹寫入文件TreePrint中.實現(xiàn)提示(1)編碼結(jié)果以文本方式存儲在文件CodeFile中.(2)用戶界面可以設(shè)計為菜單方式：顯示上述功能符號,再加上“Q',表示退出運行Quit.請用戶鍵入一個選擇功能符.此功能執(zhí)行完畢后再顯示此菜單,直至某次用戶選擇了“Q為止.(3)在程序的一次執(zhí)行過程中,第一次執(zhí)行I,D或C命令之后,哈夫曼樹已經(jīng)在內(nèi)存了,不必再讀入.每次執(zhí)行中不一定執(zhí)行I命令,由于文件hfmTree可能早

28、已建好.測試數(shù)據(jù)(1)利用下面這道題中的數(shù)據(jù)調(diào)試程序.某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符,其概率分別為0.25,0.29,0.07,0.08,0.14,0.23,0.03,0.11,試設(shè)計哈夫曼編碼.(2)用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹,并實現(xiàn)以下報文的編碼和譯碼：“THISPROGRAMISMYFAVORITE.7、校園導(dǎo)游咨詢系統(tǒng)問題描述設(shè)計一個校園導(dǎo)游程序,為來訪的客人提供信息查詢服務(wù).根本要求(1)設(shè)計學(xué)校的校園平面圖,所含景點不少于10個,以圖中頂點表示校內(nèi)各景點,存放景點名稱、代號、簡介等信息,以邊表示路徑,存放路徑長度等相關(guān)信息.(2)為來訪客人提供圖中任意

29、景點相關(guān)信息的查詢；(3)為來訪客人提供從校門口到圖中任意景點的問路查詢；8、推銷員問題：問題描述有一個推銷員要至JN(N>0)個城市去推銷產(chǎn)品,他從某個城市出發(fā),經(jīng)歷每個城市,且每個城市只能去一次,然后回到初始城市,以距離作為代價,他希望找出一個最正確路徑.這N個城市相互都有道路可通,但距離各不相同,城市個數(shù)和各個城市的相通距離可由學(xué)生自己設(shè)定.根本要求(1)可以輸入城市個數(shù)(不少于10個)、輸入城市信息和城市之間的距離(為整數(shù))；(2)根據(jù)輸入出發(fā)城市,根據(jù)城市的距離最短給出路徑選擇.(3)界面要求：有合理的提示和人機交互.9、全國交通咨詢模擬問題描述處于不同目的的旅客對交通工具有不

30、同的要求.例如,因公出差的旅客希望在旅途中的時間盡可能的短,出門旅游的游客那么期望旅費盡可能省,而老年旅客那么要求中轉(zhuǎn)次數(shù)最少.編制一個全國城市間的交通咨詢程序,為旅客提供最優(yōu)決策的交通咨詢.根本要求(1)提供對城市信息進行編輯(如：添加或刪除)的功能；(2)城市之間有兩種交通工具：火車或飛機,提供對全國城市交通圖和列車時刻表及飛機航班表進行編輯的功能.(信息的輸入方式可以是文件輸入和鍵盤輸入兩種方式)(3)提供兩種最優(yōu)決策：最快到達和最省錢到達.(選作：旅途中轉(zhuǎn)次數(shù)最少的最優(yōu)決策)(4)旅途中消耗的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間.(5)咨詢以用戶和計算機的對話方式進行.a)由用戶輸入起始站、

31、終點站、最優(yōu)決策原那么和交通工具；b)輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達,并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地.10、關(guān)鍵路徑問題問題描述設(shè)計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關(guān)鍵活動.根本要求(1)對一個描述工程的AOE網(wǎng),應(yīng)判斷其是否能夠順利進行.(2)假設(shè)該工程能順利進行,輸出完成整項工程至少需要多少時間,以及每一個關(guān)鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間.類型四查找和排序1、二叉排序樹問題描述從鍵盤讀入一組數(shù)據(jù),建立二叉排序樹并對其進行查找、遍歷、格式化打印等有關(guān)操作.根本要求建立二叉排序樹并對其進行查找,包括成功和不成功兩種情況,并給出查找長度.測試數(shù)據(jù)由學(xué)生依據(jù)軟件工程的測試技術(shù)自己確定.注意測試邊界數(shù)據(jù).選作內(nèi)容實現(xiàn)二叉排序樹的插入、刪除操作2、內(nèi)部排序算法比擬問題描述各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階,或大概執(zhí)行時間.試通過隨機的數(shù)據(jù)比擬各算法的關(guān)鍵字比擬次數(shù)和關(guān)鍵字移動次數(shù),以取得直觀感受.根本要求(1)對以下10種常用的內(nèi)部排序算法進行比擬：