ĐỀ THI HẾT HỌC PHẦN - MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ĐỀ SỐ 04
Đề thi gồm 02 trang - Sinh viên làm bài trong 60 phút
Phần 1. (Sinh viên trả lời bằng cách ghi ra kết quả mà không cần giải thích gì thêm)
1. Viết các phần tử của mảng a[] = {-1, 10, -7, -5, -15} tại mỗi giai đoạn i khi áp dụng thuật toán sắp xếp nổi bọt để sắp xếp a theo thứ tự giảm:
(i= 5)
(i= 4)
(i= 3)
(i= 2)
2. Viết các phần tử của mảng a[] = {11, 1, -7, 5, -11} tại mỗi giai đoạn i khi áp dụng thuật toán sắp xếp xen vào để sắp xếp a theo thứ tự tăng:
(i= 1)
(i= 2)
(i= 3)
(i= 4)
3. Viết các phần tử của mảng a[] = {-1, 10, -7, 15, 21} tại mỗi giai đoạn i khi áp dụng thuật toán sắp xếp lựa chọn để sắp xếp a theo thứ tự giảm:
(i= 1)
(i= 2)
(i= 3)
(i= 4)
4. Viết các phần tử của cây nhị phân AVL được tạo từ các nút có khóa là các số nguyên 2, 17, 15, -5, -2, 25, 8, 1, 10, -30 khi thực hiện phép duyệt cây theo thứ tự giữa:
5. Viết các phần tử của cây nhị phân AVL được tạo từ các nút có khóa là các số nguyên 2, 17, 15, -5, -2, 25, 8, 1, 10, -30 khi thực hiện phép duyệt cây theo thứ tự trước:
6. Viết các phần tử của cây nhị phân AVL được tạo từ các nút có khóa là các số nguyên 2, 17, 15, -5, -2, 25, 8, 1, 10, -30 khi thực hiện phép duyệt cây theo thứ tự sau:
1. Viết các phần tử của mảng a[] = {-1, 10, -7, -5, -15} tại mỗi giai đoạn i khi áp dụng thuật toán sắp xếp nổi bọt để sắp xếp a theo thứ tự giảm:
(i= 5)
(i= 4)
(i= 3)
(i= 2)
2. Viết các phần tử của mảng a[] = {11, 1, -7, 5, -11} tại mỗi giai đoạn i khi áp dụng thuật toán sắp xếp xen vào để sắp xếp a theo thứ tự tăng:
(i= 1)
(i= 2)
(i= 3)
(i= 4)
3. Viết các phần tử của mảng a[] = {-1, 10, -7, 15, 21} tại mỗi giai đoạn i khi áp dụng thuật toán sắp xếp lựa chọn để sắp xếp a theo thứ tự giảm:
(i= 1)
(i= 2)
(i= 3)
(i= 4)
4. Viết các phần tử của cây nhị phân AVL được tạo từ các nút có khóa là các số nguyên 2, 17, 15, -5, -2, 25, 8, 1, 10, -30 khi thực hiện phép duyệt cây theo thứ tự giữa:
5. Viết các phần tử của cây nhị phân AVL được tạo từ các nút có khóa là các số nguyên 2, 17, 15, -5, -2, 25, 8, 1, 10, -30 khi thực hiện phép duyệt cây theo thứ tự trước:
6. Viết các phần tử của cây nhị phân AVL được tạo từ các nút có khóa là các số nguyên 2, 17, 15, -5, -2, 25, 8, 1, 10, -30 khi thực hiện phép duyệt cây theo thứ tự sau:
Phần 2. (Lập trình)
Cho file dữ liệu trungto.in gồm một dòng ghi lại một biểu thức trung tố gồm các toán hạng là các chữ cái thường và toán tử là các phép toán +, -, *, / và ^.
Hãy sử dụng cấu trúc dữ liệu kiểu ngăn xếp viết chương trình chuyển biểu thức trung tố trong file trungto.in thành biểu thức hậu tố.
Biểu thức hậu tố tìm được được ghi ra màn hình sao cho các toán tử và toán hạng cách nhau một vài kí tự trống.
Ví dụ:
Thang điểm:
Phần 1: 3 điểm
Phần 2: 5 điểm
Trả lời các câu hỏi của giám khảo: 2 điểm
Hãy sử dụng cấu trúc dữ liệu kiểu ngăn xếp viết chương trình chuyển biểu thức trung tố trong file trungto.in thành biểu thức hậu tố.
Biểu thức hậu tố tìm được được ghi ra màn hình sao cho các toán tử và toán hạng cách nhau một vài kí tự trống.
Ví dụ:
Thang điểm:Phần 1: 3 điểm
Phần 2: 5 điểm
Trả lời các câu hỏi của giám khảo: 2 điểm
