wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

Câu hỏi về Thuật toán

Total questions: 84

Worksheet time: 44mins

Name
Class
Date
1.

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

a)

A.

b)

B.

c)

C.

d)

D.

2.

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

a)

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)

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

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)

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

3.

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

a)

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

b)

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

c)

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

d)

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)

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)

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)

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

d)

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)

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

b)

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)

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

d)

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)

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

b)

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. Có thể giải được bằng thuật toán đơn định trong thời gian hàm mũ

d)

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.

Câu 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.

Câu 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 n giai thừa

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.

Câu 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.

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

a)

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

b)

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

c)

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

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ính số lượng ước của một số nguyên dương N:

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ũ

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):

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ũ

14.

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

a)

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

b)

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

c)

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 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 chưa chắc là trên đ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" Có 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 (Chọn 2 phương án đúng nhất)

a)

Độ phức tạp đa thức có dạng O(n^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.

Phương pháp nào thường dùng để giải bài toán NP trong thực tế? (Chọn 2 phương án đúng nhấ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

37.

Ví dụ nào sau đây thuộc lớp P với độ phức tạp O(n²)? (Chọn 2 phương án đúng nhất)

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

38.

Thuật toán không đơn định có đặc điểm nào?

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

39.

Bài toán thuộc lớp P có tính chất nào?

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

40.

Trong một thuật toán không đơn định, điều nào đúng?

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

41.

Bài toán lớp P thỏa mãn điều kiện nào?

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!)

42.

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

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ế

43.

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

44.

Chọn hai phương án đúng liên quan đến lớp bài toán P
(Sinh viên chọn 2 phương án đúng nhất)

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.

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 kiếm nhị phân

b)

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

c)

phân hoạch tập số

d)

tô màu đồ thị

46.

Đặc điểm nhận biết bài toán thuộc lớp NP là:
(Chọn 2 phương án đúng)

a)

có thuật toán đơn định giải trong thời gian tuyến tính

b)

Có thể tìm được lời giải bằng thuật toán logarit

c)

có thể kiểm tra nghiệm trong thời gian đa thức.

d)

được giải quyết bởi các phương pháp xấp xỉ

47.

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.

48.

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

49.

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

50.

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

51.

Câu 5: 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

52.

Câu 6: 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

53.

Câu 7: 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

54.

Câu 8: 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

55.

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

56.

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

57.

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

58.

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?

59.

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)

C dẫn về được B

c)

C dẫn về được A

d)

A dẫn về được C

60.

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

61.

Để 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

62.

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

63.

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

64.

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

65.

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

66.

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

67.

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

68.

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

69.

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

a)

P

b)

NP

c)

NP-Hard

d)

NPC

70.

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

71.

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

72.

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

73.

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

74.

Đặ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ó

75.

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

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

76.

Đ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ó

77.

Để 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

78.

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

79.

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)

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

80.

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

81.

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

82.

Để 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ó

83.

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

84.

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

a)

từ TSP sang HC

b)

từ HC sang TSP

c)

từ P sang NP

d)

từ SAT sang 3 SAT

Similar Resources on Wayground

Vi mô nâng cao

88 questions

Vi mô nâng cao

quiz

Worksheet

•

University

Thuật ngữ chuyên ngành Logisitcs

79 questions

Thuật ngữ chuyên ngành Logisitcs

quiz

Worksheet

•

University

Quiz về Quản Trị

80 questions

Quiz về Quản Trị

quiz

Worksheet

•

University

HoanXinggg

82 questions

HoanXinggg

quiz

Worksheet

•

University

Câu hỏi về Marketing Số

89 questions

Câu hỏi về Marketing Số

quiz

Worksheet

•

University

Trắc nghiệm Quản lý dự án phần mềm

80 questions

Trắc nghiệm Quản lý dự án phần mềm

quiz

Worksheet

•

University

Câu Hỏi Thi Trắc Nghiệm Máy Tính

82 questions

Câu Hỏi Thi Trắc Nghiệm Máy Tính

quiz

Worksheet

•

University