Đề bài
Cho đoạn mã giả sau:
| 1 | i $ \leftarrow 0$ |
|---|---|
| 2 | while $(i < n):$ |
| 3 | if ${a_i} \ne x:$ |
| 4 | i $ \leftarrow i + 1$ |
| 5 | else $:$ |
| 6 | return i |
| 7 | return "Không tìm thấy" |
Sau khi đọc đoạn mã giả trên, một số bạn học sinh đã có các nhận xét sau:
(Trong mỗi ý a, b, c, d, thí sinh chọn đúng hoặc sai.)
Lời giải chi tiết
Đoạn mã giả được cho là một thuật toán tìm kiếm tuần tự (sequential search), hoạt động theo các bước sau:
- Khởi tạo biến
ibằng 0. - Sau đó kiểm tra điều kiện
(i < n), nếu đúng sẽ thực hiện vòng lặp while. - Trong mỗi vòng lặp, kiểm tra nếu
a[i] \neq x, thì tăngithêm 1 và lặp lại vòng lặp. - Nếu không, trả về chỉ số
i, nơi tìm thấy phần tử có giá trị bằngKtrong dãy. - Nếu thoát khỏi vòng lặp mà vẫn không tìm thấy, trả về "Không tìm thấy".
Dựa trên phân tích trên, ta xét từng ý kiến:
a. Thuật toán duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K.
Nhận xét này đúng. Thuật toán thực hiện dòng lệnh i \leftarrow i + 1 để đi qua từng phần tử của dãy A và kiểm tra điều kiện từng phần tử với K.
b. Có thể sử dụng danh sách liên kết để lưu trữ các phần tử trong dãy A.
Nhận xét này đúng. Danh sách liên kết có thể được dùng để lưu trữ các phần tử, mặc dù thực tế thời gian truy cập phần tử sẽ chậm hơn mảng tĩnh vì cần duyệt qua từng node để tới node i-th.
c. Với bộ dữ liệu A=[2,5,7,9,13,21,25],K=13, thuật toán trả lại kết quả là 13.
Nhận xét này sai. Thuật toán sẽ trả lại vị trí của phần tử (giá trị là chỉ số trong mảng), không phải là giá trị phần tử. Với dãy A và K như đã cho, giá trị trả lại sẽ là 4 - vị trí của phần tử có giá trị 13 trong mảng.
d. Với bộ dữ liệu A=[2,5,7,9,13,21,25],K=15, thuật toán trả lại kết quả không tìm thấy sau 7 bước lặp. Ta có thể cải tiến để thuật toán kết thúc sau 5 bước lặp.
Nhận xét này không có cơ sở rõ ràng. Hiện tại, thuật toán đã kiểm tra tất cả các phần tử và trả lại "không tìm thấy" khi không có phần tử nào bằng K. Để cải thiện thành 5 bước lặp, cần xác định rằng K lớn hơn tất cả các phần tử từ 21 về sau, nhưng thuật toán không có thông tin này vì không tổng quan duyệt hết mảng.
Chú ý khi giải
- Hiểu rõ cấu trúc và điểm dừng của vòng lặp với các điều kiện thoát khỏi vòng lặp.
- Phân biệt giữa giá trị phần tử và vị trí phần tử (chỉ số) khi tìm kiếm trong mảng.
- Nhận diện giới hạn của thuật toán tuần tự thông qua cách duyệt từng phần tử mà không có thông tin trước về cấu trúc hoặc sự sắp xếp của mảng.