JavaScript is required

Xét thủ tục sau:

int TimKiemNP (int M[], int First, int Last, int X)

{

if (First > Last)

return (-1);

int Mid = (First + Last)/2;

if (X == M[Mid])

return (Mid);

if (X < M[Mid])

return(TimKiemNP (M, First, Mid – 1, X));

else

return(TimKiemNP (M, Mid + 1, Last, X));

}

Lựa chọn câu đúng nhất để mô tả thủ tục trên:

A.

Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last

B.

Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last

C.

Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

D.

Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

Trả lời:

Đáp án đúng: B


Đề bài cung cấp một đoạn mã C++ thực hiện thuật toán tìm kiếm nhị phân (binary search) một cách đệ quy. Ta cần xác định mô tả chính xác nhất về chức năng của đoạn mã này. * **Phân tích mã:** * Hàm `TimKiemNP` nhận vào một mảng `M`, chỉ số đầu `First`, chỉ số cuối `Last`, và giá trị cần tìm `X`. * Nếu `First > Last`, hàm trả về -1, nghĩa là không tìm thấy `X` trong mảng. * Tính chỉ số giữa `Mid = (First + Last) / 2`. * Nếu `X == M[Mid]`, hàm trả về `Mid` (vị trí tìm thấy). * Nếu `X < M[Mid]`, hàm gọi đệ quy `TimKiemNP` với nửa đầu của mảng (`First` đến `Mid - 1`). * Ngược lại (`X > M[Mid]`), hàm gọi đệ quy `TimKiemNP` với nửa sau của mảng (`Mid + 1` đến `Last`). * **Xét các phương án:** * Phương án 1: "Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last". Đúng một phần, nhưng chưa đủ chính xác vì không đề cập đến tính đệ quy. * Phương án 2: "Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last". Đây là mô tả chính xác nhất. Nó chỉ rõ thuật toán tìm kiếm và phương pháp đệ quy được sử dụng, đồng thời xác định rõ phạm vi tìm kiếm (từ `First` đến `Last`). * Phương án 3: "Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First". Sai, vì thứ tự chỉ số tìm kiếm là từ `First` đến `Last`, không phải ngược lại. Thuật toán tìm kiếm nhị phân yêu cầu mảng được sắp xếp và tìm kiếm theo thứ tự tăng dần của chỉ số. * Phương án 4: "Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First". Sai, vì thuật toán sử dụng đệ quy và thứ tự chỉ số tìm kiếm cũng sai. Vậy phương án 2 là đáp án chính xác nhất.

Đề 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