Đề cương ôn tập Cấu trúc dữ liệu và giải thuật

Tổng hợp lý thuyết và bài tập ôn thi cuối kỳ môn Cấu trúc dữ liệu và giải thuật. Tài liệu bám sát đề cương của bộ môn, mỗi phần đều có ví dụ và độ phức tạp kèm theo. File PDF đính kèm là bản đầy đủ có hình minh họa. Chương 1: Danh sách liên kết Danh sách liên kết là cấu trúc dữ liệu gồm nhiều nút, mỗi nút chứa dữ liệu và con trỏ tới nút khác. Khác với mảng, các nút không cần nằm liền nhau trong bộ nhớ nên việc thêm và xóa không phải dịch chuyển phần tử. Mục 1.1 Danh sách liên kết đơn Mỗi nút giữ đúng một con trỏ trỏ tới nút kế tiếp. Nút cuối trỏ tới null. - Thêm vào đầu: O(1), chỉ cần đổi con trỏ head - Thêm vào cuối: O(n) nếu không giữ con trỏ tail - Tìm kiếm: O(n), bắt buộc duyệt tuần tự - Xóa một nút đã biết vị trí trước đó: O(1) Lỗi hay gặp khi làm bài: quên cập nhật con trỏ head khi xóa chính nút đầu tiên, dẫn tới mất toàn bộ danh sách. Mục 1.2 Danh sách liên kết đôi Mỗi nút giữ thêm con trỏ tới nút phía trước, nhờ vậy duyệt được cả hai chiều và xóa một nút bất kỳ chỉ tốn O(1) khi đã có con trỏ tới nó. Đổi lại tốn thêm bộ nhớ cho con trỏ thứ hai và mọi thao tác đều phải cập nhật hai chiều. Chương 2: Ngăn xếp và hàng đợi Mục 2.1 Ngăn xếp Ngăn xếp hoạt động theo nguyên tắc vào sau ra trước. Hai thao tác chính là push và pop, cả hai đều O(1). Ứng dụng thường gặp: 1. Kiểm tra dấu ngoặc cân bằng trong biểu thức 2. Chuyển biểu thức trung tố sang hậu tố 3. Khử đệ quy, lưu trạng thái lời gọi hàm 4. Chức năng hoàn tác trong trình soạn thảo Mục 2.2 Hàng đợi Hàng đợi theo nguyên tắc vào trước ra trước. Khi cài bằng mảng nên dùng hàng đợi vòng, nếu không phần đầu mảng bị bỏ trống sau nhiều lần lấy phần tử ra mà không dùng lại được. Chương 3: Cây nhị phân tìm kiếm Cây nhị phân tìm kiếm có tính chất: mọi nút bên trái nhỏ hơn nút gốc, mọi nút bên phải lớn hơn nút gốc. Nhờ vậy tìm kiếm chỉ mất O(log n) khi cây cân bằng. Vấn đề: nếu chèn dãy đã sắp xếp sẵn, cây suy biến thành danh sách liên kết và độ phức tạp tụt về O(n). Cây AVL giải quyết bằng cách tự xoay lại sau mỗi lần chèn hoặc xóa để giữ chênh lệch chiều cao hai nhánh không quá 1. Ba cách duyệt cây cần thuộc: - Duyệt trước: gốc, trái, phải - Duyệt giữa: trái, gốc, phải, cho ra dãy đã sắp xếp tăng dần - Duyệt sau: trái, phải, gốc Chương 4: Bảng băm Bảng băm dùng hàm băm ánh xạ khóa thành chỉ số trong mảng, cho phép tra cứu trung bình O(1). Hai khóa khác nhau có thể cho cùng chỉ số, gọi là va chạm. Hai cách xử lý va chạm: 1. Nối chuỗi: mỗi ô chứa một danh sách liên kết các phần tử trùng chỉ số 2. Địa chỉ mở: dò tuyến tính, dò bậc hai hoặc băm kép để tìm ô trống kế tiếp Hệ số tải càng cao thì va chạm càng nhiều. Khi vượt ngưỡng khoảng 0.75 nên cấp phát mảng lớn hơn và băm lại toàn bộ. Chương 5: Các thuật toán sắp xếp Bảng so sánh cần nhớ để làm phần trắc nghiệm: - Sắp xếp nổi bọt: trung bình và xấu nhất đều O(n^2), ổn định - Sắp xếp chèn: xấu nhất O(n^2) nhưng tốt nhất O(n) khi dãy gần như đã sắp - Sắp xếp trộn: luôn O(n log n), ổn định, cần thêm O(n) bộ nhớ - Sắp xếp nhanh: trung bình O(n log n), xấu nhất O(n^2) khi chọn chốt kém - Sắp xếp vun đống: luôn O(n log n), không ổn định, sắp tại chỗ Câu hỏi hay ra thi: vì sao sắp xếp nhanh thường chạy nhanh hơn sắp xếp trộn dù cùng độ phức tạp trung bình? Trả lời gọn: sắp xếp nhanh làm việc tại chỗ nên tận dụng bộ nhớ đệm tốt hơn và hằng số ẩn nhỏ hơn.