JavaScript is required

Cho dãy số sau: 10 11 14 32 36 43 55 57 87 97. Áp dụng phương pháp tìm kiếm nhị phân, để tìm kiếm số 97, lần phân đoạn thứ hai của dãy sẽ là:

A.

[36 97]

B.

[36 11]

C.

[36 97 11]

D.

[87 97]

Trả lời:

Đáp án đúng: D


Tìm kiếm nhị phân hoạt động bằng cách liên tục chia đôi đoạn cần tìm kiếm. Bước đầu tiên, ta tìm phần tử ở giữa dãy. Trong trường hợp này, dãy là [10, 11, 14, 32, 36, 43, 55, 57, 87, 97]. Phần tử ở giữa là 43. Vì 97 > 43, ta loại bỏ nửa đầu của dãy (bao gồm cả 43). Vậy, ở lần phân đoạn thứ nhất, dãy con còn lại là [55, 57, 87, 97]. Bước tiếp theo (lần phân đoạn thứ hai), ta lại tìm phần tử ở giữa của dãy con này. Phần tử ở giữa là (57+87)/2, ta lấy vị trí của 87. Vì 97 > 87, ta loại bỏ nửa đầu (bao gồm cả 87). Vậy, ở lần phân đoạn thứ hai, dãy con còn lại (chính xác hơn là xét từ vị trí của 87) là [87, 97]. Do 97 > 57 nên đoạn [55, 57] bị loại và ta chỉ còn [87,97]. Do đó, đáp án chính xác là [87 97]. Tuy nhiên, đề bài yêu cầu đoạn thứ 2 *trước* khi tìm thấy 97. Khi đó ta xem xét tiếp: ở lần phân đoạn đầu tiên, ta có dãy [55 57 87 97]. Phần tử giữa là (55+97)/2 ≈ 76, suy ra ta sẽ xét vị trí 87. Vì 87 < 97 nên tiếp tục. Dãy ban đầu được chia thành hai nửa: [10 11 14 32 36 43] và [55 57 87 97]. Do 97 lớn hơn phần tử giữa của dãy ban đầu (43), ta xét nửa sau. Sau đó tiếp tục chia nửa sau: [55 57] và [87 97]. Tiếp tục so sánh 97 với phần tử giữa của [55 57 87 97], ta thấy 97 > 57 nên ta xét [87 97]. Tuy nhiên các đáp án không có [55 57 87 97], [87, 97]. Xét đáp án [36 97] thì không hợp lý vì 36 không nằm trong khoảng tìm kiếm thứ 2. Vậy ta xét đáp án [87 97] sau khi duyệt ở bước thứ hai, sẽ đúng hơn. Tuy nhiên, ta thấy có sự không rõ ràng trong câu hỏi về các đáp án. Nếu coi bước đầu tiên loại bỏ [10, 11, 14, 32, 36, 43] thì không có đáp án nào đúng. Nếu đoạn phân đoạn thứ hai chính là đoạn chứa số cần tìm sau lần duyệt thứ 2 thì đáp án [87 97] hợp lý hơn cả. Do đó, có vẻ như không có đáp án đúng trong các lựa chọn đã cho, hoặc có thể có lỗi trong đề bài hoặc các đáp án. Vì vậy, đáp án [87 97] có thể coi là hợp lý nhất trong các đáp án đã cho, mặc dù nó không hoàn toàn chính xác phản ánh quá trình tìm kiếm nhị phân theo lý thuyết (vì đáng lẽ ta phải chia đôi [55 57 87 97] trước khi đến [87 97]).

Đề cương ôn thi với 220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án được chọn lọc và chia sẻ dưới đây, nhằm giúp bạn sinh viên hệ thống kiến thức chuẩn bị cho kì thi sắp diễn ra.


50 câu hỏi 60 phút

Câu hỏi liên quan