title: MOOC Zhejiang University Data Structure Exercise Record - PTA Data Structure Exercise Collection (Complete)

link: MOOC Zhejiang University Data Structure Exercise Record - PTA Data Structure Exercise Collection (Complete)

sticky: true

catalog: true

lang: en

date: 2020-07-05 00:18:16

subtitle: This blog is created to record the exercises I did while studying data structures. If there are any errors in the code, please let me know! PS: Since I have already learned C++, I wrote all the code in C++.

tags:

- c++
- PTA
- data structure
- algorithm

categories: - Exercise Record

Original Blog: MOOC Zhejiang University Data Structure Exercise Record - PTA Data Structure Exercise Collection (Complete)

This blog is created to record the exercises I did while studying data structures. If there are any errors in the code, please let me know! It's also a summary of data structures~

PS: Since I have already learned C++, I wrote all the code in C++, but there are also many things in C.

MOOC Link

## Week 1 - Maximum Subsequence Sum Algorithm, Binary Search#

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 1 - Maximum Subsequence Sum Algorithm, Binary Search

## 01-Complexity 1 Maximum Subsequence Sum Problem (20 points)#

## 01-Complexity 2 Maximum Subsequence Sum (25 points)#

## 01-Complexity 3 Binary Search (20 points)#

## Week 2 - Linear Structures#

Study notes can be found in the blog: Linear List, Stack

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 2 - Linear Structures

## 02-Linear Structure 1 Merge Two Sorted Lists (15 points)#

## 02-Linear Structure 2 Multiplication and Addition of Polynomials (20 points)#

## 02-Linear Structure 3 Reversing Linked List (25 points)#

## 02-Linear Structure 4 Pop Sequence (25 points)#

## Week 3 - Planting Trees (Binary Trees, etc.)#

Study notes can be found in the blog: Binary Tree, Queue

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 3 - Planting Trees (Binary Trees, etc.)

## 03-Tree 1 Isomorphic Trees (25 points)#

## 03-Tree 2 List Leaves (25 points)#

## 03-Tree 3 Tree Traversals Again (25 points)#

## Week 4 - Binary Search Tree & AVL Tree#

Study notes can be found in the blog: Binary Search Tree and AVL Tree

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 4 - Binary Search Tree & AVL Tree

## 04-Tree 4 Same Binary Search Tree? (25 points)#

## 04-Tree 5 Root of AVL Tree (25 points)#

## 04-Tree 6 Complete Binary Search Tree (30 points)#

## 04-Tree 7 Operations on Binary Search Tree (30 points)#

## Week 5 - Heap & Huffman Tree & Disjoint Set#

Study notes can be found in the blog: Heap, Huffman Tree, and Disjoint Set

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 5 - Heap & Huffman Tree & Disjoint Set

## 05-Tree 7 Paths in a Heap (25 points)#

## 05-Tree 8 File Transfer (25 points)#

## 05-Tree 9 Huffman Codes (30 points)#

## Week 6 - Graph (Part 1)#

Study notes can be found in the blog: Graph

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 6 - Graph (Part 1)

Topics covered include basic representation and traversal methods of graphs (BFS, DFS)

## 06-Graph 1 Connected Components (25 points)#

## 06-Graph 2 Saving James Bond - Easy Version (25 points)#

## 06-Graph 3 Six Degrees of Separation (30 points)#

## Week 7 - Graph (Part 2)#

Study notes can be found in the blog: Graph Theory

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 7 - Graph (Part 2)

Topics covered include single-source shortest path algorithms in graphs (Floyd's algorithm, Dijkstra's algorithm)

## 07-Graph 4 Harry Potter's Exam (25 points)#

## 07-Graph 5 Saving James Bond - Hard Version (30 points)#

## 07-Graph 6 Travel Plan (25 points)#

## Week 8 - Graph (Part 3)#

Study notes can be found in the blog: Solving Minimum Spanning Tree Problems (Kruskal's algorithm & Prim's algorithm), Data Structure Study Notes <8> Sorting

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 8 - Graph (Part 3)

Topics covered include minimum spanning tree in graphs, topological sorting for critical path analysis, etc.

## 08-Graph 7 Village Road Network (30 points)#

## 08-Graph 8 How Long Does It Take (25 points)#

## 08-Graph 9 Critical Activity (30 points)#

## Week 9 - Sorting (Part 1)#

Study notes can be found in the blog: Data Structure Study Notes <8> Sorting, Iterative Implementation of Merge Sort (for storage)

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 9 - Sorting (Part 1)

Topics covered include various sorting algorithms (insertion sort, merge sort, heap sort, etc.)

## 09-Sorting 1 Sorting (25 points)#

## 09-Sorting 2 Insert or Merge (25 points)#

## 09-Sorting 3 Insertion or Heap Sort (25 points)#

## Week 10 - Sorting (Part 2)#

Study notes can be found in the blog: Data Structure Study Notes <8> Sorting

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 10 - Sorting (Part 2)

Topics covered include applications of various sorting algorithms, sorting of structures, cycle detection in table sorting, etc.

## 10-Sorting 4 Counting Employees (20 points)#

## 10-Sorting 5 PAT Judge (25 points)#

## 10-Sorting 6 Sort with Swap(0, i) (25 points)#

## Week 11 - Hashing#

Study notes can be found in the blog: Data Structure Study Notes <9> Hashing

Code and thoughts can be found in the blog: PTA Data Structure Exercise Collection Week 11 - Hashing

Topics covered include applications of hashing, KMP, etc.

## 11-Hashing 1 Phone Bill (25 points)#

## 11-Hashing 2 Hashing (25 points)#

## 11-Hashing 3 QQ Account Registration and Login (25 points)#

## KMP String Matching (25 points)#

## Summary#

When doing these exercises, I intentionally used the data structure definitions taught in the online course, and sometimes used STL to save time. It's frustrating to not use convenient things when they are available (such as using priority queue instead of min heap or max heap, using map instead of hashing, STL is really useful).

Anyway, I finally finished them after a long summer vacation. It wasn't in vain. Haha~ I'll work harder and learn Java during the winter vacation. The end. [bushi]