PAT题解

1

PAT（甲级）2020年春季考试 7-1 Prime Day

• 乔梓鑫   2020-12-03 发布
• 1 收藏

The above picture is from Sina Weibo, showing May 23rd, 2019 as a very cool "Prime Day". That is, not only that the corresponding number of the date 20190523 is a prime, but all its sub-strings end...

1

PAT（甲级）2019年秋季考试 7-4 Dijkstra Sequence

• 乔梓鑫   2020-12-03 发布
• 1 收藏

Dijkstra's algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to ...

1

PAT（甲级）2019年秋季考试 7-3 Postfix Expression

• 乔梓鑫   2020-12-03 发布
• 1 收藏

Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.

1

PAT（甲级）2019年秋季考试 7-2 Merging Linked Lists

• 乔梓鑫   2020-12-03 发布
• 1 收藏

Given two singly linked lists L​1​​=$a​_1$​​→$a​_2$→⋯→$a​_{n-1}$​​→$a​_n$​​ and L​2​​=$b​_1​​$→$b​_2$​​→⋯→$b​_{m-1}$​​→$b​_m​​$​​. If n≥2m, you are supposed to reverse and merge the shorter one int...

1

PAT（甲级）2019年秋季考试 7-1 Forever

• 乔梓鑫   2020-12-03 发布
• 1 收藏

"Forever number" is a positive integer A with K digits, satisfying the following constrains:

1

PAT（甲级）2019年冬季考试 7-4 Cartesian Tree

• 乔梓鑫   2020-12-02 发布
• 1 收藏

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence ...

1

PAT（甲级）2019年冬季考试 7-3 Summit

• 乔梓鑫   2020-12-02 发布
• 1 收藏

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyon...

1

PAT（甲级）2019年冬季考试 7-2 Block Reversing

• 乔梓鑫   2020-12-02 发布
• 1 收藏

Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to...

1

PAT（甲级）2019年冬季考试 7-1 Good in C

• 乔梓鑫   2020-12-02 发布
• 1 收藏

When your interviewer asks you to write "Hello World" using C, can you do as the following figure shows?

1

PAT（甲级）2019年春季考试 7-4 Structure of a Binary Tree

• 乔梓鑫   2020-12-02 发布
• 1 收藏

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

1

PAT（甲级）2019年春季考试 7-3 Telefraud Detection

• 乔梓鑫   2020-12-02 发布
• 1 收藏

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a pro...

1

PAT（甲级）2019年春季考试 7-2 Anniversary

• 乔梓鑫   2020-12-02 发布
• 1 收藏

Zhejiang University is about to celebrate her 122th anniversary in 2019. To prepare for the celebration, the alumni association （校友会） has gathered the ID's of all her alumni. Now your job is t...

1

PAT（甲级）2019年春季考试 7-1 Sexy Primes

• 乔梓鑫   2020-12-02 发布
• 1 收藏

Sexy primes are pairs of primes of the form (p, p+6), so-named since "sex" is the Latin word for "six". (Quoted from [链接])

1

PAT_甲级_1153 Decode Registration Card of PAT

• 乔梓鑫   2020-12-01 发布
• 1 收藏

题目大意：给出一组学生的准考证号和成绩，准考证号包含了等级(乙甲顶)，考场号，日期，和个人编号信息，并有三种查询方式type1：给出考试等级，找出该等级的考生，按照成绩降序，准考证升序排序type2：给出考场...

1

PAT_甲级_1155 Heap Paths

• 乔梓鑫   2020-12-01 发布
• 1 收藏

给定一颗N个节点的完全二叉树的层次序列，需要输出该树的所有从根节点到叶子节点的路径(优先访问右子树),然后判断是否是堆，如果不是输出Not Heap，否则输出Max Heap或者Min Heap。

1

PAT_甲级_1154 Vertex Coloring

• 乔梓鑫   2020-11-30 发布
• 1 收藏

我们使用set diff_colors保存每一次输入的每一个顶点，其大小就是不同顶点的个数，然后遍历每一条边，如果出现一条边的2个顶点颜色相同的情况，说明不存在k-coloring，输出No,否则输出diff_colors集合的大小。

1

PAT_甲级_1152 Google Recruitment

• 乔梓鑫   2020-11-30 发布
• 1 收藏

使用字符串s接受输入的字符串，并枚举每个k位的子串(起始位置从0到L-K)，然后再转换成整数，判断是否是素数，如果是就直接输出并退出程序。如果不存在就输出404.

1

PAT_甲级_1151 LCA in a Binary Tree

• 乔梓鑫   2020-11-30 发布
• 1 收藏

我们借鉴建树的递归过程完成树的部分搜索，如果当前搜索的子树的根节点和查询节点U和V相等，说明其中之一就是祖先，直接保存并返回即可，否则获取U和V是否在左子树或者右子树的标志，如果都在左子树，那么就都往...

1

PAT_甲级_1148 Werewolf - Simple Version

• 乔梓鑫   2020-11-30 发布
• 1 收藏

已知 N 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家，如果有解，在一行中按递增顺序输出 2 个狼人的编号；如果解不唯一，则...

1

PAT_甲级_1150 Travelling Salesman Problem

• 乔梓鑫   2020-11-30 发布
• 1 收藏

给定一个N个顶点和M条边的无向图,K个查询，每一个查询输入长度为n的路径，判断该路径是否是TS cycle或者TS simple cycle并输出题目要求的对应信息。