CNTT - Thời gian: từ 10/04/2016 - 10/11/2016 Thứ ba, 21/05/2024 - 03:29:04 
Đề cương ôn thi TN "CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT" hệ Cao đẳng năm 2016
ĐỀ CƯƠNG ÔN THI TỐT NGHIỆP HỆ CAO ĐẲNG
NGÀNH: CÔNG NGHỆ THÔNG TIN
Môn: Cấu trúc dữ liệu và giải thuật
I. CẤU TRÚC DỮ LIỆU DANH SÁCH TUYẾN TÍNH
- Danh sách tuyến tính là gì?
- Biểu diễn danh sách tuyến tính bằng mảng và con trỏ.
- Trình bày các phép toán trên danh sách tuyến tính (biểu diễn bằng mảng hay con trỏ): Khởi tạo, tạo danh sách có n phần tử, chèn một phần tử vào danh sách, xóa một phần tử khỏi danh sách bao gồm: tư tưởng, thủ tục, độ phức tạp thủ tục, lấy ví dụ minh họa.
II. CẤU TRÚC DỮ LIỆU (CTDL) DẠNG STACK, QUEUE:
- Định nghĩa
- Biểu diễn dữ liệu trên máy tính (sử dụng mảng hay con trỏ)
- Trình bày các phép toán trên cấu trúc dữ liệu (biểu diễn bằng mảng hay con trỏ): Khởi tạo, thêm vào CTDL một phần tử, xóa khỏi CTDL một phần tử,Kiểm tra CTDL đầy, kiểm tra CTDL rỗng, bao gồm: tư tưởng, thủ tục, độ phức tạp thủ tục, lấy ví dụ minh họa.
II. CẤU TRÚC DỮ LIỆU CÂY NHỊ PHÂN, CÂY TỔNG QUÁT
- Định nghĩa và các khái niệm
- Biểu diễn trên máy tính
- Trình bày các phép duyệt cây: duyệt theo trật tự trước, duyệt theo trật tự giữa, duyệt theo trật tự sau, bao gồm: tư tưởng, thủ tục, độ phức tạp thủ tục, lấy ví dụ minh họa.
IV. MỘT SỐ THUẬT TOÁN SẮP XẾP
- Bài toán sắp xếp
- Trình bày về các giải thuật sắp xếp: Sắp xếp bằng chọn (Selection Sort), sắp xếp bằng chèn (Insertion Sort), sắp xếp nổi bọt (bubble sort), Sắp xếp nhanh (Quick Sort), Sắp xếp bằng vun đống (Heap Sort), Sắp xếp bằng trộn (Merge Sort)
Trong đó mỗi phương pháp trình bày: tư tưởng của phương pháp, thủ tục, độ phức tạp, lấy ví dụ minh hoạ.
V. MỘT SỐ THUẬT TOÁN TÌM KIẾM
- Bài toán tìm kiếm
- Các phương pháp tìm kiếm
1. Tìm kiếm tuần tự: trình bày tư tưởng của phương pháp, thủ tục, độ phức tạp, lấy ví dụ minh hoạ.
2. Tìm kiếm nhị phân: trình bày tư tưởng của phương pháp, thủ tục, độ phức tạp, lấy ví dụ minh hoạ.
3. Cây tìm kiếm nhị phân:
a). Định nghĩa cây tìm kiếm nhị phân
b). Các thao tác trên cây TKNP (tìm kiếm, chèn, xóa): trình bày tư tưởng giải thuật, thủ tục, độ phức tạp, lấy ví dụ minh hoạ.
Truy cập: 5814 lượt