【正文】 42 攔截導彈 問題描述　　某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。　　輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。輸入格式　　一行，為導彈依次飛來的高度輸出格式　　兩行，分別是最多能攔截的導彈數(shù)與要攔截所有導彈最少要配備的系統(tǒng)數(shù)樣例輸入389 207 155 300 299 170 158 65樣例輸出6243 二叉搜索樹判斷兩序列是否為同一個二叉搜索樹序列 要求：輸入：開始一個數(shù)n，(1=n=20) 表示有n個序列需要判斷，n= 0 的時候輸入結(jié)束。接下去一行是一個序列，序列長度小于10，包含(0~9)的數(shù)字，沒有重復數(shù)字，根據(jù)這個序列可以構(gòu)造出一顆二叉搜索樹。接下去的n行有n個序列，每個序列格式跟第一個序列一樣，請判斷這兩個序列是否能組成同一顆二叉搜索樹。輸出：如果序列相同則輸出YES，否則輸出NOSample Input25674325432675763420Sample OutputYESNO44 會議中心 　　會議中心　　Siruseri政府建造了一座新的會議中心。許多公司對租借會議中心的會堂很感興趣，他們希望能夠在里面舉行會議。　　對于一個客戶而言，僅當在開會時能夠獨自占用整個會堂，他才會租借會堂。會議中心的銷售主管認為：最好的策略應該是將會堂租借給盡可能多的客戶。顯然，有可能存在不止一種滿足要求的策略。　　例如下面的例子。總共有4個公司。他們對租借會堂發(fā)出了請求，并提出了他們所需占用會堂的起止日期（如下表所示）。開始日期結(jié)束日期公司149公司2911公司31319公司41017　　上例中，最多將會堂租借給兩家公司。租借策略分別是租給公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意會議中心一天最多租借給一個公司，所以公司1和公司2不能同時租借會議中心，因為他們在第九天重合了?！　′N售主管為了公平起見，決定按照如下的程序來確定選擇何種租借策略：首先，將租借給客戶數(shù)量最多的策略作為候選，將所有的公司按照他們發(fā)出請求的順序編號。對于候選策略，將策略中的每家公司的編號按升序排列。最后，選出其中字典序最小[1]的候選策略作為最終的策略?！　±校瑫米罱K將被租借給公司1和公司3：3個候選策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)(1,4)(2,3)?！　∧愕娜蝿帐菐椭N售主管確定應該將會堂租借給哪些公司。輸入格式　　輸入的第一行有一個整數(shù)N，表示發(fā)出租借會堂申請的公司的個數(shù)。第2到第N+1行每行有2個整數(shù)。第i+1行的整數(shù)表示第i家公司申請租借的起始和終止日期。對于每個公司的申請，起始日期為不小于1的整數(shù)，終止日期為不大于109的整數(shù)。輸出格式　　輸出的第一行應有一個整數(shù)M，表示最多可以租借給多少家公司。第二行應列出M個數(shù)，表示最終將會堂租借給哪些公司。數(shù)據(jù)規(guī)模和約定　　對于50%的輸入，N≤3000。在所有輸入中，N≤200000。樣例輸入44 99 1113 1910 17樣例輸出21 3[1] 字典序指在字典中排列的順序，如果序列l(wèi)1是序列l(wèi)2的前綴，或者對于l1和l2的第一個不同位置j，l1[j]l2[j]，則l1比l2小。45 串數(shù)一個A和兩個B一共可以組成三種字符串:ABB,BAB,BBA.給定若干字母和它們相應的個數(shù),計算一共可以組成多少個不同的字符串.要求：輸入：每組測試數(shù)據(jù)分兩行,第一行為n(1=n=26),表示不同字母的個數(shù),第二行為n個數(shù)A1,A2,...,An(1=Ai=12),=0為結(jié)束.輸出：對于每一組測試數(shù)據(jù),輸出一個m,表示一共有多少種字符串.Sample Input21 232 2 20Sample Output39046 樹的應用 要實現(xiàn)樹與二叉樹的轉(zhuǎn)換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應包含建樹的實現(xiàn)。47 求先序排列 問題描述　　給出一棵二叉樹的中序與后序排列。求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，長度=8）。輸入格式　　兩行，每行一個字符串，分別表示中序和后序排列輸出格式　　一個字符串，表示所求先序排列樣例輸入BADCBDCA樣例輸出ABCD48 大臣的旅費 問題描述很久以前，T王國空前繁榮。為了更好地管理國家，王國修建了大量的快速路，用于連接首都和王國內(nèi)的各大城市。為節(jié)省經(jīng)費，T國的大臣們經(jīng)過思考，制定了一套優(yōu)秀的修建方案，使得任何一個大城市都能從首都直接或者通過其他大城市間接到達。同時，如果不重復經(jīng)過大城市，從首都到達每個大城市的方案都是唯一的。J是T國重要大臣，他巡查于各大城市之間，體察民情。所以，從一個城市馬不停蹄地到另一個城市成了J最常做的事情。他有一個錢袋，用于存放往來城市間的路費。聰明的J發(fā)現(xiàn)，如果不在某個城市停下來修整，在連續(xù)行進過程中，他所花的路費與他已走過的距離有關(guān)，在走第x千米到第x+1千米這一千米中（x是整數(shù)），他花費的路費是x+10這么多。也就是說走1千米花費11，走2千米要花費23。J大臣想知道：他從某一個城市出發(fā)，中間不休息，到達另一個城市，所有可能花費的路費中最多是多少呢？輸入格式輸入的第一行包含一個整數(shù)n，表示包括首都在內(nèi)的T王國的城市數(shù)城市從1開始依次編號，1號城市為首都。接下來n1行，描述T國的高速路（T國的高速路一定是n1條）每行三個整數(shù)Pi, Qi, Di，表示城市Pi和城市Qi之間有一條高速路，長度為Di千米。輸出格式輸出一個整數(shù)，表示大臣J最多花費的路費是多少。樣例輸入151 2 21 3 12 4 52 5 4樣例輸出1135輸出格式大臣J從城市4到城市5要花費135的路費。49 小朋友排隊 問題描述　　n 個小朋友站成一排。現(xiàn)在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個小朋友?！　∶總€小朋友都有一個不高興的程度。開始的時候，所有小朋友的不高興程度都是0?！　∪绻硞€小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類推。當要求某個小朋友第k次交換時，他的不高興程度增加k?！　≌垎枺屗行∨笥寻磸牡偷礁吲抨?，他們的不高興程度之和最小是多少?！　∪绻袃蓚€小朋友身高一樣，則他們誰站在誰前面是沒有關(guān)系的。輸入格式　　輸入的第一行包含一個整數(shù)n，表示小朋友的個數(shù)?！　〉诙邪?n 個整數(shù) H1 H2 … Hn，分別表示每個小朋友的身高。輸出格式　　輸出一行，包含一個整數(shù)，表示小朋友的不高興程度和的最小值。樣例輸入33 2 1樣例輸出9樣例說明　　首先交換身高為3和2的小朋友，再交換身高為3和1的小朋友，再交換身高為2和1的小朋友，每個小朋友的不高興程度都是3，總和為9。50 接水問題 問題描述　　學校里有一個水房，水房里一共裝有m 個龍頭可供同學們打開水，每個龍頭每秒鐘的 供水量相等，均為1。 現(xiàn)在有n 名同學準備接水，他們的初始接水順序已經(jīng)確定。將這些同學按接水順序從1 到n 編號，i 號同學的接水量為wi。接水開始時，1 到m 號同學各占一個水龍頭，并同時打 開水龍頭接水。當其中某名同學j 完成其接水量要求wj 后，下一名排隊等候接水的同學k 馬上接替j 同學的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即 j 同學第x 秒結(jié)束時完成接水，則k 同學第x+1 秒立刻開始接水。若當前接水人數(shù)n’不足m， 則只有n’個龍頭供水，其它m?n’個龍頭關(guān)閉。 現(xiàn)在給出n 名同學的接水量，按照上述接水規(guī)則，問所有同學都接完水需要多少秒。輸入格式　　第1 行2 個整數(shù)n 和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。 第2 行n 個整數(shù)ww……、wn，每兩個整數(shù)之間用一個空格隔開，wi 表示i 號同 學的接水量。輸出格式　　輸出只有一行，1 個整數(shù)，表示接水所需的總時間。樣例輸入5 34 4 1 2 1樣例輸出4樣例輸入8 423 71 87 32 70 93 80 76樣例輸出163輸入輸出樣例 1 說明　　第1 秒，3 人接水。第1 秒結(jié)束時，3 號同學每人的已接水量為1，3 號同學接完　　水，4 號同學接替3 號同學開始接水?！　〉? 秒，3 人接水。第2 秒結(jié)束時，2 號同學每人的已接水量為2，4 號同學的已接　　水量為1?！　〉? 秒，3 人接水。第3 秒結(jié)束時，2 號同學每人的已接水量為3，4 號同學的已接　　水量為2。4 號同學接完水，5 號同學接替4 號同學開始接水?！　〉? 秒，3 人接水。第4 秒結(jié)束時，2 號同學每人的已接水量為4，5 號同學的已接　　水量為1。5 號同學接完水，即所有人完成接水?！　】偨铀畷r間為4 秒?！墩n程設計報告》文檔規(guī)范及注意事項一、按照《實驗指導書》中“課程設計示例”模式寫；即：應包括題目、問題分析和任務定義、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設計、詳細設計和編碼、上機調(diào)試過程、測試結(jié)果及其分析、用戶使用說明、參考文獻、附錄這幾個部分和順序；二、文檔格式為A4紙、宋體、5號字、一級標題加粗、單倍行距；三、圖、表應有標號和名稱，且圖名位于圖下，表名位于表格上方；四、參考文獻格式為：序號 作者．書名．出版地：出版社名稱，出版社年份序號 作者．論文題名．期刊名稱，年份，卷號（期號）：起至頁碼五、附錄中的源代碼應有適當?shù)淖⑨?；六、按照格式要求填寫《課程設計報告封面》、《課程設計評分表》中學生應填寫的內(nèi)容。七、課程設計結(jié)束后，學生應提交的文檔包括紙質(zhì)文檔和電子文檔。紙質(zhì)文檔包括：《課程設計報告》1份（用塑料拉桿夾裝訂好）；《課程設計評分表》1份；《課程設計任務書》1份（可以雙面打?。?；《課程設計的心得體會》1份；紙質(zhì)文檔裝入“課程設計資料袋”上交。電子文檔包括：課程設計報告 課程設計評分表課程設計任務書課程設計的心得體會源程序程序的可執(zhí)行文件（.exe）將這些電子檔形成一個壓縮文件，文件名為：學號姓名課程設計名，發(fā)送至指導老師的郵箱。合肥學院計算機科學與技術(shù)系課程設計報告20 ～20 學年第 學期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設計名稱學生姓名高蘇廣學號020202086專業(yè)班級03計科(1)指導教師20 年 月計算機科學與技術(shù)系課程設計評分表學生/學號： （5號字、宋體） 專業(yè)/班級：計算機科學與技術(shù)06級1班設計題目二元多項式加減運算問題成績 課程設計主要內(nèi)容一、內(nèi)容設計程序以實現(xiàn)降冪建立、輸出、加、減任意兩個二元多項式。要求：（1）所設計的數(shù)據(jù)結(jié)構(gòu)應盡可能節(jié)省存儲空間。（2）程序的運行時間應盡可能少。二、任務和要求任務：⑴ 通過獨立解決某個課程設計問題，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應用、算法的設計及其實現(xiàn)等方面加深對課程基本內(nèi)容的理解和綜合運用。⑵ 深刻理解、牢固掌握數(shù)據(jù)結(jié)構(gòu)和算法設計技術(shù)，提高分析和解決實際問題的能力。⑶ 在程序設計方法以及上機操作等基本技能和科學作風方面進行比較系統(tǒng)和嚴格的訓練。要求：按“課程設計教學大綱”的要求完成不“數(shù)據(jù)結(jié)構(gòu)與算法課程設計報告”。序號評 價 項 目評 分滿分得分1實驗過程出勤率好。102實驗預研報告清晰、正確、圖表齊全、質(zhì)量高103態(tài)度認真，作風嚴謹，并按規(guī)定的進度開展實驗工作104能很好地完成任務書規(guī)定的工作量105在實驗中，學生使用和操作儀器的能力、觀察和分析實驗現(xiàn)象的能力、主動排除故障的能力106對實驗結(jié)果有自己獨立見解107答辯簡明扼要、重點突出地闡述課題的主要內(nèi)容108準確流利地回答各種問題，能否闡明自己的觀點109課程設計報告，內(nèi)容充實、圖表齊全、數(shù)據(jù)處理正確、結(jié)構(gòu)合理、書面整潔1010文字表達能力強，準確地表達自己的思想。10總體評價累計得分教師簽名日期注：（1）成績評定 采用五級記分制 優(yōu)秀(90～100分)、良好(80～89分)、中等(70～79分)、及格(60～69分)、不及格(60分以下)合肥學院計算機科學與技術(shù)系課程設計任務書2008 ～2009 學年第一學期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設計名稱二元多項式加減運算問題專業(yè)班級計算機科學與技術(shù)06