wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

W4: Algorithm Complexity and Determinism

Total questions: 137

Worksheet time: 1hrs 20mins

Name
Class
Date
1.

Thuật toán A với kích thước dữ liệu đầu vào n có độ phức tạp đa thức nếu

a)

tồn tại đa thức P(n) mà T_A(n) >= C·P(n), ∀ n < = N_0; với C và N_0 là các hằng số

b)

tồn tại đa thức P(n) mà T_A(n) ≤ C·P(n), ∀ n ≥ N_0; với C và N_0 là các hằng số

c)

tồn tại đa thức P(n) mà T_A(n) ≤ P(n), ∀ n < = N_0; với N_0 là hằng số

d)

tồn tại đa thức P(n) mà T_A(n) ≥ C·P(n), ∀ n ≥ N_0; với C và N_0 là các hằng số

2.

Thuật toán được gọi là đa thức nếu

a)

độ phức tạp về thời gian trong trường hợp tốt nhất của nó là đa thức

b)

độ phức tạp về không gian trong trường hợp xấu nhất của nó là đa thức

c)

độ phức tạp về thời gian trong trường hợp xấu nhất của nó là đa thức

d)

độ phức tạp về không gian trong trường hợp trung bình của nó là đa thức

3.

Thuật toán đơn định là

a)

Thuật toán mà tại mỗi bước, chỉ có một lựa chọn duy nhất

b)

Thuật toán mà tại mỗi bước, có nhiều lựa chọn

c)

Thuật toán chạy không xác định thời gian

d)

Thuật toán không cần dữ liệu đầu vào

4.

Thuật toán đơn định đa thức là

a)

thuật toán đơn định có độ phức tạp trong trường hợp tốt nhất là đa thức

b)

thuật toán đơn định có độ phức tạp trong trường hợp trung bình là đa thức

c)

thuật toán đơn định có độ phức tạp là đa thức

d)

thuật toán đơn định có độ phức tạp là trên đa thức (hàm mũ)

5.

Thuật toán không đơn định là

a)

thuật toán mà tại mỗi bước, có một lựa chọn duy nhất

b)

thuật toán mà tại mỗi bước, có nhiều lựa chọn có thể thực hiện thay vì một lựa chọn duy nhất

c)

thuật toán luôn cho kết quả chính xác

d)

thuật toán không có dữ liệu đầu vào

6.

Lớp P bao gồm những bài toán:

a)

Không thể giải quyết được

b)

Có thể giải được bằng thuật toán không đơn định trong thời gian hàm mũ

c)

Có thể giải được bằng thuật toán đơn định trong thời gian hàm mũ

d)

Có thể giải được bằng thuật toán đơn định trong thời gian đa thức

7.

Một bài toán thuộc lớp P nếu:

a)

Nó có thể được giải quyết trong thời gian đa thức bằng một thuật toán không đơn định

b)

Nó có thể được giải quyết trong thời gian đa thức bằng một thuật toán đơn định

c)

Nó không được giải quyết trong thời gian đa thức

d)

Nó không được giải quyết bằng thuật toán nào cả

8.

Lớp NP bao gồm những bài toán:

a)

Chưa tìm được thuật toán với độ phức tạp đa thức nhưng chỉ ra được phương pháp kiểm định nghiệm của nó (nếu có) với thời gian đa thức

b)

Chưa tìm được thuật toán với độ phức tạp đa thức nhưng chỉ ra được phương pháp kiểm định nghiệm của nó (nếu có) với thời gian hàm mũ

c)

Chưa tìm được thuật toán đơn định với độ phức tạp hàm mũ

d)

Chưa tìm được thuật toán không đơn định với độ phức tạp hàm mũ

9.

NP là lớp các bài toán

a)

mà mọi nghiệm giả định đều không được kiểm chứng trong thời gian đa thức

b)

mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian hàm mũ

c)

mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian hàm mũ

d)

mà mọi nghiệm giả định đều có thể được kiểm chứng trong thời gian đa thức

10.

Thuật toán không đơn định có thể:

a)

Chỉ thử một lựa chọn tại mỗi bước

b)

Thử nhiều lựa chọn tại mỗi bước

c)

Chạy mãi mãi mà không kết thúc

d)

Luôn luôn cho kết quả đúng

11.

Kiểm định nghiệm trong thời gian đa thức có nghĩa là:

a)

A. Giải quyết bài toán trong thời gian đa thức

b)

B. Tìm kiếm nghiệm đúng trong thời gian đa thức

c)

C. Tìm kiếm nghiệm gần đúng trong thời gian đa thức

d)

D. Kiểm tra một nghiệm có đúng hay không trong thời gian đa thức

12.

Một thuật toán tìm số ước của một số nguyên dương N

1.Nhập N

2. dem=0;

3. for (i=1; i =N; ++i)

4. if (N%i = =0)

5. dem=dem+1;

6. Xuất dem

Được đánh giá là:

a)

A. Thuật toán đơn định, đa thức

b)

B. Thuật toán đơn định, hàm mũ

c)

C. Thuật toán không đơn định, đa thức

d)

D. Thuật toán không đơn định, hàm mũ

13.

Một thuật toán tính tổng của các số chẵn từ 1 đến N (N là số nguyên dương)

1.Nhập N

2. S=0;

3. for (i=1; i =N; ++i)

4. if (i%2 = =0)

5. S=S+i;

6. Xuất S

Được đánh giá là :

a)

A. Thuật toán đơn định, đa thức

b)

B. Thuật toán đơn định, hàm mũ

c)

C. Thuật toán không đơn định, đa thức

d)

D. Thuật toán không đơn định, hàm mũ

14.
a)

A. Thuật toán đơn định, đa thức

b)

B. Thuật toán đơn định, hàm mũ

c)

C. Thuật toán không đơn định, đa thức

d)

D. Thuật toán không đơn định, hàm mũ

15.
a)

Thuật toán đơn định, đa thức

b)

Thuật toán đơn định, hàm mũ

c)

Thuật toán không đơn định, đa thức

d)

Thuật toán không đơn định, hàm mũ

16.

Nếu một bài toán thuộc lớp NP nhưng không thuộc lớp P thì:

a)

Lời giải của nó có được kiểm định trong thời gian đa thức nhưng không thể tìm được trong thời gian đa thức

b)

Lời giải của nó có thể tìm thấy trong thời gian đa thức

c)

Lời giải của nó không thể được kiểm định trong thời gian đa thức

d)

Lời giải của nó không tồn tại

17.

Nếu một bài toán có thể được giải quyết trong thời gian đa thức bằng một thuật toán không đơn định, nhưng không thể giải quyết bằng thuật toán đơn định, điều đó có nghĩa là:

a)

Bài toán đó thuộc lớp P

b)

Bài toán đó thuộc lớp NP nhưng không thuộc lớp P

c)

Bài toán đó không thuộc lớp NP

d)

Bài toán đó không thể giải quyết được

18.

Thuật toán nào sau đây có khả năng giải quyết bài toán NP trong thời gian đa thức?

a)

Thuật toán đơn định

b)

Thuật toán không đơn định

c)

Thuật toán heuristic

d)

Không có lựa chọn nào đúng

19.

Bài toán “tìm kiếm tuần tự giá trị k trong một dãy n số nguyên x1, x2, …,xn “, có thuộc lớp P?

a)

Có

b)

Không

c)

Chỉ khi danh sách rất nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

20.

Bài toán “sắp xếp dãy n số nguyên x1, x2, …, xn theo chiều tăng dần” bằng thuật toán QuickSort có thuộc lớp P?

a)

Có

b)

Không

c)

Chỉ khi danh sách rất nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

21.

Bài toán “xác định số nguyên tố”, có thể được giải quyết trong thời gian đa thức bởi thuật toán đơn định không?

a)

Có

b)

Không

c)

Chỉ khi số nguyên tố rất nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

22.

Bài toán “tính một số hạng trong dãy Fibonacci” bằng cách không sử dụng thuật toán đệ quy, có thuộc lớp P?

a)

Có

b)

Không

c)

Chỉ khi số hạng là một số nguyên nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

23.

Thuật toán trên máy Turing là đa thức thì:

a)

Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng không là đa thức

b)

Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng chưa chắc là đa thức

c)

Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng chưa chắc là đa thức

d)

Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL tương ứng là đa thức

24.

Thuật toán trên máy xử lý thuật toán bằng ngôn ngữ tựa ALGOL là đa thức thì:

a)

Thuật toán tương ứng trên máy Turing là không đơn định

b)

Thuật toán tương ứng trên máy Turing là đơn định

c)

Thuật toán tương ứng trên máy Turing chưa chắc là đa thức

d)

Thuật toán tương ứng trên máy Turing là đa thức

25.

Nếu thuật toán tựa ALGOL là đa thức và trong thuật toán chỉ có các phép toán cơ bản, dữ liệu vào có độ phức tạp đa thức theo quan niệm 2 (độ dài mã) thì thuật toán trên máy Turing tương ứng là:

a)

Hằng số

b)

Đa thức

c)

Hàm mũ

d)

Hàm giai thừa

26.

Bài toán Tìm đường đi ngắn nhất trong đồ thị có trọng số thuộc lớp nào?

a)

P

b)

NP

c)

NP-Hard

d)

Không thuộc P hoặc NP

27.

Bài toán “tìm chu trình Euler trong một đồ thị”, có thuộc lớp P?

a)

Có

b)

Không

c)

Chỉ khi đồ thị có số cạnh nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

28.

Bài toán “kiểm tra đồ thị có chứa chu trình Hamilton”, có thuộc lớp P?

a)

Có

b)

Không

c)

Chỉ khi đồ thị có số cạnh rất nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

29.

Bài toán xác định cây khung nhỏ nhất trên đồ thị thuộc lớp nào?

a)

P

b)

NP

c)

NP-Hard

d)

Không thuộc P hoặc NP

30.

Bài toán “xác định một số nguyên dương N có phải là số nguyên tố hay không” thuộc lớp P?

a)

Có

b)

Không

c)

Chỉ khi số rất nhỏ

d)

Chỉ khi sử dụng thuật toán không đơn định

31.

Chọn hai phương án đúng liên quan đến lớp bài toán NP.

a)

Tìm phần tử lớn nhất trong mảng là bài toán lớp NP

b)

Bài toán tìm tập con có tổng bằng 0 là bài toán lớp NP

c)

Bài toán phân hoạch cũng thuộc lớp NP

d)

Thuật toán kiểm chứng nghiệm bài toán NP luôn là đệ quy

32.

Chọn hai phương án đúng về quan hệ giữa các bài toán P và NP

a)

Nếu một bài toán có độ phức tạp O(2^n) thì chắc chắn thuộc lớp P

b)

Nếu P = NP thì tất cả các bài toán NP đều giải được bằng thuật toán đơn định trong thời gian đa thức

c)

Một số bài toán có thể kiểm tra nghiệm nhanh nhưng tìm nghiệm thì rất khó

d)

Lớp NP chỉ chứa các bài toán dễ

33.

Bài toán nào sau đây thuộc lớp P?

a)

Sắp xếp dãy số bằng thuật toán QuickSort

b)

Tô màu đồ thị

c)

Tìm chu trình Hamilton

d)

Tìm kiếm tuyến tính

34.

Bài toán nào sau đây có thể kiểm chứng nghiệm trong thời gian đa thức?

a)

Tìm kiếm tuyến tính

b)

Tính tổng dãy số

c)

Xác định số nguyên tố

d)

Tập con có tổng bằng 0 (Subset Sum Problem)

35.

Chọn hai phương án đúng về thuật toán đơn định.

a)

Độ phức tạp đa thức có dạng O( nkn^k ) với k là hằng số

b)

Thuật toán đơn định có thể lựa chọn nhiều hướng đi

c)

Thuật toán đơn định luôn cho kết quả giống nhau với cùng đầu vào

d)

Tất cả các thuật toán đơn định đều có độ phức tạp tuyến tính

36.

Chọn hai phương án đúng về quan hệ giữa các lớp bài toán P và NP

a)

Lớp NP chỉ chứa các bài toán dễ

b)

Nếu P = NP thì tất cả các bài toán NP đều giải được bằng thuật toán đơn định trong thời gian đa thức

c)

Nếu một bài toán có độ phức tạp O(2^n) thì chắc chắn thuộc lớp P

d)

Một số bài toán có thể kiểm tra nghiệm nhanh nhưng tìm nghiệm thì rất khó

37.

Phương pháp nào thường dùng để giải bài toán NP trong thực tế?

a)

Sắp xếp nhanh

b)

Thuật toán xấp xỉ

c)

Tìm kiếm vét cạn

d)

Heuristic

38.

Ví dụ nào sau đây thuộc lớp P với độ phức tạp O(n²)?

a)

Nhân ma trận

b)

Kiểm tra tính liên thông đồ thị

c)

Tìm chu trình Hamilton

d)

Tính lũy thừa nhị phân

39.

Thuật toán không đơn định có đặc điểm nào? (Chọn 2 phương án)

a)

Luôn đi theo một hướng duy nhất tại mỗi bước

b)

Có thể "thử" các khả năng khác nhau cùng lúc

c)

Kết quả luôn giống nhau với cùng đầu vào

d)

Có nhiều hướng đi tiếp tại mỗi bước

40.

Bài toán thuộc lớp P có tính chất nào? (Chọn 2 phương án)

a)

Có thể kiểm chứng nghiệm trong thời gian đa thức

b)

Có thể giải bằng thuật toán vét cạn trong thời gian mũ

c)

Có thể giải bằng thuật toán đơn định trong thời gian đa thức

d)

Chỉ có thể giải bằng thuật toán không đơn định

41.

Phát biểu nào đúng về thuật toán đơn định? (Chọn 2 phương án)

a)

Độ phức tạp đa thức có dạng O(n^k) với k là hằng số

b)

Có thể lựa chọn nhiều hướng đi cùng lúc

c)

Luôn cho kết quả giống nhau với cùng đầu vào

d)

Tất cả đều có độ phức tạp tuyến tính

42.

Trong một thuật toán không đơn định, điều nào đúng? (Chọn 2 phương án)

a)

Không bao giờ đưa ra kết quả sai

b)

Có thể "thử" các khả năng khác nhau cùng lúc

c)

Có nhiều hướng đi tiếp tại mỗi bước

d)

Luôn có lời giải duy nhất

43.

Bài toán lớp P thỏa mãn điều kiện nào? (Chọn 2 phương án)

a)

Là bài toán không thể giải trong thực tế

b)

Có thể giải bằng thuật toán đơn định trong thời gian đa thức

c)

Có thể kiểm chứng nghiệm trong thời gian đa thức

d)

Luôn có độ phức tạp là O(n!)

44.

Chọn hai phương án đúng liên quan đến lớp bài toán P. (Chọn 2 phương án)

a)

Lớp P được coi là lớp bài toán khó

b)

Lớp P gồm các bài toán giải trong thời gian đa thức bằng thuật toán đơn định

c)

Sắp xếp và tìm kiếm tuyến tính là bài toán lớp P

d)

Mọi bài toán lớp P đều không giải được trong thực tế

45.

Bài toán nào sau đây có thể được giải bằng thuật toán không đơn định đa thức? (Chọn 2 phương án)

a)

Xếp ba lô 0-1

b)

Nhân ma trận

c)

Tìm chu trình Euler

d)

Tìm chu trình Hamilton

46.

Cho hai bài toán A và B,  A được gọi là “dẫn về được” B một cách đa thức nếu

a)

có một thuật toán đơn định đa thức để giải bài toán B thì cũng có một thuật toán đơn định đa thức khác để giải bài toán A.

b)

có một thuật toán đơn định đa thức để giải bài toán A thì cũng có một thuật toán đơn định đa thức khác để giải bài toán B.

c)

có một thuật toán đơn định để giải bài toán B thì cũng có một thuật toán đơn định khác để giải bài toán A

d)

có một thuật toán không đơn định đa thức để giải bài toán B thì cũng có một thuật toán không đơn định đa thức khác để giải bài toán A.

47.

Nếu bài toán A “dẫn về được” bài toán B sau thời gian đa thức, thì

a)

bài toán A “dễ hơn” bài toán B

b)

bài toán A “khó bằng” bài toán B

c)

bài toán A “khó hơn” bài toán B

d)

bài toán B là trường hợp riêng của bài toán A

48.

Khái niệm phép quy dẫn trong lý thuyết độ phức tạp là:

a)

Quy trình giải một bài toán bằng cách sử dụng bài toán khác

b)

Phương pháp cải thiện tốc độ của thuật toán

c)

Quy trình để giảm kích thước dữ liệu

d)

Phương pháp để tăng cường độ chính xác của thuật toán

49.

Một bài toán A có thể được quy dẫn về bài toán B nếu:

a)

Bài toán B có thể được giải quyết nhanh hơn bài toán A

b)

Bài toán A có thể được giải quyết bằng cách giải bài toán B

c)

Bài toán B là dễ hơn bài toán A

d)

Bài toán A không thể giải quyết được

50.

Lớp NPC bao gồm những bài toán nào:

a)

Những bài toán không thể giải quyết được

b)

Những bài toán có thể kiểm định nghiệm trong thời gian đa thức và mọi bài toán trong NP có thể quy dẫn đến chúng

c)

Những bài toán có thể giải quyết trong thời gian đa thức

d)

Những bài toán có thể giải quyết trong thời gian đa thức bằng thuật toán không đơn định

51.

Bài toán A được gọi là NP-Hard (NP- khó) nếu:

a)

Tồn tại thuật toán đa thức để giải bài toán A thì kéo theo sự tồn tại thuật toán đa thức để giải một bài toán trong NP

b)

Tồn tại thuật toán đa thức để giải bài toán A thì kéo theo sự tồn tại thuật toán đa thức để giải mọi bài toán trong NP

c)

Tồn tại thuật toán để giải bài toán A thì kéo theo sự tồn tại thuật toán để giải một bài toán trong NP

d)

Tồn tại thuật toán để giải bài toán A thì kéo theo sự tồn tại thuật toán để giải mọi bài toán trong NP

52.

Bài toán A được gọi là NPC nếu:

a)

A là bài toán trong NP, mọi bài toán trong NP đều có thể dẫn về được A

b)

A là bài toán trong NP, tồn tại bài toán trong NP dẫn về được A

c)

A là bài toán quyết định và A không là bài toán trong NP, mọi bài toán trong NP đều có thể dẫn về được A

d)

A là bài toán quyết định và A là bài toán trong NP, mọi bài toán trong NP đều có thể dẫn về được A

53.

Lớp NP-Hard bao gồm những bài toán nào:

a)

Những bài toán có thể giải quyết trong thời gian đa thức

b)

Những bài toán có thể kiểm định nghiệm trong thời gian đa thức

c)

Những bài toán mà tất cả các bài toán trong NP có thể quy dẫn đến chúng

d)

Những bài toán không thể giải quyết trong thời gian đa thức

54.

Nếu một bài toán thuộc lớp NPC, thì điều gì đúng?

a)

Nó thuộc lớp NP và mọi bài toán trong NP có thể quy dẫn đến nó

b)

Nó không thuộc lớp NP

c)

Nó không thể giải quyết được

d)

Nó thuộc lớp NP-Hard nhưng không thuộc NP

55.

Bài toán mà đầu ra chỉ có thể là “Yes” hoặc “No” (Đúng/sai, chấp nhận/từ chối) được gọi là:

a)

Bài toán liệt kê

b)

Bài toán đếm

c)

Bài toán tối ưu

d)

Bài toán quyết định

56.

Nếu bài toán A là NP-Hard, điều gì đúng?

a)

A thuộc lớp P

b)

A không thể thuộc NP

c)

Bài toán trong NP có thể quy dẫn đến bài toán A

d)

A có thể giải quyết trong thời gian đa thức

57.

Cho 1 ba lô có trọng lượng là B, n đồ vật có trọng lượng a1,a2,…,an. Bài toán xếp Ba lô 0-1 (KNAPSACK) cần xác định tập chỉ số T ⊂ {1,2,…,n} sao cho:

a)

∑_{i∈T} ai <= B

b)

∑_{i∈T} ai > B

c)

∑_{i∈T} ai < B

d)

∑_{i∈T} ai = B

58.

Cho 1 ba lô có trọng lượng là B, n đồ vật có trọng lượng a1,a2,…,an, giá trị tương ứng của các đồ vật là: p1, p2,…,pn. Bài toán xếp Ba lô mở rộng cần xác định tập chỉ số T ⊂ {1,2,…,n} sao cho:

a)

∑_{i∈T} ai < B và ∑_{i∈T} pi đạt giá trị min

b)

∑_{i∈T} ai = B và ∑_{i∈T} pi đạt giá trị max

c)

∑_{i∈T} ai = B và ∑_{i∈T} pi đạt giá trị min

d)

∑_{i∈T} ai <= B và ∑_{i∈T} pi đạt giá trị max

59.

Cho 1 ba lô có trọng lượng là B, n đồ vật có trọng lượng a1,a2,…,an, giá trị tương ứng của các đồ vật là: p1, p2,…,pn. Số lượng mỗi loại đồ vật là không hạn chế; xi (nguyên dương) là số lượng loại đồ vật thứ i (i=1..n). Bài toán xếp Ba lô giá trị nguyên cần xác định nhóm đồ vật thỏa mãn:

a)

∑i=1naixi\sum_{i=1}^{n} a_i x_i < B và ∑i=1npixi\sum_{i=1}^{n} p_i x_i đạt giá trị max

b)

∑i=1naixi=B\sum_{i=1}^{n} a_i x_i = B và ∑i=1npixi\sum_{i=1}^{n} p_i x_i đạt giá trị min

c)

∑i=1naixi≤B\sum_{i=1}^{n} a_i x_i \leq B và ∑i=1npixiđạtgiaˊtrịmax\sum_{i=1}^{n} p_i x_i đạt giá trị max

d)

∑i=1naixi=B\sum_{i=1}^{n} a_i x_i = B và ∑i=1npixi\sum_{i=1}^{n} p_i x_i đạt giá trị max

60.

Bài toán 3-SAT được phát biểu:

a)

Cho một công thức CNF, hỏi rằng có tồn tại một bộ giá trị của các biến sao cho biểu thức nhận giá trị TRUE hay không?

b)

Cho một công thức CNF, hỏi rằng có tồn tại một bộ giá trị của các biến sao cho biểu thức nhận giá trị FALSE hay không?

c)

Cho một công thức 3-CNF, hỏi rằng có tồn tại một bộ giá trị của các biến sao cho biểu thức nhận giá trị TRUE hay không?

d)

Cho một công thức 3-CNF, hỏi rằng có tồn tại một bộ giá trị của các biến sao cho biểu thức nhận giá trị FALSE hay không?

61.

Cho A, B, C là các bài toán. Nếu A dẫn về được B và B dẫn về được C thì

a)

B dẫn về được A

b)

A dẫn về được C

c)

C dẫn về được A

d)

C không dẫn về được B

62.

Khi bài toán A “dẫn về được” bài toán B sau thời gian đa thức,  được hiểu là:

a)

Bài toán B “khó bằng” bài toán A

b)

Bài toán B “khó hơn” bài toán A

c)

Bài toán A “khó bằng” bài toán B

d)

Bài toán A “khó hơn” bài toán B

63.

Để chứng minh bài toán B là NPC cần thực hiện:

a)

1.Chứng minh B thuộc NP;

2.Tìm bài toán A thuộc N;

3. Chứng minh bài toán A quy dẫn về bài toán B

b)

1.Chứng minh B thuộc NP;

 2.Tìm bài toán A thuộc NP;

3. Chứng minh bài toán A quy dẫn về bài toán B

c)

1.Chứng minh B thuộc NP;

2.Tìm bài toán A thuộc NP-Hard;

3. Chứng minh bài toán B quy dẫn về bài toán A

d)

1.Chứng minh B thuộc NP;

2.Tìm bài toán A thuộc NPC;

3. Chứng minh bài toán A quy dẫn về bài toán B

64.

Bài toán nào sau đây thuộc lớp NP nhưng không phải NPC:

a)

Bài toán TSP

b)

Bài toán tập phủ đỉnh tối ưu

c)

Bài toán Tối ưu hóa tuyến tính

d)

Bài toán xác định chu trình Hamiltonian

65.

Bài toán TSP (người du lịch) thuộc lớp nào:

a)

NPC

b)

NP-Hard

c)

P

d)

NP

66.

Bài toán  tìm chu trình Hamilton thuộc lớp nào

a)

P

b)

NP

c)

NP-Hard

d)

NPC

67.

Nếu bài toán A có thể quy dẫn đến bài toán B, và bài toán B thuộc lớp NPC, điều gì đúng:

a)

Bài toán A thuộc lớp NPC

b)

Bài toán A không thuộc lớp NP

c)

Bài toán A thuộc lớp NP-Hard

d)

Bài toán A không thể giải quyết được

68.

Bài toán nào sau đây là NPC và được gọi là “ bài toán khó dễ nhất”:

a)

Bài toán 3- SAT

b)

Bài toán phủ đỉnh

c)

Bài toán xác định chu trình Hamilton

d)

Bài toán phân hoạch

69.

Bài toán Max-Cut thuộc lớp bài toán nào:

a)

NPC

b)

NP-Hard

c)

P

d)

NP

70.

Bài toán phủ đỉnh(Vertex Cover- VC) thuộc lớp bài toán nào:

a)

NPC

b)

NP-Hard

c)

P

d)

NP

71.

Bài toán 3-SAT thuộc lớp bài toán nào:

a)

P

b)
NP-hard
c)

NP

d)

NPC

72.

Bài toán về bè lớn nhất của đồ thị (MaxClique) thuộc lớp bài toán nào:

a)

P

b)

NP

c)

NP-Hard

d)

NPC

73.

Bài toán tô màu đồ thị thuộc lớp bài toán nào:

a)

P

b)

NP

c)

NPC

d)

NP-Hard

74.

Bài toán lập lịch thuộc lớp bài toán nào

a)

NP

b)

P

c)

NPC

d)

NP-Hard

75.

Bài toán Ba lô giá trị nguyên thuộc lớp bài toán nào:

a)

NP

b)

P

c)

NPC

d)

NP-Hard

76.

Đặc điểm của bài toán thuộc lớp NPC là

a)

Không thuộc lớp NP

b)

Là bài toán quyết định

c)

Không thể kiểm định lời giải trong thời gian đa thức

d)

Mọi bài toán trong NP có thể quy dẫn đến nó

77.

Khẳng định nào sau đây là đúng về lớp NP-Hard:

(Chọn 2 phương án đúng)

a)

Là lớp con của NPC

b)

Bao gồm các bài toán mà mọi bài toán NP đều quy dẫn đến

c)

Có thể bao gồm cả bài toán tối ưu

d)

Không chứa các bài toán quyết định

78.

Điều kiện nào cần thỏa mãn để một bài toán được xem là NPC:

a)

Thuộc lớp NP

b)

Có thể kiểm định nghiệm trong thời gian tuyến tính

c)

Không cần là bài toán quyết định

d)

Mọi bài toán NP quy dẫn về nó

79.

Để quy dẫn từ bài toán SAT sang bài toán Max-Cut, cần:

a)

Dùng mô hình Hamilton

b)

Mã hóa ràng buộc logic bằng trọng số cạnh

c)

Biểu diễn biến logic thành đỉnh và cạnh của đồ thị

d)

Tìm đường đi Euler

80.

Trong phép quy dẫn từ KNAPSACK sang PHẠT, điều nào sau đây là đúng khi xét mối liên hệ giữa ba lô và lịch trình?

a)

Mỗi đồ vật được xử lý tại thời điểm cụ thể

b)

Trọng lượng tối đa của balo tương đương với hạn định hoàn thành

c)

Mỗi công việc tương ứng với một điểm phạt ứng với trọng lượng

d)

Trọng lượng balo được ánh xạ thành tổng thời gian xử lý cho phép

81.

Một bài toán được gọi là NP-Hard khi:

a)

Có thuật toán không đơn định giải trong thời gian đa thức

b)

Có thể được giải trong thời gian đa thức

c)

Nếu có thuật toán đa thức giải nó thì mọi bài toán trong NP cũng giải được

d)

Nếu có thuật toán đa thức giải nó thì mọi bài toán trong NP cũng giải được

D. Mọi bài toán trong NP có thể quy dẫn đến nó

82.

Chứng minh bài toán PHẬT là NPC dựa trên bài toán nào:

a)

TSP

b)

KNAPSACK

c)

Max-Cut

d)

CIRCUIT-SAT

83.

Trong các bước sau, bước nào không đúng khi chứng minh bài toán là NPC?

a)

Tìm một bài toán trong lớp P để quy dẫn

b)

Quy dẫn bài toán đang xét về bài toán đã biết

c)

Chứng minh bài toán thuộc NP

d)

Dùng bài toán đã biết là NPC để quy dẫn về bài toán đang xét

84.

Để chứng minh một bài toán là NPC, ta cần:

a)

Chứng minh nó có lời giải duy nhất

b)

Tìm một bài toán NPC có thể quy dẫn về nó

c)

Chứng minh bài toán đó thuộc NP

d)

Chứng minh mọi bài toán P đều quy dẫn về nó

85.

Bài toán nào sau đây thuộc NPC:

a)

Phân hoạch tập (Partition)

b)

Nhân hai số nguyên lớn

c)

3-SAT

d)

Tìm kiếm tuyến tính

86.

Kỹ thuật chia để trị hoạt động bằng cách:

a)

Chia nhỏ một bài toán phức tạp thành các bài toán con nhỏ hơn, sau đó kết hợp các bài toán con để có được lời giải cho bài toán ban đầu.

b)

Chia nhỏ một bài toán phức tạp thành các bài toán con nhỏ hơn, giải quyết từng bài toán con một cách độc lập để có được lời giải cho bài toán ban đầu.

c)

Chia nhỏ một bài toán phức tạp thành các bài toán con độc lập, sau đó kết hợp để có được lời giải cho bài toán ban đầu.

d)

Chia nhỏ một bài toán phức tạp thành các bài toán con nhỏ hơn, giải quyết từng bài toán con một cách độc lập, sau đó tổng hợp các kết quả lại để có được lời giải cho bài toán ban đầu.

87.

Các bước chính trong kỹ thuật "Chia để trị" gồm:

a)

1. Chia nhỏ 2. Giải quyết 3. Tổng hợp

b)

1. Chia đôi; 2. Giải quyết ;3. Tổng hợp

c)

1. Chia đôi; 2. Tổng hợp ;3. Giải quyết

d)

1. Chia nhỏ ;2. Tổng hợp ;3. Giải quyết

88.

Bước chia nhỏ trong kỹ thuật chia để trị có ý nghĩa là:

a)

Bài toán A ban đầu được chia thành nhiều bài toán con, mỗi bài toán con có kích thước bằng kích thước của bài toán A.

b)

Bài toán A ban đầu được chia thành nhiều bài toán con, mỗi bài toán con có kích thước lớn hơn bài toán A

c)

Bài toán A ban đầu được chia thành nhiều bài toán con nhỏ hơn, độc lập với nhau, có cấu trúc tương tự như bài toán ban đầu nhưng với kích thước nhỏ hơn.

d)

Bài toán A ban đầu được chia thành nhiều bài toán con nhỏ hơn, độc lập với nhau, có cấu trúc tương tự như bài toán ban đầu nhưng với kích thước lớn hơn.

89.

Bước giải quyết trong kỹ thuật chia để trị có ý nghĩa là:

a)

Mỗi bài toán con được giải quyết độc lập. Nếu bài toán con đủ nhỏ, nó sẽ được giải trực tiếp; nếu không, lại tiếp tục áp dụng phương pháp chia để trị cho bài toán con này.

b)

Mỗi bài toán con được giải quyết độc lập. Nếu bài toán con đủ lớn nó sẽ được giải bằng phương pháp chia để trị.

c)

Mỗi bài toán con được giải quyết không độc lập, nếu không giải được thì lại tiếp tục dùng phương pháp chia để trị cho bài toán con này.

d)

Mỗi bài toán con được giải quyết độc lập. Nếu bài toán con có kích thước lớn thì lại tiếp tục dùng phương pháp chia để trị cho bài toán con này.

90.

Bước tổng hợp trong kỹ thuật chia để trị có ý nghĩa là:

a)

Tổng hợp các bài toán con để có được bài toán ban đầu

b)

Tổng hợp một lời giải của các bài toán con để có được bài toán ban đầu

c)

Tổng hợp các lời giải của các bài toán con để có được lời giải cho bài toán ban đầu

d)

Tổng hợp các lời giải của các bài toán con để có được mô hình phát biểu của bài toán ban đầu

91.

Kỹ thuật chia để trị được thiết kế theo kiểu: 

a)

Từ trên xuống (top – down)

b)

Từ dưới lên (bottom – up)

c)

Từ trái sang phải (left – right)

d)

Từ phải sang trái (right – left)

92.

Ý tưởng “chia bài toán cần giải quyết thành các bài toán con cùng dạng, có kích cỡ nhỏ hơn, cứ như vậy lặp lại nhiều lần cho đến khi bài toán thu được đủ đơn giản để có thể giải quyết được trực tiếp. Sau đó, lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu” là của kỹ thuật:

a)

Quay lui

b)

Nhánh cận

c)

Tham lam

d)

Chia để trị

93.

Chia để trị là 1 phương pháp áp dụng cho các bài toán:

a)

Có thể giải quyết bằng cách chia nhỏ bài toán ban đầu ra thành các bài toán con và giải quyết các bài toán con này. Sau đó lời giải của các bài toán con được tổng hợp lại thành lời giải cho bài toán ban đầu.

b)

Có thể giải quyết bằng cách tìm lời giải của các bài toán cùng dạng và tổng hợp lại thành lời giải cho bài toán ban đầu.

c)

Có thể giải quyết bằng cách chia đôi bài toán ban đầu

d)

Có thể giải quyết bằng cách chia ba bài toán ban đầu

94.

Việc tổng hợp lời giải của các bài toán con để nhận được lời giải cho bài toán cần giải quyết trong kỹ thuật “chia để trị” có thể không cần thực hiện, trong trường hợp:

a)

Bài toán ban đầu đã được phân chia hết

b)

Các bài toán con nhận được không cần phân chia nữa

c)

Các bài toán cơ sở đã được giải hết

d)

. Quá trình phân chia bài toán ban đầu thành các bài toán cơ sở đã chứa đựng việc tổng hợp kết quả. Khi giải xong các bài toán cơ sở thì bài toán ban đầu cũng đã được giải quyết.

95.

Với thuật toán Mergesort  khi sử dụng kỹ thuật “chia để trị”  quá trình phân chia thể hiện:

a)

Chia đôi một danh sách, cho đến khi danh sách chỉ còn một nửa số phần tử

b)

Chia đôi một danh sách, cho đến khi danh sách chỉ còn một phần tư số phần tử

c)

Chia đôi một danh sách, cho đến khi danh sách chỉ còn hai phần tử

d)

Chia đôi một danh sách, cho đến khi danh sách chỉ còn một phần tử

96.

Với thuật toán Mergesort  khi sử dụng kỹ thuật “chia để trị” , bài toán cơ sở có dạng:

a)

Sắp xếp một danh sách có độ dài bằng 1

b)

Sắp xếp một danh sách có độ dài bằng 2

c)

Sắp xếp một danh sách có độ dài bằng một nửa danh sách ban đầu

d)

Sắp xếp một danh sách có độ dài bằng một phần tư danh sách ban đầu

97.

Với thuật toán Mergesort  khi sử dụng kỹ thuật “chia để trị” , việc tổng hợp kết quả là :

a)

“trộn” 2 danh sách đã có thứ tự để được một danh sách không có thứ tự.

b)

“trộn” 2 danh sách đã có thứ tự để được một danh sách có thứ tự.

c)

“trộn” 2 danh sách chưa có thứ tự để được một danh sách có thứ tự.

d)

“trộn” 2 danh sách chưa có thứ tự để được một danh sách chưa có thứ tự.

98.

Bài toán con trong quá trình phân chia của kỹ thuật “chia để trị”  là:

a)

Không cùng dạng với bài toán ban đầu và có kích cỡ là nhỏ hơn

b)

Có cùng dạng với bài toán ban đầu và có kích cỡ là lớn hơn

c)

Không cùng dạng với bài toán ban đầu và có kích cỡ là lớn hơn

d)

Có cùng dạng với bài toán ban đầu và có kích cỡ là nhỏ hơn

99.

Kỹ thuật “chia để trị”  thường dẫn đến một thuật toán:

a)

Đệ quy

b)

Quay lui

c)

Liệt kê

d)

Tối ưu

100.

Lược đồ chung của kỹ thuật chia để trị :

a)

void DivideConquer(A,x); {Tìm nghiệm x của bài toán A}{ If A đủ nhỏ then Giải bài toán A;Else { Chia A thành các bài toán con A1, A2,…,Am; for (i=1; i =m; i++) DivideConquer(Ai,xi); Kết hợp các nghiệm xi (i = 1, 2, …, m) của các bài toán con Ai để nhận được nghiệm x của bài toán A; }}

b)

void DivideConquer(A,x); {Tìm nghiệm x của bài toán A}{ If A đủ nhỏ then Giải bài toán A;Else { Chia A thành các bài toán con A1, A2,…,Am; for (i=1; i =m; i++) DivideConquer(Ai,xi); Kết hợp các bài toán con Ai để nhận được bài toán A; }}

c)

void DivideConquer(A,x); {Tìm nghiệm x của bài toán A} { Chia A thành các bài toán con A1, A2,…,Am; for (i=1; i =m; i++) Kết hợp các bài toán con Ai để nhận được bài toán A; }

d)

void DivideConquer(A,x); {Tìm nghiệm x của bài toán A} { Chia A thành các bài toán con A1, A2,…,Am; for (i=1; i =m; i++) DivideConquer(Ai,xi); Kết hợp các nghiệm xi (i = 1, 2, …, m) của các bài toán con Ai để nhận được nghiệm x của bài toán A;}

101.

Tư tưởng chính của kỹ thuật chia để trị là:

a)

Chia bài toán đã cho thành một số bài toán con có kích thước nhỏ hơn. Giải các bài toán con (kích thước giảm đến trường hợp tầm thường được gọi là bài toán cơ sở). Tổng hợp (kết hợp) các bài toán con để nhận bài toán ban đầu.

b)

Chia bài toán đã cho thành một số bài toán con có kích thước nhỏ hơn. Giải các bài toán con (kích thước giảm đến trường hợp tầm thường được gọi là bài toán cơ sở). Tổng hợp (kết hợp) kết quả của các bài toán con để nhận được lời giải cho bài toán ban đầu.

c)

Chia bài toán đã cho thành một số bài toán cơ sở. Giải các bài toán cơ sở (kích thước giảm đến trường hợp tầm thường). Tổng hợp (kết hợp) các bài toán cơ sở để nhận được bài toán ban đầu.

d)

Chia bài toán đã cho thành một số bài toán cơ sở. Giải các bài toán cơ sở (kích thước giảm đến trường hợp tầm thường). Tổng hợp (kết hợp) kết quả của các bài toán cơ sở để nhận được bài toán ban đầu.

102.

Với thuật toán Quicksort khi sử dụng kỹ thuật “chia để trị” , bài toán cơ sở có dạng:  

a)

Sắp xếp một danh sách chỉ gồm một phần tử

b)

Sắp xếp một danh sách gồm nhiều phần tử có khóa bằng nhau

c)

Sắp xếp một danh sách chỉ gồm một phần tử hoặc nhiều phần tử có khóa bằng nhau

d)

Sắp xếp một danh sách chỉ gồm một phần tử hoặc nhiều phần tử có khóa không bằng nhau

103.

Với thuật toán Quicksort khi sử dụng kỹ thuật “chia để trị” , ”  quá trình phân chia thể hiện:

a)

Phân chia danh sách thành 2 danh sách con “bên trái” và “bên phải

b)

Sắp xếp hai danh sách “bên trái” và “bên phải” của khóa chốt để được danh sách không có thứ tự

c)

Phân chia danh sách thành 2 danh sách con “bên trái” và “bên phải”, sắp xếp “bên trái” và “bên phải” để được danh sách có thứ tự

d)

Phân chia danh sách thành 2 danh sách con “bên trái” và “bên phải”, trộn “bên trái” và “bên phải” để được danh sách có thứ tự

104.

Với bài toán xếp lịch thi đấu thể thao khi sử dụng kỹ thuật “chia để trị” , bài toán cơ sở có dạng:  

a)

Xếp lịch thi đấu cho 1 cầu thủ

b)

Xếp lịch thi đấu cho 2 cầu thủ

c)

Xếp lịch thi đấu cho 3 cầu thủ

d)

Xếp lịch thi đấu cho 4 cầu thủ

105.

Với bài toán xếp lịch thi đấu thể thao khi sử dụng kỹ thuật “chia để trị” , quá trình phân chia thể hiện:

a)

Để xếp lịch cho n cầu thủ, ta xếp lịch cho 2n cầu thủ

b)

Để xếp lịch cho n cầu thủ, ta xếp lịch cho 2n cầu thủ

c)

Để xếp lịch cho n cầu thủ, ta xếp lịch cho n/4 cầu thủ; để xếp lịch cho n/4 cầu thủ, ta xếp lịch cho 4 cầu thủ, …

d)

Để xếp lịch cho n cầu thủ, ta xếp lịch cho n/2 cầu thủ; để xếp lịch cho n/2 cầu thủ, ta xếp lịch cho n/4 cầu thủ, …

106.

Với bài toán xếp lịch thi đấu thể thao khi sử dụng kỹ thuật “chia để trị” , quá trình tổng hợp lời giải thể hiện:

a)

Từ lịch của 2 cầu thủ xếp lịch thi đấu cho 4 cầu thủ; Từ lịch của 4 cầu thủ xếp lịch thi đấu cho 8 cầu thủ, …

b)

Từ lịch của 2 cầu thủ xếp lịch thi đấu cho 3 cầu thủ; Từ lịch của 3 cầu thủ xếp lịch thi đấu cho 4 cầu thủ, …

c)

Từ lịch của 2 cầu thủ xếp lịch thi đấu cho 3 cầu thủ; Từ lịch của 3 cầu thủ xếp lịch thi đấu cho 6 cầu thủ, …

d)

Từ lịch của 2 cầu thủ xếp lịch thi đấu cho 4 cầu thủ; Từ lịch của 4 cầu thủ xếp lịch thi đấu cho 6 cầu thủ,…

107.

Với bài toán tìm kiếm nhị phân giá trị x trên một dãy đã sắp xếp, quá trình chia để trị được thể hiện:

a)

- Tìm phần tử ở giữa dãy- So sánh x với phần tử ở giữa dãy - Nếu bằng nhau thì trả về vị trí giữa - Nếu x nhỏ hơn thì tìm ở nửa bên trái - Nếu x lớn hơn thì tìm ở nửa bên phải- Trả về giá trị 0 (nếu không tìm thấy)

b)

- Tìm phần tử ở giữa dãy- So sánh x với phần tử ở giữa dãy - Nếu bằng nhau thì trả về vị trí giữa - Nếu x nhỏ hơn thì tìm ở nửa bên phải - Nếu x lớn hơn thì tìm ở nửa bên trái- Trả về giá trị 0 (nếu không tìm thấy)

c)

- Tìm phần tử ở vị trí số 2 của dãy (khóa)- So sánh x với phần tử khóa - Nếu bằng nhau thì trả về vị trí số 2 - Nếu x nhỏ hơn thì tìm ở nửa bên trái - Nếu x lớn hơn thì tìm ở nửa bên phải- Trả về giá trị 0 (nếu không tìm thấy)

d)

- Tìm phần tử ở vị trí số n-1 của dãy (khóa)- So sánh x với phần tử khóa - Nếu bằng nhau thì trả về vị trí số n-1 - Nếu x nhỏ hơn thì tìm ở nửa bên phải - Nếu x lớn hơn thì tìm ở nửa bên trái- Trả về giá trị 0 (nếu không tìm thấy)

108.

Với bài toán tìm kiếm nhị phân giá trị x trên một dãy đã sắp xếp, bài toán cơ sở có dạng:  

a)

Tìm kiếm trong một dãy chỉ gồm một phần tử

b)

Tìm kiếm trong một dãy chỉ gồm hai phần tử

c)

Tìm kiếm trong một dãy có số phần tử còn một nửa

d)

Tìm kiếm trong một dãy có số phần tử còn một phần tư

109.
a)

. Chia nhỏ số mũ n ra cho đến khi n=2

b)

Chia nhỏ số mũ n ra cho đến khi n=1

c)

Chia nhỏ số mũ n ra cho đến khi n=4

d)

Chia nhỏ số mũ n ra cho đến khi n=8

110.
a)

b)

c)

d)

111.

Xét bài toán nhân 2 số nguyên lớn có n chữ số X và Y, công thức để tổng hợp kết quả của bài toán khi sử dụng kỹ thuật chia để trị là:

a)

b)

c)

d)

112.

Xét bài toán nhân 2 số nguyên lớn có n chữ số X và Y, bài toán cơ sở khi sử dụng kỹ thuật chia để trị là:

a)

Nhân các số nguyên có n/2 chữ số

b)

Nhân các số nguyên có n/4 chữ số

c)

Nhân các số nguyên chỉ gồm một chữ số

d)

Nhân các số nguyên gồm có hai chữ số

113.

Xét bài toán tìm giá trị lớn nhất (max) của dãy a có n phần tử số nguyên (n nguyên dương), theo kỹ thuật chia  để trị, tư tưởng chia theo nhị phân được thể hiện:

 

a)

Chia đôi dãy, tìm max1 của nửa đầu dãy, tìm max2 của nửa cuối dãy, sau đó so sánh max1 và max2 để tìm max của dãy.

b)

Chia đôi dãy, tìm max1 của nửa đầu dãy, tìm max2 của nửa cuối dãy, sau đó kết luận max1 là max của dãy.

c)

Chia đôi dãy, tìm max1 của nửa đầu dãy, tìm max2 của nửa cuối dãy, sau đó kết luận max2 là max của dãy.

d)

Chia đôi dãy, tìm max1 của nửa đầu dãy, tìm max2 của nửa cuối dãy, sau đó kết luận giá trị trung bình của max1 và max2 là max của dãy.

114.

Khi giải quyết bài toán Tháp Hà Nội“Cho 3 cột A, B, C. Trên cột A đặt n cái đĩa với kích cỡ khác nhau, theo thứ tự to dần đến nhỏ dần từ dưới lên. Hãy di chuyển n cái đĩa từ cột A sang cột C, sao cho: Mỗi bước chỉ có thể chuyển 1 cái đĩa từ cột này sang cột khác, cái đĩa được nhấc ra phải là cái đĩa ở trên cùng (không được đi chuyển cái đĩa khi có đĩa khác ở trên nó)Khi chuyển đĩa sang một cột thì phải đặt nó ở trên cùng.Không được đặt một cái đĩa to lên trên cái đĩa nhỏ hơn. Tức là một đĩa chỉ có thể được chuyển vào một cột trống hoặc cột đang có đĩa to hơn nó ở trên cùng.”ý tưởng chia để trị :

a)

1. Chuyển n-1 đĩa từ cột A sang cột B;2. Chuyển một đĩa (thứ n) từ cột A sang cột C;3. Chuyển n-1 đĩa từ cột B sang cột C.

b)

1.Chuyển 1 đĩa từ cột A sang cột B;2.Chuyển n-1 đĩa từ cột A sang cột C;3.Chuyển n-1 đĩa từ cột B sang cột C.

c)

1.Chuyển 2 đĩa từ cột A sang cột B;2.Chuyển n-1 đĩa từ cột A sang cột C;3.Chuyển n-1 đĩa từ cột B sang cột C.

d)

1.Chuyển n-1 đĩa từ cột A sang cột C;2.Chuyển 1 đĩa từ cột A sang cột C;3.Chuyển n-1 đĩa từ cột C sang cột B.

115.

Xét bài toán tìm giá trị lớn nhất (max) của dãy a có n phần tử số nguyên (n nguyên dương), theo kỹ thuật chia  để trị, bài toán cơ sở là:

a)

Tìm giá trị lớn nhất (max) của dãy a có một phần tử số nguyên

b)

Tìm giá trị lớn nhất (max) của dãy a có hai phần tử số nguyên

c)

Tìm giá trị lớn nhất (max) của dãy a có n/2 phần tử số nguyên

d)

Tìm giá trị lớn nhất (max) của dãy a có n/4 phần tử số nguyên

116.

Thuật toán đơn định có đặc điểm nào sau đây? (Chọn 2 phương án đúng)

a)

Có thể cho nhiều kết quả với cùng đầu vào

b)

Luôn kết thúc sau số bước xác địn

c)

Có độ phức tạp không xác định

d)

Luôn chọn một hành động duy nhất tại mỗi bước

117.

Trong một thuật toán không đơn định, điều nào đúng? (Chọn 2 phương án đúng)

a)

Có nhiều hướng đi tiếp tại mỗi bước

b)

Luôn có lời giải duy nhất

c)

Có thể "thử" các khả năng khác nhau cùng lúc

d)

Không bao giờ đưa ra kết quả sai

118.

Ví dụ nào thuộc lớp NP nhưng chưa biết có nằm trong P hay không? (Chọn 2 phương án đúng)

a)

Tô màu đồ thị

b)

Tìm phần tử lớn nhất

c)

Phân hoạch tập số

d)

Tìm kiếm nhị phân

119.

Bài toán nào sau đây là ví dụ của bài toán NPC? (Chọn 2 phương án đúng)

a)

Bài toán phủ đỉnh

b)

Tìm đường đi Hamilton

c)

Sắp xếp chèn

d)

Bài toán Nhân ma trận

120.

Một bài toán A thuộc lớp NP và mọi bài toán trong lớp NP đều có thể quy dẫn về A trong thời gian đa thức thì: (Chọn 2 phương án đúng)

a)

Bài toán thuộc lớp NP-Hard

b)

Bài toán có thể giải được trong thời gian tuyến tính

c)

Bài toán thuộc lớp NP

d)

Bài toán không thể là bài toán tối ưu

121.

Chọn 2 phương án đúng nói về việc sử dụng đệ quy trong bài toán Fibonacci

a)

Hàm tính Fibonacci có hai lời gọi đệ quy

b)

Fibonacci không thể tính bằng vòng lặp

c)

Dãy Fibonacci là ví dụ kinh điển của thuật toán đệ quy

d)

Tính fibo(5) chỉ gọi một lần đệ quy

122.

Chọn 2 phương án đúng liên quan đến ưu, nhược điểm của đệ quy:

a)

Đệ quy chỉ dùng được khi dữ liệu là số nguyên

b)

Một số bài toán đòi hỏi bắt buộc phải dùng đệ quy

c)

Đệ quy giúp biểu diễn bài toán ngắn gọn hơn

d)

Đệ quy là cách viết khó hơn và ít ứng dụng hơn vòng lặp

123.

Ví dụ nào sau đây là đệ quy đúng trong lập trình? (Chọn 2 phương án đúng)

a)

Một hàm gọi hàm khác

b)

Một hàm gọi chính nó mà không thay đổi tham số

c)

Một hàm dùng vòng lặp for

d)

Một hàm gọi chính nó với tham số giảm dần

124.

Các phần bắt buộc để xây dựng một chương trình con đệ quy là gì?

(Chọn 2 phương án đúng)

a)

Câu lệnh gán → Không bắt buộc.

b)

Lời gọi đệ quy

c)

Sử dụng vòng lặp

d)

Điều kiện dừng

125.

Trong định lý Cook, Bài toán nào được chứng minh đầu tiên là NPC:

(Chọn 2 phương án đúng)

a)

CIRCUIT-SAT

b)

3-SAT

c)

TSP

d)

Partition

126.

Chọn 2 phương án đúng về việc lặp và sử dụng phương trình đệ quy.

a)

Để tính độ phức tạp thuật toán đệ quy, cần lập phương trình đệ quy.

b)

T(n)=T(n−1)+C có độ phức tạp O(n).

c)

T(n)=T(n)+1 là phương trình đúng (Đây là một phương trình sai về mặt toán học).

d)

T(n)=T(n−1)−C là công thức phổ biến (Phương trình đệ quy thường thể hiện sự tăng trưởng, không phải giảm).

 

127.

Chọn hai phương án đúng về quan hệ giữa các lớp bài toán P và NP.

a)

Nếu P = NP thì tất cả các bài toán NP đều giải được bằng thuật toán đơn định trong thời gian đa thức.

b)

Một số bài toán có thể kiểm tra nghiệm nhanh nhưng tìm nghiệm thì rất khó.

c)

Nếu một bài toán có độ phức tạp O(2n) thì chắc chắn thuộc lớp P

d)

Lớp NP chỉ chứa các bài toán dễ

128.

Chọn 2 phương án đúng liên quan đến hàm đệ quy uscIn(a, b).

a)

Đệ quy không được sử dụng trong các phép chia

b)

Hàm uscIn(a, b) sẽ chạy vô hạn nếu b luôn khác 0

c)

Phép gọi uscIn(b, a % b) là phần đệ quy

d)

Hàm uscIn(a, b) có phần cơ sở là khi b == 0

129.

Phương trình đệ quy nào có thể được phân tích bằng định lý Master?

a)

T(n) = T(n-1) + n

b)

T(n) = 4T(n/3) + n²

c)

T(n) = 2T(n-1) + 1

d)

T(n) = 3T(n/2) + n

130.

Ví dụ điển hình về quy dẫn từ bài toán SAT là?

a)

Từ HC sang TSP

b)

Từ TSP sang HC

c)

Từ SAT sang 3-SAT

d)

Từ P sang NP

131.

Trong thuật toán Quicksort, phần tử “chốt” (pivot) được dùng để làm gì?

a)

So sánh các phần tử với phần tử “chốt” để phân hoạch mảng

b)

Sử dụng để phân hoạch mảng

c)

Dùng để lưu trữ giá trị lớn nhất

d)

Dùng để kết thúc đệ quy

132.

Trong mô hình nhân số nguyên cải tiến (thuật toán Strassen), mục đích chính là gì?

a)

Giảm số phép nhân từ 4 còn 3

b)

Giảm số phép cộng từ 5 còn 2

c)

Giảm độ phức tạp từ O(n²) xuống O(n^1.59)

d)

Loại bỏ phép chia

133.

Trong bài toán Tháp Hà Nội, để di chuyển n đĩa từ cọc nguồn sang cọc đích, ta cần:

a)

Dùng đệ quy chuyển từng đĩa

b)

Chuyển tất cả đĩa cùng lúc

c)

Dùng thuật toán quay lui

d)

Di chuyển n-1 đĩa sang cọc phụ trước

134.

Trong thuật toán Mergesort, các bước chính là gì?

a)

Gọi đệ quy sắp xếp từng nửa

b)

Chia mảng thành hai nửa

c)

Tìm phần tử chốt để phân hoạch

d)

Trộn hai nửa lại với nhau

135.

Các bước cơ bản của kỹ thuật chia để trị bao gồm:

a)

Chia nhỏ – Giải quyết – Tổng hợp (kết hợp)

b)

Tìm kiếm và duyệt toàn bộ

c)

Phân tích và tổng hợp

d)

Xử lý đồng thời và lưu trữ

136.

Khi nào việc áp dụng kỹ thuật chia để trị hiệu quả nhất?

a)

Khi bài toán có nhiều vòng lặp lồng nhau

b)

Khi các bài toán con có thể giải đồng thời

c)

Khi bài toán có thể phân tách thành các bài toán con độc lập

d)

Khi cần giảm độ phức tạp bằng phương pháp vét cạn

137.

Bài toán Tháp Hà Nội sử dụng chia để trị bằng cách:
(Chọn 2 phương án đúng)

a)

Dùng đệ quy chuyển từng đĩa

b)

Dùng vòng lặp chính xác

c)

Không có bước tổng hợp

d)

Di chuyển n-1 đĩa sang cọc phụ

Similar Resources on Wayground

PTMĐ - C2

141 questions

PTMĐ - C2

quiz

Worksheet

•

University

Trắc nghiệm CS 226

133 questions

Trắc nghiệm CS 226

quiz

Worksheet

•

University

IU01-cb

135 questions

IU01-cb

quiz

Worksheet

•

University