Bài tập CTDLGT giữa kỳ 20161

Cài đặt dùng Java hoặc C# hoặc C/C++

Bài 1. Cài đặt các hàm đầy đủ để mô tả cấu trúc dữ liệu mảng kích thước biến đổi

Các thao tác cần có gồm

• Add (int value): Thêm phần tử vào cuối mảng,
• RemoveAt(int index): xóa phần tử ở vị trí index 
• Size(): trả về số lượng phần tử hiện có của mảng
• Maxsize(): trả về kích thước/ số lượng phần tử tối đa mà cấu trúc có thể lưu
• Find(int value): trả về vị trí phần tử có gía trị bằng value trong mảng nếu có, ngược lại thì trả về giá trị -1
• Get(int index) trả về giá trị phần tử tại ví trí index trong mảng nếu có

Xây dựng thành class là tốt nhất, nếu không tổ chức thành các hàm trong C/C++ với tham số truyền vào như yêu cầu trên.

Bài 2. Cài đặt đầy đủ các hàm/ phương thức của cấu trúc danh sách liên kết đơn nối thẳng có kiểu class T

• Thêm (đâù, giữa/cuối)
• Xóa (đâù, giữa/cuối)
• Tìm kiếm

Các lớp cài đặt này nên dùng Template class

Bài 3. Cài đặt các hàm mô tả cấu trúc danh sách liên kết đơn nối vòng

Bài 4. Cài đặt các hàm mô tả danh sách liên kết đôi

Bài 5. Cài đặt cấu trúc Ngăn xếp/Hàng đợi dùng mảng kích thước biến đổi

Bài 6. Cài đặt lớp biểu diễn cây nhị phân với các tính năng sau

• Thêm nút trái
• Thêm nút phải
• Lấy giá trị nút trái/phải
• Đếm số nút trên cây
• Tìm nút lá sâu nhất/nông nhất (thời gian O(n))
• Tìm chiều cao của cây
• Tìm tổ tiên chung gần nhất của 2 nút bất kỳ trên cây
• Duyệt cây theo thứ tự trước/giữa/sau

Bài 7. Cài đặt cây nhị phân để biểu diễn cây biểu thức

• Tạo cây biểu thức từ biểu thức trung tố (biểu thức chỉ bao gồm các toán hang 1 chữ cái/chữ số và các toán tử đơn giản +,-,*,/,%,^,!,... và dấu ngoặc đơn)
• In ra biểu thức tiền tố, trung tố, hậu tố
• Kiểm tra biểu thức trung tố ban đầu có phải hợp lệ (dấu ngoặc hợp lệ và toán tử hợp lệ, chỉ cần check với một vài toán tử thông dụng)

Bài 8. Xây dựng thuật toán sinh ra màn chơi sodoku bằng cách thêm ngẫu nhiên n số (từ 1-9 vào một màn chơi ban đầu trắng). Thuật toán này cần cài đặt dùng Backtracking và đảm bảo là màn chơi này hợp lệ.

Bài 9. Cài đặt lớp biểu diễn cây nhị phân tìm kiếm tổng quát (có thể kế thừa từ lớp trong bài 6) hỗ trợ các thao tác

• Kiểm tra cây nhị phân có phải là cây nhị phân tìm kiếm
• Kiểm tra cây nhị phân tìm kiếm có phải cây cân bằng
• Thực hiện hàm tìm kiếm và trả về nút chứa khóa (nếu tìm thấy) trên cây
• Thực hiện hàm thêm nút/xóa nút trên cây