Video 4.0 - Bài toán sinh hoán vị

Khi bắt đầu sinh hoán vị cho n phần tử, số lựa chọn có thể tại bước đầu tiên là:

• A. 2 lựa chọn

• B. n lựa chọn

• C. n! lựa chọn ngay lập tức

• D. Không xác định

Tại sao không thể sinh hoán vị bằng cách “gán 0 hoặc 1” như bài sinh xâu nhị phân?

• A. Vì số lượng hoán vị lớn hơn số lượng xâu nhị phân

• B. Vì mỗi vị trí phải chứa một giá trị duy nhất

• C. Vì xâu nhị phân quá dài

• D. Vì không dùng được đệ quy

Sau khi thử phần tử i tại vị trí k và quay lui, ta cần làm gì?

• A. Xóa phần tử i khỏi mảng x

• B. Đặt visited[i] = false

• C. Gán x[k] = 0

• D. Không cần làm gì cả

Trong thuật toán sinh hoán vị bằng backtracking, mảng visited có vai trò chính là gì?

• A. Giúp xác định đã sinh được bao nhiêu hoán vị.

• B. Đánh dấu phần tử nào đã được chọn để tránh dùng lại.

• C. Ghi lại kết quả cuối cùng.

• D. Tăng tốc độ đệ quy.

Trong quá trình sinh hoán vị n = 3, nếu đã chọn x[1] = 1 và x[2] = 3, thì phần tử nào có thể đặt vào x[3]?

• A. 1

• B. 2

• C. 3

• D. Không có phần tử nào

Điểm khác biệt quan trọng nhất giữa sinh xâu nhị phân và sinh hoán vị là gì?

• A. Sinh xâu nhị phân dùng for, còn hoán vị dùng while.
  

• B. Sinh xâu nhị phân có 2 lựa chọn tại mỗi vị trí, còn hoán vị có nhiều lựa chọn nhưng không được trùng.

• C. Sinh xâu nhị phân không dùng đệ quy.

• D. Hoán vị luôn có ít kết quả hơn.