【正文】 of letters assigned to that particular key. Letters are not separated from each 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十三、二叉排序樹的應(yīng)用(基于二叉排序樹的個人通信錄) 在日常生活中，個人通信錄是我們不可少的，不管是紙式的個人通信錄 還是我們手機中的個人通信錄，查尋是其最基本的操作，幾乎所有的操作都是在查尋的基礎(chǔ)上進行的，所以，查尋時間的快慢很大程度上決定了整個通信錄的性能。所以，一個有著良好界面、查尋速快的通信錄，是人們所追求的。本設(shè)計應(yīng)用折半查尋法 的技術(shù)思想進行查尋，從本思想出發(fā)，可以有兩種數(shù)據(jù)組織方式：一是應(yīng)用鏈表進行組織數(shù)據(jù)，由于折半查尋法的特殊性，所要進行查尋的數(shù)據(jù)列必須是有序的數(shù)據(jù)列，這樣要求對數(shù)據(jù)列進行排序。出于系統(tǒng)實時查尋的考慮，每次對通信錄進行改變后都得進行重新排序，這樣才能保證數(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)的成敗，所以在此進行詳細分析一下刪除操作的實現(xiàn)。 此功能函數(shù)主要應(yīng)用于刪除將要進行刪除的記錄，此操作較其它幾個操作難一點，同時也是此次設(shè)計的重點，所以，本函數(shù)的成敗可以直接影響到本次設(shè)計的成敗，同時，在進行二叉排序樹進行組織時，如果不從系統(tǒng)的整體進行考慮，只想到簡單地實現(xiàn)刪除功能，將會出現(xiàn)錯誤。 在設(shè)計初期，由于沒有考慮所有可能的情況，所以在進行刪除最后一個結(jié)點時，總會出現(xiàn)內(nèi)存不能引用的錯誤。最后想到應(yīng)用浪費一個結(jié)點空間的技術(shù)進行處理此問題，就是根結(jié)點用來保存二叉排序樹的某些信息，而不保存記錄，與我們單鏈表中的頭結(jié)點一樣，這樣做解決了上面所說的問題，同時在進行查尋雙親結(jié)點時也帶來了很大的方便。 有關(guān)二叉排序樹的刪除的有關(guān)問題，請讀者參考相關(guān)的參考文獻 ，在此不再進行說明，本節(jié)重點在于說明本課程設(shè)計中有關(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é)號不相等，且當(dāng)前結(jié)點的左右子樹為空，則返回空，結(jié)束查尋過程。 經(jīng)過對雙親結(jié)點的查尋，如果沒有此記錄，則進行提示，否則進行刪除操作 [1] [5] ，在進行刪除時，有以下幾種可能，以下操作中假設(shè)每次把要進行刪除結(jié)點進行刪除后，同時也釋放了此結(jié)點所占用的內(nèi)存空間，防止內(nèi)存在運行過程中丟失。 第一：要進行刪除的結(jié)點為葉結(jié)點，直接把其從二叉排序樹中進行刪除。 第二：此結(jié)點只有左子樹或者右子樹，這種情況下只需將只需把此結(jié)點的左子樹或者右子樹替換為雙親結(jié)點的左子樹。 第三：此結(jié)點有左子樹同時有也右子樹，此種操作比較復(fù)雜，其中有兩種方法進行刪除，本課程設(shè)計中應(yīng)用的方法是從某子樹中找出一個結(jié)點（假設(shè)為 Temp ），將其值代替要進行刪除結(jié)點的值，再把 Temp 結(jié)點進行刪除。 十四、DNA分子的最佳比對171。問題描述： DNA分子是人類遺傳信息的載體，它間接地指導(dǎo)蛋白質(zhì)的合成。DNA分子是由四種核苷酸組成的長鏈，這四種核苷酸分別是腺嘌呤核苷酸（用A代表）、鳥嘌呤核苷酸（用G代表）、胞嘧啶核苷酸（用C代表）和胸腺嘧啶核苷酸（用T代表）。習(xí)慣上用一個字符集為{A，T，C，G}的字符串來表示一個DNA分子序列，如CGTTAGA。 在生物進化過程中，DNA分子可能發(fā)生各種各樣的突變。這種突變形成了生物遺傳信息的改變，從而使生物得以分化，構(gòu)成了生物的多樣性。主要的突變有三種：（1）在一個DNA序列中插入一個新的核苷酸，（2）DNA序列中丟失了一個核苷酸，（3）DNA序列中的某個核苷酸被另一個核苷酸所取代。 所謂兩個DNA序列的一個比對是尋找一種排列方式，使得兩個DNA序列在同樣的位置上有相同的核苷酸，而若在同樣的位置上兩個DNA序列的核苷酸不同，則是由三種突變之一得到。例如，對兩個DNA序列T=ATCAG，T=ACTAG，可以按如下方式比對， 比對1： T T A A T （“”表示空白） C C T A A G G也可以按如下方式比對 比對2： T T A A T C C T A A G G如果兩個DNA序列在相同的位置上有越多相同的核苷酸對，則表明它們之間越相似，即它們存在功能上的相似性和進化史上的親緣關(guān)系。 對于兩個DNA序列的一個比對，規(guī)定如下得分方式：（1）一個同樣的位置上有相同的核苷酸對，則可得1分；（2）一個同樣的位置上有不同的核苷酸對，則得0分；（3）如果在某個位置上一個序列有核苷酸，而另一個序列在該位置上為“”，則得2分。例如，比對1的得分是0分，比對2的得分是3分。 171。編程任務(wù)：對于兩個DNA序列，尋找一種比對方式，使得它們的得分最高。171。數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為INPUT3.*的文本文件提供，共有2行。第1行為DNA序列T, 第2行為DNA序列T。序列的長度不大于5000。序列中的字母是英文小寫或者大寫字母。171。結(jié)果輸出:程序運行結(jié)束時，在屏幕上輸出兩個DNA序列比對的最高得分。輸入文件示例輸出示例AtcagActag3Human Gene Functions Time 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 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 timeconsuming biological experiments, often with the help of puter 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 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 databas