Lý thuyết Tin học 7 Chân trời sáng tạo bài 13
Lý thuyết Tin học lớp 7 bài 13: Thuật toán tìm kiếm sách Chân trời sáng tạo hay, chi tiết cùng với bài tập trắc nghiệm chọn lọc có đáp án giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt môn Tin học 7.
Bài: Thuật toán tìm kiếm
A. Lý thuyết Tin học 7 bài 13
1. Thuật toán tìm kiếm tuần tự
- Thuật toán tìm kiếm tuần tự thực hiện so sánh lần lượt 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ài tìm kiếm một số trên thẻ được mô tả như sau:
+ Đầu vào: Dãy số (được ghi trên các thẻ) và số cần tìm.
+ Đầu ra: Thông báo vị trí tìm thấy hoặc thông báo không tìm thấy số cần tìm.
Hình 1. Sơ đồ khối mô tả thuật toán tìm kiếm tuần tự để tìm một số
2. Thuật toán tìm kiếm nhị phân
- Áp dụng với dãy giá trị đã được sắp xếp.
- Ở mỗi lần lặp, thực hiện:
Bước 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.
Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
Bước 3. 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.
Bướ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.
Hình 2. Sơ đồ khối mô tả thuật toán tìm kiếm nhị phân để tìm kiếm số trong một dãy đã được sắp xếp thứ tự
- Sắp xếp giúp việc tìm kiếm được thực hiện nhanh hơn, hiệu quả hơn.
B. Bài tập trắc nghiệm Tin học 7 bài 13
Câu 1. 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 nhỏ 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 lớn 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.
Đáp án: A
Giải thích:
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.
Câu 2. Dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thứ tự không giảm), sau bước Kiểm tra: số cần tìm nhỏ hơn giá trị trên thẻ? nếu nhận kết quả Sai, ta thực hiện bước nào?
A. Xét dãy thẻ số đứng sau thẻ số vừa lật.
B. Xét dãy thẻ số đứng trước thẻ số vừa lật.
C. Kết thúc.
D. Kiểm tra: dãy rỗng.
Đáp án: A
Giải thích:
Khi dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số, sau bước Kiểm tra: số cần tìm nhỏ hơn giá trị trên thẻ? nếu nhận kết quả Sai, ta thực hiện bước Xét dãy thẻ số đứng sau thẻ số vừa lật.
Câu 3. Khi dùng thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số (được sắp xếp theo thứ tự không giảm), sau bước Kiểm tra: dãy rỗng? nếu nhận kết quả Sai, ta thực hiện bước nào?
A. Xét dãy thẻ số đứng sau thẻ số vừa lật.
B. Lật thẻ số ở giữa dãy.
C. Kết thúc.
D. Đầu ra: thông báo không tìm thấy.
Đáp án: B
Giải thích:
Trong thuật toán tìm kiếm nhị phân để tìm một số trong dãy thẻ số, sau bước Kiểm tra: dãy rỗng? nếu nhận kết quả Sai, ta thực hiện bước Lật thẻ số ở giữa dãy.
Câu 4. Chọn phát biểu sai?
A. Thuật toán tìm kiếm tuần tự chỉ áp dụng với dãy giá trị đã được sắp xếp.
B. Thuật toán tìm kiếm nhị phân chỉ áp dụng với dãy giá 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.
Đáp án: A
Giải thích:
Đối với dãy chưa được sắp xếp thì ta có thể dùng thuật toán tìm kiếm tuần tự để tìm.
⇒ A sai.
Câu 5. 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.
Đáp án: A
Giải thích:
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 +1) : 2.
Câu 6. 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.
Đáp án: A
Giải thích:
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.
Câu 7. 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.
Đáp án: A
Giải thích:
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 Kiểm tra: Số thẻ có đúng là số cần tìm không?
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.
Đáp án: C
Giải thích:
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 Đầu ra: thông báo vị trí tìm thấy.
Câu 9. Để tìm kiếm một số trong dãy số bằng thuật toán tìm kiếm tuần tự, 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ố.
Đáp án: B
Giải thích:
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.
Câu 10. 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.
Đáp án: D
Giải thích:
Thuật toán tìm kiếm tuần tự có thể giúp em: Tìm số điện thoại trong danh bạ để biết người đã gọi đến; Tìm bạn học sinh cùng tháng sinh nhật với em trong danh sách lớp; Tìm một bạn trong bức ảnh chụp tập thể lớp.
Câu 11. Trong thuật toán tìm kiếm nhị phân, ở mỗi lần lặp ta thực hiện mấy bước?
A. 3.
B. 4.
C. 2.
D. 5.
Đáp án: B
Giải thích:
Trong thuật toán tìm kiếm nhị phân, ở mỗi lần lặp ta thực hiện 4 bước:
+ Bước 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.
+ Bước 2. Nếu bằng nhau thì thông báo vị trí tìm thấy và kết thúc.
+ Bước 3. 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.
+ Bướ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.
Câu 12. 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.
Đáp án: C
Giải thích:
Khẳng định C sai, đúng là: 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.
Câu 13. 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.
Đáp án: B
Giải thích:
- Thuật toán tìm kiếm nhị phân áp dụng với dãy giá trị đã được sắp xếp.
Câu 14. 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.
Đáp án: A
Giải thích:
A sai vì: 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 + 1)/2.
Câu 15. 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.
Đáp án: B
Giải thích:
- Lần lặp 1: Lật thẻ ở giữa dãy: 67. Do 25 < 67 nên chỉ cần tìm ở nửa trước gồm 18, 21, 25, 27
- Lần lặp 2: Lật thẻ ở giữa dãy: 21. Do 25 > 21 nên ta tìm ở nửa sau gồm 25, 27.
- Lần lặp 3: Lật thẻ ở giữa dãy: 25. Do 25 = 25 nên ta dừng thuật toán.
Có 3 lần lặp được thực hiện.
>>>> Bài tiếp theo: Lý thuyết Tin học 7 Chân trời sáng tạo bài 14
Trên đây là toàn bộ nội dung bài Lý thuyết Tin học lớp 7 bài 13: Thuật toán tìm kiếm sách Chân trời sáng tạo. Các em học sinh tham khảo thêm Tin học lớp 7 Kết nối tri thức và Tin học 7 Cánh diều. VnDoc liên tục cập nhật lời giải cũng như đáp án sách mới của SGK cũng như SBT các môn cho các bạn cùng tham khảo.
