1135. Is It A Red-Black Tree (30)-PAT甲级真题

There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties:

(1) Every node is either red or black.
(2) The root is black.
(3) Every leaf (NULL) is black.
(4) If a node is red, then both its children are black.
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

For each given binary search tree, you are supposed to tell if it is a legal red-black tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (<=30) which is the total number of cases. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

Output Specification:

For each test case, print in a line “Yes” if the given tree is a red-black tree, or “No” if not.

Sample Input:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17
Sample Output:
Yes
No
No

题目大意:给一个树的前序遍历,判断它是否为红黑树,是输出Yes,否则输出No。

分析:判断以下几点:
1.是否是二叉搜索树
2.根结点是否为黑色
3.如果一个结点是红色,它的孩子节点是否都为黑色
4.从任意结点到叶子结点的路径中,黑色结点的个数是否相同
所以分为以下几步:
0. 根据先序建立一棵树,用链表表示
1. 根据先序遍历,通过递归和二叉搜索树的性质得到后序post数组,若post的大小不等于n说明不是二叉搜索树~【getPost函数】
2. 判断根结点(题目所给先序的第一个点即根结点)是否是黑色【arr[0] < 0】
3. 根据建立的树,从根结点开始遍历,如果当前结点是红色,判断它的孩子节点是否为黑色,递归返回结果【judge1函数】
4. 从根节点开始,递归遍历,检查每个结点的左子树的高度和右子树的高度(这里的高度指黑色结点的个数),比较左右孩子高度是否相等,递归返回结果【judge2函数】

注意:终于知道自己PAT考试的时候错在哪了。。。维基百科定义:红黑树(英语:Red–black tree)是一种自平衡二叉查找树。AVL树:在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。所以说红黑树不是一种AVL树,红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。而我根据先序遍历直接建树后判断了是否AVL平衡,把判断是否平衡的那段代码注释掉就AC了~

 

1134. Vertex Cover (25)-PAT甲级真题

A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and the edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N-1) of the two ends of the edge.

After the graph, a positive integer K (<= 100) is given, which is the number of queries. Then K lines of queries follow, each in the format:

Nv v[1] v[2] … v[Nv]

where Nv is the number of vertices in the set, and v[i]’s are the indices of the vertices.

Output Specification:

For each query, print in a line “Yes” if the set is a vertex cover, or “No” if not.

Sample Input:
10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2
Sample Output:
No
Yes
Yes
No
No

题目大意:给n个结点m条边,再给k个集合。对这k个集合逐个进行判断。每个集合S里面的数字都是结点编号,求问整个图所有的m条边两端的结点,是否至少一个结点出自集合S中。如果是,输出Yes否则输出No

分析:用vector v[n]保存某结点属于的某条边的编号,比如a b两个结点构成的这条边的编号为0,则v[a].push_back(0),v[b].push_back(0)——表示a属于0号边,b也属于0号边。对于每一个集合做判断,遍历集合中的每一个元素,将当前元素能够属于的边的编号i对应的hash[i]标记为1,表示这条边是满足有一个结点出自集合S中的。最后判断hash数组中的每一个值是否都是1,如果有不是1的,说明这条边的两端结点没有一个出自集合S中,则输出No。否则输出Yes~

 

1075. 链表元素分类(25)-PAT乙级真题

给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而[0, K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如:给定链表为 18→7→-4→0→5→-6→10→11→-2,K为10,则输出应该为 -4→-6→-2→7→0→5→10→18→11。

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出:第1个结点的地址;结点总个数,即正整数N (<= 105);以及正整数K (<=1000)。结点的地址是5位非负整数,NULL地址用-1表示。

接下来有N行,每行格式为:

Address Data Next

其中Address是结点地址;Data是该结点保存的数据,为[-105, 105]区间内的整数;Next是下一结点的地址。题目保证给出的链表不为空。

输出格式:

对每个测试用例,按链表从头到尾的顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。

输入样例:
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
输出样例:
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

分析:将结点用list[10000]保存,list为node类型,node中保存结点的值value和它的next地址。list的下标就是结点的地址。将<0、0~k、>k三部分的结点地址分别保存在v[0]、v[1]、v[2]中,最后将vector中的值依次输出即可~

 

1133. Splitting A Linked List (25)-PAT甲级真题

Given a singly linked list, you are supposed to rearrange its elements so that all the negative values appear before all of the non-negatives, and all the values in [0, K] appear before all those greater than K. The order of the elements inside each class must not be changed. For example, given the list being 18→7→-4→0→5→-6→10→11→-2 and K being 10, you must output -4→-6→-2→7→0→5→10→18→11.

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 (<=1000). The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer in [-105, 105], and Next is the position of the next node. It is guaranteed that the list is not empty.

Output Specification:

For each case, output in order (from beginning to the end of the list) the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
Sample Output:
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

题目大意:给一个链表和K,遍历链表后将<0的结点先输出,再将0~k区间的结点输出,最后输出>k的结点

分析:将结点用list[10000]保存,list为node类型,node中保存结点的值value和它的next地址。list的下标就是结点的地址。将<0、0~k、>k三部分的结点地址分别保存在v[0]、v[1]、v[2]中,最后将vector中的值依次输出即可~

 

1132. Cut Integer (20)-PAT甲级真题

Cutting an integer means to cut a K digits long integer Z into two integers of (K/2) digits long integers A and B. For example, after cutting Z = 167334, we have A = 167 and B = 334. It is interesting to see that Z can be devided by the product of A and B, as 167334 / (167 x 334) = 3. Given an integer Z, you are supposed to test if it is such an integer.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 20). Then N lines follow, each gives an integer Z (10<=Z<=231). It is guaranteed that the number of digits of Z is an even number.

Output Specification:

For each case, print a single line “Yes” if it is such a number, or “No” if not.

Sample Input:
3
167334
2333
12345678
Sample Output:
Yes
No
No

题目大意:给一个偶数个位的正整数num,把它从中间分成左右两个整数a、b,问num能不能被a和b的乘积整除,能的话输出yes,不能的话输出no

分析:要注意a*b如果为0的时候不能取余,否则会浮点错误~
直接用int保存num的值,计算出num的长度len,则令d = pow(10, len / 2)时,num取余d能得到后半部分的整数,num除以d能得到前半部分的整数,计算num % (a*b)是否等于0就可以得知是否可以被整除~