Font size
WorksheetsTHUẬT TOÁN TIM KIẾM_SX
Total questions: 45
Worksheet time: 22mins
Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa sau của dãy:
Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.
Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm
Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.
Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.
Điều gì xảy ra khi thuật toán tìm kiếm nhị phân không tìm thấy giá trị cần tìm trong danh sách?
Tiếp tục tìm kiếm và không bao giờ kết thúc.
Thông báo “Tìm thấy” và tìm tiếp xem còn phần tử nào khác nữa không.
Thông báo “Tìm thấy” và kết thúc.
Thông báo “Không tìm thấy” và kết thúc.
Để 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:
So sánh số cần tìm với số ở giữa dãy số.
Sắp xếp dãy số theo thứ tự tăng dần.
So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy”, cho kết quả là:
1
2
3
4
Trong bài toán tìm kiếm nhị phân, đối với dãy đã sắp xếp tăng dần khi nào phạm vi tìm kiếm nằm ở nửa đầu của dãy:
Khi số cần tìm lớn hơn phần tử giữa của phạm vi tìm kiếm.
Khi số cần tìm nhỏ hơn phần tử giữa của phạm vi tìm kiếm.
Khi số cần tìm lớn hơn phần tử đầu tiên của dãy.
Khi số cần tìm nhỏ hơn phần tử cuối cùng của dãy.
Tìm kiếm nhị phân là:
Tìm kiếm lần lượt từ đầu tới cuối dãy.
Tìm kiếm ở đầu dãy.
Tìm kiếm bằng cách chia dãy làm hai nửa, loại bỏ nửa dãy chắc chắn không chứa phần tử cần tìm, chỉ tìm kiếm trong nửa dãy còn lại.
Tìm kiếm ở cuối dãy.
Thuật toán tìm kiếm nhị phân bắt đầu thực hiện ở vị trí nào trong danh sách?
Vị trí đầu tiên.
Vị trí cuối cùng.
Vị trí giữa.
Bất kì vị trí nào.
Khẳng định nào sau đây là đúng khi nói về thuật toán tìm kiếm nhị phân?
Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy đã sắp xếp thứ tự.
Thuật toán tìm kiếm nhị phân áp dụng được cho mọi bài toán.
Thuật toán tìm kiếm nhị phân áp dụng được cho dãy đã sắp xếp thứ tự và dãy không sắp xếp thứ tự .
Thuật toán tìm kiếm nhị phân chỉ áp dụng được cho dãy không sắp xếp thứ tự.
Cho dãy số 2, 4, 6, 8, 9. Bài toán “Tìm vị trí của số 8 trong dãy”, có phạm vi tìm kiếm là:
Nửa dãy đầu.
Tất cả dãy.
Nửa dãy sau.
Không có phạm vi.
Điều gì xảy ra khi thuật toán tìm kiếm nhị phân không tìm thấy giá trị cần tìm trong danh sách?
Tiếp tục tìm kiếm và không bao giờ kết thúc.
Thông báo “Tìm thấy” và tìm tiếp xem còn phần tử nào khác nữa không.
Thông báo “Tìm thấy” và kết thúc.
Thông báo “Không tìm thấy” và kết thúc.
Để 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:
So sánh số cần tìm với số ở giữa dãy số.
Sắp xếp dãy số theo thứ tự tăng dần.
So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm.
Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm.
2
3
4
5
Tìm trong nửa sau của danh sách.
Tìm trong nửa đầu của danh sách.
Dừng lại.
Tìm trong nửa đầu hoặc nửa sau của danh sách.
Chưa tìm thấy phần tử cần tìm.
Chưa hết danh sách.
Chưa tìm thấy phần tử cần tìm hoặc chưa hết danh sách.
Chưa tìm thấy phần tử cần tìm và chưa hết danh sách.
Tìm trên danh sách đã sắp xếp, bắt đầu từ đầu danh sách, nếu chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
Tìm trên danh sách bất kì, bắt đầu từ giữa danh sách, nếu chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
Tìm trên danh sách đã sắp xếp, bắt đầu từ giữa danh sách, nếu chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp.
Tìm trên danh sách bất kì, bắt đầu từ đầu danh sách, nếu chưa tìm thấy hoặc chưa tìm hết thì còn tìm tiếp
Thu hẹp danh sách tìm kiếm chỉ còn một nửa.
Danh sách sẽ được sắp xếp lại.
Các phần tử trong danh sách ban đầu sẽ giảm một nửa.
Đáp án khác.
Thuật toán tìm kiếm nhị phân cần bao nhiêu bước để tìm thấy “Mai” trong danh sách ["Hoa”, "Lan”, "Ly", "Mai", “Phong”, "Vị"]?
1
2
3
4
Tìm số 5 trong dãy [1, 2, 3, 4, 5, 6]
Tìm số 5 trong dãy [1, 5, 3, 6]
Tìm số 5 trong dãy [6, 5, 4, 3, 2, 1]
Tìm số 5 trong dãy [6, 5, 4, 3, 2, 1] và dãy [1, 2, 3, 4, 5, 6]
Phương pháp tìm kiếm nhị phân hoạt động như thế nào?
Phương pháp tìm kiếm nhị phân hoạt động bằng cách tìm kiếm từng phần tử trong mảng và so sánh với giá trị tìm kiếm.
Phương pháp tìm kiếm nhị phân hoạt động bằng cách sắp xếp mảng theo thứ tự ngẫu nhiên và tìm kiếm giá trị trong mảng đã sắp xếp.
Phương pháp tìm kiếm nhị phân hoạt động bằng cách tìm kiếm từng phần tử trong mảng và so sánh với giá trị tìm kiếm theo thứ tự ngẫu nhiên.
Phương pháp tìm kiếm nhị phân hoạt động bằng cách chia mảng đã được sắp xếp thành hai phần và so sánh giá trị tìm kiếm với giá trị ở phần giữa.
Tìm kiếm nhị phân được sử dụng trong lĩnh vực nào?
Tìm kiếm và lưu trữ dữ liệu.
Tìm kiếm và sắp xếp dữ liệu.
Tìm kiếm và phân tích dữ liệu.
Tìm kiếm và xử lý dữ liệu.
Giải thuật tìm kiếm nhị phân chỉ hoạt động trên dãy số đã được sắp xếp tăng dần. Đúng hay sai?
Đúng
Sai
Không biết
Chưa rõ
Tìm kiếm nhị phân có độ phức tạp thời gian là bao nhiêu?
O(n)
O(log n)
O(n^2)
O(1)
Khi tìm kiếm nhị phân, nếu phần tử cần tìm nằm ở giữa dãy số, ta sẽ làm gì?
Tiếp tục tìm kiếm ở nửa dãy số mà phần tử cần tìm nằm trong đó.
Tìm kiếm ở phần tử sau đó của dãy số.
Tìm kiếm ở phần tử trước đó của dãy số.
Dừng tìm kiếm vì đã tìm thấy phần tử cần tìm.
Để 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:
Lấy ngẫu nhiên một số trong dãy số để so sánh với số cần tìm
So sánh lần lượt từ số đầu tiên trong dãy số với số cần tìm
Sắp xếp dãy số theo thứ tự tăng dần
So sánh số cần tìm với số ở giữa dãy số
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?
5 lần
6 lần
7 lần
8 lần
Cho dãy số A = {24, 28, 14, 18, 19, 12, 19}. Để tìm kiếm số 39 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?
5 lần
6 lần
7 lần
8 lần
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?
2 lần
3 lần
4 lần
5 lần
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.
1 – 2 – 3 – 4
1 – 3 – 4 – 2
1 – 3 – 2 – 4
1 – 2 – 4 – 3
cho danh sách sau: 40, 68, 89, 83,19, 71, 82, 22 nên sử dụng phương pháp tìm kiếm nào
Tìm kiếm nhị phân
Tất cả đều sai
Giải thuật Quicksort
Tìm kiếm tuần tự
Trong Phương pháp tìm kiếm nhị phân, cần các biến nào sau đây
Left
Right
Mid
Tất cả đều đều đúng
Trong Phương pháp tìm kiếm nhị phân khi tìm khóa key trong danh sách mảng 1 chiều, các biến left, right mid là:
Danh sách của mảng
Giá trị của mảng
tất cả đều đúng
Chỉ số của mảng
Thuật toán tìm kiếm tuần tự yêu cầu danh sách cần tìm phải được sắp xếp.
Đúng
Sai
Hoán đổi vị trí hai phần tử liên tiếp khi chúng không đúng thứ tự là cách sắp xếp của thuật toán nào?
Nổi bọt
Chọn
Dùng thuật toán sắp xếp nổi bọt để sắp xếp một dãy số tăng dần. Mỗi vòng lặp sẽ duyệt các phần tử từ cuối danh sách đến đầu danh sách. Kết thúc vòng lặp thứ nhất, phần tử đầu tiên sẽ có giá trị:
Nhỏ nhất trong dãy số.
Lớn nhất trong dãy số.
Không thay đổi.
Bằng giá trị của phần tử liền trước.
Các nhiệm vụ để thực hiện việc sắp xếp gồm
So sánh
Đổi chỗ
So sánh và đổi chỗ
Đổi chỗ và xoá
Cho dãy số sau: 15, 20, 10, 18. Bạn Minh sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy số tăng dần. Mỗi vòng lặp sẽ duyệt từ phần tử cuối đến phần tử đầu tiên. Em hãy chọn phương án mô tả đúng dãy số sắp xếp sau mỗi vòng lặp.
15, 20, 10, 18→10, 15, 18, 20→ 10, 15, 18, 20
15, 20, 10, 18 → 10, 20, 15, 18→ 10, 15, 20, 18 → 10, 15, 18, 20.
15, 20, 10, 18→ 15, 10, 20, 18→ 10, 15, 18, 20.
15, 20, 10, 18→10, 15, 20, 18→ 10, 15, 18, 20
Đâu là phát biểu đúng khi nói đến thuật toán tìm kiếm tuần tự?
Thực hiện tìm lần lượt từ đầu đến cuối danh sách.
Khi chưa tìm thấy và chưa tìm hết thì còn tìm tiếp.
Cả A, B đúng.
Cả A, B sai.
