Câu hỏi:
21/08/2022 1,542
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.
Quảng cáo
Trả lời:
Giải bởi Vietjack
Đá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.
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
Sách thầy cô Vietjack biên soạn:
Trọng tâm Văn - Sử - Địa - GDCD và Toán - Anh - KHTN lớp 7 (chương trình mới)
Đã bán 230
₫ 235.000
₫ 120.000
Trọng tâm Văn - Sử - Địa - GDCD và Toán - Anh - KHTN lớp 8 (chương trình mới)
Đã bán 287
₫ 230.000
₫ 120.000
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn?
Ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn?
Xem đáp án »
21/08/2022
11,989
Câu 2:
Thuật toán tìm kiếm nhị phân chỉ áp dụng cho dãy số như thế nào?
Thuật toán tìm kiếm nhị phân chỉ áp dụng cho dãy số như thế nào?
Xem đáp án »
21/08/2022
7,097
Câu 3:
Tìm kiếm nhị phân và tìm kiếm tuần tự thì thuật toán nào nhanh hơn?
Tìm kiếm nhị phân và tìm kiếm tuần tự thì thuật toán nào nhanh hơn?
Xem đáp án »
21/08/2022
5,214
Câu 4:
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ì?
Xem đáp án »
21/08/2022
3,385
Câu 5:
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ì?
Xem đáp án »
21/08/2022
3,013
Câu 6:
Nhận định nào sau đây đúng nhất về thuật toán tìm kiếm nhị phân?
Nhận định nào sau đây đúng nhất về thuật toán tìm kiếm nhị phân?
Xem đáp án »
21/08/2022
2,925
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 10 có đáp án
-
Đề kiểm tra học kì 2 Tin học 7 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 14 có đáp án
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 15 có đáp án
-
Đề kiểm tra học kì 2 Tin học 7 Cánh diều có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 9 có đáp án
-
Đề kiểm tra giữa học kì 2 Tin học 7 Kết nối tri thức có đáp án - Đề 1
-
15 câu Trắc nghiệm Tin học 7 Kết nối tri thức Bài 13 có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận