May.BYT's Blog

博主自己搭建个人网站时的全过程，图文并茂！小白友好！既是记录自己建站的过程，也是希望能够帮助到需要的朋友们。

计算机网络的学习笔记

03-树 2 List Leaves题目要求Given a tree, you are supposed to list all the leaves in the order of top down, and left to right. Input Specification:Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-“ will be p ...

03-树 1 树的同构题目要求给定两棵树 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2，则我们称两棵树是“同构”的。例如图 1 给出的两棵树就是同构的，因为我们把其中一棵树的结点 A、B、G 的左右孩子互换后，就得到另外一棵树。而图 2 就不是同构的。 图 1 图 2 现给定两棵树，请你判断它们是否是同构的。 输入格式:输入给出 2 棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从 0 到N−1 编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。 输出格式:如果两棵树是同构的，输出“Yes”，否则输出“No”。 输入样例 1（对应图 1）：1234567891011121314151617188A 1 2B 3 4C 5 -D - -E 6 -G 7 -F - -H - -8G - 4B 7 6F - -A 5 ...

02-线性结构 4 Pop Sequence题目要求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. Input Specification:Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum cap ...

02-线性结构 3 Reversing Linked List题目要求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. Input Specification: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 ...

02-线性结构 2 一元多项式的乘法与加法运算题目要求设计函数分别求两个一元多项式的乘积与和。 输入格式:输入分 2 行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。 输出格式:输出分 2 行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。 输入样例:124 3 4 -5 2 6 1 -2 03 5 20 -7 4 3 1 输出样例:1215 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 15 20 -4 4 -5 2 9 1 -2 0 解题思路：根据输入样例，多项式均是以指数递减的方式输入，可用动态数组和单链表来表示多项式，本题采用单链表来表示。链表结构如下 123456typedef struct PolyNode *Polynomial; // 多项式struct PolyNode { int coef; ...

02-线性结构 1 两个有序链表序列的合并（函数题）题目要求本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。 函数接口定义：1List Merge( List L1, List L2 ); 其中List结构定义如下： 123456typedef struct Node *PtrToNode;struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */};typedef PtrToNode List; /* 定义单链表类型 */ L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。 裁判测试程序样例：1234567891011121314151617181920212223242526272829#include <stdio.h>#include <stdlib.h>typ ...

01-复杂度 3 二分查找 （函数题）题目要求本题要求实现二分查找算法。 函数接口定义：1Position BinarySearch( List L, ElementType X ); 其中List结构定义如下： 123456typedef int Position;typedef struct LNode *List;struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */}; L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标 1 开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。 裁判测试程序样例：1234567891011121314151617181920212223242526272829303132#include <stdio.h>#in ...

01-复杂度 2 Maximum Subsequence Sum题目要求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 subs ...