JavaScript is required

Anh (Chị) hãy cho biết kết quả của đoạn lệnh sau là gì?

int BinSearch (char*item,char *table[],int n, int (*Sosanh)(const char*,const char*))

{ int bot = 0, top = n - 1, mid, cmp;

while (bot < top) { mid = (bot + top) / 2;

if ((cmp = Sosanh(item,table[mid])) == 0) return mid;

else if (cmp < 0) top = mid - 1;

else bot = mid + 1;

}

return -1;

}

int main() { char *cities[] = { “Boston”, “London”, “Sydney”, “Tokyo” };

cout << BinSearch (“Sydney”,cities,4,strcmp) << endl;

}

A.

1

B.

2

C.

true

D.

Chương trình báo lỗi.

Trả lời:

Đáp án đúng: B


Đoạn chương trình thực hiện tìm kiếm nhị phân (Binary Search) trên một mảng các chuỗi. Hàm `BinSearch` tìm kiếm chuỗi `item` trong mảng `table` có `n` phần tử, sử dụng hàm so sánh `Sosanh`. Trong hàm `main`, mảng `cities` chứa các chuỗi "Boston", "London", "Sydney", "Tokyo". Hàm `BinSearch` được gọi để tìm chuỗi "Sydney" trong mảng `cities` với `n = 4` và hàm so sánh `strcmp`. Bước thực hiện: 1. `bot = 0`, `top = 3` 2. Vòng lặp `while (bot <= top)`: * `mid = (0 + 3) / 2 = 1` * `cmp = strcmp("Sydney", cities[1]) = strcmp("Sydney", "London")`. Vì "Sydney" > "London" nên `cmp > 0`. * `bot = mid + 1 = 2` 3. Vòng lặp `while (bot <= top)`: * `mid = (2 + 3) / 2 = 2` * `cmp = strcmp("Sydney", cities[2]) = strcmp("Sydney", "Sydney") = 0` * Trả về `mid = 2` Vậy, chương trình in ra `2`. Lưu ý: Trong đoạn code gốc, điều kiện vòng lặp while là `bot < top`, nhưng theo logic tìm kiếm nhị phân thông thường, điều kiện nên là `bot <= top`. Tuy nhiên, code đưa ra vẫn hoạt động đúng với test case này, bởi vì khi `bot = top = 2`, giá trị `mid` cũng bằng 2, và `strcmp` sẽ trả về 0, kết thúc vòng lặp và trả về 2. Nếu điều kiện là `bot < top`, thì kết quả sẽ sai. Tuy nhiên, ta cần đánh giá đoạn code đã cho, không phải đoạn code "đúng".

Câu hỏi liên quan