数据结构编程题

《数据结构编程题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第4周二叉树基础4-2:文本二叉树总时间限制:1000ms内存限制:65536kB描述如上图，一棵每个节点都是一个字母，且字母互不相同的二叉树，可以用以下若干行文本表示:A-B--*--C-D--E---*---F在这若干行文本中：1)每个字母代表一个节点。该字母在文本中是第几行，就称该节点的行号是几。根在第1行2)每个字母左边的'-'字符的个数代表该结点在树中的层次（树根位于第0层）3)若某第i层的非根节点在文本中位于第n行，则其父节点必然是第i-1层的节点中，行号小于n,且行号与n的差最小的那个4)若某文本中位于第n行的节点(层次是i)

2、有两个子节点，则第n+1行就是其左子节点，右子节点是n+1行以下第一个层次为i+1的节点5)若某第i层的节点在文本中位于第n行，且其没有左子节点而有右子节点，那么它的下一行就是i+1个'-'字符再加上一个'*'给出一棵树的文本表示法，要求输出该数的前序、后序、中序遍历结果输入第一行是树的数目n接下来是n棵树，每棵树以'0'结尾。'0'不是树的一部分每棵树不超过100个节点输出对每棵树，分三行先后输出其前序、后序、中序遍历结果两棵树之间以空行分隔样例输入2A-B--*--C-D--E---*---F0A-B-C0样例输出ABCDEFCBFED

3、ABCAEFDABCBCABAC4-3:由中根序列和后根序列重建二叉树总时间限制:500ms内存限制:65535kB描述我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树中根序列是953267后根序列932675前根序列596732输入两行。第一行是二叉树的中根序列，第二

4、行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。输出一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。样例输入953267932675样例输出5967324-4:表达式·表达式树·表达式求值总时间限制:1000ms内存限制:65535kB描述众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树：+/a*/bc现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达

5、式用表达式二叉树的形式输出出来。输入输入分为三个部分。第一部分为一行，即中缀表达式。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。第二部分为一个整数n，表示中缀表达式的变量数。第三部分有n行，每行格式为C　x，C为变量的字符，x为该变量的值。输出输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐

6、标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。样例输入a+b*c3a2b7c5样例输出abc*+

7、+/a*/bc37第5周二叉树应用5-1:实现堆结构总时间限制:3000ms内存限制:65535kB描述定义一个数组，初始化为空。在数组上执行两种操作：1、增添1个元素，把1个新的元素放入数组。2、输出并删除数组中最小的数。使用堆结构实现上述功能的高效算法。输入第一行输入一个整数t，代表测试数据的组数。对于每组测试数据，第一行输入一个整数n，代表操作的次数。每次操作首先输入一个整数type。当type=1，增添操作，接着输入一个整数u，代表要插入的元素。当type=2，输出删除操作，输出并删除数组中最小的元素。1<=n<=100000。

8、输出每次删除操作输出被删除的数字。样例输入251112132241511172样例输出121提示每组测试数据的复杂度为O(nlgn)的算法才能通过本次，否则会返回TLE(超时)需