ĐỀ THI HẾT HỌC PHẦN - MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT ĐỀ SỐ 07
Đề 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[] = {-12, 10, -7, 5, 17} 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)
2. Viết các phần tử của mảng a[] = {-11, 10, -17, 25, 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ự tăng:
(i= 5)
(i= 4)
(i= 3)
(i= 2)
3. Viết các phần tử của mảng a[] = {11, 12, -7, -15, -1} 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ự 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 -21, 10, 15, -5, -2, 25, 8, 1, -10, 30 khi thực hiện phép duyệt cây theo thứ tự trước:
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 -21, 10, 15, -5, -2, 25, 8, 1, -10, 30 khi thực hiện phép duyệt cây theo thứ tự giữa:
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 -21, 10, 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[] = {-12, 10, -7, 5, 17} 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)
2. Viết các phần tử của mảng a[] = {-11, 10, -17, 25, 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ự tăng:
(i= 5)
(i= 4)
(i= 3)
(i= 2)
3. Viết các phần tử của mảng a[] = {11, 12, -7, -15, -1} 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ự 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 -21, 10, 15, -5, -2, 25, 8, 1, -10, 30 khi thực hiện phép duyệt cây theo thứ tự trước:
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 -21, 10, 15, -5, -2, 25, 8, 1, -10, 30 khi thực hiện phép duyệt cây theo thứ tự giữa:
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 -21, 10, 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)
Viết chương trình tìm X = (x 1 , x 2 ,..,x n ) và giá trị f(X) của hàm
đạt giá trị nhỏ nhất. Trong đó,
là các số nguyên, n, b là các số tự nhiên, n ≤ 100.
đạt giá trị nhỏ nhất. Trong đó,
là các số nguyên, n, b là các số tự nhiên, n ≤ 100.Dữ liệu vào n, c j , a j , b được cho trong file data.in theo khuôn dạng sau:
- Dòng đầu tiên ghi lại số tự nhiên n và b. Hai số được ghi cách nhau bởi một vài ký tự trống;
- Dòng kế tiếp ghi lại n số nguyên c i (i=1, 2, .., n). Hai số được ghi cách nhau bởi một vài ký tự trống;
- Dòng cuối cùng ghi lại n số nguyên a i (i = 1, 2, ..,n). Hai số được ghi cách nhau bởi một vài ký tự trống.
Giá trị tối ưu f(x 1 ,x 2 ,..,x n ) và phương án tối ưu X = (x 1 , x 2 ,..,x n ) tìm được ghi ra màn hình theo khuôn dạng sau:
- Dòng đầu tiên in ra giá trị nhỏ nhất f(x 1 ,x 2 ,..,x n );
- Dòng kế tiếp in ra phương án tối ưu tương ứng X = (x 1 , x 2 ,..,x n ). Hai phần tử khác nhau của X được ghi cách nhau bởi một vài khoảng 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
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
