Cho hàm sau đây được viết bằng ngôn ngữ lập trình Python và C++:
Hàm viết bằng ngôn ngữ Python (số ở đầu là Dòng):
1 def F(A, n):
2 for i in range(1, n):
3 x = A[i]
4 j = i - 1
5 while j >= 0 and A[j] > x:
6 A[j + 1] = A[j]
7 j = j - 1
8 A[j + 1] = x
9 return (A[0] + A[n // 2]) / 2Hàm viết bằng ngôn ngữ C++ (số ở đầu là Dòng):
1 float F(int A[], int n) {
2 for (int i = 1; i < n; i++) {
3 int x = A[i];
4 int j = i - 1;
5 while (j >= 0 && A[j] > x) {
6 A[j + 1] = A[j];
7 j = j - 1;
8 }
9 A[j + 1] = x;
10 }
11 return (A[0] + A[n / 2]) / 2.0;
12 }Sau khi chọn một trong hai ngôn ngữ Python hoặc C++ để tìm hiểu hàm trên, một số bạn học sinh đã nêu các ý kiến sau:
- a)(Đáp án: Sai)
Mảng A biểu diễn cấu trúc dữ liệu hàng đợi (Queue).
- b)(Đáp án: Đúng)
Nếu dữ liệu đầu vào là mảng A gồm n phần tử đã được sắp xếp theo chiều không giảm thì các câu lệnh tại Dòng 6 và Dòng 7 không được thực hiện lần nào.
- c)(Đáp án: Sai)
Nếu dữ liệu đầu vào là n = 6 và mảng A là (9, 7, 5, 2, 4, 6) thì sau khi câu lệnh
fortại Dòng 2 thực hiện lần lặp thứ 2, giá trị của mảng A là (2, 5, 7, 9, 4, 6). - d)(Đáp án: Đúng)
Nếu dữ liệu đầu vào là n = 7 và mảng A là (8, 6, 4, 2, 3, 5, 7) thì hàm trả về giá trị 3.5.
Lời giải
Đáp án đúng: a) Sai, b) Đúng, c) Sai, d) Đúng.
Hàm F sắp xếp mảng A theo thứ tự không giảm bằng thuật toán sắp xếp chèn, rồi trả về trung bình cộng của A[0] và A[n // 2].
a) Sai. Mảng A được truy cập trực tiếp theo chỉ số ở mọi vị trí, không theo nguyên tắc vào trước ra trước của hàng đợi.
b) Đúng. Nếu A đã sắp xếp không giảm thì ở mọi lần lặp, điều kiện A[j] > x sai ngay từ đầu, vòng while không chạy, nên các câu lệnh tại Dòng 6 và Dòng 7 không được thực hiện lần nào.
c) Sai. A = (9, 7, 5, 2, 4, 6). Lần lặp 1 (): chèn 7 trước 9 → (7, 9, 5, 2, 4, 6). Lần lặp 2 (): chèn 5 lên đầu → (5, 7, 9, 2, 4, 6), không phải (2, 5, 7, 9, 4, 6).
d) Đúng. Sau khi sắp xếp, A = (2, 3, 4, 5, 6, 7, 8). Với n = 7 thì n // 2 = 3, nên A[0] = 2 và A[3] = 5; hàm trả về , tức 3.5.