數(shù)據(jù)結(jié)構(gòu)課程課外實踐任務(wù)

1、 . . . 數(shù)據(jù)結(jié)構(gòu)課程課外實踐安排（2012-2013學(xué)年第一學(xué)期）課外實踐學(xué)時：32學(xué)時課外實踐目的：綜合應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程中所學(xué)的數(shù)據(jù)結(jié)構(gòu)：線性表、棧、隊列、串、數(shù)組、廣義表、樹、二叉樹、圖、查找表中的一種或多種數(shù)據(jù)結(jié)構(gòu)完成一個較大問題的求解（其實這里的問題也并不太大，所用的數(shù)據(jù)結(jié)構(gòu)可能是其中的多個，也可能是其中的一個兩個）。從而培養(yǎng)學(xué)生綜合應(yīng)用基本數(shù)據(jù)結(jié)構(gòu)分析、解決實際問題的能力，并進一步加深對所學(xué)知識的理解和掌握。課外實踐要求：1、課外實踐以組為單位開展，每組35名同學(xué)，自由組合，確定組長一名。2、每組從附件1列出的題目中任意選擇其中一個完成（鼓勵大家選擇對你自己而言有一定挑戰(zhàn)性的題

2、目），每個題目最多由3組同學(xué)選做。強調(diào)獨立思考，組分工明確，每組自己完成。3、鼓勵大家參考教材上、參考書上和所選題目相關(guān)的容和算法。不鼓勵大家一拿到實驗題目就去網(wǎng)上或參考書上找相關(guān)程序源代碼，通過思考該問題并最終解決該問題不僅可以鍛煉大家，從而提高大家的水平，而且大家對該問題的解決也會有成就感！4、實現(xiàn)你所選題目要求的功能，并能夠進行較完善友好的輸入輸出驗證。5、完成你所選的課外實踐題目后，就該題目給出設(shè)計報告（設(shè)計報告格式另給），并按時上交。6、每組同學(xué)須仔細(xì)閱讀所選題目的要求，認(rèn)真主動完成設(shè)計要求。有問題與時主動通過各種方式與教師聯(lián)系溝通。同學(xué)們要發(fā)揮自主學(xué)習(xí)的能力，充分利用課外時間，安排

3、好課外實踐的時間，并在設(shè)計過程中不斷檢測自己的計劃完成情況，與時的向教師匯報。 課外實踐按照教學(xué)要求需要思考和上機調(diào)試程序至少32學(xué)時，代碼量要求在6003000行。7、課外實踐的考核需要按組進行答辯，安排在第16周或17周進行。附件1：數(shù)據(jù)結(jié)構(gòu)課程課外實踐可選題目一、運動會分?jǐn)?shù)統(tǒng)計系統(tǒng) 任務(wù)：參加運動會有n個學(xué)校，學(xué)校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20） 功能要求

4、：1).可以輸入各個項目的前三名或前五名的成績； 2)能統(tǒng)計各學(xué)?？偡郑?3)可以按學(xué)校編號、學(xué)?？偡帧⒛信畧F體總分排序輸出； 4).可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。 規(guī)定：輸入數(shù)據(jù)形式和圍：20以的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運動項目的名稱） 輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整數(shù) 界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。 存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料

5、中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)與測試結(jié)果請在上交的資料中寫明；二、學(xué)籍信息管理實驗?zāi)康木C合考察數(shù)據(jù)存儲、以與對各種存儲結(jié)構(gòu)的建立、插入、刪除、排序、查找等操作。實驗要求設(shè)計一個簡單的學(xué)籍管理系統(tǒng)。包括建立、插入、修改，查找、輸出、排序（按不同關(guān)鍵字）實驗容1. 從學(xué)生基本信息文件讀入數(shù)據(jù)以建立學(xué)籍信息。下面是一個例子：學(xué)號 性別 宿舍 07011001 成成 男 501 87732111 07011002 成華 女 101 87723112 07011003 王成鳳 女 101 87723

6、112 07011004 明明 男 502 87734333 07011005 東 男 501 87732111 每個學(xué)生信息至少包括：學(xué)號、性別。文件至少包括10個學(xué)生。2. 從學(xué)生成績信息文件讀入其容建立學(xué)生的成績信息。以下一個例子：（至少包含20項信息）學(xué)號 課程編號 課程名稱 學(xué)分平時成績 實驗成績 卷面成績 綜合成績 實得學(xué)分 07011001 A01 大學(xué)物理 3 66 78 82 07011002 B03 高等數(shù)學(xué) 4 78 -1 90 07011001 B03 高等數(shù)學(xué) 4 45 -188 07011002 C01VF 3 65 7666功能要求極其說明： （1）數(shù)據(jù)錄入功能：

7、錄入每個學(xué)生的學(xué)號、課程編號、課程名稱、學(xué)分、平時成績、實驗成績、卷面成績共7個數(shù)據(jù)。實得成績、實得學(xué)分根據(jù)條件自動運算。 綜合成績的計算： a.如果本課程的實驗成績?yōu)?1，則表無實驗成績，綜合成績=平時成績*30%+卷面成績*70% b.如果實驗成績不為-1，表示本課程有實驗成績，綜合成績=平時成績*15%+實驗成績*15%+卷面成績*70%實得學(xué)分的計算：采用等級學(xué)分制。 綜合成績在90100之間，應(yīng)得學(xué)分=學(xué)分*100% 綜合成績在8090之間，應(yīng)得學(xué)分=學(xué)分*80% 綜合成績在7080之間，應(yīng)得學(xué)分=學(xué)分*75% 綜合成績在6070之間，應(yīng)得學(xué)分=學(xué)分*60% 綜合成績在60分以下，應(yīng)

8、得學(xué)分=學(xué)分*0%3. 查詢功能：分為學(xué)生基本情況查詢和成績查詢兩種 4. 刪除功能：根據(jù)輸入的學(xué)生或?qū)W好刪除相應(yīng)的學(xué)生信息。5. 排序功能：能實現(xiàn)選擇按綜合成績或?qū)嵉脤W(xué)分升序或降序排序并顯示數(shù)據(jù)。三、隊列應(yīng)用（用隊列模擬超市交款處的顧客流）使用一個隊列模擬一隊通過丹尼斯超市交款處的顧客流。為了創(chuàng)建這個模擬，我們必須模擬排隊時間和顧客通過流。我們可以通過一個循環(huán)模擬時間，每通過一個顧客代表一定的時間間隔例如，一分鐘。我們可以使用一個隊列模擬顧客流，隊列中的一個數(shù)據(jù)項代表一位顧客。為了完成這個模擬，我們需要知道顧客加入交款處隊列的頻率、交款結(jié)算服務(wù)情況和離開的頻率。假設(shè)交款隊列有以下屬性。

9、83; 每分鐘有一個顧客完成交款并離開（假設(shè)此時至少有一個顧客等待服務(wù)）。 · 每分鐘有零個到兩個顧客加入，沒有顧客到達的概率是50% , 一個顧客到達的概率是 25 % ，兩個顧客到達的概率是 25 。（如何模擬？）我們可以使用下面的算法模擬一個時間段 n 分鐘的顧客流。初始化隊列為空。for （minute = 0 ; minute < n ; + + minute） 如果隊列不空，對頭顧客交款并離開（即出對）；產(chǎn)生一個0-3圍的隨機數(shù)k；如果k=1，一個顧客加入交款隊列（入對）；如果k=2，兩個顧客加入交款隊列（入對）；如果k=0或3，不增加任何顧客到交款隊列； 調(diào)用 r

10、and ( ）函數(shù)是產(chǎn)生偽隨機數(shù)的一種簡單的方法,rand函數(shù)在<stdlib.h>中。我們的模擬程序應(yīng)該在每一個模擬分鐘期間更新下列信息，即每一次通過循環(huán)。· 完成交款服務(wù)的總顧客數(shù)· 這些顧客花費在排隊等待的時間總和· 顧客花費在排隊等待的最長時間為了計算顧客等待的時間長度，我們需要存儲“minute”，作為這個客戶隊列數(shù)據(jù)項的一部分，表示顧客加入的時間。如果你使用程序模擬一列顧客流，試著完成下面的表格。請注意，平均等待時間是等待時間總和除以總的服務(wù)顧客數(shù)。時間（分鐘） 總的顧客服務(wù)時間 平均等待時間 最長等待時間3060120480四、應(yīng)用哈夫曼

11、樹實現(xiàn)文件的壓縮 實驗?zāi)康模赫莆斩鏄涞逆準(zhǔn)酱鎯Y(jié)構(gòu)和常用算法。利用哈夫曼樹設(shè)計最優(yōu)壓縮編碼。實驗容：1) 編寫函數(shù)，實現(xiàn)建立哈夫曼樹和顯示哈夫曼樹的功能。2) 編寫函數(shù)，實現(xiàn)生成哈夫曼編碼的功能。3) 編寫主函數(shù)，從終端輸入一段英文文本；統(tǒng)計各個字符出現(xiàn)的頻率，然后構(gòu)建哈夫曼樹并求出對應(yīng)的哈夫曼編碼；顯示哈夫曼樹和哈夫曼編碼。選做容：修改程序，選擇實現(xiàn)以下功能：4) 編碼：用哈夫曼編碼對一段英文文本進行壓縮編碼，顯示編碼后的文本編碼序列；5) 統(tǒng)計：計算并顯示文本的壓縮比例；6) 解碼：將采用哈夫曼編碼壓縮的文本還原為英文文本。 算法說明：1) 二叉樹和哈夫曼樹的相關(guān)算法見講義。2) 編碼的

12、方法是：從頭開始逐個讀取文本字符串中的每個字符，查編碼表得到它的編碼并輸出。重復(fù)處理直至文本結(jié)束。3) 解碼的方法是：將指針指向哈夫曼樹的樹根，從頭開始逐個讀取編碼序列中的每位，若該位為1則向右子樹走，為0則向左子樹走。當(dāng)走到葉子節(jié)點時，取出節(jié)點中的字符并輸出。重新將指針放到樹根，繼續(xù)以上過程直至編碼序列處理完畢。4) 壓縮比例的計算：編碼后的文本長度為編碼序列中的0和1的個數(shù)，原文本長度為字符數(shù)*8。兩者之比即為壓縮比。五、數(shù)據(jù)壓縮實驗?zāi)康?）調(diào)研數(shù)據(jù)壓縮原理與相關(guān)算法的實現(xiàn)；2）實現(xiàn)一個壓縮/解壓縮程序?qū)嶒炓?. 閱讀相關(guān)資料，理解數(shù)據(jù)壓縮的意義和過程。2. 調(diào)研幾個著名的數(shù)據(jù)壓縮算法，

13、寫一份調(diào)研報告，說明其算法與所使用的數(shù)據(jù)結(jié)構(gòu)。3. 實現(xiàn)一個壓縮/解壓縮程序，算法任意。4. 程序要求：控制臺界面。首先實現(xiàn)對單文件壓縮的功能。命令行格式：壓縮： 程序名 -c 輸入文件 輸出文件名解壓縮： 程序名 -d 輸入文件 輸出文件名里容表示可選。控制臺輸出：壓縮： 原始文件大小、壓縮后文件大小、壓縮比例、消耗時間解壓縮： 解壓前文件大小，解壓后文件大小、壓縮比例、消耗時間選做：1）將多個文件壓縮到一個文件；2）檢查壓縮文件完整性，測試其能夠完成解壓縮；3）對文件測試，不壓縮，輸入其若壓縮后的壓縮率；4）列出壓縮文件所包含的文件名；4）實現(xiàn)對整個目錄進行壓縮的功能。文件格式：對壓縮文件

14、起一個后綴名。若在命令行中沒指定輸入文件的話，輸出文件名應(yīng)該是 輸入文件名+.后綴名 的格式；若在命令行中指定輸出文件名的話，后綴也應(yīng)自動加上。實現(xiàn)的壓縮比例越高、壓縮事件越短越好。六、HTML文件中有序列表的語法樹提取與基于樹的檢索實驗說明HTML語言用來描述Web文檔的通用格式和布局。詳細(xì)的介紹可以參照一些書本或者網(wǎng)上資料。HTML中基本的語法單位稱為標(biāo)簽?？偟膩碚f，標(biāo)簽用于指定容的類別。對于每個類別，針對特定的容，瀏覽器都有默認(rèn)的顯示方式。標(biāo)簽的使用語法是利用一對尖括號“<>”將標(biāo)簽名稱包圍起來。大部分標(biāo)簽都是成對的：包括開始標(biāo)簽和結(jié)束標(biāo)簽，如<html>和<

15、;/html>。開始標(biāo)簽和結(jié)束標(biāo)簽之間的信息稱為標(biāo)簽的容。這里僅考慮一個HTML語言的子集，該子集包含以下標(biāo)簽：<html>, </html>：標(biāo)識文檔的根元素；<head>, </head>：包含了文檔的頭部分，該部分提供了文檔的相關(guān)信息，而沒有提供文檔的容；<title>, </title>：文檔的標(biāo)題元素，其容顯示在瀏覽器的頂部；<body>, </body>：文檔的主體部分，提供了文檔的容；<ol>, </ol>：有序列表標(biāo)簽，用于創(chuàng)建有序列表，列表中的條目是通

16、過標(biāo)簽<li>, </li>指定的?？梢郧短子行蛄斜?lt;ol>。標(biāo)簽<ol>后不能直接嵌套<ol>，而必須通過<li>嵌套。例如，下面的示例演示了嵌套的有序列表：<html><head><title> test for nested lists </title></head><body><ol><li>Section 1<ol><li>Section 1.1</li><li>Sect

17、ion 1.2</li></ol></li><li>Section 2</li></ol></body></html>顯示結(jié)果是：1. AnhuiProvince1. City Hefei2. City Wuhu2. Shanghai對應(yīng)的語法樹為：Anhui ProvinceShanghaiCity HefeiCity Wuhu圖2.1通過上面的HTML語言子集，可以設(shè)計結(jié)構(gòu)化的Web文檔。對于這樣的文檔，我們可以提取其結(jié)構(gòu)信息，建立對應(yīng)的結(jié)構(gòu)化數(shù)據(jù)存儲，并可以在此基礎(chǔ)上進一步做相應(yīng)應(yīng)用如查詢操作

18、等。實驗?zāi)康氖炀殤?yīng)用線性結(jié)構(gòu)、樹等數(shù)據(jù)結(jié)構(gòu)。實驗容1. 根據(jù)前面介紹的HTML語言子集，編寫合法的文檔，作為輸入文件。也可以使用附錄中所給的容建立文檔作為輸入；2. 然后用相應(yīng)算法提取其結(jié)構(gòu)化信息，生成如圖2.1的樹形結(jié)構(gòu)。3. 在已經(jīng)建立的結(jié)構(gòu)化存儲數(shù)據(jù)結(jié)構(gòu)上，做單詞查詢操作。輸入一個查詢關(guān)鍵字（如”City”），要求返回所有匹配的單詞所在原HTML文檔中的位置信息（如，City: Section 1.2 the first word and Section 1.2 the first word）。4. 下面給出一個實現(xiàn)的算法。這里考慮一個簡單的情況，即<body>中只有一個有向

19、列表，對于<body>標(biāo)簽中有多個列表的情況，通過簡單的修改此算法可以解決：1） 對于這樣一個HTML文檔，<html>, <head>, <title>是無關(guān)緊要的，在讀取文檔容時可以忽略。核心的結(jié)構(gòu)化信息在有序列表中。2） 遇到第一個<ol>時，生成頭節(jié)點，頭節(jié)點容為空，curParent=curNode都指向該節(jié)點；3） 每當(dāng)遇到一個<li>，生成curParent指向的節(jié)點的一個子節(jié)點curNode，<li>后容即為該節(jié)點的容；4） 每當(dāng)遇到一個<ol>，curParent=curNode，

20、準(zhǔn)備以curParent為根的子樹（遞歸操作）；5） 每當(dāng)遇到一個</li>，則curNode指向的節(jié)點生成完畢（即不再往下遞歸地生成子樹），繼續(xù)讀文件（注意，</ol>后的第一個</li>應(yīng)忽略，因為</ol>其后必然有一個</li>）；6） 每當(dāng)遇到一個</ol>，則以curParent 為根的子樹生成完畢，curParent=curParent->parent；7） 當(dāng)讀到</body>時，整個樹生成完畢，返回其頭指針。針對前面示例的html文件，其語法樹生成過程圖示如下：1curParentcur

21、NodeAnhui Province12curParentcurNode(a) 讀到第一個<ol>，生成空的頭節(jié)點1 。 (b) 讀到<ol>后第一個<li>，生成第一個 子節(jié)點2，并將<li>其后容作為節(jié)點容。Anhui Province123City HefeicurParentcurNodeCity WuhuCity HefeiAnhui Province1234curParentcurNode(c) 遇到<ol>，curParent=curNode，準(zhǔn)備 (d) 再次讀到<li>，生成以curParent以curP

22、arent為根生成子樹；讀到<li>，生 為根的子節(jié)點4；讀到</li>，非</ol>成以curParent為根的子節(jié)點3；讀到</li> 后第一個</li>，curNode指向的節(jié)點，非</ol>后的第一個</li>，curNode指向 生成完畢。的節(jié)點生成完畢。 Anhui ProvinceCity WuhuCity Hefei1234curParentcurNodeAnhui ProvinceCity WuhuCity HefeiShanghai1234curParentcurNode5(e) 讀到<

23、;/ol>，則以curParent為根的子樹 (f) 讀到<li>，生成以curParent為根的生成完畢，curParent=curParent->parent， 子節(jié)點5，容為”Section 2”；再讀到即curParent從2變?yōu)?；再往下讀到</li>， </li>，curNode節(jié)點生成結(jié)束；讀到此為</ol>后第一個</li>，忽略掉，繼續(xù)往后 </ol>，以curParent（節(jié)點1）為根的讀文件。 子樹生成完畢；讀到</body>，整個樹 生成完畢，返回頭指針。六、迷宮問題。傳說在

24、遠(yuǎn)古時候，米諾斯國王統(tǒng)治著愛琴端的克里特島。他建造了一座有無數(shù)宮室的迷宮，在迷宮中喂養(yǎng)了一頭人身牛頭的惡獸米諾牛。為了供奉它，米諾斯要希臘的雅典每九年進貢七對童男女喂米諾牛。當(dāng)時，雅典有位名叫忒休斯的王子，他不忍人民遭受這種災(zāi)難，毅然決定跟隨第四批被進貢的童男女去克里特殺死米諾牛。在克里特，英勇的忒休斯贏得了米諾斯的女兒的愛慕。她交給忒休斯一個線團，讓他按下面規(guī)則邊走邊放線：（1）每到一個岔口，找沒有鋪上線的路走；若找不到未鋪上線的路，就沿原來的路返回到前一個岔口。（2）不走已鋪上兩條線的路。用這種方法，忒休斯終于殺死米諾牛，勝利的走出迷宮七、學(xué)生數(shù)據(jù)結(jié)構(gòu)成績管理系統(tǒng)基本要求(1)學(xué)生信息與成

25、績的錄入要求包括的學(xué)生信息有：學(xué)號、性別、出生日期、民族與數(shù)據(jù)結(jié)構(gòu)成績（具體容可自行假設(shè)，至少錄入10名以上學(xué)生）所錄入的學(xué)生按學(xué)號散列存儲（散列函數(shù)為：學(xué)號%5 取整，如 1002%5 =2），采用拉鏈法解決沖突。(2)學(xué)生成績的查詢要求根據(jù)提供的學(xué)號完成學(xué)生成績的查詢（必須采用哈希查找）(3)學(xué)生成績的分段統(tǒng)計和排序輸出統(tǒng)計出各分?jǐn)?shù)段學(xué)生人數(shù)（60分以下，6070，7180，.)采用任何一種排序方法，將學(xué)生成績從高到低排序輸出八、哈希表應(yīng)用問題描述針對某個集體中人名設(shè)計一個哈希表，使得平均查找長度不超過R，并完成相應(yīng)的建表和查表程序?；疽蠹僭O(shè)人名為中國人的漢語拼音形式。待填入哈希表的人

26、名共有300個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列法或鏈地址法處理沖突。測試數(shù)據(jù)取讀者周圍較熟悉的300個人名。選作容（1） 從教科書上介紹的集中哈希函數(shù)構(gòu)造方法中選出適用者并設(shè)計幾個不同的哈希函數(shù)，比較他們的地址沖突率（可以用更大的名字集進行實驗）。（2） 研究這300個人名的特點，努力找一個哈希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。（3） 在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希表中關(guān)鍵字的聚集性。九、部排序算法比較問題描述各種部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過

27、隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。基本要求（1） 對以下10種常用的部排序算法任意選擇6種進行比較：直接插入排序；折半折入排序；二路插入排序；希爾排序；起泡排序；快速排序；簡單選擇排序；堆排序；歸并排序；基數(shù)排序。（2） 待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字移動次數(shù)（關(guān)鍵字交換計為3次移動）。測試數(shù)據(jù)由隨機產(chǎn)生器決定。實現(xiàn)提示主要工作是設(shè)法在程序中適當(dāng)?shù)牡胤讲迦胗嫈?shù)操作。程序還可以包括計算幾組數(shù)據(jù)得出結(jié)果波動大小的解釋。注意分塊調(diào)試的方法。十、校園導(dǎo)游程序

28、問題描述用無向網(wǎng)表示師學(xué)院校園景點或建筑物平面圖，圖中頂點表示主要景點或建筑物，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關(guān)景點介紹、游覽路徑等問題?；疽螅?） 查詢各景點的相關(guān)信息；（2） 查詢圖中任意兩個景點間的最短路徑。（3） 查詢圖中任意兩個景點間的所有路徑。（4） 增加、刪除、更新有關(guān)景點和道路的信息。（5） 求多個景點的最佳（最短）游覽路徑。十一、實現(xiàn)第7章圖中的部分算法，這些算法至少包括以下兩組：（1） 深度和廣度優(yōu)先搜索遍歷圖；（2） 構(gòu)造最小生成樹的兩種算法（3） 拓?fù)渑判蛩惴?；?） 求解關(guān)鍵路徑；（5） 求解最短路徑

29、。十二、合理設(shè)計手機鍵盤題意描述我們的手機鍵盤上將26個字母如下左圖設(shè)置在8個鍵盤上，但每個字母的按鍵頻率是不同的，因此如果按照右圖的方式設(shè)置字母在鍵盤上的相對位置可能會使所有字母的按鍵頻率與按鍵次數(shù)乘積之和達到最小，從而更加方便客戶使用。我們的任務(wù)是根據(jù)輸入的鍵盤數(shù)和字符數(shù)與每個字符的使用頻率來確定最合理的分配方式，使分配后所有字符的頻率和按鍵次數(shù)的乘積之和最小。在每個鍵盤上，處于第i個位置上的字符按鍵次數(shù)為i，在分配的過程中我們不能更改字符的相對位置。該題目詳細(xì)描述如下：I-KeyboardTime Limit: 2000MSMemory Limit: 32768KTotal Submis

30、sions: 3235Accepted: 1690DescriptionMost of you have probably tried to type an SMS message on the keypad of a cellular phone. It is sometimes very annoying to write longer messages, because one key must be usually pressed several times to produce a single letter. It is due to a low number of keys on

31、 the keypad. Typical phone has twelve keys only (and maybe some other control keys that are not used for typing). Moreover, only eight keys are used for typing 26 letters of an English alphabet. The standard assignment of letters on the keypad is shown in the left picture: 1 2abc3def4ghi5jkl6mn

32、o7pqrs8tuv9wxyz* 0space#       1 2abcd3efg4hijk5lm6nopq7rs8tuv9wxyz* 0space# There are 3 or 4 letters assigned to each key. If you want the first letter of any group, you press that key once. If you want the second letter, you have to press the

33、key twice. For other letters, the key must be pressed three or four times. The authors of the keyboard did not try to optimise the layout for minimal number of keystrokes. Instead, they preferred the even distribution of letters among the keys. Unfortunately, some letters are more frequent than othe

34、rs. Some of these frequent letters are placed on the third or even fourth place on the standard keyboard. For example, S is a very common letter in an English alphabet, and we need four keystrokes to type it. If the assignment of characters was like in the right picture, the keyboard would be much m

35、ore comfortable for typing average English texts. ACM have decided to put an optimised version of the keyboard on its new cellular phone. Now they need a computer program that will find an optimal layout for the given letter frequency. We need to preserve alphabetical order of letters, because the u

36、ser would be confused if the letters were mixed. But we can assign any number of letters to a single key. InputThere is a single positive integer T on the first line of input. It stands for the number of test cases to follow. Each test case begins with a line containing two integers K, L (1 <= K

37、<= L <= 90) separated by a single space. K is the number of keys, L is the number of letters to be mapped onto those keys. Then there are two lines. The first one contains exactly K characters each representing a name of one key. The second line contains exactly L characters representing names

38、 of letters of an alphabet. Keys and letters are represented by digits, letters (which are case-sensitive), or any punctuation characters (ASCII code between 33 and 126 inclusively). No two keys have the same character, no two letters are the same. However, the name of a letter can be used also as a

39、 name for a key. After those two lines, there are exactly L lines each containing exactly one positive integer F1, F2, . FL. These numbers determine the frequency of every letter, starting with the first one and continuing with the others sequentially. The higher number means the more common letter.

40、 No frequency will be higher than 100000. OutputFind an optimal keyboard for each test case. Optimal keyboard is such that has the lowest "price" for typing average text. The price is determined as the sum of the prices of each letter. The price of a letter is a product of the letter frequ

41、ency (Fi) and its position on the key. The order of letters cannot be changed, they must be grouped in the given order. If there are more solutions with the same price, we will try to maximise the number of letters assigned to the last key, then to the one before the last one etc. More formally, you

42、 are to find a sequence P1, P2, . PL representing the position of every letter on a particular key. The sequence must meet following conditions: P1 = 1 for each i>1, either Pi = Pi-1+1 or Pi = 1 there are at most K numbers Pi such that Pi = 1 the sum of products SP = F1*P1+F2*P2+.+FL*PL is minima

43、l for any other sequence Q meeting these criteria and with the same sum SQ = SP, there exists such M, 1 <= M <= L that for any J, M < J <= L, PJ = QJ, and PM > QM. The output for every test case must start with a single line saying Keypad #I:, where I is a sequential order of the test

44、 case, starting with 1. Then there must be exactly K lines, each representing one letter, in the same order that was used in input. Each line must contain the character representing the key, a colon, one space and a list of letters assigned to that particular key. Letters are not separated from each

45、 other. Print one blank line after each test case, including the last one. Sample Input18 2623456789ABCDEFGHIJKLMNOPQRSTUVWXYZ337158915751614621297177319042989123209158815132996326910801212726308343681334518752427733871Sample OutputKeypad #1:2: ABCD3: EFG4: HIJK5: LM6: NOPQ7: RS8: TUV9: WXYZ十三、二叉排序樹

46、的應(yīng)用(基于二叉排序樹的個人通信錄)     在日常生活中，個人通信錄是我們不可少的，不管是紙式的個人通信錄還是我們手機中的個人通信錄，查尋是其最基本的操作，幾乎所有的操作都是在查尋的基礎(chǔ)上進行的，所以，查尋時間的快慢很大程度上決定了整個通信錄的性能。所以，一個有著良好界面、查尋速快的通信錄，是人們所追求的。本設(shè)計應(yīng)用折半查尋法的技術(shù)思想進行查尋，從本思想出發(fā)，可以有兩種數(shù)據(jù)組織方式：一是應(yīng)用鏈表進行組織數(shù)據(jù)，由于折半查尋法的特殊性，所要進行查尋的數(shù)據(jù)列必須是有序的數(shù)據(jù)列，這樣要求對數(shù)據(jù)列進行排序。出于系統(tǒng)實時查尋的考慮，每次對通信錄進行改變后都得進行重

47、新排序，這樣才能保證數(shù)據(jù)列是實時有序的。這樣當(dāng)操作量大時，排序所消耗的時間對整個系統(tǒng)有很大的影響。二是應(yīng)用二叉排序樹來組織數(shù)據(jù)，由于二叉排序樹是應(yīng)用折半查尋法思想進行對數(shù)據(jù)進行存儲的，所以，其左孩子大于雙親結(jié)點、右孩子小于雙親結(jié)點（或者左孩子小于雙親結(jié)點、右孩子大于雙親結(jié)點），這樣就可以應(yīng)用折半查尋法的思想進行查尋，從而減少對排序時所消耗的時間。本設(shè)計采用第二種方法，即應(yīng)用二叉排序樹進行組織數(shù)據(jù)，在此基礎(chǔ)上進行對個人通信錄的各種操作。由于刪除操作是本設(shè)計的重點，刪除操作的成功與否直接影響到整個系統(tǒng)的成敗，所以在此進行詳細(xì)分析一下刪除操作的實現(xiàn)。此功能函數(shù)主要應(yīng)用于刪除將要進行刪除的記錄，此操作

48、較其它幾個操作難一點，同時也是此次設(shè)計的重點，所以，本函數(shù)的成敗可以直接影響到本次設(shè)計的成敗，同時，在進行二叉排序樹進行組織時，如果不從系統(tǒng)的整體進行考慮，只想到簡單地實現(xiàn)刪除功能，將會出現(xiàn)錯誤。在設(shè)計初期，由于沒有考慮所有可能的情況，所以在進行刪除最后一個結(jié)點時，總會出現(xiàn)存不能引用的錯誤。最后想到應(yīng)用浪費一個結(jié)點空間的技術(shù)進行處理此問題，就是根結(jié)點用來保存二叉排序樹的某些信息，而不保存記錄，與我們單鏈表中的頭結(jié)點一樣，這樣做解決了上面所說的問題，同時在進行查尋雙親結(jié)點時也帶來了很大的方便。有關(guān)二叉排序樹的刪除的有關(guān)問題，請讀者參考相關(guān)的參考文獻，在此不再進行說明，本節(jié)重點在于說明本課程設(shè)計中

49、有關(guān)刪除的問題。在本設(shè)計中，刪除的首要條件是找到將要進行刪除結(jié)點的雙親結(jié)點，由于根結(jié)點不用于存儲記錄，所以，可以不用進行判斷根結(jié)點的情況，進行查尋雙親結(jié)點時，從根結(jié)點開始，首先進行判斷根結(jié)點的左右子樹是否為空，如果根結(jié)點的左右子樹為空，則返回NULL，如果根結(jié)點的左子樹（右子樹）不為空，則將其左子樹（右子樹）的記錄的學(xué)號與將要進行刪除的學(xué)號進行比較，如果相等，則返回根結(jié)點；否則進行比較，如果左子樹（右子樹）不為空，且左子樹（右子樹）的學(xué)號大于（小于）要進行刪除的學(xué)號，則進行遞歸在左子樹（右子樹）中進行查尋，直到查尋到或者當(dāng)前結(jié)點的左右子樹為空時結(jié)束。如果當(dāng)前結(jié)點的學(xué)號與要進行刪除的學(xué)號不相等，

50、且當(dāng)前結(jié)點的左右子樹為空，則返回空，結(jié)束查尋過程。經(jīng)過對雙親結(jié)點的查尋，如果沒有此記錄，則進行提示，否則進行刪除操作1 5 ，在進行刪除時，有以下幾種可能，以下操作中假設(shè)每次把要進行刪除結(jié)點進行刪除后，同時也釋放了此結(jié)點所占用的存空間，防止存在運行過程中丟失。第一：要進行刪除的結(jié)點為葉結(jié)點，直接把其從二叉排序樹中進行刪除。第二：此結(jié)點只有左子樹或者右子樹，這種情況下只需將只需把此結(jié)點的左子樹或者右子樹替換為雙親結(jié)點的左子樹。第三：此結(jié)點有左子樹同時有也右子樹，此種操作比較復(fù)雜，其中有兩種方法進行刪除，本課程設(shè)計中應(yīng)用的方法是從某子樹中找出一個結(jié)點（假設(shè)為Temp），將其值代替要進行刪除結(jié)點的值

51、，再把 Temp 結(jié)點進行刪除。十四、DNA分子的最佳比對«問題描述：DNA分子是人類遺傳信息的載體，它間接地指導(dǎo)蛋白質(zhì)的合成。DNA分子是由四種核苷酸組成的長鏈，這四種核苷酸分別是腺嘌呤核苷酸（用A代表）、鳥嘌呤核苷酸（用G代表）、胞嘧啶核苷酸（用C代表）和胸腺嘧啶核苷酸（用T代表）。習(xí)慣上用一個字符集為A，T，C，G的字符串來表示一個DNA分子序列，如CGTTAGA。 在生物進化過程中，DNA分子可能發(fā)生各種各樣的突變。這種突變形成了生物遺傳信息的改變，從而使生物得以分化，構(gòu)成了生物的多樣性。主要的突變有三種：（1）在一個DNA序列中插入一個新的核苷酸，（2）DNA序列中丟失了一

52、個核苷酸，（3）DNA序列中的某個核苷酸被另一個核苷酸所取代。 所謂兩個DNA序列的一個比對是尋找一種排列方式，使得兩個DNA序列在同樣的位置上有一樣的核苷酸，而若在同樣的位置上兩個DNA序列的核苷酸不同，則是由三種突變之一得到。例如，對兩個DNA序列T=ATCAG，T=ACTAG，可以按如下方式比對， 比對1： TT A A T - （“-”表示空白） C C - T A A G G也可以按如下方式比對 比對2： TT A A T C C T A A G G如果兩個DNA序列在一樣的位置上有越多一樣的核苷酸對，則表明它們之間越相似，即它們存在功能上的相似性和進化史上的親緣關(guān)系。 對于兩個DN

53、A序列的一個比對，規(guī)定如下得分方式：（1）一個同樣的位置上有一樣的核苷酸對，則可得1分；（2）一個同樣的位置上有不同的核苷酸對，則得0分；（3）如果在某個位置上一個序列有核苷酸，而另一個序列在該位置上為“-”，則得-2分。例如，比對1的得分是0分，比對2的得分是3分。«編程任務(wù)：對于兩個DNA序列，尋找一種比對方式，使得它們的得分最高。«數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為INPUT3.*的文本文件提供，共有2行。第1行為DNA序列T, 第2行為DNA序列T。序列的長度不大于5000。序列中的字母是英文小寫或者大寫字母。«結(jié)果輸出:程序運行結(jié)束時，在屏幕上輸出兩個DNA序

54、列比對的最高得分。輸入文件示例輸出示例INPUT3.001AtcagActag3Human Gene FunctionsTime Limit:1000MS  Memory Limit:10000KTotal Submit:2255 Accepted:1440DescriptionIt is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and

55、T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them. A human gene can be identified through a series of time-consuming biological experiments, often with the help of compu

56、ter programs. Once a sequence of a gene is obtained, the next job is to determine its function. One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched

57、 stores many gene sequences and their functions many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet. A database search will return a list of gene sequences from the database that are similar to the query gene. Biologists assume that sequence similarity often implies functional similarity. S