PTA习题：中国大学MOOC-陈越、何钦铭-数据结构-2017秋1

目录

01-复杂度 1 最大子列和问题（20 分） ........................................................................................6

输入格式: .........................................................................................................................6

输出格式: .........................................................................................................................6

输入样例: .........................................................................................................................6

输出样例: .........................................................................................................................6

01-复杂度 2 Maximum Subsequence Sum（25 分）......................................................................6

Input Specification:...........................................................................................................7

Output Specification: ........................................................................................................7

输出样例： ......................................................................................................................9

02-线性结构 2 一元多项式的乘法与加法运算（20 分） ............................................................9

输入格式: .........................................................................................................................9

输出格式: .........................................................................................................................9

输入样例: .........................................................................................................................9

输出样例: .........................................................................................................................9

02-线性结构 3 Reversing Linked List（25 分）.............................................................................10

Input Specification:.........................................................................................................10

Output Specification: ......................................................................................................10

Sample Input:..................................................................................................................10

03-树 1 树的同构（25 分） ..........................................................................................................12

输入格式: .......................................................................................................................12

输出格式: .......................................................................................................................12

输入样例 1（对应图 1）：...........................................................................................12

输出样例 1: ....................................................................................................................13

输入样例 2（对应图 2）：...........................................................................................13

输出样例 2: ....................................................................................................................14

03-树 2 List Leaves（25 分）.........................................................................................................14

Input Specification:.........................................................................................................14

Output Specification: ......................................................................................................14

Sample Output: ...............................................................................................................16

04-树 4 是否同一棵二叉搜索树（25 分） ..................................................................................16

输入格式: .......................................................................................................................16

输出格式: .......................................................................................................................16

输入样例: .......................................................................................................................16

输出样例: .......................................................................................................................16

04-树 5 Root of AVL Tree（25 分） ...............................................................................................17

Input Specification:.........................................................................................................18

Output Specification: ......................................................................................................18

Sample Input 1:...............................................................................................................18

Sample Input:..................................................................................................................19

Sample Output: ...............................................................................................................19

04-树 7 二叉搜索树的操作集（30 分） ......................................................................................19

函数接口定义： ............................................................................................................19

裁判测试程序样例： ....................................................................................................20

输入样例： ....................................................................................................................21

输出样例： ....................................................................................................................22

05-树 7 堆中的路径（25 分） ......................................................................................................22

输入格式: .......................................................................................................................22

输出格式: .......................................................................................................................22

Sample Output 1: ............................................................................................................24

Sample Input 2:...............................................................................................................24

Sample Output 2: ............................................................................................................24

05-树 9 Huffman Codes（30 分） .................................................................................................24

Input Specification:.........................................................................................................25

Output Specification: ......................................................................................................25

Sample Input:..................................................................................................................25

输入格式: .......................................................................................................................26

输出格式: .......................................................................................................................26

输入样例: .......................................................................................................................26

06-图 2 Saving James Bond - Easy Version（25 分） ....................................................................27

Sample Output 2: ............................................................................................................28

06-图 3 六度空间（30 分） ..........................................................................................................28

输入格式: .......................................................................................................................29

输出格式: .......................................................................................................................29

输入样例: .......................................................................................................................29

输出样例: .......................................................................................................................30

输入格式: .......................................................................................................................30

输出格式: .......................................................................................................................30

输入样例: .......................................................................................................................31

输出样例: .......................................................................................................................31

07-图 5 Saving James Bond - Hard Version（30 分） ...................................................................31

Input Specification:.........................................................................................................32

07-图 6 旅游规划（25 分） ..........................................................................................................33

08-图 7 公路村村通（30 分） ......................................................................................................34

输入格式: .......................................................................................................................34

输出格式: .......................................................................................................................34

输入样例: .......................................................................................................................34

输出样例: .......................................................................................................................35

08-图 8 How Long Does It Take（25 分） .....................................................................................35

Input Specification:.........................................................................................................35

Output Specification: ......................................................................................................35

Sample Input 1:...............................................................................................................35

Sample Input 2:...............................................................................................................36

08-图 9 关键活动（30 分）..........................................................................................................36

输入格式: .......................................................................................................................37

输入样例: .......................................................................................................................37

输出样例: .......................................................................................................................37

09-排序 1 排序（25 分） ..............................................................................................................37

输入格式: .......................................................................................................................38

输出格式: .......................................................................................................................38

输入样例: .......................................................................................................................38

输出样例: .......................................................................................................................38

09-排序 2 Insert or Merge（25 分） .............................................................................................38

Input Specification:.........................................................................................................39

Sample Input 2:...............................................................................................................39

09-排序 3 Insertion or Heap Sort（25 分）...................................................................................39

Input Specification:.........................................................................................................40

Output Specification: ......................................................................................................40

Sample Input 1:...............................................................................................................40

Sample Output 1: ............................................................................................................40

10-排序 4 统计工龄（20 分） ......................................................................................................41

输入格式: .......................................................................................................................41

输出格式: .......................................................................................................................41

输入样例: .......................................................................................................................41

Input Specification:.........................................................................................................41

10-排序 6 Sort with Swap(0, i)（25 分）.......................................................................................43

Input Specification:.........................................................................................................43

Output Specification: ......................................................................................................43

Sample Output: ...............................................................................................................44

输出样例: .......................................................................................................................44

11-散列 2 Hashing（25 分） .........................................................................................................44

Output Specification: ......................................................................................................45

11-散列 3 QQ 帐户的申请与登陆（25 分） ................................................................................45

输入格式: .......................................................................................................................45

输出格式: .......................................................................................................................45

输入样例: .......................................................................................................................46

输出样例: .......................................................................................................................46

11-散列 4 Hashing - Hard Version（30 分） .................................................................................46

Input Specification:.........................................................................................................46

输入格式: .......................................................................................................................47

输出格式: .......................................................................................................................47

输入样例: .......................................................................................................................47

输出样例: .......................................................................................................................47