目录
Function
01-复杂度3 二分查找 (20 分)
02-线性结构1 两个有序链表序列的合并 (15 分)
04-树7 二叉搜索树的操作集 (30 分)
Programming
01-复杂度1 最大子列和问题 (20 分)
01-复杂度2 Maximum Subsequence Sum (25 分)
02-线性结构2 一元多项式的乘法与加法运算 (20 分)
02-线性结构3 Reversing Linked List (25 分)
02-线性结构4 Pop Sequence (25 分)
03-树1 树的同构 (25 分)
04-树4 是否同一棵二叉搜索树 (25 分)
05-树7 堆中的路径 (25 分)
05-树8 File Transfer (25 分)
本题要求实现二分查找算法。
思路：
想一想这个说法是否正确？在二分查找的程序实现中，如果left和right的更新不是取mid+1和mid-1而是都取mid，程序也是正确的。
答案
这个说法是错误的 。
考虑查找值大于数组内最大值的情况，如果都取mid，循环到只有两元素时就会导致mid始终与左边界值相等，从而程序**无限循环**；考虑查找值小于数组内最小值的情况，由于可能存在数列中仅有一个元素的情况所以进入循环的条件必须要包含left==right，在此前提下，循环到最后左右边界与mid将会重合从而无限循环。
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
思路：注意非递减的意思是，不严格递增。也就是说，当遇到两个相同的数字时，两个数字都要合并进去。
完成日期：21.11.06
本题要求实现给定二叉搜索树的5种常用操作。
函数接口定义：
其中<code>BinTree</code>结构定义如下：
函数<code>Insert</code>将<code>X</code>插入二叉搜索树<code>BST</code>并返回结果树的根结点指针；
函数<code>Delete</code>将<code>X</code>从二叉搜索树<code>BST</code>中删除，并返回结果树的根结点指针；如果<code>X</code>不在树中，则打印一行<code>Not Found</code>并返回原树的根结点指针；
函数<code>Find</code>在二叉搜索树<code>BST</code>中找到<code>X</code>，返回该结点的指针；如果找不到则返回空指针；
函数<code>FindMin</code>返回二叉搜索树<code>BST</code>中最小元结点的指针；
函数<code>FindMax</code>返回二叉搜索树<code>BST</code>中最大元结点的指针。
裁判测试程序样例：
输入样例：
输出样例：
AC code：
根据搜索二叉树左小右大的特点设置函数。
时常利用递归。
多考虑树节点为空的情况。
本地AC code：
给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
数据1：与样例等价，测试基本正确性；
数据2：10^2个随机整数；
数据3：10^3个随机整数；
数据4：10^4个随机整数；
数据5：10^5个随机整数；
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出<code>0 0</code>。
输入样例:
输出样例:
答案：
思路：用数组实现，<code>MaxSubseqSum2</code>使用两个for循环，比较当前子列和与预设最大子列和。
Given a sequence of K integers { N1, N2, ..., NK }. A continuous subsequence is defined to be { Ni, Ni+1, ..., Nj } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.
Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input:
Sample Output:
AC code:
Reference AC code:
思路：要区分两种特殊情况。
至少有一个零，输出结果为 <code>0 0 0</code>
全都是负数，输出结果为 <code>0 first_neg_number last_neg_number</code>
设计函数分别求两个一元多项式的乘积与和。
注意：
1、<code>P(front)</code>作为头部空结点指针，最后<code>P(front)</code>要用<code>t</code>配合<code>free</code>函数释放。
2、<code>rear = P(front)</code> 一开始是空结点指针，但最后会作为尾部结点指针，所以最终<code>rear->link == NULL</code>
3、设置<code>flag</code>调整输出格式。
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.
翻译：给定一个常数K和一个单链链表L，你应该把L上每个K元素的链结颠倒。例如，给定L为1→2→3→4→5→6，如果K=3，那么你必须输出3→2→1→6→5→4；如果K=4，你必须输出4→3→2→1→5→6。
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
翻译：每个输入文件包含一个测试用例。对于每种情况，第一行包含第一个节点的地址、节点总数的正N（<105）和要反转的子列表的长度的正K（<N）。节点的地址是一个5位非负整数，空值用-1表示。
Then N lines follow, each describes a node in the format:
where <code>Address</code> is the position of the node, <code>Data</code> is an integer, and <code>Next</code> is the position of the next node.
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
思路：用三个数组的方式模拟链表，分别存放当前地址、数值、下一个地址。实际上用结构数组、链表的方法也可以，但三个数组易于理解。
样例图示：
参考链接1；参考链接2
完成日期：21.11.07
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.
翻译：
给定一个最多能保存M个数的堆栈。按1，2，3，…，N的顺序推N个数字，然后随机弹出。您应该知道给定的数字序列是否可能是堆栈的弹出序列。例如，如果M是5，N是7，我们可以从堆栈中获得1，2，3，4，5，6，7，但不能从3，2，1，7，5，6，4。
输入规格：
每个输入文件包含一个测试用例。对于每种情况，第一行包含3个数字（都不超过1000）：M（堆栈的最大容量）、N（推送序列的长度）和K（要检查的pop序列的数量）。接下来是K行，每行包含N个数字的pop序列。一行中的所有数字都用空格隔开。
输出规格：
对于每个弹出序列，如果确实是堆栈的可能弹出序列，则在一行中打印 "YES"，如果不是，则打印"NO"。
pop randomly这句话要和堆栈先进后出的特点紧密联系。
按1，2，3....，N（正整数序列）依次入栈，每入栈一个元素都要先判断是否溢出，如果没溢出，再判断该元素能否出栈及其之前已经入栈的元素能否出栈。最后，如果样例所有元素都能出栈，则说明是出栈序列。
参考链接
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。
现给定两棵树，请你判断它们是否是同构的。
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
如果两棵树是同构的，输出“Yes”，否则输出“No”。
输入样例1（对应图1）：
输出样例1:
输入样例2（对应图2）：
输出样例2:
判断cl、cr是否为横杠<code>-</code>时，四个if语句是处于同一水平同时判断的。
初始化root为Null可以使得当N为空时，能够返回Null(-1)。
判断是否“同构”时，需要多方考虑。也要经常调用递归。
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
两个flag要区分开，<code>Check</code>的flag是要用来标记是否已经检查过，不要重复检查
<code>Judge</code>的flag是用来标记两棵树是否已经一致
除了对照树要当作树来建立，目标树当作序列对待即可，这也是<code>Check</code>设置flag的原因
b站参考链接
将一系列给定数字插入一个初始为空的小顶堆<code>H[]</code>。随后对任意给定的下标<code>i</code>，打印从<code>H[i]</code>到根结点的路径。
每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。
对输入中给出的每个下标<code>i</code>，在一行中输出从<code>H[i]</code>到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。
思路：先丢个链接，何钦铭老师的思路。
We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?
Each input file contains one test case. For each test case, the first line contains N (2≤N≤104), the total number of computers in a network. Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:
where <code>I</code> stands for inputting a connection between <code>c1</code> and <code>c2</code>; or
where <code>C</code> stands for checking if it is possible to transfer files between <code>c1</code> and <code>c2</code>; or
where <code>S</code> stands for stopping this case.
For each <code>C</code> case, print in one line the word "yes" or "no" if it is possible or impossible to transfer files between <code>c1</code> and <code>c2</code>, respectively. At the end of each case, print in one line "The network is connected." if there is a path between any pair of computers; or "There are <code>k</code> components." where <code>k</code> is the number of connected components in this network.
Sample Input 1:
Sample Output 1:
Sample Input 2:
Sample Output 2:
思路：先丢个链接，陈越老师的思路。
![在DOS下运行不了ipconfig命令[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)