Đề thi cuối kỳ: Cấu trúc dữ liệu & Giải thuật

Nội dung đề thi & Yêu cầu

Đề thi bao gồm các kiến thức trọng tâm đã học trong học kỳ, yêu cầu sinh viên nắm vững lý thuyết và kỹ năng cài đặt thuật toán:

• Câu 1 (3 điểm): Phân tích độ phức tạp thuật toán (Big-O). So sánh hiệu năng các giải thuật sắp xếp (QuickSort, MergeSort, HeapSort).
• Câu 2 (3 điểm): Các thao tác trên cấu trúc dữ liệu tuyến tính: Danh sách liên kết (Linked List), Ngăn xếp (Stack), Hàng đợi (Queue). Ứng dụng Stack để tính biểu thức hậu tố.
• Câu 3 (4 điểm - Bài tập lớn): Cây nhị phân tìm kiếm (BST) hoặc Đồ thị (Graph).
  • - Cài đặt các hàm thêm, xóa, sửa nút trên cây.
  • - Duyệt cây (LNR, NLR, LRN).
  • - Thuật toán tìm đường đi ngắn nhất (Dijkstra) hoặc Duyệt đồ thị (BFS/DFS).

*Lưu ý: Sinh viên không được sử dụng tài liệu trong phòng thi.