Bài 19 Bài toán tìm kiếm
Lớp 11Tin Học14 câu hỏiBài tập
Phần 1
Câu 1
(Câu 19.1 trang 66 SBT Tin học 11) Khi nào thì thuật toán tìm kiếm tuần tự trên một danh sách tốn nhiều thời gian nhất?
AKhi không tìm thấy phần tử cần tìm trong danh sách.
BKhi phần tử cần tìm nằm ở vị trí đầu tiên của danh sách.
CKhi danh sách chỉ có một phần tử.
DKhi phần tử cần tìm nằm ở vị trí giữa danh sách.
Câu 2
(Câu 19.2 trang 66 SBT Tin học 11) Có ý kiến cho rằng: “Thiết kế các thuật toán tìm kiếm phụ thuộc rất nhiều vào cấu trúc dữ liệu của miền cần tìm kiếm”. Nhận định nào sau đây đúng?
AÝ kiến đó đúng vì cấu trúc dữ liệu ảnh hưởng đến cách tổ chức và thực hiện tìm kiếm.
BÝ kiến đó sai vì mọi cấu trúc dữ liệu đều dùng chung một thuật toán tìm kiếm.
CÝ kiến đó sai vì thuật toán tìm kiếm chỉ phụ thuộc vào ngôn ngữ lập trình.
DÝ kiến đó đúng nhưng chỉ áp dụng cho dữ liệu kiểu số nguyên.
Câu 3
(Câu 19.7 trang 66 SBT Tin học 11) Với thuật toán tìm kiếm nhị phân, khi nào thì tìm kiếm nhanh nhất, cần ít phép so sánh nhất?
AKhi giá trị phần tử có chỉ số mid bằng K ngay ở lần so sánh đầu tiên.
BKhi K nhỏ hơn tất cả các phần tử trong dãy.
CKhi K lớn hơn tất cả các phần tử trong dãy.
DKhi không tìm thấy K trong dãy.
Câu 4
(Câu 19.8 trang 66 SBT Tin học 11) Với thuật toán tìm kiếm nhị phân, khi nào thì việc tìm kiếm chậm nhất, cần nhiều phép so sánh nhất?
AKhi không tìm thấy giá trị K trong dãy.
BKhi phần tử giữa đầu tiên có giá trị bằng K.
CKhi dãy chỉ có một phần tử.
DKhi giá trị K nằm đúng ở vị trí giữa dãy.
Câu 5
(Câu 19.10 trang 66 SBT Tin học 11) Trong trò chơi lật thẻ bài đã mô tả trong sách giáo khoa, cách chơi tối ưu nhất mà bạn Minh nên sử dụng là gì?
ALật các quân bài theo cách của phương pháp tìm kiếm nhị phân.
BLật lần lượt từng quân bài từ trái sang phải.
CLật ngẫu nhiên các quân bài cho đến khi tìm thấy.
DLật tất cả các quân bài cùng một lúc.
Phần 2
Câu 1
(Câu 19.3 trang 66 SBT Tin học 11) Cho ma trận số A bậc m x n. Cần viết chương trình thực hiện tìm kiếm tuần tự trên ma trận A; nếu tìm thấy K thì trả về cặp chỉ số (i, j), nếu không thì trả về (-1, -1).
a)Có thể duyệt lần lượt từng hàng của ma trận A.
b)Trong mỗi hàng, có thể duyệt lần lượt từng cột để so sánh A[i][j] với K.
c)Nếu A[i][j] = K thì có thể trả về cặp chỉ số (i, j).
d)Nếu không tìm thấy K trong ma trận thì chương trình nên trả về (0, 0).
Câu 2
(Câu 19.3 trang 66 SBT Tin học 11) Xét hàm tìm kiếm tuần tự trên ma trận A: def TimKiem(A, K): for i in range(len(A)): for j in range(len(A[i])): if A[i][j] == K: return (i, j); return (-1, -1).
a)Hàm duyệt các phần tử của ma trận theo từng hàng.
b)Nếu tìm thấy phần tử có giá trị bằng K, hàm trả về cặp chỉ số của phần tử đó.
c)Nếu có nhiều phần tử bằng K, hàm trả về vị trí đầu tiên tìm thấy trong quá trình duyệt.
d)Hàm luôn trả về tất cả các vị trí có giá trị bằng K.
Câu 3
(Câu 19.4 trang 66 SBT Tin học 11) Xét ví dụ về dữ liệu nhiệt độ trung bình trong các ngày của năm qua.
a)Dãy số liệu nhiệt độ trung bình trong các ngày của năm qua có thể là một miền dữ liệu để thực hiện tìm kiếm.
b)Có thể tìm kiếm một ngày có nhiệt độ trung bình bằng một giá trị K cho trước.
c)Nếu dữ liệu chưa được sắp xếp, có thể dùng thuật toán tìm kiếm tuần tự.
d)Tìm kiếm nhiệt độ trong dãy số liệu luôn bắt buộc phải dùng tìm kiếm nhị phân.
Câu 4
(Câu 19.5 trang 66 SBT Tin học 11) Giả sử dữ liệu tên và điểm thi môn Tin học của các bạn trong lớp được cho dưới dạng danh sách các cặp như [("Hà", 7.5), ("Bình", 8), ("Quang", 9.2), ("An", 10)]. Cần nhập một điểm số từ bàn phím và tìm xem có bạn nào có điểm thi bằng điểm đã nhập không.
a)Mỗi phần tử trong danh sách là một cặp gồm tên học sinh và điểm thi.
b)Có thể duyệt lần lượt từng phần tử trong danh sách để so sánh điểm thi với điểm nhập vào.
c)Nếu tìm thấy điểm bằng điểm đã nhập thì có thể thông báo tên một bạn tương ứng.
d)Nếu không tìm thấy thì chương trình vẫn phải thông báo “Tìm thấy bạn An”.
Câu 5
(Câu 19.5 trang 66 SBT Tin học 11) Xét đoạn xử lí tìm học sinh theo điểm thi: K = float(input("Nhập điểm cần tìm: ")); found = False; for x in DS: if x[1] == K: print("Tìm thấy bạn", x[0]); found = True; break; if not found: print("Không tìm thấy").
a)Câu lệnh float(input(...)) giúp nhập điểm cần tìm dưới dạng số thực.
b)x[1] là điểm thi của học sinh trong mỗi cặp dữ liệu.
c)Khi tìm thấy một bạn có điểm bằng K, chương trình in tên bạn đó và dừng tìm kiếm bằng break.
d)Biến found luôn giữ giá trị False kể cả khi tìm thấy học sinh có điểm bằng K.
Câu 6
(Câu 19.6 trang 66 SBT Tin học 11) Viết thuật toán tìm kiếm tuần tự mở rộng: Cho trước dãy A và giá trị K; cần tìm tất cả các phần tử trong A có giá trị bằng K; kết quả trả về là list chỉ số của các phần tử bằng K, nếu không tìm thấy thì trả về list rỗng.
a)Cần tạo một danh sách rỗng để lưu các chỉ số tìm thấy.
b)Cần duyệt tất cả các phần tử của dãy A.
c)Nếu A[i] = K thì thêm chỉ số i vào danh sách kết quả.
d)Khi tìm thấy phần tử đầu tiên bằng K thì bắt buộc phải dừng ngay thuật toán.
Câu 7
(Câu 19.6 trang 66 SBT Tin học 11) Với A = [1, 0, 3, 2, 5, 1, 8] và K = 1, kết quả của thuật toán tìm kiếm tuần tự mở rộng là gì?
a)Kết quả trả về là danh sách [0, 5].
b)Vì A[0] = 1 nên chỉ số 0 được đưa vào kết quả.
c)Vì A[5] = 1 nên chỉ số 5 được đưa vào kết quả.
d)Kết quả trả về là danh sách rỗng vì dãy A có nhiều hơn một phần tử bằng K.
Câu 8
(Câu 19.9 trang 66 SBT Tin học 11) Cần cải tiến thuật toán tìm kiếm nhị phân để tìm nhanh hơn nếu K nằm ngoài vùng giá trị của dãy A đã sắp xếp tăng dần.
a)Trước khi tìm kiếm nhị phân, có thể kiểm tra nếu K < A[0] hoặc K > A[len(A)-1] thì kết luận không tìm thấy.
b)Việc kiểm tra K ngoài vùng giá trị của dãy giúp tránh thực hiện các bước tìm kiếm không cần thiết.
c)Cải tiến này chỉ áp dụng khi dãy A đã được sắp xếp tăng dần.
d)Nếu K < A[0] thì vẫn chắc chắn tìm thấy K ở cuối dãy.
Câu 9
(Câu 19.9 trang 66 SBT Tin học 11) Xét hàm tìm kiếm nhị phân cải tiến trên dãy A đã sắp xếp tăng dần: nếu len(A) == 0 hoặc K < A[0] hoặc K > A[-1] thì trả về -1; sau đó mới thực hiện tìm kiếm nhị phân thông thường.
a)Điều kiện len(A) == 0 giúp xử lí trường hợp dãy rỗng.
b)Điều kiện K < A[0] hoặc K > A[-1] giúp nhận biết K nằm ngoài vùng giá trị của dãy.
c)Nếu K nằm ngoài vùng giá trị của dãy, hàm có thể trả về -1 mà không cần tiếp tục tìm kiếm.
d)Với dãy chưa sắp xếp, có thể luôn dùng kiểm tra K < A[0] hoặc K > A[-1] để kết luận không tìm thấy.