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

1、第4周 二叉樹基礎(chǔ)4-2:文本二叉樹總時(shí)間限制: 1000ms內(nèi)存限制: 65536kB描述如上圖，一棵每個(gè)節(jié)點(diǎn)都是一個(gè)字母，且字母互不相同的二叉樹，可以用以下若干行文本表示:A-B-*-C-D-E-*-F在這若干行文本中：1) 每個(gè)字母代表一個(gè)節(jié)點(diǎn)。該字母在文本中是第幾行，就稱該節(jié)點(diǎn)的行號是幾。根在第1行2) 每個(gè)字母左邊的-字符的個(gè)數(shù)代表該結(jié)點(diǎn)在樹中的層次（樹根位于第0層）3) 若某第 i 層的非根節(jié)點(diǎn)在文本中位于第n行，則其父節(jié)點(diǎn)必然是第 i-1 層的節(jié)點(diǎn)中，行號小于n,且行號與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行，且其沒有左子節(jié)點(diǎn)而有右子節(jié)點(diǎn)，那么它的下一行就是 i+1個(gè)- 字符再加上一個(gè) * 給出一棵樹的文本表示法，要求輸出該數(shù)的前序、后序、中序遍歷結(jié)果輸入第一行是樹的數(shù)目 n接下來是n棵樹，每棵樹以0結(jié)尾。0不是樹的一部分每棵樹不超過100個(gè)節(jié)點(diǎn)輸出對每棵樹，分三行先后輸出其前序、后序、中序遍歷結(jié)果兩棵樹之間以空行分隔樣例輸入2A-B-*-C-D-E-*-F0A-B-C0樣例輸出ABCDEFCBFEDABCAEFDABCBCABAC4-3:由中根序列和后根序列重建二叉樹總時(shí)間限制: 500ms內(nèi)存限制: 65535

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

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

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

6、偏左一格，出現(xiàn)的橫坐標(biāo)位置為父結(jié)點(diǎn)的橫坐標(biāo)偏右一格。也就是說，如果樹高為m，則輸出就有2m-1行。第三部分為一個(gè)整數(shù)，表示將值代入變量之后，該中綴表達(dá)式的值。需要注意的一點(diǎn)是，除法代表整除運(yùn)算，即舍棄小數(shù)點(diǎn)后的部分。同時(shí)，測試數(shù)據(jù)保證不會出現(xiàn)除以0的現(xiàn)象。樣例輸入a+b*c3a 2b 7c 5樣例輸出abc*+ + / a * / b c37第5周 二叉樹應(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，代表測試數(shù)據(jù)的組數(shù)。對于每組測試數(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提示每組測試數(shù)據(jù)的復(fù)雜度為O(nlgn)的算法才能通過本次，否則會返回TLE(超時(shí))需要使用最小堆結(jié)構(gòu)來實(shí)現(xiàn)本題的算法5-2:二叉搜索樹總時(shí)間限制: 1000ms內(nèi)存限制: 1024kB描述 二叉搜索樹在動態(tài)查表中有特別的用處，一個(gè)無序序

8、列可以通過構(gòu)造一棵二叉搜索樹變成一個(gè)有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。每次插入的新的結(jié)點(diǎn)都是二叉搜索樹上新的葉子結(jié)點(diǎn)，在進(jìn)行插入操作時(shí)，不必移動其它結(jié)點(diǎn)，只需改動某個(gè)結(jié)點(diǎn)的指針，由空變?yōu)榉强占纯伞?這里，我們想探究二叉樹的建立和序列輸出。輸入只有一行，包含若干個(gè)數(shù)字，中間用空格隔開。（數(shù)字可能會有重復(fù)）輸出輸出一行，對輸入數(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í)間限制: 1000ms內(nèi)存限制: 65535kB描述構(gòu)造一個(gè)具有n個(gè)外部節(jié)點(diǎn)的擴(kuò)充二叉樹，每個(gè)外部節(jié)點(diǎn)Ki有一個(gè)Wi對應(yīng)，作為該外部節(jié)點(diǎn)的權(quán)。使得這個(gè)擴(kuò)充二叉樹的葉節(jié)點(diǎn)帶權(quán)外部路徑長度總和最?。?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ì)算最小外部路徑長度總和。輸入第一行輸入一個(gè)整數(shù)t，代表測試數(shù)據(jù)的組數(shù)。對于每組測試數(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)在請你將一些一般的樹用這種方法轉(zhuǎn)換為二叉樹，并輸出轉(zhuǎn)換前和轉(zhuǎn)換后樹的高度。輸入輸入包括多行，最后一行以一個(gè)#表示結(jié)束。每行是一個(gè)由“u”和“d”組成的字符串，表示一棵樹的深度優(yōu)先搜索信息。比如，dudduduudu可以用來表示上文中的左樹，因?yàn)樗阉鬟^程為：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)為每棵樹的結(jié)點(diǎn)數(shù)至少為2，并且不超過10000。

11、輸出對于每棵樹，按如下格式輸出轉(zhuǎn)換前和轉(zhuǎn)換后樹的高度：Tree t: h1 = h2其中t是樹的編號（從1開始），h1是轉(zhuǎn)換前樹的高度，h2是轉(zhuǎn)換后樹的高度。樣例輸入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），你不太可能詢問每個(gè)人的宗教信仰，因?yàn)樗麄儾惶敢馔嘎?。但是?dāng)你

12、同時(shí)找到2名學(xué)生，他們卻愿意告訴你他們是否信仰同一宗教，你可以通過很多這樣的詢問估算學(xué)校里的宗教數(shù)目的上限。你可以認(rèn)為每名學(xué)生只會信仰最多一種宗教。輸入輸入包括多組數(shù)據(jù)。每組數(shù)據(jù)的第一行包括n和m，0 = m = n(n-1)/2，其后m行每行包括兩個(gè)數(shù)字i和j，表示學(xué)生i和學(xué)生j信仰同一宗教，學(xué)生被標(biāo)號為1至n。輸入以一行 n = m = 0 作為結(jié)束。輸出對于每組數(shù)據(jù)，先輸出它的編號（從1開始），接著輸出學(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:電話號碼總時(shí)間限制: 1000ms內(nèi)存限制: 65536kB描述給你一些電話號碼，請判斷它們是否是一致的，即是否有某個(gè)電話是另一個(gè)電話的前綴。比如：Emergency 911Alice 97 625 999Bob 91 12 54 26在這個(gè)例子中，我們不可能撥通Bob的電話，因?yàn)镋mergency的電話是它的前綴，當(dāng)撥打Bob的電話時(shí)會先接通Emergency，所以這些電話號碼不是一致的。輸入第一行是一個(gè)整數(shù)t，1 t 40，表示測試數(shù)據(jù)的數(shù)目。每個(gè)測試樣例的第一行是一個(gè)整數(shù)n，1 n 10000，其后n行每行是一個(gè)不超過10位的電話號碼。輸出對于每個(gè)測試數(shù)據(jù)，如果是一致的輸出“YES”

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

15、刻骨難忘。再也沒有了圖書館自習(xí)的各種紛紜，再也沒有了運(yùn)動場上的揮汗如雨，有的，只是心中永遠(yuǎn)的不舍，與牽掛。夜，已深。人，卻不愿離去。天邊有一顆流星劃過，是那般靜，寧謐。忍不住不回頭，我的眼邊，有淚光，劃過。這時(shí)候，突然有一位路人甲從你身旁出現(xiàn)，問你：從XX到XX怎么走？索性，就讓我再愛你一次。因?yàn)椋贝笥肋h(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疼的一道題。說出不少傷感事啊。兩個(gè)最短路的算法都是可以用的，可以視情況選擇你習(xí)慣的那個(gè)算法。7-2:寶昌縣長要修路總時(shí)間限制: 1000ms內(nèi)存限制: 10000kB描述寶昌縣長意氣風(fēng)發(fā)，他決定整修之前縣里的道路。縣里的道路

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

19、母和每月維修該道路的花費(fèi)組成。維修費(fèi)用是正整數(shù)的并且小于100。該行的所有數(shù)據(jù)字段分隔單一空白。該公路網(wǎng)將始終連接所有的村莊。該公路網(wǎng)將永遠(yuǎn)不會超過75條道路。沒有任何一個(gè)村莊會有超過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提示考慮看成最小生成樹問題，注意輸入表示。7-3:拓?fù)渑判蚩倳r(shí)間限制: 10000ms內(nèi)存限制: 1000kB描述給出一個(gè)圖的結(jié)構(gòu)，輸出其拓?fù)渑判蛐蛄?，要求在同等條件下，編號小的頂點(diǎn)在前輸入若干行整數(shù)，第一行有2個(gè)數(shù)，分別為頂點(diǎn)數(shù)v和弧數(shù)a，接下來有a行，每一行有2個(gè)數(shù)，分別是該條弧所關(guān)聯(lián)的兩個(gè)頂點(diǎn)編號輸出若干個(gè)空格隔開的頂點(diǎn)構(gòu)成的序列(用小寫字母)樣例輸入6 81 21 31 43 23 54 56 46 5樣例輸出v1 v3 v2 v6 v4 v57-4:地震之后總時(shí)間限制: