Trắc nghiệm tin học 7 chân trời sáng tạo Bài 13: Thuật toán tìm kiếm

CHỦ ĐỀ 5: GIẢI QUYẾT VẤN ĐỀ VỚI SỰ TRỢ GIÚP CỦA MÁY TÍNH

BÀI 13: THUẬT TOÁN TÌM KIẾM

A. TRẮC NGHIỆM

1. NHẬN BIẾT (9 câu)

Câu 1: Thuật toán tìm kiếm nhị phân áp dụng với bài toán tìm kiếm kiểu nào?

A. Áp dụng được với mọi bài toán tìm kiếm.

B. Áp dụng với dãy giá trị đã được sắp xếp.

C. Áp dụng được với dãy giá trị chưa được sắp xếp.

D. Cả A, B và C.

Câu 2: Thuật toán tìm kiếm tuần tự kết thúc khi:

A. Tìm kiếm được vị trí số cần tìm.

B. Thông báo không tìm thấy số cần tìm.

C. Tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

D. Cả A, B, C đều sai.

Câu 3: Trong thuật toán tìm kiếm tuần tự để tìm một số trong dãy thẻ số, sau bước Lật thẻ thứ nhất thì ta sẽ thực hiện bước nào?

A. Kiểm tra: Số thẻ có đúng là số cần tìm không?

B. Kiểm tra: tất cả các thẻ số đã được lật?

C. Đầu ra: thông báo vị trí tìm thấy.

D. Kết thúc.

Câu 4: Thuật toán tìm kiếm nhị phân thực hiện như thế nào?

A. Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm lớn hơn.

B. Chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

C. So sánh lần lượt phần tử cuối cùng của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

D. So sánh lần lượt phần tử đầu của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

Câu 5: Bài toán: Thực hiện tìm một số bất kì trong dãy số. Đầu vào của bài toán tìm kiếm một số trong dãy số cho trước là:

A. Dãy thẻ số

B. Số cần tìm

C. Dãy thẻ số và số cần tìm

D. Vị trí tìm thấy

Câu 6: Thuật toán tìm kiếm tuần tự có thể giúp em:

A. Tìm số điện thoại trong danh bạ để biết người đã gọi đến.

B. Tìm bạn học sinh cùng tháng sinh nhật với em trong danh sách lớp.

C. Tìm một bạn trong bức ảnh chụp tập thể lớp.

D. Cả A, B và C.

Câu 7: Điều kiện để thực hiện thật toán tìm kiếm nhị phân là:

A. Dãy số chưa được sắp xếp.

B. Dãy số đã được sắp xếp không giảm.

C. Dãy số được sắp xếp không tăng.

D. Cả A và B đều đúng.

Câu 8: Thuật toán tìm kiếm tuần tự thực hiện như thế nào?

A. So sánh lần lượt phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

B. So sánh lần lượt phần tử cuối cùng của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

C. So sánh lần lượt phần tử đầu tiên của dãy với phần tử kế tiếp, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

D. So sánh lần lượt phần tử cuối cùng của dãy với giá trị kế tiếp, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

Câu 9: Lợi ích của việc sắp xếp trong tìm kiếm là?

A. Giúp tìm kiếm chính xác hơn.

B. Giúp tìm kiếm nhanh hơn.

C. Giúp tìm kiếm đầy đủ hơn.

D. Cả A, B và C.

2. THÔNG HIỂU (9 câu)

Câu 1: Lựa chọn phương án đúng

Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm, ta thực hiện:

A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

C. Sắp xếp dãy số theo thức tự tăng dần.

D. So sánh số cần tìm với số ở giữa dãy số.

Câu 2: Chọn phát biểu sai?

A. Thuật toán tìm kiếm nhị phân chỉ áp dụng với dãy gia trị đã được sắp xếp.

B. Thuật toán tìm kiếm tuần tự chỉ áp dụng với dãy gia trị đã được sắp xếp.

C. Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

D. Việc chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

Câu 3: Ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn?

A. Dễ thực hiện và nhanh cho ra kết quả.

B. Cho kết quả chính xác hơn.

C. Cho kết quả cụ thể hơn.

D. Cho kết quả khái quát hơn.

Câu 4: Ưu điểm của thuật toán tìm kiếm nhị phân là:

A. Thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp.

B. Số lần lặp tương tự như thuật toán tìm kiếm tuần tự.

C. Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm.

D. Cả A và C.

Câu 5: Chọn khẳng định sai trong các khẳng định sau:

A. Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt phần tử đầu tiên của dãy với giá trị cần tìm, việc tìm kiếm kết thúc khi tìm thấy hoặc đã duyệt hết các phần tử trong dãy.

B. Thuật toán tìm kiếm tuần tự thực hiện lặp đi lặp lại việc duyệt từng thẻ số, vòng lặp sẽ kết thúc khi tìm thấy số cần tìm hoặc đã duyệt hết các thẻ số.

C. Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm lớn hơn.

D. Cả 3 phương án trên.

Câu 6: Với thuật toán tìm kiếm nhị phân. Hãy sắp xếp các bước thực hiện ở mỗi lần lặp:

1. So sánh giá trị cần tìm với giá trị của phần tử giữa dãy đang xét.

2. Nếu nhỏ hơn thì xét dãy ở nửa trước, nếu lớn hơn thì xét dãy ở nửa sau.

3. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.

4. Nếu dãy rỗng thì thông báo không tìm thấy và kết thúc tìm kiếm, không thì quay lại bước 1.

A. 1 – 2 – 3 – 4

B. 1 – 3 – 2 – 4

C. 1 – 4 – 2 – 3

D. 2 – 1 – 4 – 3

Câu 7: Chọn phương án đúng: Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm nhị phân, ta thực hiện:

A. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.

B. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.

C. Sắp xếp dãy số theo thứ tự tăng dần.

D. So sánh số cần tìm với số ở giữa dãy số.

Câu 8: Trong thuật toán tìm kiếm tuần tự để tìm một số trong dãy thẻ số, sau bước Kiểm tra: Số thẻ có đúng là số cần tìm không? Mà nhận được kết quả Đúng thì ta sẽ thực hiện bước nào?

A. Kiểm tra: Số thẻ có đúng là số cần tìm không?

B. Kiểm tra: tất cả các thẻ số đã được lật?

C. Đầu ra: thông báo vị trí tìm thấy.

D. Kết thúc.

Câu 9: Chọn phát biểu sai về thuật toán tìm kiếm nhị phân?

A. Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia (số lượng thẻ của dãy) /2.

B. Khi dãy chỉ còn một thẻ số thì nửa trước (hoặc nửa sau) là dãy rỗng (dãy không có thể số nào).

C. Vòng lặp sẽ kết thúc khi tìm thấy số cần tìm hoặc dãy không còn thẻ số nào nữa.

D. Thuật toán tìm kiếm nhị phân thực hiện chia bài toán tìm kiếm ban đầu thành những bài toán tìm kiếm nhỏ hơn.

3. VẬN DỤNG (9 câu)

Câu 1: Cho dãy số A = {24, 28, 14, 18, 19, 12, 19}. Để tìm kiếm số 19 trong dãy theo thuật toán tìm kiếm tuần tự cần thực hiện mấy lần lặp?

A. 5 lần

B. 6 lần

C. 7 lần

D. 8 lần

Câu 2: Cho tình huống sau: Ban tổ chức đại hội thể thao Đông Nam Á (SEA Games) lập bảng tổng sắp huy chương của các nước tham gia.

Cách sắp xếp theo thứ tự phù hợp nhất là?

A. Sắp xếp theo thứ tự thời gian tăng dần.

B. Sắp xếp theo trình tự bảng chữ cái.

C. Sắp xếp theo thứ tự ưu tiên (người già, trẻ em, ...) và thời gian tăng dần.

D. Sắp xếp theo thứ tự số huy chương vàng, bạc, đồng giảm dần.

Câu 3: Tìm một từ tiếng Anh trong cuốn từ điển, em sẽ tìm kiếm theo cách nào nhanh nhất?

A. Tìm kiếm tuần tự

B. Tìm kiếm nhị phân

C. Cả A và B đều không áp dụng được.

D. Cả A và B đều áp dụng được.

Câu 4: Cho tình huống sau: Lớp trưởng lập danh sách các bạn trong lớp đăng kí tham gia cuộc thi văn nghệ.

Cách sắp xếp theo thứ tự phù hợp nhất là?

A. Sắp xếp theo thứ tự thời gian tăng dần.

B. Sắp xếp theo trình tự bảng chữ cái.

C. Sắp xếp theo thứ tự ưu tiên (người già, trẻ em, ...) và thời gian tăng dần.

D. Sắp xếp theo thứ tự số huy chương vàng, bạc, đồng giảm dần.

Câu 5: Cho dãy số: 47, 35, 36, 11, 36, 46, 36, 63, 36, 18, 24. Để tìm số 36 trong dãy số này bằng thuật toán tìm kiếm tuần tự, ta cần thực hiện bao nhiêu lần lặp?

A. 3 lần.

B. 5 lần.

C. 7 lần.

D. 9 lần.

Câu 6: Cho tình huống sau: Nhân viên y tế sắp xếp hồ sơ người chờ đến lượt khám sức khỏe.

Cách sắp xếp theo thứ tự phù hợp nhất là?

A. Sắp xếp theo thứ tự thời gian tăng dần.

B. Sắp xếp theo trình tự bảng chữ cái.

C. Sắp xếp theo thứ tự ưu tiên (người già, trẻ em, ...) và thời gian tăng dần.

D. Sắp xếp theo thứ tự số huy chương vàng, bạc, đồng giảm dần.

Câu 7:Khi thực hiện tìm kiếm nhị phân số 25 trong dãy số 18, 21, 25, 27, 67, 69, 72, 77, 79, 81 cần thực hiện mấy vòng lặp?

A. 2.

B. 3.

C. 4.

D. 5.

Câu 8: Cho tình huống sau: Giáo viên lập danh sách tên học sinh của một lớp.

Cách sắp xếp theo thứ tự phù hợp nhất là?

A. Sắp xếp theo thứ tự thời gian tăng dần.

B. Sắp xếp theo trình tự bảng chữ cái.

C. Sắp xếp theo thứ tự ưu tiên (người già, trẻ em, ...) và thời gian tăng dần.

D. Sắp xếp theo thứ tự số huy chương vàng, bạc, đồng giảm dần.

Câu 9: Với dãy số lần lượt là: 12, 14, 15, 18, 19, 21, 24, 25, 26. Nếu thực hiện theo thuật toán tìm kiếm nhị phân để tìm số 21 ta cần thực hiện mấy lần lặp?

A. 2 lần

B. 3 lần

C. 4 lần

D. 5 lần

4. VẬN DỤNG CAO (1 câu)

Câu 1: Trong thuật toán tìm kiếm nhị phân, thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia nào?

A. (Số lượng thẻ của dãy +1) : 2.

B. Số lượng thẻ của dãy +1 : 2.

C. (Số lượng thẻ của dãy +1) : 3.

D. Số lượng thẻ của dãy : 2.