Video 3.4 - Sinh xâu nhị phân

Vì sao sinh xâu nhị phân phù hợp để dùng backtracking?

• A. Vì chỉ có số lượng rất nhỏ xâu nên không tốn thời gian.

• B. Vì mỗi vị trí chỉ có 2 lựa chọn, và việc thử – quay lui tạo ra cây duyệt rõ ràng.

• C. Vì backtracking luôn nhanh hơn mọi phương pháp khác cho bài này.

• D. Vì không thể dùng vòng lặp để sinh xâu nhị phân.

Với xâu nhị phân độ dài n, số nút lá (leaf) trong cây duyệt backtracking là bao nhiêu?

• A. n

• B. 2 × n

• C. 2^n

• D. n!

Điều kiện dừng đúng cho thuật toán sinh xâu nhị phân là gì?

• A. Khi tìm thấy xâu toàn số 1.

• B. Khi k > n.

• C. Khi k == n (đã gán đủ n vị trí).

• D. Khi x[k] = 0.

Thứ tự sinh xâu nào sau đây không thể là đầu ra của thuật toán backtracking duyệt từ 0 sang 1 như mô tả?

• A. 000, 001, 010, 011, 100…

• B. 000, 010, 001, 011…

• C. 000, 001, 010, 011, 100, 101…

• D. 000, 001, 010, 011, 100, 101, 110, 111

Tại sao thuật toán luôn phải backtrack (hoàn tác lựa chọn)?

• A. Vì nếu không backtrack, chương trình sẽ bị lỗi.

• B. Vì nếu không hoàn tác, các giá trị cũ sẽ ảnh hưởng kết quả của các nhánh sau.

• C. Vì backtracking là bắt buộc trong mọi thuật toán đệ quy.

• D. Vì hoàn tác giúp in kết quả đẹp hơn.