Đề bài
Cho hàm Python sau:
| ${\rm{def\;Ham}}\left( {A,K} \right):$ $n = {\rm{len}}\left( A \right)$ ${\rm{for\;i\;in\;range\;}}\left( n \right):$ ${\rm{if\;}}A\left[ i \right] = = K:$ ${\rm{return\;i}}$ ${\rm{return\;}} - 1$ |
|---|
Các phát biểu đúng hay sai?
1. Hàm trả lại vị trí của tất cả các phần tử có giá trị bằng $K$ nằm trong mảng $A$.
2. Hàm thể hiện ý tưởng của thuật toán tìm kiếm tuần tự.
3. Với giá trị trong mảng $A = \left[ {3,5,7,9} \right]$, giá trị $K = 7$, hàm trả lại giá trị 3 .
4. Độ phức tạp thời gian tính của hàm trên là $T\left( n \right) = {\rm{O}}\left( n \right)$.
Đáp án đúng: 1Đ, 2Đ, 3S, 4Đ
Lời giải 3
Lời giải chi tiết
Chào các em học sinh, thầy sẽ hướng dẫn các em giải bài tập này nhé. Chúng ta cùng phân tích từng phát biểu một:
- Phát biểu 1: "Hàm trả lại vị trí của tất cả các phần tử có giá trị bằng K nằm trong mảng A ."
Lời giải: Hàm chỉ trả về vị trí đầu tiên mà nó tìm thấy giá trị bằng K trong mảng A , và dừng lại. Nếu không tìm thấy, hàm trả về -1. Vì vậy, phát biểu này sai. - Phát biểu 2: "Hàm thể hiện ý tưởng của thuật toán tìm kiếm tuần tự."
Lời giải: Hàm duyệt qua từng phần tử của mảng A để tìm giá trị K , đây chính là ý tưởng của thuật toán tìm kiếm tuần tự. Vì vậy, phát biểu này đúng. - Phát biểu 3: "Với giá trị trong mảng A = [3,5,7,9] , giá trị K = 7 , hàm trả lại giá trị 3."
Lời giải: Hàm sẽ duyệt mảng A từ đầu. Vị trí của các phần tử trong mảng A là: 3 ở vị trí 0, 5 ở vị trí 1, 7 ở vị trí 2, 9 ở vị trí 3. Vì vậy, khi K = 7 , hàm sẽ trả về giá trị 2, chứ không phải 3. Phát biểu này sai. - Phát biểu 4: "Độ phức tạp thời gian tính của hàm trên là T(n) = O(n) ."
Lời giải: Trong trường hợp xấu nhất, hàm phải duyệt qua tất cả n phần tử của mảng A để tìm K (hoặc không tìm thấy). Vì vậy, độ phức tạp thời gian là O(n) . Phát biểu này đúng.
Chú ý khi giải
- Đọc kỹ đoạn code để hiểu rõ thuật toán mà hàm thực hiện.
- Xác định rõ mục đích của hàm và giá trị trả về trong các trường hợp khác nhau.
- Khi tính độ phức tạp thời gian, cần xét trường hợp xấu nhất để đảm bảo tính chính xác.