數(shù)據(jù)結(jié)構(gòu)課程課外實(shí)踐任務(wù)-資料下載頁(yè)
2025-06-17 16:16本頁(yè)面
【正文】 e that are similar to the query gene. Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed. Your job is to make a program that pares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one. Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of the genes to make them equally long and score the resulting genes according to a scoring matrix. For example, one space is inserted into AGTGATG to result in AGTGATG, and three spaces are inserted into GTTAG to result in –GTTAG. A space is denoted by a minus sign (). The two genes are now of equal length. These two strings are aligned: AGTGATG GTTAG In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix. denotes that a spacespace match is not allowed. The score of the alignment above is (3)+5+5+(2)+(3)+5+(3)+5=9. Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions): AGTGATG GTTAG This alignment gives a score of (3)+5+5+(2)+5+(1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the similarity of the two genes is 14. InputThe input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100. OutputThe output should print the similarity of each test case, one per line. Sample Input2 7 AGTGATG 5 GTTAG 7 AGCTATT 9 AGCTTTAAA Sample Output1421 SourceTaejon 2001十五、二叉樹(shù)的相關(guān)算法實(shí)現(xiàn)編程實(shí)現(xiàn)二叉樹(shù)的創(chuàng)建、遍歷（采用非遞歸算法）、線(xiàn)索化、能夠進(jìn)行簡(jiǎn)單的輸入輸出驗(yàn)證等。十六、圖的實(shí)現(xiàn)問(wèn)題描述：對(duì)于如下地圖，實(shí)現(xiàn)圖的基本算法。基本要求：1以鄰接表作交通圖的存儲(chǔ)結(jié)構(gòu)，表示該圖。2 求出該圖的最小生成樹(shù)3 針對(duì)用戶(hù)所輸入的兩個(gè)城市、求出其最小距離，并輸出所經(jīng)歷的城市及總距離。十七 成績(jī)統(tǒng)計(jì)問(wèn)題描述：給出n個(gè)學(xué)生的m門(mén)考試的成績(jī)表，每個(gè)學(xué)生的信息由學(xué)號(hào)、姓名以及各科成績(jī)組成。對(duì)學(xué)生的考試成績(jī)進(jìn)行有關(guān)統(tǒng)計(jì)，并打印統(tǒng)計(jì)表?；疽? 按總數(shù)高低次序，打印出名次表，分?jǐn)?shù)相同的為同一名次；2 按名次打印出每個(gè)學(xué)生的學(xué)號(hào)、姓名、總分以及各科成績(jī)。十八 算術(shù)表達(dá)式的求解問(wèn)題描述：給定一個(gè)算術(shù)表達(dá)式，通過(guò)程序求出最后的結(jié)果?；疽螅?從鍵盤(pán)輸入要求解的算術(shù)表達(dá)式；2采用棧結(jié)構(gòu)進(jìn)行算術(shù)表達(dá)式的求解過(guò)程；3能夠判斷算術(shù)表達(dá)式正確與否；4對(duì)于錯(cuò)誤表達(dá)式給出提示；5對(duì)于正確的表達(dá)式給出最后的結(jié)果；十九 編寫(xiě)一個(gè)五子棋的游戲程序問(wèn)題描述：實(shí)現(xiàn)五子棋人與機(jī)對(duì)下的功能。基本要求：用矩陣來(lái)描述棋盤(pán)及對(duì)弈情況；通過(guò)輸入行數(shù)、列數(shù)表示人所下的位置；由程序來(lái)確定電腦所下的位置；設(shè)計(jì)輸、贏判斷規(guī)則函數(shù)；顯示每一步所對(duì)應(yīng)的矩陣；二十 血緣關(guān)系判斷問(wèn)題描述：針對(duì)任意2個(gè)人，判斷2個(gè)人之間是否有血緣關(guān)系?；疽螅?每個(gè)人都與父母具有直接血緣關(guān)系，針對(duì)每個(gè)人建立其血緣關(guān)系樹(shù)；2通過(guò)兩棵樹(shù)的遍歷、比較判斷2個(gè)人之間是否有血緣關(guān)系3計(jì)算兩個(gè)人血緣關(guān)系的遠(yuǎn)近、并輸出兩個(gè)人在遺傳學(xué)上的距離(假設(shè)父子、母子關(guān)系的遺傳學(xué)距離為1)4 輸出兩棵樹(shù)及運(yùn)算結(jié)果二十一：長(zhǎng)整數(shù)四則運(yùn)算【問(wèn)題描述】 設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序?！净疽蟆坷秒p向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。任何整型變量的范 圍是－(215l)~(2151) 。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)?！緶y(cè)試數(shù)據(jù)】(1) 0；0； 應(yīng)輸出 0 。(2)－2345，6789； －7654，3211； 應(yīng)輸出 －1，0000，0000 。 (3)－9999，9999；1，0000，0000，0000； 應(yīng)輸出 9999，0000，0001 。 (4) 1，0001，0001；－1，0001，0001； 應(yīng)輸出 0 。(5) 1，0001，0001；－1，0001，0000； 應(yīng)輸出 1 。(6) 9999，9999，9999；－9999，9999，9999；應(yīng)輸出 －1，9999，9999，9998 。 (7) 1，0000，9999，9999；1； 應(yīng)輸出 1，0001，0000，0000 。【實(shí)現(xiàn)提示】(1) 每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為 2151=32767， 才能保證兩數(shù)相加不會(huì)溢出。但若這樣存放，即相當(dāng)于按32768進(jìn)制數(shù)存放，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制數(shù)。(2) 可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。 【選作內(nèi)容】(1) 實(shí)現(xiàn)長(zhǎng)整數(shù)的四則運(yùn)算；(2) 實(shí)現(xiàn)長(zhǎng)整數(shù)的乘方和階乘運(yùn)算；(3) 整型量范圍是－ (2n－1) ~ (2n－1)， 其中，n是由程序讀人的參量。輸入數(shù)據(jù)的分組方法可以另行規(guī)定。二十二：字符串生成【問(wèn)題描述】假設(shè)用x→y 表示字符串x可以被替換為y，有如下的五條替換規(guī)則；請(qǐng)窮舉出在該五條替換規(guī)則下，所有能夠產(chǎn)生的字符串，字符串中只能包含小寫(xiě)字母a、b。S→aAAAAAAAAA…AAA(假設(shè)有n個(gè)A,n=20)A→aB A→空 意思是A可以直接被去掉 B→bB→空【實(shí)現(xiàn)提示】構(gòu)造一個(gè)棧，將aAAAAAAAAA…AAA壓入棧，依次彈出字符，彈出時(shí)將A替換為aB，并將aB替換為ab或a；或者不做任何處理(意味著A被替換為空)；替換完畢，窮舉出所有在替換過(guò)程中所生成的字符串。所生成的所有字符串可以用單鏈表來(lái)表示；二十三：拓?fù)渑判蚝完P(guān)鍵路徑 【問(wèn)題描述】拓?fù)渑判蚩膳袛郃OV網(wǎng)絡(luò)中是否存在回路，使的所有活動(dòng)可排成一個(gè)線(xiàn)性序列，使用每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面。關(guān)鍵路徑的工期決定了整個(gè)項(xiàng)目的工期。任何關(guān)鍵路徑上的終端元素的延遲將直接影響項(xiàng)目的預(yù)期完成時(shí)間（例如在關(guān)鍵路徑上沒(méi)有浮動(dòng)時(shí)間）?！救蝿?wù)要求】 構(gòu)建AOV網(wǎng)絡(luò)，并輸出其拓?fù)湫蛄薪Y(jié)果，輸出該圖的關(guān)鍵路徑和關(guān)鍵活動(dòng)，存儲(chǔ)結(jié)構(gòu)自行選擇?！緶y(cè)試數(shù)據(jù)】下圖的AOV
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1