PTA数据结构与算法题目集(中文) 7-277-27 家谱处理 (30 分) 人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例：JohnRobertFrankAndrewNancyDavid家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他有两个子女Robert和Nancy，Robert有两个子女Frank和Andrew，Nancy只有一个子女David。在实验中，研究人员还收集了家庭文件，并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例：JohnistheparentofRobertRobertisasiblingofNancyDavidisadescendantofRobert研究人员需要判断每个陈述语句是真还是假，请编...

PTA数据结构与算法题目集(中文) 7-267-26 Windows消息队列 (25 分) 消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在进程中有特定事件发生，如点击鼠标、文字改变等，系统将把这个消息加到队列当中。同时，如果队列不是空的，这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列，将消息加到队列中以及从队列中获取消息。输入格式:输入首先给出正整数N（≤），随后N行，每行给出一个指令——GET或PUT，分别表示从队列中取出消息或将消息添加到队列中。如果指令是PUT，后面就有一个消息名称、以及一个正整数表示消息的优先级，此数越小表示优先级越高。消息名称是长度不超过10个字符且不含空格的字符串；题目保证队列中消息的优先级无重复，且输入至少有一个GET。输出格式:对于每个GET指令，在一行中输出消息队列中优先级最高的消息的名称和参数。如果消息队列中没有消息，输出EMPTYQUEUE!。对于PUT指令则没有输出。输入样例:9PUTm...

PTA数据结构与算法题目集(中文) 7-257-25 朋友圈 (25 分) 某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。输入格式:输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：第i个俱乐部的人数Mi（空格）学生1（空格）学生2…学生Mi输出格式:输出给出一个整数，表示在最大朋友圈中有多少人。输入样例:743123214356716输出样例:4题目分析：这道题是并查集的利用没什么需要注意的1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>3#include<string.h>...

PTA数据结构与算法题目集(中文) 7-247-24 树种统计 (25 分) 随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。输入格式:输入首先给出正整数N（≤），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（大小写不区分）。输出格式:按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，保留小数点后4位。输入样例:29RedAlderAshAspenBasswoodAshBeechYellowBirchAshCherryCottonwoodAshCypressRedElmGumHackberryWhiteOakHickoryPecanHardMapleWhiteOakSoftMapleRedOakRedOakWhiteOakPoplanSassafrasSycamoreBlackWalnutWillow输出样例:Ash13.7931%Aspen3.4483%Basswood3.4483%B...

PTA数据结构与算法题目集(中文) 7-237-23 还原二叉树 (25 分) 给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。输入格式:输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。输出格式:输出为一个整数，即该二叉树的高度。输入样例:9ABDFGHIECFDHGIBEAC输出样例:5题目分析：利用前序遍历与中序遍历计算树的高度利用前序遍历找树节点然后在中序遍历中限制范围这个我写的最后一个测试点无法通过1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>34intFind(charc,charstr[],intBegin,intEnd)5{6for(inti=Begin;i<End;i++)7{8if(c==str[i])9returni;10}11return-1;12}1314intGetHeight(charstr1[],charstr2[],in...

PTA数据结构与算法题目集(中文) 7-207-20 表达式转换 (25 分) 算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:输入在一行中给出不含空格的中缀表达式，可包含+、-、*、以及左右括号()，表达式不超过20个字符。输出格式:在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。输入样例:2+3*(7-4)+8/4输出样例:2374-*+84/+题目分析：一开始没思路百度一下就有了。。看了大佬的思路一种方法是利用树的想法将中缀表达式写成树的形式利用先序遍历可以输出前缀表达式利用后续遍历可以输出后缀表达式另一种方法是利用栈的想法可以利用栈将中缀表达式转换为前缀后缀表达式https://www.cnblogs.com/zxcjj/p/7793329.html先把我写的这个放在这这个一个测试点都没过。。1#define_CRT_SECURE_NO_WARNING...

PTA数据结构与算法题目集(中文) 7-197-19 求链式线性表的倒数第K项 (20 分) 给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。输入格式:输入首先给出一个正整数K，随后是若干正整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。输出格式:输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。输入样例:41234567890-1输出样例:7题目分析：看到高效就想用数组来因为数组按秩查找是相当快的后面搜了一下别人的做法更好1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>3#include<malloc.h>45intSize;6intmain()7{8intk;9int*Array=(int*)malloc(sizeof(int)*1000000);10scanf("%d",&k);11while(1)12{13intnum;14scanf("%d",&num);15if(num==-...

PTA数据结构与算法题目集(中文) 7-187-18 银行业务队列简单模拟 (25 分) 设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍——即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。输入格式:输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。输出格式:按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。输入样例:821394111315输出样例:13291141315题目分析：一道简单的利用队列的题没什么需要注意的点用这些基础题练手后要学会使用STL自己手写堆栈麻烦不说还可能出错1#define_CRT_SECURE_NO_WARNINGS2#include<s...

PTA数据结构与算法题目集(中文) 7-167-16 一元多项式求导 (20 分) 设计函数求一元多项式的导数。输入格式:以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式:以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。输入样例:34-5261-20输出样例:123-10160题目分析：要注意判断输入停止的标志利用~scanf来判断其它问题到没发现(os:看了其它人的写法发现自己写的不够灵性代码还是一言难尽)1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>34structPolyNode5{6intCoefficient;//系数7intExponent;//指数8}Polynomial[10000],Poly[10000];9intN=0;10intM=0;11voidRead()12{13intCoe,Exp;14while(~scanf("%d%d",&Coe,&a...

PTA数据结构与算法题目集(中文) 7-157-15 QQ帐户的申请与登陆 (25 分) 实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。输入格式:输入首先给出一个正整数N（≤），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。输出格式:针对每条指令，给出相应的信息：1）若新申请帐户成功，则输出“New:OK”；2）若新申请的号码已经存在，则输出“ERROR:Exist”；3）若老帐户登陆成功，则输出“Login:OK”；4）若老帐户Q...

PTA数据结构与算法题目集(中文) 7-147-14 电话聊天狂人 (25 分) 给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。输入格式:输入首先给出正整数N（≤），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。输出格式:在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。输入样例:41300571186213588625832135057118621308862583213588625832180879258321500571386213588625832输出样例:135886258323（7-12是简单的桶排序应用7-13是排序的应用至于排序在另一篇博客里写到了）题目分析:一道利用散列表(哈希表)的基础题将数据读入后进行判断就可以了需要注意要记录所有狂人的人数那么在找到最新的那个狂人时候将人数设为1之后找到与他次数相同的认识将人数加11#defi...

PTA数据结构与算法题目集(中文) 7-117-11 关键活动 (30 分) 假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期...

PTA数据结构与算法题目集(中文) 7-107-10 公路村村通 (30 分) 现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。输入格式:输入数据包括城镇数目正整数N（≤）和候选道路数目M（≤）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。输出格式:输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−，表示需要建设更多公路。输入样例:6151251331471541622342462522663463513614510468563题目分析:一道图的最小生成树算法的基础题利用Prim或Kruskal算法来解决最小生成树问题稠密图用Prim算法稀疏图使用Kruskal算法注意收录顶点在找到后就立刻进行这样就不会对对角线上的元素进行判断1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>3#...

PTA数据结构与算法题目集(中文) 7-97-9 旅游规划 (25 分) 有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。输入格式:输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。输出格式:在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。输入样例:45030112013230034100222023120输出样例:340题目分析:一道图的Dijkstra算法基本题注意本题中不需要输出最短路径的顺序所以不需要记录路径的Path数组需要记录源点到目标点的路径长...

PTA数据结构与算法题目集(中文) 7-87-8 哈利·波特的考试 (25 分) 哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。输...