15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 19 có đáp án
15 câu hỏi
PHẦN I. Câu trắc nghiệm nhiều phương án lựa chọn. Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ lựa chọn một phương án.
Bài toán tìm kiếm tuần tự thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]?
4
6
8
7
Đáp án: D
Giải thích: Thuật toán tìm kiếm tuần tự duyệt từ đầu đến cuối dãy số. Để tìm phần tử 47 ở vị trí thứ 7, cần duyệt 7 phần tử.
Trong tìm kiếm tuần tự, khi nào ta có thể tìm thấy kết quả ngay với ít bước nhất?
Khi phần tử cần tìm ở giữa danh sách
Khi phần tử cần tìm ở cuối danh sách
Khi phần tử cần tìm không có trong danh sách
Khi phần tử cần tìm là phần tử đầu tiên
Đáp án: D
Giải thích: Nếu phần tử cần tìm là phần tử đầu tiên của danh sách, kết quả sẽ được tìm thấy ngay sau bước đầu tiên
Trong tìm kiếm tuần tự, khi nào cần nhiều bước nhất để tìm ra kết quả?
Khi phần tử cần tìm ở giữa danh sách
Khi phần tử cần tìm là phần tử cuối cùng
Khi phần tử cần tìm không có trong danh sách
Khi phần tử cần tìm là phần tử đầu tiên
Đáp án: B
Giải thích: Khi phần tử cần tìm là phần tử cuối cùng, thuật toán phải duyệt qua toàn bộ danh sách trước khi tìm thấy nó.
Thuật toán tìm kiếm nhị phân chỉ có thể áp dụng khi danh sách dữ liệu đã được sắp xếp như thế nào?
Tăng dần
Giảm dần
Không cần sắp xếp
Sắp xếp theo bất kỳ thứ tự nào
Đáp án: A
Giải thích: Thuật toán tìm kiếm nhị phân yêu cầu danh sách phải được sắp xếp theo thứ tự tăng dần để chia đôi dữ liệu và thu hẹp phạm vi tìm kiếm.
Với thuật toán tìm kiếm nhị phân, cần bao nhiêu lần duyệt để tìm phần tử có giá trị bằng 34 trong dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67]?
2
3
4
5
Đáp án: C
Giải thích: Thuật toán tìm kiếm nhị phân sẽ duyệt qua 4 bước để tìm ra phần tử 34 bằng cách chia đôi phạm vi tìm kiếm.
Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần tử có giá trị bằng 34 trong dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67]?
6
10
12
11
Đáp án: D
Giải thích: Tìm kiếm tuần tự sẽ phải duyệt qua 11 phần tử để tìm thấy phần tử có giá trị bằng 34.
Thuật toán tìm kiếm nhị phân có ưu điểm gì so với tìm kiếm tuần tự?
Đơn giản hơn trong lập trình
Có thể áp dụng cho mọi danh sách
Tốc độ nhanh hơn khi danh sách đã sắp xếp
Không cần phải sắp xếp danh sách trước khi tìm
Đáp án: C
Giải thích: Tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự khi danh sách đã được sắp xếp vì phạm vi tìm kiếm được thu hẹp mỗi lần chia đôi.
Cho dãy A = [1, 3, 4, 7, 8, 9, 10]. Cần tìm giá trị K = 9 bằng thuật toán tìm kiếm nhị phân, chỉ số nào sẽ được trả về?
3
4
5
6
Đáp án: C
Giải thích: Sau khi thu hẹp phạm vi tìm kiếm, giá trị 9 được tìm thấy ở vị trí thứ 5.
Thuật toán tìm kiếm tuần tự có thể áp dụng trong trường hợp nào?
Dữ liệu đã được sắp xếp
Dữ liệu chưa được sắp xếp
Chỉ cho các dãy số
Chỉ cho các dãy chữ cái
Đáp án: B
Giải thích: Tìm kiếm tuần tự có thể áp dụng cho cả dữ liệu đã sắp xếp và chưa sắp xếp.
Nếu dãy số đã được sắp xếp giảm dần, thuật toán tìm kiếm nhị phân sẽ hoạt động như thế nào?
Thuật toán vẫn hoạt động bình thường
Phải thay đổi thuật toán để so sánh ngược lại
Không thể áp dụng tìm kiếm nhị phân
Chỉ áp dụng cho dãy số ngắn
Đáp án: B
Giải thích: Đối với dãy giảm dần, thuật toán phải được thay đổi để so sánh ngược lại và thu hẹp phạm vi tìm kiếm từ phải sang trái.
PHẦN II. Câu trắc nghiệm đúng sai. Thí sinh trả lời từ câu 1 đến câu 2. Trong mỗi ý a), b), c), d) ở mỗi câu, thí sinh chọn đúng hoặc sai
Miền dữ liệu của bài toán tìm kiếm hình ảnh hoa hồng trên Internet là gì?
a) Tất cả các tệp văn bản có trên máy tính.
b) Tất cả các hình ảnh có trên các máy tính kết nối Internet.
c) Tất cả các bài viết về cách trồng hoa.
d) Tất cả các danh sách học sinh trong lớp.
a) Sai. Miền dữ liệu không phải là tệp văn bản mà là hình ảnh.
b) Đúng. Miền dữ liệu chính là tất cả hình ảnh có sẵn trên Internet, vì bài toán yêu cầu tìm hình ảnh hoa hồng.
c) Sai. Miền dữ liệu không phải là bài viết mà là hình ảnh.
d) Sai. Miền dữ liệu không liên quan đến danh sách học sinh.
Trong bài toán tìm kiếm tuần tự, khi nào thuật toán tìm kiếm có thể tìm thấy ngay kết quả cần tìm?
a) Khi phần tử cần tìm nằm ở vị trí đầu tiên của dãy số.
b) Khi phần tử cần tìm nằm ở vị trí giữa của dãy số.
c) Khi dãy số có số lượng phần tử lớn hơn 10.
d) Khi phần tử cần tìm nằm ở vị trí cuối cùng của dãy số
a) Đúng. Nếu phần tử cần tìm nằm ở đầu dãy, thuật toán sẽ tìm thấy ngay ở lần duyệt đầu tiên.
b) Sai. Mặc dù phần tử ở vị trí giữa có thể được tìm thấy sớm nhưng không phải là lần duyệt đầu tiên.
c) Sai. Số lượng phần tử không ảnh hưởng đến việc tìm thấy ngay lập tức.
d) Sai. Nếu phần tử cần tìm nằm ở cuối, thuật toán sẽ cần duyệt qua tất cả các phần tử trước đó.
PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3
Bài toán tìm kiếm hình ảnh hoa hồng trên Internet có miền dữ liệu nào?
Đáp án: Miền dữ liệu là tất cả các hình ảnh có trên các máy tính kết nối mạng Internet.
Giải thích: Trong bài toán này, mục tiêu là tìm kiếm các hình ảnh cụ thể. Miền dữ liệu rộng lớn vì Internet có hàng triệu hình ảnh, và thuật toán tìm kiếm cần phải xử lý nhiều thông tin để tìm ra những hình ảnh liên quan đến hoa hồng.
Khi nào thuật toán tìm kiếm tuần tự sẽ tìm được kết quả nhanh nhất?
Đáp án: Tìm kiếm tuần tự sẽ tìm được kết quả nhanh nhất khi phần tử cần tìm là phần tử đầu tiên trong dãy.
Giải thích: Trong trường hợp này, thuật toán chỉ cần một lần duyệt để tìm ra phần tử, dẫn đến số bước thực hiện là tối thiểu. Nếu phần tử cần tìm nằm ở đầu dãy, không cần duyệt qua các phần tử khác.
So sánh số bước giữa tìm kiếm tuần tự và tìm kiếm nhị phân với cùng một dãy số. Khi nào thuật toán nào sẽ hiệu quả hơn?
Đáp án: Tìm kiếm nhị phân sẽ hiệu quả hơn khi dãy số đã được sắp xếp
Giải thích: Thuật toán tìm kiếm nhị phân thu hẹp phạm vi tìm kiếm mỗi lần kiểm tra phần tử giữa, dẫn đến số bước cần thiết giảm một nửa sau mỗi lần lặp. Trong khi đó, tìm kiếm tuần tự phải duyệt qua tất cả các phần tử cho đến khi tìm thấy, có thể dẫn đến số bước lớn hơn đáng kể, đặc biệt trong dãy số dài.
