CHỦ ĐỀ 6: KĨ THUẬT LẬP TRÌNH

BÀI 19: BÀI TOÁN TÌM KIẾM

A. TRẮC NGHIỆM

1. NHẬN BIẾT

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

1. 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.
2. 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.
3. 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.
4. 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 2: 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?

1. Kiểm tra: Số thẻ có đúng là số cần tìm không?
2. Kiểm tra: tất cả các thẻ số đã được lật?
3. Đầu ra: thông báo vị trí tìm thấy.
4. Kết thúc.

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 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?

1. Kiểm tra: Số thẻ có đúng là số cần tìm không?
2. Kiểm tra: tất cả các thẻ số đã được lật?
3. Đầu ra: thông báo vị trí tìm thấy.
4. Kết thúc.

Câu 4: Để 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:

1. Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
2. So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
3. Sếp xếp dãy số theo thứ tự tăng dần.
4. So sánh số cần tìm với số ở giữa dãy số.

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

1. Tìm số điện thoại trong danh bạ để biết người đã gọi đến.
2. Tìm bạn học sinh cùng tháng sinh nhật với em trong danh sách lớp.
3. Tìm một bạn trong bức ảnh chụp tập thể lớp.
4. Cả A, B và C.

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

1. 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.
2. 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.
3. 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.
4. 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 7: 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?

1. Xét dãy thẻ số đứng sau thẻ số vừa lật.
2. Xét dãy thẻ số đứng trước thẻ số vừa lật.
3. Kết thúc.
4. Kiểm tra: dãy rỗng.

Câu 8: 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?

1. Xét dãy thẻ số đứng sau thẻ số vừa lật.
2. Lật thẻ số ở giữa dãy.
3. Kết thúc.
4. Đầu ra: thông báo không tìm thấy.

2. THÔNG HIỂU

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

1. 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.
2. 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.
3. 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.
4. 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 2: Thẻ số ở giữa dãy có số thứ tự là phần nguyên của phép chia nào?

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

Câu 3: 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?

3. 3.
4. 4.
5. 2.
6. 5.

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

1. 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.
2. 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ố.
3. 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.
4. Cả 3 phương án trên.

Câu 5: 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?

1. Áp dụng được với mọi bài toán tìm kiếm.
2. Áp dụng với dãy giá trị đã được sắp xếp.
3. Áp dụng được với dãy giá trị chưa được sắp xếp.
4. Cả A, B và C.

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

2. 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.
3. 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).
4. 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.
5. 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 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?

2. 2.
3. 3.
4. 4.
5. 5.

Câu 8: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần nhiều bước nhất?

1. Khi cho 1 phần tử
2. Khi cho nhiều phần tử giống nhau
3. Khi cho nhiều phần tử khác nhau
4. Khi cho 2 phần tử

Câu 9: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?

1. Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt các phân tử của dãy để tìm phần tử có giá trị nhỏ hơn giá trị cần tìm.
2. Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phân tử của dãy từ đầu đến cuối để tìm phần tử có giá trị lớn hơn giá trị cần tìm.
3. Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phân tử của dãy từ cuối lên đầu để tìm phần tử có giá trị khác giá trị cần tìm.
4. Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phân tử của dãy từ đầu đến cuối để tìm phần tử có giá trị bằng giá trị cần tìm.

3. VẬN DỤNG

Câu 1: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần 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?

1. Số cần tìm chỉ số 7
2. Số cần tìm chỉ số 1
3. Số cần tìm chỉ số 4
4. Số cần tìm chỉ số 5

Câu 2: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}. 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?

1. cần duyệt 10 phần tử để tìm ra phần từ có giá trị bằng 34
2. cần duyệt 6 phần tử để tìm ra phân tử có giá trị bằng 34
3. Nếu số bé hơn K lật 10 lần, số lớn hơn K lật 1 lần
4. Tất cả các đáp án trên đều đúng.

Câu 3: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}. Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?

1. cần duyệt 10 phần tử để tìm ra phần từ có giá trị bằng 34
2. cần duyệt 6 phần tử để tìm ra phân tử có giá trị bằng 34
3. Nếu số bé hơn K lật 10 lần, số lớn hơn K lật 1 lần
4. Tất cả các đáp án trên đều đúng.

Câu 4: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm.

1. Không dừng ngay khi tìm thấy số đầu tiên bằng x mà vẫn tiếp tục kiểm tra đến cuối dãy.
2. Thêm biến đếm, bắt đầu với đếm =0, mỗi khi thấy số đang xét = x thì tăng đếm lên 1 đơn vị.
3. Đáp án A, B đều đúng
4. Đáp án A, B đều sai

4. VẬN DỤNG CAO

Câu 1: Cho dãy A= {0, 4, 8, 10, 12,14, 17, 18, 20, 31, 34, 87}. Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?

1. cần duyệt 10 phần tử để tìm ra phần từ có giá trị bằng 34
2. cần duyệt 6 phần tử để tìm ra phân tử có giá trị bằng 34
3. Nếu số bé hơn K lật 10 lần, số lớn hơn K lật 1 lần
4. Tất cả các đáp án trên đều đúng.

Câu 2: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần như sau:

def binary_search(arr, x):

   left = 0

   right = len(arr) - 1

   while left <= right:

       mid = (left + right) // 2

       if arr[mid] == x:

           return mid

       elif arr[mid] < x:

           right = mid - 1

       else:

           left = mid + 1

   return -1

# Sử dụng hàm để tìm kiếm giá trị 5 trong dãy sắp xếp giảm dần [9, 8, 6, 5, 3, 1]

arr = [9, 8, 6, 5, 3, 1]

x = 5

result = binary_search(arr, x)

if result != -1:

   print("Element is present at index", str(result))

else:

   print("Element is not present in array")

Em hãy nhận xét về cách viết chương trình này:

1. Đúng
2. Sai
3. Cần bổ sung thêm dấu “;” sau “if”
4. Đáp án khác

 --------------- Còn tiếp ---------------