Data structures are crucial—this is a consensus for everyone in Computer Science and coding. It is worth looking into famous books and courses. I personally completed CS106x. There are certainly more advanced courses worth taking.

Anyway, self-study is essential. This repository only provides some course materials. You can find the course labs in my other repositories.

Data Structure Course Resources

This repository contains resources, code examples, and assignments for the Data Structure course.

Project Structure

• avl_tree_demo_gemini/: A C++ implementation demonstration of an AVL Tree.
• dijkstra/: Implementation of Dijkstra's algorithm.
• red_black_tree/: Implementation of a Red-Black Tree.
• homework/: Course homework assignments.
• Lab/: Laboratory exercises and slides.
• powerpoint/: Course presentation slides.
• AVL_红黑树_B树_B+树.txt: Notes on various tree data structures.

Getting Started

To run the code examples, you will need a C++ compiler (like g++ or clang++).

AVL Tree Demo

Navigate to avl_tree_demo_gemini/ and use the provided Makefile or compile the source files in src/.

Other Algorithms

The dijkstra and red_black_tree folders contain standalone C++ files that can be compiled directly.

Data Structure Exam Question Types and Scope for 2025 Fall

Multiple Choice Questions (10 questions, 20 points)

• Analyze time complexity of given algorithms.
• Circular singly linked list model with a head node.
• Characteristics of stacks.
• Compressed storage of symmetric matrices.
• Pre-order, in-order, and post-order traversal sequences of binary trees, and constructing binary trees from given traversal sequences.
• Simulation of the Huffman coding decoding process.
• Principles of solving topological sort using Depth First Search (DFS).
• Number of nodes and minimality of DAGs representing expressions.
• Correlation between comparison counts and the initial dataset in sorting algorithms.
• Probe counts for synonyms in linear probing hashing.

Free Response Questions (5 questions, 60 points)

Try to write as much as possible, get as many points as possible!

• Tree Structures: Simulation of constructing a Binary Search Tree (BST) from a given sequence; simulation of constructing a Balanced Binary Search Tree (AVL Tree) (identifying types of imbalance and corresponding rotation adjustments); restoring a forest from a binary tree.
• Hash Tables: Construct a hash table using linear probing based on a given key sequence, hash function, and table length; calculate the average search length for successful and unsuccessful searches under equal probability.
• Graph Algorithms: Simulation of Dijkstra's algorithm for solving the single-source shortest path problem; simulation of Kruskal's algorithm for finding the Minimum Spanning Tree.
• Critical Path: Construction of AOE network; Kahn's algorithm for solving DAG topological sort; calculating earliest and latest occurrence times of events; minimum time required to complete the project; earliest and latest start times of activities; identifying critical activities and critical paths.
• Sorting: Simulate the execution process of specified sorting algorithms (Shell Sort, Quick Sort) based on a given key sequence.

Algorithm Design Questions (2 questions, 20 points)

Try to write as much as possible, get as many points as possible!

• Linked List: Implementation of comprehensive operations on a singly linked list (combining basic operations like search, delete, etc.) (8 points).
• Sorting: Bubble Sort algorithm and its optimized variants (12 points).
  • First, briefly describe the main idea of the algorithm.
  • Then, write a function in C++ to implement the specified functionality, providing comments at key points.
  • Note: Function names, parameters, and return values should comply with coding standards. If dynamic memory allocation is involved, explicitly release memory when it is no longer used (e.g., delete p) to prevent memory leaks.