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[n // 2] + A[n - 1]) / 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[n / 2] + A[n - 1]) / 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)Sai
Mảng A biểu diễn cấu trúc dữ liệu ngăn xếp (Stack).
- b)Sai
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 được thực hiện n lần.
- c)Đúng
Nếu dữ liệu đầu vào là n = 6 và mảng A là (6, 4, 2, 1, 3, 5) 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, 4, 6, 1, 3, 5). - d)Đú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ị 6.5.
Lời giải
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[n // 2] và A[n - 1].
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 sau ra trước của ngăn xếp.
b) Sai. 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; các câu lệnh tại Dòng 6 và Dòng 7 được thực hiện 0 lần, không phải n lần.
c) Đúng. A = (6, 4, 2, 1, 3, 5). Lần lặp 1 (): chèn 4 trước 6 → (4, 6, 2, 1, 3, 5). Lần lặp 2 (): chèn 2 lên đầu → (2, 4, 6, 1, 3, 5).
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[3] = 5 và A[6] = 8; hàm trả về , tức 6.5.