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函數中要注意兩連結清單等價時都要輸出，比較完之後還要看兩連結清單有沒有剩餘的數字。