Trắc Nghiệm Cấu Trúc Dữ Liệu Và Giải Thuật - Bài 11
1-
Trong bài toán liệt kê, có nhiều phương pháp liệt kê, nhưng chúng cần phải đáp ứng được yêu cầu là:
A -
Không được bỏ sót một cấu hình
B -
Không được lặp lại một cấu hình
C -
Chỉ ra phạm vi giải quyết của cấu hình
D -
Cả A và B đều đúng
2-
Cho S là một tập hữu hạn gồm n phần tử và k là một số tự nhiên. Gọi X là tập các số nguyên dương từ 1 đến k: X = {1, 2, …, k} . Chỉnh hợp lặp chập k của S là:
A -
Mỗi ánh xạ f: X → S. Cho tương ứng với mỗi i ε X, một và chỉ một phần tử f(i) ε S.
B -
Mỗi ánh xạ X: f → S. Cho tương ứng với mỗi i ε S, một và chỉ một phần tử f(i) ε S.
C -
Mỗi ánh xạ f: X → S. Cho tương ứng với mỗi i ε S, một và chỉ một phần tử f(i) ε X
D -
Mỗi ánh xạ X: f → S. Cho tương ứng với mỗi i ε X, một và chỉ một phần tử f(i) ε X
3-
Cho S = {A, B, C, D, E, F}; k = 3. Một ánh xạ f có thể cho như sau:
Số chỉnh hợp lặp chập k của tập gồm n phần tử là:
A -
n
B -
n2
C -
nk
D -
n2k
4-
Chỉnh hợp không lặp là:
A -
Khi f là đa ánh có nghĩa là với ∀i, j ε X ta có f(i) = f(j) ⇔ i = j
B -
Khi f là đa ánh có nghĩa là với ∀i, j ε X ta có f(i) > f(j) ⇔ i > j
C -
Khi f là đơn ánh có nghĩa là với ∀i, j ε X ta có f(i) = f(j) ⇔ i = j
D -
Khi f là đơn ánh có nghĩa là với ∀i, j ε X ta có f(i) > f(j) ⇔ i > j
5-
Một chỉnh hợp không lặp (C, A, E) :
Số chỉnh hợp không lặp chập k của tập gồm n phần tử là:
A -
nPk = n(n - 1)(n - 2)...(n - k ) = n!/(n - k )!
B -
nPk = n(n - 1)(n - 2)...(n - k +1) = n!/(n - k )!
C -
nPk = n(n + 1)(n + 2)...(n + k +1 ) = n!/(n + k )!
D -
nPk = n(n + 1)(n + 2)...(n + k ) = n!/(n + k )!
6-
Hoán vị là:
A -
Khi k = 1. Một chỉnh hợp không lặp chập n của S được gọi là một hoán vị các phần tử của S.
B -
Khi k = 1. Một chỉnh hợp lặp chập n của S được gọi là một hoán vị các phần tử của S.
C -
Khi k = n. Một chỉnh hợp không lặp chập n của S được gọi là một hoán vị các phần tử của S.
D -
Khi k = n. Một chỉnh hợp lặp chập n của S được gọi là một hoán vị các phần tử của S.
7-
Một hoán vị: 〈A, D, C, E, B, F〉 của S = {A, B, C, D, E, F}
Số hoán vị của tập gồm n phần tử = số chỉnh hợp không lặp chập:
A -
n = 1
B -
n = n
C -
n = n2
D -
n = n!
8-
Tổ hợp là :
A -
Khi k = 1. Một chỉnh hợp không lặp chập n của S được gọi là một hoán vị các phần tử của S.
B -
Khi k = n. Một chỉnh hợp không lặp chập n của S được gọi là một hoán vị các phần tử của S.
C -
Một tập con gồm k phần tử của S được gọi là một tổ hợp chập k của S.
D -
Một tập mẹ gồm k phần tử của S được gọi là một tổ hợp chập k của S.
9-
Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu như điều kiện sau thoả mãn:
A -
Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể biết đượccấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đó
B -
Xây dựng được thuật toán từ một cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp nó
C -
Cả A và B đều đúng
D -
Cả A và B đều sai
10-
Tập {A, B, C} là tập con của tập S, thì: 〈A, B, C〉, 〈C, A, B〉, 〈B, C, A〉, … là các chỉnh hợp không lặp chập 3 của S. Điều đó tức là khi liệt kê tất cả các chỉnh hợp không lặp chập k thì mỗi tổ hợp chập k sẽ được tính k! lần. Vậy số tổ hợp chập k của tập gồm n phần tử là:
