PTA数据结构与算法题目集(中文) 7-43字符串关键字的散列映射(25分)7-43 字符串关键字的散列映射 (25 分) 给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数(将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3；然后根据表长得到，即是该字符串的散列映射位置。发生冲突时请用平方探测法解决。输入格式:输入第一行首先给出两个正整数N（≤）和P（≥的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个字符串关键字，每个长度不超过8位，其间以空格分隔。输出格式:在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。输入样例1:411HELLOANNKZOELOLI输出样例1:31040输入样例2:611LLOANNANNKZOJINNKAAA输出样例2:3010961...

PTA数据结构与算法题目集(中文) 7-42整型关键字的散列映射(25分)7-42 整型关键字的散列映射 (25 分) 给定一系列整型关键字和素数P，用除留余数法定义的散列函数将关键字映射到长度为P的散列表中。用线性探测法解决冲突。输入格式:输入第一行首先给出两个正整数N（≤）和P（≥的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个整型关键字。数字间以空格分隔。输出格式:在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。输入样例:4524156188输出样例:4013题目分析:一道基本的散列表的题1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>3#include<string.h>4#include<malloc.h>5#include<math.h>6#defineMAXTABLESIZE1000007typedefenum{Legitimate,Empty,Dele...

PTA数据结构与算法题目集(中文) 7-41PAT排名汇总(25分)7-41 PAT排名汇总 (25 分) 计算机程序设计能力考试（ProgrammingAbilityTest，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准（网址http://www.patest.cn）。每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。输入格式:输入的第一行给出一个正整数N（≤100），代表考点总数。随后给出N个考点的成绩，格式为：首先一行给出正整数K（≤300），代表该考点的考生总数；随后K行，每行给出1个考生的信息，包括考号（由13位整数字组成）和得分（为[0,100]区间内的整数），中间用空格分隔。输出格式:首先在第一行里输出考生总数。随后输出汇总的排名表，每个考生的信息占一行，顺序为：考号、最...

PTA数据结构与算法题目集(中文) 7-40奥运排行榜(25分)7-40 奥运排行榜 (25 分) 每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”；而美国的奖牌总数第一，于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”，说不定非洲的国家会成为榜魁……现在就请你写一个程序，对每个前来咨询的国家按照对其最有利的方式计算它的排名。输入格式:输入的第一行给出两个正整数N和M（≤，因为世界上共有224个国家和地区），分别是参与排名的国家和地区的总个数、以及前来咨询的国家的个数。为简单起见，我们把国家从0~ N−1编号。之后有N行输入，第i行给出编号为i−1的国家的金牌数、奖牌数、国民人口数（单位为百万），数字均为[0,1000]区间内的整数，用空格分隔。最后面一行给出M个前来咨询的国家的编号，用...

PTA数据结构与算法题目集(中文) 7-39魔法优惠券(25分)7-39 魔法优惠券 (25 分) 在火星上有个魔法商店，提供魔法优惠券。每个优惠劵上印有一个整数面值K，表示若你在购买某商品时使用这张优惠劵，可以得到K倍该商品价值的回报！该商店还免费赠送一些有价值的商品，但是如果你在领取免费赠品的时候使用面值为正的优惠劵，则必须倒贴给商店K倍该商品价值的金额……但是不要紧，还有面值为负的优惠劵可以用！（真是神奇的火星）例如，给定一组优惠劵，面值分别为1、2、4、-1；对应一组商品，价值为火星币M$7、6、-2、-3，其中负的价值表示该商品是免费赠品。我们可以将优惠劵3用在商品1上，得到M$28的回报；优惠劵2用在商品2上，得到M$12的回报；优惠劵4用在商品4上，得到M$3的回报。但是如果一不小心把优惠劵3用在商品4上，你必须倒贴给商店M$12。同样，当你一不小心把优惠劵4用在商品1上，你必须倒贴给商店M$7。规定每张优惠券和每件商品都只能最多被使用一次，求你可以得到的最大回报。输入格式:输入有两行。第一行首...

PTA数据结构与算法题目集(中文) 7-38寻找大富翁(25分)7-38 寻找大富翁 (25 分) 胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。输入格式:输入首先给出两个正整数N（≤）和M（≤），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。输出格式:在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。输入样例:8381273209518输出样例:201812题目分析：一道利用表排序的题目注意下结果中不同情况的处理1#define_CRT_SECURE_NO_WARNINGS2#include<stdio.h>3#include<string.h>4#include<malloc.h>56intTable[1000000];7intmain()8{9intN...

PTA数据结构与算法题目集(中文) 7-37模拟EXCEL排序(25分)7-37 模拟EXCEL排序 (25 分) Excel可以对一组纪录按任意指定列排序。现请编写程序实现类似功能。输入格式:输入的第一行包含两个正整数N(≤)和C，其中N是纪录的条数，C是指定排序的列号。之后有 N行，每行包含一条学生纪录。每条学生纪录由学号（6位数字，保证没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（[0,100]内的整数）组成，相邻属性用1个空格隔开。输出格式:在N行中输出按要求排序后的结果，即：当C=1时，按学号递增排序；当C=2时，按姓名的非递减字典序排序；当C=3时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。输入样例:31000007James85000010Amy90000001Zoe60输出样例:000001Zoe60000007James85000010Amy90题目分析：这道题是利用表排序和排序算法的一道题排序算法采用快排但最后有两组数据没通过查了资料用c++S...

PTA数据结构与算法题目集(中文) 7-36社交网络图中结点的“重要性”计算(30分)7-36 社交网络图中结点的“重要性”计算 (30 分) 在社交网络中，个人或单位（结点）之间通过某些关系（边）联系起来。他们受到这些关系的影响，这种影响可以理解为网络中相互连接的结点之间蔓延的一种相互作用，可以增强也可以减弱。而结点根据其所处的位置不同，其在网络中体现的重要性也不尽相同。“紧密度中心性”是用来衡量一个结点到达其它结点的“快慢”的指标，即一个有较高中心性的结点比有较低中心性的结点能够更快地（平均意义下）到达网络中的其它结点，因而在该网络的传播过程中有更重要的价值。在有N个结点的网络中，结点v​i​​的“紧密度中心性”(数学上定义为v​i​​到其余所有结点v​j​​ (j≠i)的最短距离(的平均值的倒数：对于非连通图，所有结点的紧密度中心性都是0。给定一个无权的无向图以及其中的一组结点，计算这组结点中每个...

PTA数据结构与算法题目集(中文) 7-35城市间紧急救援(25分)作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。输入格式:输入第一行给出4个正整数N、M、S、D，其中N（2）是城市的个数，顺便假设城市的编号为0~ (；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。输出格式:第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。输入样例:450320304010011132033022232输...

PTA数据结构与算法题目集(中文) 7-347-34 任务调度的合理性 (25 分) 假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。你现在的工作是写程序判定任何一个给定的任务调度是否可行。输入格式:输入说明：输入第一行给出子任务数N（≤），子任务按1~N编号。随后N行，每行给...

PTA数据结构与算法题目集(中文) 7-337-33 地下迷宫探索 (30 分) 地道战是在抗日战争时期，在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事，如下图所示。我们在回顾前辈们艰苦卓绝的战争生活的同时，真心钦佩他们的聪明才智。在现在和平发展的年代，对多数人来说，探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？输入格式:输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1，表示通道所有交叉点和端点）、边数M（≤，表示通道数）和探索起始节点编号S（节点从1到N编号）。随后的M行对应M条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。输出格式:若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的...

PTA数据结构与算法题目集(中文) 7-327-32 哥尼斯堡的“七桥问题” (25 分) 哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(LeonhardEuler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？输入格式:输入第一行给出两个正整数，分别是节点数N (1)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。输出格式:若欧拉回路存在则输出1，否则输出0。输入样例1:61012233145566414163436输出样例1:1输入样例2:581213232425535434输出样例2:0题目分析：一道利用图的遍历的题做这道题需要知道的是无向图存在欧拉回路的...

PTA数据结构与算法题目集(中文) 7-317-31 笛卡尔树 (25 分) 笛卡尔树是一种特殊的二叉树，其结点包含两个关键字K1和K2。首先笛卡尔树是关于K1的二叉搜索树，即结点左子树的所有K1值都比该结点的K1值小，右子树则大。其次所有结点的K2关键字满足优先队列（不妨设为最小堆）的顺序要求，即该结点的K2值比其子树中所有结点的K2值小。给定一棵二叉树，请判断该树是否笛卡尔树。输入格式:输入首先给出正整数N（≤1000），为树中结点的个数。随后N行，每行给出一个结点的信息，包括：结点的K1值、K2值、左孩子结点编号、右孩子结点编号。设结点从0~(N-1)顺序编号。若某结点不存在孩子结点，则该位置给出−。输出格式:输出YES如果该树是一棵笛卡尔树；否则输出NO。输入样例1:682751940-1-11020031221-141522-1-1535-1-1输出样例1:YES输入样例2:682751940-1-11020031211-141522-1-15035-1-1输出样例2:NO题目分析:一道树的应用题主要考察的是...

PTA数据结构与算法题目集(中文) 7-297-29 修理牧场 (25 分) 农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L​i​​个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L​i​​的总和。但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。请编写程序帮助农夫计算将木头锯成N块的最少花费。输入格式:输入首先给出正整数N（≤），表示要将木头锯成N块。第二行给出N个正整数（≤），表示每段木块的长度。输出格式:输出一个整数，即将木头锯成N块的最少花费。输入样例:845121311输出样例:49题目分析：一道基础的利用哈夫曼树的题利用最小堆建哈夫曼树可以再建哈夫曼树的过程中就计算总共...

PTA数据结构与算法题目集(中文) 7-287-28 搜索树判断 (25 分) 对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。输入格式:输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。输出格式:输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。输入样例1:7865710811输出样例1:YES576811108输入样例2:7868510911输出样例2:NO题目分析:一道利用树的基础题将数据读入后再按先序遍历输出比较注意因为有镜像二叉搜索树所...