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]
