DSA On Thi Thao Tác 1: Ôn Tập Cấu Trúc Dữ Liệu Cơ Bản. Môn Cấu trúc dữ liệu và giải thuật (UET) | Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội.

lOMoAR cPSD| 59735516
Cơ bản cấu trúc dữ liệu:
Queue, Stack, Priority Queue (heap), Map/Set( BST, cây cân bằng, bảng băm)
- liệt kê được API (các thao tác cơ bản), các cách cài đặt.
- với từng cách cài đặt, biết độ phức tạp tính toán của các thao tác cơ bản theo thời gian chạy, bộ nhớ.
- biết thuật toán của các thao tác cơ bản,
- biết cách áp dụng cấu trúc dữ liệu cho bài toán cụ thể (với bài toán cụ thể, cho biết cần
sử dụng cấu trúc dữ liệu gì để mô hình hóa dữ liệu, mô hình hóa như thế nào). 1. Stack (Ngăn xếp):
- Hoạt động theo nguyên tắc LIFO (Last In, First Out). Chỉ thao tác ở đỉnh ngăn xếp.
- Các thao tác cơ bản: push(x), pop(), top(), empty(). -
Các cách cài đặt: Mảng, Linked List. 2. Queue (Hàng đợi):
- Hoạt động theo nguyên tắc FIFO (First In, First Out).
- Các thao tác cơ bản: enqueue(x), dequeue(), front(), empty(). - Các cách cài đặt: Mảng vòng, Linked List.
3. Priority Queue (Hàng đợi ưu tiên):
- Phần tử có độ ưu tiên cao hơn được xử lý trước.
- Các thao tác cơ bản: push(x), pop(), top(), empty().
- Các cách cài đặt: Heap (O(log(n))); Mảng hoặc Linked List O(n). 4. Map/Set
- Map: Lưu cặp Key-value, cho phép ánh xạ key sang value.
- Set: Lưu trữ các phần tử duy nhất, không trùng lặp.
- Các thao tác cơ bản: insert(), erase(), find(), (count() -> kiểm tra có tồn tại hay không). - Cách cài đặt:
- Binary Search Tree: (O(log(n))); nếu mất cân bằng sẽ giảm hiệu suất.
- Balanced Tree - AVL: Tự cân bằng khi thao tác; (O(log(n))).
- Hash Table: Tốt nhất O(1), tệ nhất O(n) khi xảy ra đụng độ. lOMoAR cPSD| 59735516