数据结构编程题

数据结构编程题数据结构编程题全文共40页，当前为第1页。数据结构编程题全文共40页，当前为第1页。第4周二叉树基础4-2:文本二叉树总时间限制:1000ms内存限制:65536kB描述

如上图，一棵每个节点都是一个字母，且字母互不相同的二叉树，可以用以下若干行文本表示:

A

-B

--*

--C

-D

--E

---*

---F数据结构编程题全文共40页，当前为第2页。数据结构编程题全文共40页，当前为第2页。数据结构编程题全文共40页，当前为第3页。数据结构编程题全文共40页，当前为第3页。数据结构编程题全文共40页，当前为第4页。数据结构编程题全文共40页，当前为第4页。A-B-C0样例输出ABCDEFCBFEDABCAEFDABCBCABAC4-3:由中根序列和后根序列重建二叉树总时间限制:500ms内存限制:65535kB描述数据结构编程题全文共40页，当前为第5页。数据结构编程题全文共40页，当前为第5页。用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树中根序列是953267后根序列932675前根序列596732输入两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。输出数据结构编程题全文共40页，当前为第6页。数据结构编程题全文共40页，当前为第6页。样例输入953267932675样例输出5967324-4:表达式·表达式树·表达式求值总时间限制:1000ms内存限制:65535kB描述众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：数据结构编程题全文共40页，当前为第7页。数据结构编程题全文共40页，当前为第7页。现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。输入输入分为三个部分。

第一部分为一行，即中缀表达式。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。

第二部分为一个整数n，表示中缀表达式的变量数。

第三部分有n行，每行格式为Cx，C为变量的字符，x为该变量的值。输出数据结构编程题全文共40页，当前为第8页。输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。

第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（\）来表示树数据结构编程题全文共40页，当前为第8页。样例输入a+b*c3a2b7c5样例输出数据结构编程题全文共40页，当前为第9页。数据结构编程题全文共40页，当前为第9页。+/\a*/\bc37第5周二叉树应用5-1:实现堆结构总时间限制:3000ms内存限制:65535kB描述定义一个数组，初始化为空。在数组上执行两种操作：1、增添1个元素，把1个新的元素放入数组。2、输出并删除数组中最小的数。使用堆结构实现上述功能的高效算法。输入数据结构编程题全文共40页，当前为第10页。第一行输入一个整数t，代表测试数据的组数。

对于每组测试数据，第一行输入一个整数n，代表操作的次数。

每次操作首先输入一个整数type。

当type=1，增添操作，接着输数据结构编程题全文共40页，当前为第10页。输出每次删除操作输出被删除的数字。样例输入25111213224151117数据结构编程题全文共40页，当前为第11页。数据结构编程题全文共40页，当前为第11页。样例输出121提示每组测试数据的复杂度为O(nlgn)的算法才能通过本次，否则会返回TLE(超时)

需要使用最小堆结构来实现本题的算法5-2:二叉搜索树总时间限制:1000ms内存限制:1024kB描述二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。数据结构编程题全文共40页，当前为第12页。数据结构编程题全文共40页，当前为第12页。输入只有一行，包含若干个数字，中间用空格隔开。（数字可能会有重复）输出输出一行，对输入数字建立二叉搜索树后进行前序周游的结果。样例输入41467334500169724478358962464705145281827961491995942827436样例输出414673341691452813584644365004784917247059628279619429955-3:Huffman编码树总时间限制:1000ms内存限制:65535kB描述数据结构编程题全文共40页，当前为第13页。构造一个具有n个外部节点的扩充二叉树，每个外部节点Ki有一个Wi对应，作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小：数据结构编程题全文共40页，当前为第13页。Min(W1*L1+W2*L2+W3*L3+…+Wn*Ln)Wi:每个节点的权值。Li:根节点到第i个外部叶子节点的距离。编程计算最小外部路径长度总和。输入第一行输入一个整数t，代表测试数据的组数。

对于每组测试数据，第一行输入一个整数n，外部节点的个数。第二行输入n个整数，代表各个外部节点的权值。

2<=N<=100输出输出最小外部路径长度总和。样例输入23123数据结构编程题全文共40页，当前为第14页。数据结构编程题全文共40页，当前为第14页。1135样例输出917提示仅考查huffman树的建立，数据范围小，可以不需要使用堆结构.

不过鼓励使用第一题实现的堆来寻找最小和次小元素。第6周树与森林6-1:物质分解记录总时间限制:60000ms内存限制:131064kB描述数据结构编程题全文共40页，当前为第15页。对物质分解记录的结构进行统计分析。

例如：

给出一份物质分解记录。

Material_1

{

Material_2

{

Material_3

Material_4

Material_5

{

Material_6

Material_7

}

Material_8

}

Material_9

Material_10

}

Material_11

{

Material_l3

Material_7

Material_2

{

Material_3

Material_4

数据结构编程题全文共40页，当前为第16页。Material_5

{

Material_6

M数据结构编程题全文共40页，当前为第15页。数据结构编程题全文共40页，当前为第16页。数据结构编程题全文共40页，当前为第17页。

现输入一个物质名称R，要求输出所有和物质R在记录中属于同一层次且位置在R之后的物质名称。

比如R=“Material_1”，则应该输出“Material_11”；

比如R数据结构编程题全文共40页，当前为第17页。输入输入包含多组数据。第一行是物质分解记录的份数，仅用一个整数表示。从第二行开始，每组数据包括物质分解记录和所需查找的物质R两部分，物质分解记录样式如描述中所示，R的内容和物质分解记录之间有一行空行，下一份记录与上一个R之间有两行空行。

若输入！则表示输入结束。

为简单起见，物质分解记录中每一行的内容为“{”或者“}”或者一个物质名称，不会有其他情况（比如空行）出现。同时每行文字前不会有任何缩进。物质名称是英文字母、数字和下划线组成的字符串。输出数据结构编程题全文共40页，当前为第18页。对每组数据输出一行，如果R在记录中找到，则输出所有与R在同一层次且位置在R之后的物质名称，名称之间无需添加空格，紧密连接即可；否则输出数据结构编程题全文共40页，当前为第18页。样例输入3Material_1{Material_2{Material_3Material_4Material_5{Material_6Material_7}Material_8}Material_9数据结构编程题全文共40页，当前为第19页。数据结构编程题全文共40页，当前为第19页。}Material_2Material_1{Material_2{Material_3Material_4Material_5{Material_6Material_7}Material_8}Material_9Material_10}数据结构编程题全文共40页，当前为第20页。数据结构编程题全文共40页，当前为第20页。{Material_3Material_7Material_2{Material_3Material_4Material_5{Material_6Material_7}Material_8}Material_13}Material_2Material_1数据结构编程题全文共40页，当前为第21页。数据结构编程题全文共40页，当前为第21页。Material_2{Material_3Material_4Material_5{Material_6Material_7}Material_8}Material_9Material_10}Material_20！样例输出数据结构编程题全文共40页，当前为第22页。数据结构编程题全文共40页，当前为第22页。Material_9Material_10No提示读入数据时，需采用如下方式进行读取。

例：若要读取一行输入内容，则

cin.getline(line,lineSize,'\n');

sscanf(line,"%s",tmp);

其中line和tmp为数组指针，类型为char*，linesize为line所指向的数组的规模，为int型。

所需读取的内容最终是存储在tmp数组中。之后如需对读取的内容进行操作，就对tmp进行操作即可，读到空行时tmp长度即为0。

采用其他方法读取可能会出现WA以及RE，TLE。6-2:树的转换总时间限制:5000ms内存限制:65536kB描述数据结构编程题全文共40页，当前为第23页。数据结构编程题全文共40页，当前为第23页。00/|\/123===>1/\\452/\43\5现在请你将一些一般的树用这种方法转换为二叉树，并输出转换前和转换后树的高度。输入数据结构编程题全文共40页，当前为第24页。输入包括多行，最后一行以一个#表示结束。

每行是一个由“u”和“d”组成的字数据结构编程题全文共40页，当前为第24页。输出对于每棵树，按如下格式输出转换前和转换后树的高度：

Treet:h1=>h2

其中t是树的编号（从1开始），h1是转换前树的高度，h2是转换后树的高度。样例输入dudduduududdddduuuuudddduduuuudddduuduuu#样例输出Tree1:2=>4Tree2:5=>5Tree3:4=>5Tree4:4=>4数据结构编程题全文共40页，当前为第25页。6-数据结构编程题全文共40页，当前为第25页。总时间限制:5000ms内存限制:65536kB描述世界上有许多宗教，你感兴趣的是你学校里的同学信仰多少种宗教。你的学校有n名学生（0<n<=50000），你不太可能询问每个人的宗教信仰，因为他们不太愿意透露。但是当你同时找到2名学生，他们却愿意告诉你他们是否信仰同一宗教，你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。输入输入包括多组数据。

每组数据的第一行包括n和m，0<=m<=n(n-1)/2，其后m行每行包括两个数字i和j，表示学生i和学生j信仰同一宗教，学生被标号为1至n。输入以一行n=m=0作为结束。输出数据结构编程题全文共40页，当前为第26页。数据结构编程题全文共40页，当前为第26页。样例输入10912131415161718191101042345485800样例输出数据结构编程题全文共40页，当前为第27页。数据结构编程题全文共40页，当前为第27页。Case2:76-4:电话号码总时间限制:1000ms内存限制:65536kB描述给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：

Emergency911

Alice97625999

Bob91125426

在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。输入第一行是一个整数t，1≤t≤40，表示测试数据的数目。

每个测试样例的第一行是一个整数n，1≤n≤10000，其后n行每行是一个不超过10位的电话号码。数据结构编程题全文共40页，当前为第28页。数据结构编程题全文共40页，当前为第28页。对于每个测试数据，如果是一致的输出“YES”，如果不是输出“NO”。样例输入2391197625999911254265113123401234401234598346样例输出NOYES第7周图数据结构编程题全文共40页，当前为第29页。7-数据结构编程题全文共40页，当前为第29页。总时间限制:1000ms内存限制:65535kB描述“红楼飞雪，一时英杰……”耳边传来了那熟悉的歌声。而这，只怕是我最后一次听到这个声音了。想当年，我们曾经怀着豪情壮志，许下心愿，走过静园，走过一体，走过未名湖畔的每个角落。想当年，我们也曾慷慨高歌，瞻仰民主与科学，瞻仰博雅塔顶，那百年之前的遗韵。没错，我爱北大，我爱这个校园。然而，从当我们穿上学位服的那一刻起，这个校园，就再也不属于我。它只属于往事，属于我的回忆。没错，这，是我在北大的最后一日。此时，此景，此生，此世，将刻骨难忘。再也没有了图书馆自习的各种纷纭，再也没有了运动场上的挥汗如雨，有的，只是心中永远的不舍，与牵挂。数据结构编程题全文共40页，当前为第30页。数据结构编程题全文共40页，当前为第30页。忍不住不回头，我的眼边，有泪光，划过。这时候，突然有一位路人甲从你身旁出现，问你：从XX到XX怎么走？索性，就让我再爱你一次。因为，北大永远在你心中。北大的地图，永远在你的心中。轻手挥扬，不带走一分云彩。输入数据结构编程题全文共40页，当前为第31页。输入分为三个部分。

第一个部分有P+1行，第一行为一个整数P，之后的P行表示北大的地点。

第二个部分有Q+1行，第一行为一个整数Q，之后的Q行每行分别为两个字符串与一个数据结构编程题全文共40页，当前为第31页。输出输出有R行，分别表示每个路线最短的走法。其中两个点之间，用->(矩离)->相隔样例输入6XueYiShiTangCanYinZhongXinXueWuShiTangXueYiXiaoBaiFangBaiNianJiangTangGongHangQuKuanJi6XueYiShiTangCanYinZhongXin80XueWuShiTangCanYinZhongXin40XueYiShiTangXueYiXiaoBaiFang35XueYiXiaoBaiFangXueWuShiTang85CanYinZhongXinGongHangQuKuanJi60GongHangQuKuanJiBaiNianJiangTang351数据结构编程题全文共40页，当前为第32页。数据结构编程题全文共40页，当前为第32页。样例输出XueYiXiaoBaiFang->(35)->XueYiShiTang->(80)->CanYinZhongXin->(60)->GongHangQuKuanJi->(35)->BaiNianJiangTang提示很O疼的一道题。。。说出不少伤感事啊。两个最短路的算法都是可以用的，可以视情况选择你习惯的那个算法。7-2:宝昌县长要修路总时间限制:1000ms内存限制:10000kB描述数据结构编程题全文共40页，当前为第33页。宝昌县长意气风发，他决定整修之前县里的道路。县里的道路很多，但维护费用昂贵。具体如图A所示。线段上面的数据表示两个节点之间的所需要的维修费用，现在需要对乡村进行道路优化，最基数据结构编程题全文共40页，当前为第33页。输入数据结构编程题全文共40页，当前为第34页。第一行只包含一个表示村庄个数的数n，n不大于26，并且这n个村庄是由大写字母表里的前n个字母表示。接下来的n-1行是由字母表的前n-1个字母开头。最后一个村庄表示的字母不用输入。对于每一行，以每个村庄表示的字母开头，然后后面跟数据结构编程题全文共40页，当前为第34页。输出输出是一个整数，表示每个数据集中每月维持道路系统连接到所有村庄所花费的最低成本。样例输入9A2B12I25B3C10H40I8C2D18G55D1E44E2F60G38F0G1H35H1I35数据结构编程题全文共40页，当前为第35页。数据结构编程题全文共40页，当前为第35页。216提示考虑看成最小生成树问题，