Bài 20 Thực hành bài toán tìm kiếm
Lớp 11Tin Học9 câu hỏiBài tập
Phần 1
Câu 1
(Câu 20.1 trang 67 SBT Tin học 11) Trong các câu lệnh sau, câu lệnh nào được dùng để mở và ghi dữ liệu vào tệp "data.inp"?
AF = open("data.inp", "w").
BF = openRead("data.inp").
CF = openWrite("data.inp").
DF = open("data.inp", "r").
Câu 2
(Câu 20.2 trang 67 SBT Tin học 11) Các dữ liệu trong tệp sẽ bị ghi đè trong trường hợp nào sau đây?
ATệp được mở với tham số “w”.
BTệp được mở với tham số “a”.
CKết thúc chương trình mà không có lệnh đóng tệp.
DCứ có lệnh mở tệp là các dữ liệu trong tệp có thể bị ghi đè.
Câu 3
(Câu 20.3 trang 67 SBT Tin học 11) Kiểu dữ liệu nào sau đây có thể áp dụng thuật toán tìm kiếm nhị phân?
ADữ liệu đã được sắp xếp.
BDữ liệu chưa được sắp xếp.
CDữ liệu được nhập từ bàn phím nhưng chưa sắp xếp.
DDữ liệu bất kì, không cần điều kiện gì.
Câu 4
(Câu 20.4 trang 67 SBT Tin học 11) Mô tả nào sau đây là đúng nhất cho thuật toán tìm kiếm tuần tự?
AKhông cần sắp xếp mảng dữ liệu, lần lượt kiểm tra từng phần tử trong mảng dữ liệu.
BSắp xếp các phần tử trong mảng theo thứ tự, sau đó lần lượt kiểm tra từng phần tử.
CSắp xếp các phần tử trong mảng theo thứ tự, chia mảng dữ liệu thành hai nửa rồi tiếp tục tìm kiếm ở nửa phù hợp.
DKhông cần sắp xếp mảng dữ liệu, chia mảng dữ liệu thành hai nửa rồi tiếp tục tìm kiếm ở nửa phù hợp.
Câu 5
(Câu 20.5 trang 67 SBT Tin học 11) Giả sử cần sử dụng thuật toán tìm kiếm tuần tự để tìm ra số “10” trong dãy số A = [1, 3, 9, 8, 10, 19, 27, 11, 17]. Hỏi có bao nhiêu phép so sánh cần được thực hiện?
A5.
B4.
C6.
D7.
Câu 6
(Câu 20.6 trang 68 SBT Tin học 11) Giả sử cần sử dụng thuật toán tìm kiếm nhị phân để tìm ra số “10” trong dãy số A = [1, 3, 10, 12, 14, 15, 16]. Hỏi có bao nhiêu phép so sánh cần được thực hiện?
A3.
B2.
C4.
DThuật toán không tìm thấy số cần tìm.
Câu 7
(Câu 20.7 trang 68 SBT Tin học 11) Trong các đặc điểm sau đây, đâu là ưu điểm của thuật toán tìm kiếm tuần tự?
AKhông cần sắp xếp trước dữ liệu đầu vào.
BCó thể hoạt động hiệu quả trên mảng dữ liệu đã sắp xếp có kích thước lớn.
CChỉ có thể hoạt động tốt trên mảng dữ liệu đã sắp xếp.
DTốc độ tìm kiếm chậm trên mảng dữ liệu có kích thước lớn.
Phần 2
Câu 1
(Câu 20.8 trang 68 SBT Tin học 11) Viết chương trình tìm số lớn nhất trong dãy số A = [1, 3, 9, 8, 10, 19, 27, 11, 17].
a)Có thể khởi tạo max = A[0] và max_index = 0 trước khi duyệt dãy.
b)Có thể duyệt lần lượt các phần tử trong dãy để so sánh với giá trị lớn nhất hiện tại.
c)Nếu max < A[i] thì cập nhật max = A[i] và max_index = i.
d)Với dãy đã cho, phần tử lớn nhất là 19 và có chỉ số là 5.
Câu 2
(Câu 20.9 trang 68 SBT Tin học 11) Cho dãy số đã được sắp xếp tăng dần A = [1, 1, 3, 3, 3, 10, 10, 12, 14, 14, 14, 15, 16]. Cần chỉnh sửa thuật toán tìm kiếm nhị phân để tìm kiếm một số và đưa ra vị trí mà số đó xuất hiện lần đầu tiên.
a)Có thể dùng thuật toán tìm kiếm nhị phân để tìm một vị trí bất kì mà phần tử cần tìm xuất hiện trong dãy.
b)Sau khi tìm được một vị trí có giá trị bằng số cần tìm, có thể so sánh ngược với các phần tử ngay trước nó để tìm vị trí xuất hiện đầu tiên.
c)Nếu số cần tìm là 3 thì vị trí xuất hiện đầu tiên có chỉ số là 2.
d)Nếu số cần tìm là 5 thì kết luận vị trí xuất hiện đầu tiên có chỉ số là 0.