PTA-数据结构与算法基础题目集（中文）

目录

Function6-1 单链表逆转 (20 分)

Programming

7-1 最大子列和问题 (20 分)

7-2 一元多项式的乘法与加法运算 (20 分)

7-51 两个有序链表序列的合并 (20 分)

ps：完成中国大学MOOC-陈越、何钦铭-数据结构-2021秋（题目类似）再更新这个博客。

本题要求实现一个函数，将给定的单链表逆转。

思路如图所示：

给定K个整数组成的序列{ N1, N2, ..., NK }，“连续子列”被定义为{ Ni, Ni+1, ..., Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；

数据2：10^2个随机整数；

数据3：10^3个随机整数；

数据4：10^4个随机整数；

数据5：10^5个随机整数；

思路：用数组实现，<code>MaxSubseqSum2</code>使用两个for循环，比较当前子列和与预设最大子列和。

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出<code>0 0</code>。

注意：

1、<code>P(front)</code>作为头部空结点指针，最后<code>P(front)</code>要用<code>t</code>配合<code>free</code>函数释放。

2、<code>rear = P(front)</code> 一开始是空结点指针，但最后会作为尾部结点指针，所以最终<code>rear-&gt;link == NULL</code>

3、设置<code>flag</code>调整输出格式。

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

思路：输入格式最后一个是<code>-1</code>且无效把我折磨了好久。Merge函数中要注意两链表等价时都要输出，比较完之后还要看两链表有没有剩余的数字。