PTA数据结构与算法题目集(中文) 7-167-16 一元多项式求导 (20 分) 设计函数求一元多项式的导数。输入格式:以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。输出格式:以与输入相同的格式输出导数多项式非零项的系数...

PTA数据结构与算法题目集(中文) 7-157-15 QQ帐户的申请与登陆 (25 分) 实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。输入格式:输入首先给出一个正整数N（≤），随后给出N行指令。每行指令的格式为：&l...

PTA数据结构与算法题目集(中文) 7-147-14 电话聊天狂人 (25 分) 给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。输入格式:输入首先给出正整数N（≤），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的1...

PTA数据结构与算法题目集(中文) 7-117-11 关键活动 (30 分) 假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务...

PTA数据结构与算法题目集(中文) 7-107-10 公路村村通 (30 分) 现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。输入格式:输入数据包括城镇数目正整数N（≤）和候选道路数目M（&l...

PTA数据结构与算法题目集(中文) 7-97-9 旅游规划 (25 分) 有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出...

PTA数据结构与算法题目集(中文) 7-87-8 哈利·波特的考试 (25 分) 哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向...

PTA数据结构与算法题目集(中文) 7-77-7 六度空间 (30 分) “六度空间”理论又称作“六度分隔（SixDegreesofSeparation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之...

PTA数据结构与算法题目集(中文) 7-67-6 列出连通集 (25 分) 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。输入...

PTA数据结构与算法题目集(中文) 7-5 堆中的路径7-5 堆中的路径 (25 分) 将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。输入格式:每组测试第1行包含2个正整数N和M(≤)，分别是插入元...

PTA数据结构与算法题目集(中文) 7-4是否同一颗二叉搜索树给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一...

PTA数据结构与算法题目集(中文) 7-3树的同构给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。 &n...

分析算法最混乱的方面大概集中在对数上面。我们已经看到，某些分治算法将以O(NlogN)时间运行。此外，对数最常出现的规律可概括为下列一般法则:如果一个算法用常数时间(O(1)）将问题的大小削减为其一部分(通常是1/2)，那么该算法就是O(logN)。另一方面，如果使用常数时间只是把问题减少一个常数的数量(如将问题减少1...

 现在我们将要叙述四个算法来求解早先提出的最大子序列和问题。第一个算法，它只是穷举式地尝试所有的可能。for循环中的循环变量反映了Java中数组从0开始而不是从1开始这样一个事实。还有，本算法并不计算实际的子序列；实际的计算还要添加一些额外的代码。publicstaticintmaxSubSum1(int[]...

有几种方法估计一个程序的运行时间。前面的表是凭经验得到的(可以参考:<数据结构与算法分析>读书笔记--要分析的问题)如果认为两个程序花费大致相同的时间，要确定哪个程序更快的最好方法很可能将它们编码并运行。一般地，存在几种算法思想，而我们总愿意尽早除去那些不好的算法思想，因此，通常需要分析算法。不仅如此，进行...