數(shù)據(jù)結(jié)構(gòu)編程題

1、第4周 二叉樹(shù)基礎(chǔ)4-2:文本二叉樹(shù)總時(shí)間限制: 1000ms內(nèi)存限制: 65536kB描述如上圖，一棵每個(gè)節(jié)點(diǎn)都是一個(gè)字母，且字母互不相同的二叉樹(shù)，可以用以下若干行文本表示:A-B-*-C-D-E-*-F在這若干行文本中：1) 每個(gè)字母代表一個(gè)節(jié)點(diǎn)。該字母在文本中是第幾行，就稱該節(jié)點(diǎn)的行號(hào)是幾。根在第1行2) 每個(gè)字母左邊的-字符的個(gè)數(shù)代表該結(jié)點(diǎn)在樹(shù)中的層次（樹(shù)根位于第0層）3) 若某第 i 層的非根節(jié)點(diǎn)在文本中位于第n行，則其父節(jié)點(diǎn)必然是第 i-1 層的節(jié)點(diǎn)中，行號(hào)小于n,且行號(hào)與n的差最小的那個(gè)4) 若某文本中位于第n行的節(jié)點(diǎn)(層次是i) 有兩個(gè)子節(jié)點(diǎn)，則第n+1行就是其左子節(jié)點(diǎn)，右子節(jié)

2、點(diǎn)是n+1行以下第一個(gè)層次為i+1的節(jié)點(diǎn)5) 若某第 i 層的節(jié)點(diǎn)在文本中位于第n行，且其沒(méi)有左子節(jié)點(diǎn)而有右子節(jié)點(diǎn)，那么它的下一行就是 i+1個(gè)- 字符再加上一個(gè) * 給出一棵樹(shù)的文本表示法，要求輸出該數(shù)的前序、后序、中序遍歷結(jié)果輸入第一行是樹(shù)的數(shù)目 n接下來(lái)是n棵樹(shù)，每棵樹(shù)以0結(jié)尾。0不是樹(shù)的一部分每棵樹(shù)不超過(guò)100個(gè)節(jié)點(diǎn)輸出對(duì)每棵樹(shù)，分三行先后輸出其前序、后序、中序遍歷結(jié)果兩棵樹(shù)之間以空行分隔樣例輸入2A-B-*-C-D-E-*-F0A-B-C0樣例輸出ABCDEFCBFEDABCAEFDABCBCABAC4-3:由中根序列和后根序列重建二叉樹(shù)總時(shí)間限制: 500ms內(nèi)存限制: 65535

3、kB描述我們知道如何按照三種深度優(yōu)先次序來(lái)周游一棵二叉樹(shù)，來(lái)得到中根序列、前根序列和后根序列。反過(guò)來(lái)，如果給定二叉樹(shù)的中根序列和后根序列，或者給定中根序列和前根序列，可以重建一二叉樹(shù)。本題輸入一棵二叉樹(shù)的中根序列和后根序列，要求在內(nèi)存中重建二叉樹(shù)，最后輸出這棵二叉樹(shù)的前根序列。用不同的整數(shù)來(lái)唯一標(biāo)識(shí)二叉樹(shù)的每一個(gè)結(jié)點(diǎn)，下面的二叉樹(shù)中根序列是9 5 32 67后根序列9 32 67 5前根序列5 9 67 32輸入兩行。第一行是二叉樹(shù)的中根序列，第二行是后根序列。每個(gè)數(shù)字表示的結(jié)點(diǎn)之間用空格隔開(kāi)。結(jié)點(diǎn)數(shù)字范圍065535。暫不必考慮不合理的輸入數(shù)據(jù)。輸出一行。由輸入中的中根序列和后根序列重建的二

4、叉樹(shù)的前根序列。每個(gè)數(shù)字表示的結(jié)點(diǎn)之間用空格隔開(kāi)。樣例輸入9 5 32 679 32 67 5樣例輸出5 9 67 324-4:表達(dá)式表達(dá)式樹(shù)表達(dá)式求值總時(shí)間限制: 1000ms內(nèi)存限制: 65535kB描述眾所周知，任何一個(gè)表達(dá)式，都可以用一棵表達(dá)式樹(shù)來(lái)表示。例如，表達(dá)式a+b*c，可以表示為如下的表達(dá)式樹(shù)： + / a * / b c現(xiàn)在，給你一個(gè)中綴表達(dá)式，這個(gè)中綴表達(dá)式用變量來(lái)表示（不含數(shù)字），請(qǐng)你將這個(gè)中綴表達(dá)式用表達(dá)式二叉樹(shù)的形式輸出出來(lái)。輸入輸入分為三個(gè)部分。第一部分為一行，即中綴表達(dá)式。中綴表達(dá)式可能含有小寫(xiě)字母代表變量（a-z），也可能含有運(yùn)算符（+、-、*、/、小括號(hào)），不

5、含有數(shù)字，也不含有空格。第二部分為一個(gè)整數(shù)n，表示中綴表達(dá)式的變量數(shù)。第三部分有n行，每行格式為Cx，C為變量的字符，x為該變量的值。輸出輸出分為三個(gè)部分，第一個(gè)部分為該表達(dá)式的逆波蘭式，即該表達(dá)式樹(shù)的后根遍歷結(jié)果。占一行。第二部分為表達(dá)式樹(shù)的顯示，如樣例輸出所示。如果該二叉樹(shù)是一棵滿二叉樹(shù)，則最底部的葉子結(jié)點(diǎn)，分別占據(jù)橫坐標(biāo)的第1、3、5、7個(gè)位置（最左邊的坐標(biāo)是1），然后它們的父結(jié)點(diǎn)的橫坐標(biāo)，在兩個(gè)子結(jié)點(diǎn)的中間。如果不是滿二叉樹(shù)，則沒(méi)有結(jié)點(diǎn)的地方，用空格填充（但請(qǐng)略去所有的行末空格）。每一行父結(jié)點(diǎn)與子結(jié)點(diǎn)中隔開(kāi)一行，用斜杠（/）與反斜杠（）來(lái)表示樹(shù)的關(guān)系。/出現(xiàn)的橫坐標(biāo)位置為父結(jié)點(diǎn)的橫坐標(biāo)

6、偏左一格，出現(xiàn)的橫坐標(biāo)位置為父結(jié)點(diǎn)的橫坐標(biāo)偏右一格。也就是說(shuō)，如果樹(shù)高為m，則輸出就有2m-1行。第三部分為一個(gè)整數(shù)，表示將值代入變量之后，該中綴表達(dá)式的值。需要注意的一點(diǎn)是，除法代表整除運(yùn)算，即舍棄小數(shù)點(diǎn)后的部分。同時(shí)，測(cè)試數(shù)據(jù)保證不會(huì)出現(xiàn)除以0的現(xiàn)象。樣例輸入a+b*c3a 2b 7c 5樣例輸出abc*+ + / a * / b c37第5周 二叉樹(shù)應(yīng)用5-1:實(shí)現(xiàn)堆結(jié)構(gòu)總時(shí)間限制: 3000ms內(nèi)存限制: 65535kB描述定義一個(gè)數(shù)組，初始化為空。在數(shù)組上執(zhí)行兩種操作：1、增添1個(gè)元素，把1個(gè)新的元素放入數(shù)組。2、輸出并刪除數(shù)組中最小的數(shù)。使用堆結(jié)構(gòu)實(shí)現(xiàn)上述功能的高效算法。輸入第一行

7、輸入一個(gè)整數(shù)t，代表測(cè)試數(shù)據(jù)的組數(shù)。對(duì)于每組測(cè)試數(shù)據(jù)，第一行輸入一個(gè)整數(shù)n，代表操作的次數(shù)。每次操作首先輸入一個(gè)整數(shù)type。當(dāng)type=1，增添操作，接著輸入一個(gè)整數(shù)u，代表要插入的元素。當(dāng)type=2，輸出刪除操作，輸出并刪除數(shù)組中最小的元素。1=n=。輸出每次刪除操作輸出被刪除的數(shù)字。樣例輸入251 11 21 32241 51 11 72樣例輸出121提示每組測(cè)試數(shù)據(jù)的復(fù)雜度為O(nlgn)的算法才能通過(guò)本次，否則會(huì)返回TLE(超時(shí))需要使用最小堆結(jié)構(gòu)來(lái)實(shí)現(xiàn)本題的算法5-2:二叉搜索樹(shù)總時(shí)間限制: 1000ms內(nèi)存限制: 1024kB描述 二叉搜索樹(shù)在動(dòng)態(tài)查表中有特別的用處，一個(gè)無(wú)序序

8、列可以通過(guò)構(gòu)造一棵二叉搜索樹(shù)變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。每次插入的新的結(jié)點(diǎn)都是二叉搜索樹(shù)上新的葉子結(jié)點(diǎn)，在進(jìn)行插入操作時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，只需改動(dòng)某個(gè)結(jié)點(diǎn)的指針，由空變?yōu)榉强占纯伞?這里，我們想探究二叉樹(shù)的建立和序列輸出。輸入只有一行，包含若干個(gè)數(shù)字，中間用空格隔開(kāi)。（數(shù)字可能會(huì)有重復(fù)）輸出輸出一行，對(duì)輸入數(shù)字建立二叉搜索樹(shù)后進(jìn)行前序周游的結(jié)果。樣例輸入41 467 334 500 169 724 478 358 962 464 705 145 281 827 961 491 995 942 827 436 樣例輸出41 467 334 169 145 281

9、 358 464 436 500 478 491 724 705 962 827 961 942 9955-3:Huffman編碼樹(shù)總時(shí)間限制: 1000ms內(nèi)存限制: 65535kB描述構(gòu)造一個(gè)具有n個(gè)外部節(jié)點(diǎn)的擴(kuò)充二叉樹(shù)，每個(gè)外部節(jié)點(diǎn)Ki有一個(gè)Wi對(duì)應(yīng)，作為該外部節(jié)點(diǎn)的權(quán)。使得這個(gè)擴(kuò)充二叉樹(shù)的葉節(jié)點(diǎn)帶權(quán)外部路徑長(zhǎng)度總和最?。?Min( W1 * L1 + W2 * L2 + W3 * L3 + + Wn * Ln)Wi:每個(gè)節(jié)點(diǎn)的權(quán)值。Li:根節(jié)點(diǎn)到第i個(gè)外部葉子節(jié)點(diǎn)的距離。編程計(jì)算最小外部路徑長(zhǎng)度總和。輸入第一行輸入一個(gè)整數(shù)t，代表測(cè)試數(shù)據(jù)的組數(shù)。對(duì)于每組測(cè)試數(shù)據(jù)，第一行輸入一個(gè)整數(shù)n，

10、外部節(jié)點(diǎn)的個(gè)數(shù)。第二行輸入n個(gè)整數(shù)，代表各個(gè)外部節(jié)點(diǎn)的權(quán)值。2=N 1 / 4 5 2 / 4 3 5現(xiàn)在請(qǐng)你將一些一般的樹(shù)用這種方法轉(zhuǎn)換為二叉樹(shù)，并輸出轉(zhuǎn)換前和轉(zhuǎn)換后樹(shù)的高度。輸入輸入包括多行，最后一行以一個(gè)#表示結(jié)束。每行是一個(gè)由“u”和“d”組成的字符串，表示一棵樹(shù)的深度優(yōu)先搜索信息。比如，dudduduudu可以用來(lái)表示上文中的左樹(shù)，因?yàn)樗阉鬟^(guò)程為：0 Down to 1 Up to 0 Down to 2 Down to 4 Up to 2 Down to 5 Up to 2 Up to 0 Down to 3 Up to 0。你可以認(rèn)為每棵樹(shù)的結(jié)點(diǎn)數(shù)至少為2，并且不超過(guò)10000。

11、輸出對(duì)于每棵樹(shù)，按如下格式輸出轉(zhuǎn)換前和轉(zhuǎn)換后樹(shù)的高度：Tree t: h1 = h2其中t是樹(shù)的編號(hào)（從1開(kāi)始），h1是轉(zhuǎn)換前樹(shù)的高度，h2是轉(zhuǎn)換后樹(shù)的高度。樣例輸入dudduduududdddduuuuudddduduuuudddduuduuu#樣例輸出Tree 1: 2 = 4Tree 2: 5 = 5Tree 3: 4 = 5Tree 4: 4 = 46-3:宗教信仰總時(shí)間限制: 5000ms內(nèi)存限制: 65536kB描述世界上有許多宗教，你感興趣的是你學(xué)校里的同學(xué)信仰多少種宗教。你的學(xué)校有n名學(xué)生（0 n = 50000），你不太可能詢問(wèn)每個(gè)人的宗教信仰，因?yàn)樗麄儾惶敢馔嘎丁５钱?dāng)你

12、同時(shí)找到2名學(xué)生，他們卻愿意告訴你他們是否信仰同一宗教，你可以通過(guò)很多這樣的詢問(wèn)估算學(xué)校里的宗教數(shù)目的上限。你可以認(rèn)為每名學(xué)生只會(huì)信仰最多一種宗教。輸入輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)的第一行包括n和m，0 = m = n(n-1)/2，其后m行每行包括兩個(gè)數(shù)字i和j，表示學(xué)生i和學(xué)生j信仰同一宗教，學(xué)生被標(biāo)號(hào)為1至n。輸入以一行 n = m = 0 作為結(jié)束。輸出對(duì)于每組數(shù)據(jù)，先輸出它的編號(hào)（從1開(kāi)始），接著輸出學(xué)生信仰的不同宗教的數(shù)目上限。樣例輸入10 91 21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0樣例輸出Case 1: 1Case 2: 76-

13、4:電話號(hào)碼總時(shí)間限制: 1000ms內(nèi)存限制: 65536kB描述給你一些電話號(hào)碼，請(qǐng)判斷它們是否是一致的，即是否有某個(gè)電話是另一個(gè)電話的前綴。比如：Emergency 911Alice 97 625 999Bob 91 12 54 26在這個(gè)例子中，我們不可能撥通Bob的電話，因?yàn)镋mergency的電話是它的前綴，當(dāng)撥打Bob的電話時(shí)會(huì)先接通Emergency，所以這些電話號(hào)碼不是一致的。輸入第一行是一個(gè)整數(shù)t，1 t 40，表示測(cè)試數(shù)據(jù)的數(shù)目。每個(gè)測(cè)試樣例的第一行是一個(gè)整數(shù)n，1 n 10000，其后n行每行是一個(gè)不超過(guò)10位的電話號(hào)碼。輸出對(duì)于每個(gè)測(cè)試數(shù)據(jù)，如果是一致的輸出“YES”

14、，如果不是輸出“NO”。樣例輸入239115113123401234598346樣例輸出NOYES第7周 圖7-1:我愛(ài)北大總時(shí)間限制: 1000ms內(nèi)存限制: 65535kB描述“紅樓飛雪，一時(shí)英杰”耳邊傳來(lái)了那熟悉的歌聲。而這，只怕是我最后一次聽(tīng)到這個(gè)聲音了。想當(dāng)年，我們?cè)?jīng)懷著豪情壯志，許下心愿，走過(guò)靜園，走過(guò)一體，走過(guò)未名湖畔的每個(gè)角落。想當(dāng)年，我們也曾慷慨高歌，瞻仰民主與科學(xué)，瞻仰博雅塔頂，那百年之前的遺韻。沒(méi)錯(cuò)，我愛(ài)北大，我愛(ài)這個(gè)校園。然而，從當(dāng)我們穿上學(xué)位服的那一刻起，這個(gè)校園，就再也不屬于我。它只屬于往事，屬于我的回憶。沒(méi)錯(cuò)，這，是我在北大的最后一日。此時(shí)，此景，此生，此世，將

15、刻骨難忘。再也沒(méi)有了圖書(shū)館自習(xí)的各種紛紜，再也沒(méi)有了運(yùn)動(dòng)場(chǎng)上的揮汗如雨，有的，只是心中永遠(yuǎn)的不舍，與牽掛。夜，已深。人，卻不愿離去。天邊有一顆流星劃過(guò)，是那般靜，寧謐。忍不住不回頭，我的眼邊，有淚光，劃過(guò)。這時(shí)候，突然有一位路人甲從你身旁出現(xiàn)，問(wèn)你：從XX到XX怎么走？索性，就讓我再愛(ài)你一次。因?yàn)?，北大永遠(yuǎn)在你心中。北大的地圖，永遠(yuǎn)在你的心中。輕手揮揚(yáng)，不帶走一分云彩。輸入輸入分為三個(gè)部分。第一個(gè)部分有P+1行，第一行為一個(gè)整數(shù)P，之后的P行表示北大的地點(diǎn)。第二個(gè)部分有Q+1行，第一行為一個(gè)整數(shù)Q，之后的Q行每行分別為兩個(gè)字符串與一個(gè)整數(shù)，表示這兩點(diǎn)有直線的道路，并顯示二者之間的矩離（單位為米

16、）。第三個(gè)部分有R+1行，第一行為一個(gè)整數(shù)R，之后的R行每行為兩個(gè)字符串，表示需要求的路線。p30,Q50,R(矩離)-相隔樣例輸入6XueYiShiTangCanYinZhongXinXueWuShiTangXueYiXiaoBaiFangBaiNianJiangTangGongHangQuKuanJi6XueYiShiTang CanYinZhongXin 80XueWuShiTang CanYinZhongXin 40XueYiShiTang XueYiXiaoBaiFang 35XueYiXiaoBaiFang XueWuShiTang 85CanYinZhongXin GongHan

17、gQuKuanJi 60GongHangQuKuanJi BaiNianJiangTang 351XueYiXiaoBaiFang BaiNianJiangTang樣例輸出XueYiXiaoBaiFang-(35)-XueYiShiTang-(80)-CanYinZhongXin-(60)-GongHangQuKuanJi-(35)-BaiNianJiangTang提示很O疼的一道題。說(shuō)出不少傷感事啊。兩個(gè)最短路的算法都是可以用的，可以視情況選擇你習(xí)慣的那個(gè)算法。7-2:寶昌縣長(zhǎng)要修路總時(shí)間限制: 1000ms內(nèi)存限制: 10000kB描述寶昌縣長(zhǎng)意氣風(fēng)發(fā)，他決定整修之前縣里的道路。縣里的道路

18、很多，但維護(hù)費(fèi)用昂貴。具體如圖A所示。線段上面的數(shù)據(jù)表示兩個(gè)節(jié)點(diǎn)之間的所需要的維修費(fèi)用，現(xiàn)在需要對(duì)鄉(xiāng)村進(jìn)行道路優(yōu)化，最基本的要求是將所有的村莊節(jié)點(diǎn)都要聯(lián)通起來(lái)，并且要求每月的維護(hù)費(fèi)用最小。比如優(yōu)化后的圖如B所示。輸入第一行只包含一個(gè)表示村莊個(gè)數(shù)的數(shù)n，n不大于26，并且這n個(gè)村莊是由大寫(xiě)字母表里的前n個(gè)字母表示。接下來(lái)的n-1行是由字母表的前n-1個(gè)字母開(kāi)頭。最后一個(gè)村莊表示的字母不用輸入。對(duì)于每一行，以每個(gè)村莊表示的字母開(kāi)頭，然后后面跟著一個(gè)數(shù)字，表示有多少條道路可以從這個(gè)村到后面字母表中的村莊。如果k是大于0，表示該行后面會(huì)表示k條道路的k個(gè)數(shù)據(jù)。每條道路的數(shù)據(jù)是由表示連接到另一端村莊的字

19、母和每月維修該道路的花費(fèi)組成。維修費(fèi)用是正整數(shù)的并且小于100。該行的所有數(shù)據(jù)字段分隔單一空白。該公路網(wǎng)將始終連接所有的村莊。該公路網(wǎng)將永遠(yuǎn)不會(huì)超過(guò)75條道路。沒(méi)有任何一個(gè)村莊會(huì)有超過(guò)15條的道路連接到其他村莊（之前或之后的字母）。在下面的示例輸入，數(shù)據(jù)是與上面的地圖相一致的。輸出輸出是一個(gè)整數(shù)，表示每個(gè)數(shù)據(jù)集中每月維持道路系統(tǒng)連接到所有村莊所花費(fèi)的最低成本。樣例輸入9A 2 B 12 I 25B 3 C 10 H 40 I 8C 2 D 18 G 55D 1 E 44E 2 F 60 G 38F 0G 1 H 35H 1 I 35樣例輸出216提示考慮看成最小生成樹(shù)問(wèn)題，注意輸入表示。7-3:拓?fù)渑判蚩倳r(shí)間限制: 10000ms內(nèi)存限制: 1000kB描述給出一個(gè)圖的結(jié)構(gòu)，輸出其拓?fù)渑判蛐蛄?，要求在同等條件下，編號(hào)小的頂點(diǎn)在前輸入若干行整數(shù)，第一行有2個(gè)數(shù)，分別為頂點(diǎn)數(shù)v和弧數(shù)a，接下來(lái)有a行，每一行有2個(gè)數(shù)，分別是該條弧所關(guān)聯(lián)的兩個(gè)頂點(diǎn)編號(hào)輸出若干個(gè)空格隔開(kāi)的頂點(diǎn)構(gòu)成的序列(用小寫(xiě)字母)樣例輸入6 81 21 31 43 23 54 56 46 5樣例輸出v1 v3 v2 v6 v4 v57-4:地震之后總時(shí)間限制: