ĐỀ CƯƠNG ÔN TẬP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT


PHẦN I CẤU TRÚC DỮ LIỆU
Một số cấu trúc dữ liệu cơ sở
Ánh xạ (map), mảng (array)
con trỏ (pointer)
mẩu tin (record)
Kiểu dữ liệu trừu tượng (ADT)
Kiểu (type)
Kiểu dữ liệu trừu tượng (Abstract Data Type)
Hạng mục dữ liệu (Data item)
Danh sách (list), ngăn xếp (stack), hàng đợi (queue)
Danh sách
Kiểu dữ liệu trừu tượng danh sách
Cài đặt danh sách dựa trên mảng
Cài đặt danh sách dựa trên con trỏ
Danh sách liên kết đơn (Simple Linked Lists)
Danh sách liên kết kép (Double Linked Lists)
Danh sách liên kết vòng (Circular Linked Lists)
Ngăn xếp
Kiểu dữ liệu trừu tượng ngăn xếp
Cài đặt ngăn xếp dựa trên mảng
Cài đặt ngăn xếp dựa trên con trỏ
Cài đặt đệ quy
Hàng đợi
Kiểu dữ liệu trừu tượng hàng đợi
Cài đặt hàng đợi dựa trên mảng
Cài đặt hàng đợi dựa trên con trỏ
Cây (tree)
Các định nghĩa và tính chất
Duyệt cây
Kiểu dữ liệu trừu tượng cây
Cài đặt cây dựa trên mảng
Cài đặt cây dựa trên con trỏ
Đồ thị (graph)
Các định nghĩa và tính chất
Cài đặt đồ thị
Duyệt đồ thị
Tập hợp (set), tự điển (dictionary)
Tập hợp
Các định nghĩa và tính chất
Kiểu dữ liệu trừu tượng tập hợp
Cài đặt tập hợp bởi hàm đặc trưng (characteristic-function/bitmap/bit-vector)
Cài đặt tập hợp bởi danh sách
Tự điển
Các định nghĩa và tính chất
Kiểu dữ liệu trừu tượng tự điển
Cài đặt tự điển
Cây tìm kiếm và tự điển
Băm (hashing)
Băm đóng
Băm mở
B-cây (B-tree)
Định nghĩa
Cài đặt B-cây

PHẦN II GIẢI THUẬT
Kỹ thuật phân tích giải thuật
Sự cần thiết phải phân tích, đánh giá giải thuật.
Khái niệm độ phức tạp của giải thuật.
Phương pháp xác định độ phức tạp của giải thuật.
Các giải thuật sắp xếp
Các giải thuật sắp xếp đơn giản
QuickSort
HeapSort
Các kỹ thuật thiết kế giải thuật
Chia để trị (Divide and Conquer)
Quy hoạch động (Dynamic Programming)
Các thuật toán "tham ăn" (Greedy Algorithms)
Lần ngược (Backtracking)
Các thuật toán tìm kiếm địa phương (local Search Algorithms)
Cấu trúc dữ liệu và giải thuật lưu trữ ngoài
Sắp xếp ngoài
Tập tin tuần tự
Tập tin bảng băm
Tập tin chỉ mục
Tập tin B-cây

Tài liệu tham khảo
Derick Wood - Data Structures, Algorithms and Performance – Addison-wesley Publishing Company - 1993
A Practical Introduction to Data Structures and Algorithm Analysis – Clifford A. Shaffer – Prentice Hall, Upper Saddle River, New Jersey – 1997
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman - Data Structures and Algorithms – Addison Wesley Publishing Company - 1982
William H. Murray, Chris H. Pappas - Data Structures with STL – Prentice Hall – 2001
Jacques Courtin, Irène Kowarski - Initiation à l`Algorithmique et aux Structures de données (volume 1, 2) – Dunod – 1995
Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley; 1998.
Đinh Mạnh Tường; Cấu trúc dữ liệu & Thuật toán; Nhà xuất bản khoa học và kĩ thuật; Hà nội-2001.
Đỗ Xuân Lôi; Cấu trúc dữ liệu & Giải thuật; 1995.
Giáo trình Cấu trúc dữ liệu, khoa Công nghệ Thông tin, 2003
Giáo trình Giải thuật, khoa Công nghệ Thông tin, 2003
http://pauillac.inria.fr/algo/AofA/
http://www.cs.pitt.edu/~kirk/algorithmcourses/