Thi Online Trắc nghiệm Tin 7 Bài 2. Tìm kiếm nhị phân (Phần 2) có đáp án
Trắc nghiệm Tin 7 Bài 2. Tìm kiếm nhị phân (Phần 2) có đáp án
-
544 lượt thi
-
10 câu hỏi
-
60 phút
Câu 1:
Thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm được gọi là gì?
Thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm được gọi là gì?
Đáp án đúng là: A
Thuật toán tìm kiếm x trong dãy đã sắp xếp thứ tự với ý tưởng chia đôi dần để giảm nhanh phạm vi tìm kiếm được gọi là thuật toán tìm kiếm nhị phân.
Câu 2:
Khi bắt đầu thuật toán, phạm vi tìm kiếm là gì?
Khi bắt đầu thuật toán, phạm vi tìm kiếm là gì?
Đáp án đúng là: B
Khi bắt đầu thuật toán, phạm vi tìm kiếm là dãy đã cho ban đầu (đã sắp xếp thứ tự).
Câu 3:
Lấy phần tử đứng giữa dãy để so sánh với x, nếu phần tử đó chính là x thì kết luận gì?
Lấy phần tử đứng giữa dãy để so sánh với x, nếu phần tử đó chính là x thì kết luận gì?
Đáp án đúng là: C
Lấy phần tử đứng giữa dãy để so sánh với x, nếu phần tử đó chính là x thì kết luận: Đã tìm thấy x và kết thúc thuật toán.
Câu 5:
Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy sắp xếp diễn biến từng bước kìm kiếm nhị phần để tìm kiếm x=60 trong dãy trên.
Tìm x = 60:
A1
A2
A3
A4
A5
A6
A7
A8
Xuất phát
5
11
18
39
41
52
63
70
Bước 1
39
41
52
63
70
Bước 2
52
63
70
Bước 3
63
1. Kết thúc thuật toán: Không tìm thấy x có trong dãy.
2. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x<A7 nên nửa sau chắc chắn không chứa x.
3. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x>A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.
4. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x >A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A5 đến A8.
Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy sắp xếp diễn biến từng bước kìm kiếm nhị phần để tìm kiếm x=60 trong dãy trên.
Tìm x = 60:
|
A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
A7 |
A8 |
Xuất phát |
5 |
11 |
18 |
39 |
41 |
52 |
63 |
70 |
Bước 1 |
|
|
|
39 |
41 |
52 |
63 |
70 |
Bước 2 |
|
|
|
|
|
52 |
63 |
70 |
Bước 3 |
|
|
|
|
|
|
63 |
|
1. Kết thúc thuật toán: Không tìm thấy x có trong dãy.
2. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x<A7 nên nửa sau chắc chắn không chứa x.
3. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x>A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.
4. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x >A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A5 đến A8.
Đáp án đúng là: C
Sắp xếp diễn biến từng bước kìm kiếm nhị phần để tìm kiếm x=60 trong dãy trên như sau:
1. Chia đôi lần 1. Phạm vi tìm kiếm từ dãy A1 đến A8. Lấy A4 là số có vị trí giữa dãy. Vì x >A4 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau cảu dãy. Phạm vi tìm kiếm từ A5 đến A8.
2. Chia đôi lần 2. Phạm vi tìm kiếm từ dãy A5 đến A8. Lấy A6 có vị trí giữa dãy. Vì x>A6 nên nửa đầu dãy chắc chắn không chứa x = 60. Tiếp theo chỉ cần tìm trong nửa sau của dãy. Phạm vi tìm kiếm từ A7 đến A8.
3. Chia đôi lần 3. Phạm vi tìm kiếm từ A7 đến A8. Lấy A7 có vị trị giữa dãy. Vì x<A7 nên nửa sau chắc chắn không chứa x.
4. Kết thúc thuật toán: Không tìm thấy x có trong dãy.
Các bài thi hot trong chương:
( 768 lượt thi )
( 747 lượt thi )
( 612 lượt thi )
( 540 lượt thi )
( 499 lượt thi )
( 470 lượt thi )
Đánh giá trung bình
0%
0%
0%
0%
0%