wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

PTTT 3

Total questions: 72

Worksheet time: 36mins

Name
Class
Date
1.

Một thuật toán được gọi là đệ quy nếu

a)

A. nó giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn một nửa

b)

B. nó giải quyết bài toán bằng cách rút gọn liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ hơn

c)

C. nó giải quyết bài toán bằng cách dùng bài toán ban đầu nhưng có dữ liệu đầu vào nhỏ hơn một nửa

d)

D. nó giải quyết bài toán bằng cách dùng bài toán ban đầu nhưng có dữ liệu đầu vào nhỏ hơn

2.

Một khái niệm X gọi là định nghĩa theo đệ quy nếu

a)

trong định nghĩa X không sử dụng khái niệm X

b)

trong định nghĩa X có sử dụng 2 lần khái niệm X

c)

trong định nghĩa X có sử dụng 2 lần trở lên khái niệm X

d)

trong định nghĩa X có sử dụng ngay chính khái niệm X

3.

Phần cơ sở của thuật toán đệ qui bao gồm

a)

các trường hợp dừng mà có thể trực tiếp giải quyết được ngay

b)

các trường hợp chưa dừng nhưng có thể trực tiếp giải quyết được

c)

các trường hợp dừng nhưng chưa thể trực tiếp giải quyết được

d)

các trường hợp chưa dừng lại mà có thể giải quyết trong trường hợp đặc biệt

4.

Một chương trình con P (hàm hoặc thủ tục) được gọi là đệ quy nếu

a)

trong quá trình thực hiện P phải gọi đến P hai lần

b)

trong quá trình thực hiện P phải gọi đến P hai lần trở lên

c)

trong quá trình thực hiện P không cần phải gọi đến P

d)

trong quá trình thực hiện P có phần phải gọi đến chính P

5.

Cấu trúc chính của một chương trình con đệ quy gồm

a)

Phần không cơ sở và phần đệ quy

b)

Phần cơ sở và phần đệ quy

c)

Phần cơ sở và phần không có đệ quy

d)

Phần không cơ sở và phần không đệ quy

6.

Dạng tổng quát của một phương trình đệ qui có dạng: T(n) C(n) F(T(k)) + d(n)
( chọn 2 đáp án)

a)

1.C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui đúng 2.F(T(k)) là một đa thức của các T(k) 3.d(n): là thời gian để tổng hợp các kết quả

b)

1.C(n): là thời gian thực hiện chương trình 2.F(T(k)) là một đa thức của các T(k) 3.d(n): là thời gian để phân chia bài toán

c)

1.C(n): là thời gian thực hiện chương trình 2.F(T(k)) là một đa thức của các T(k) 3.d(n): là thời gian để tổng hợp các kết quả

d)

1.C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui dừng 

    2.F(T(k)) là một đa thức của các T(k) 

    3.d(n): là thời gian để phân chia bài toán và tổng hợp các kết quả 

7.

Đặc điểm của chương trình con đệ qui

a)

1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán được thu nhỏ đi một nửa 3. Có một trường hợp đặc biệt, là trường hợp dừng của thuật toán và gọi đệ qui cũng kết thúc

b)

1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước 3. Có một trường hợp đặc biệt, là trường hợp dừng của thuật toán và gọi đệ qui cũng kết thúc

c)

1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước 3. Có một trường hợp đặc biệt và gọi đệ qui được tiếp tục

d)

1. Trong chương trình con đệ qui có lời gọi đến chính nó 2. Mỗi lần có lời gọi thì kích thước của bài toán được thu nhỏ đi một nửa 3. Có một trường hợp đặc biệt và gọi đệ qui được tiếp tục

8.

(Trắc nghiệm về công thức C(n), F(T(k)), d(n))

a)

C(n): là thời gian thực hiện chương trình; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để phân chia bài toán

b)

C(n): là thời gian thực hiện chương trình; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để tổng hợp các kết quả

c)

C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui dừng; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để tổng hợp các kết quả

d)

C(n): là thời gian thực hiện chương trình ứng với trường hợp đệ qui dừng; F(T(k)) là một đa thức của các T(k); d(n): là thời gian để phân chia bài toán và tổng hợp các kết quả

9.

Hàm đệ quy dưới đây tính: int facto(int n) { if (n == 0) return 1; else return n * facto(n-1); }

a)

Tổng các số từ 1 đến n

b)

Trung bình cộng của các số từ 1 đến n

c)

Giai thừa của n

d)

Bình phương của n

10.

Cho Hàm đệ quy int fibo(int n) { if (n <= 2) return 1; else return fibo(n-1) + fibo(n-2); } giá trị của fibo(5) được tính bằng:

a)

3

b)

5

c)

8

d)

13

11.

Cho Hàm đệ quy int US(int a, int b) { if (b == 0) return a; else return US(b, a % b); } giá trị của US(28,20) được tính bằng:

a)

2

b)

4

c)

6

d)

8

12.

Cho Hàm đệ quy int power(int n) { if (n == 0) return 1; else return 2*power(n-1); } giá trị của power (3) được tính bằng:

a)

6

b)

8

c)

12

d)

16

13.

Cho hàm đệ qui int sum(int n) { if (n == 0) return 0; else return n * n + sum(n - 1); } gọi hàm sum(3) trả về giá trị:

a)

A. 14

b)

B. 20

c)

C. 30

d)

D. 16

14.

Giá trị của power(2, 3) với đoạn chương trình sau, được tính bằng: int power(int base, int exp) { if (exp == 0) return 1; else return base * power(base, exp-1); }

a)

A. 8

b)

B. 6

c)

C. 4

d)

D. 2

15.

Giá trị của sum(4) với đoạn mã dưới đây được tính bằng

a)

A. 4

b)

B. 6

c)

C. 10

d)

D. 16

16.

Hàm đệ quy dưới đây tính gì? int sum(int n) { if (n == 0) return 0; else return n + sum(n - 1); }

a)

Tổng các số từ 1 đến n

b)

Tổng các số từ 1 đến n - 1

c)

Tích các số từ 1 đến n

d)

Lũy thừa của n

17.

Hàm đệ quy dưới đây thực hiện chức năng gì

int US(int a, int b) { 

     if (b == 0) return a; 

     else return US(b, a % b); 

} 

a)

Tính tổng của a và b

b)

Tính hiệu của a và b

c)

Tìm ước chung lớn nhất của a và b

d)

Tìm bội chung nhỏ nhất của a và b

18.

Hàm đệ quy sau thực hiện chức năng gì? int countt(int n) { if (n <= 0) return 0; else { printf("%d ", n); return countt(n - 1); }}

a)

Đếm số lượng các số từ n đến 1 và in ra

b)

In tất cả các số từ n, n-1, ... đến 1

c)

Tính tổng các số từ 1 đến n

d)

Tính giai thừa của số nguyên n

19.

Hàm đệ quy sau thực hiện chức năng gì?

int sum(int n) {  

    if (n <= 0) return 0;  

      else  

            if (n % 2 = = 0) return n + sum(n - 2);  

            else return sum(n - 1); 

} 

a)

Tính tổng các số chẵn từ 1 đến n

b)

Tính tổng các số lẻ từ 1 đến n

c)

Tính tổng tất cả các số từ 1 đến n

d)

Tính tổng các số nguyên tố từ 1 đến n

20.

Độ phức tạp của thuật toán đệ qui tính số hạng thứ n của dãy Fibonacci :

int fibo(int n)

{ if (n <= 2)

return 1;

       return fibo(n-1)+ fibo(n-2);

}

có kết quả bằng

a)

O(n²)

b)

O(2ⁿ)

c)

O(n)

d)

O(n!)

21.

Độ phức tạp của thuật toán đệ qui thực hiện sắp xếp các phần tử của một dãy có n phần tử theo chiều tăng dần bằng phương pháp Quicksort:

Quicksort (int a[], int L, int R) trong trường hợp tốt nhất

{ k=Partion(a, L, R);

    Quicksort (a, L, k-1);

    Quicksort (a,k,R);

}

a)

O(n)

b)

O(nlogn)

c)

O(n²)

d)

O(2ⁿ)

22.

Độ phức tạp của thuật toán đệ qui thực hiện tìm kiếm giá trị x trong dãy có n phần tử theo phương pháp nhị phân:

int bsearch(int a[], int L, int R, int x)

{ if (L>R)

return -1;

     int k=(L+R)/2;

     if x= = a[k] return k;

     if x>a[k]

return bsearch(a, k+1, R, x);

     return bsearch(a, L, k-1, x);

}

có kết quả bằng

a)

O(n)

b)

O(logn)

c)

O(n2)O(n^2)

d)

O(1)

23.

Thuật toán có phương trình đệ quy sau, (T(1)=1)

T(n) = T(5n/9) + 1

được giải theo định lý Master có nghiệm là

a)

O(n)

b)

O(logn)

c)

O(nlogn)

d)

O(n²)

24.

Thuật toán có phương trình đệ quy sau, (T(1)=1)

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

được giải theo định lý Master có nghiệm là:

a)

O(n)

b)

O(logn)

c)

O(nlogn)

d)

O(n²)

25.

Thuật toán có phương trình đệ quy sau, (T(1)=1)

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

được giải theo định lý Master có nghiệm là:

a)

O(n)

b)

O(logn)

c)

O(nlogn)

d)

O(n²)

26.

Thuật toán có phương trình đệ quy sau, (T(1)=1)

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

được giải theo định lý Master có nghiệm là:

a)

O(n)

b)

O(n²logn)

c)

O(nlogn)

d)

O(n²)

27.

Thuật toán có phương trình đệ quy sau, (T(1) = 1)

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

được giải theo định lý Master có nghiệm là:

a)

O(n)

b)

O(n²logn)

c)

O(n³)

d)

O(n²)

28.

Thuật toán có phương trình đệ quy sau, (T(1)=1)

T(n) = 16T(n/4) + n

được giải theo định lý Master có nghiệm là:

a)

O(logn)

b)

O(n²)

c)

O(nlogn)

d)

O(n)

29.

Với phương trình đệ quy T(n)=2T(n/2)+n²

Hãy xác định bộ giá trị của (a, b, k) và nghiệm tính được theo định lý Master

a)

(1, 2, 2); O(n)

b)

(2, 1, 2); O(n²)

c)

(2, 2, 2); O(n²)

d)

(2, 2, 2); O(nlogn)

30.

Với phương trình đệ quy T(n) =8T(n/2)+n³

Hãy xác định bộ giá trị của (a, b, k) và nghiệm tính được theo định lý Master

a)

(8, 2, 3); O(n³logn)

b)

(8, 1, 3); O(logn³)

c)

(8, 2, 3); O(nlogn²)

d)

(8, 1, 3); O(n³)

31.

Chọn 2 phương án đúng liên quan đến ứng dụng đệ quy:

a)

Tính tổng các phần tử mảng không thể dùng đệ quy

b)

Trong thuật toán đệ quy, bài toán được thu nhỏ qua mỗi lần gọi

c)

Bài toán đệ quy không cần điều kiện kiểm soát

d)

Tính UCLN(a, b) là ví dụ đệ quy sử dụng phép chia dư

32.

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 là cách viết khó hơn và ít ứng dụng hơn vòng lặp

d)

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

33.

Chọn 2 phương án đúng liên quan đến phần cơ sở trong đệ quy:

a)

Nếu không có phần cơ sở, chương trình sẽ lặp vô hạn

b)

Một chương trình đệ quy phải có phần cơ sở để kết thúc đệ quy

c)

Hàm đệ quy không thể dùng trong Pascal

d)

Phần cơ sở có thể được bỏ qua nếu bài toán nhỏ

34.

Chọn 2 phương án đúng nói 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 là phương trình đúng

c)

T(n) = T(n - 1) - C là công thức phổ biến

d)

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

35.

Chọn 2 phương án đúng mô tả về phần thân và lời gọi đệ quy:

a)

A. Trong ví dụ tính n giai thừa, điều kiện if (n == 0) không phải là phần cơ sở

b)

B. Trong ví dụ tính n giai thừa, phần đệ quy là return n * gt(n-1)

c)

C. Một hàm đệ quy có thể không gọi lại chính nó

d)

D. Phần đệ quy là phần gọi lại chính hàm đó

36.

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

a)

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

b)

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

c)

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

d)

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

37.

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

a)

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

b)

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

c)

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

d)

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

38.

Chọn 2 phương án đúng phát biểu đến khả năng hỗ trợ đệ quy trong các ngôn ngữ lập trình:

a)

Đệ quy không thể dùng trong bài toán tính tổng

b)

Đệ quy có thể thay thế vòng lặp trong một số trường hợp

c)

Tất cả các ngôn ngữ lập trình đều hỗ trợ đệ quy

d)

C và Pascal đều hỗ trợ hàm đệ quy

39.

Chọn 2 phương án đúng nói về đặc điểm và ví dụ của đệ quy:

a)

A. Tháp Hà Nội là bài toán điển hình dùng đệ quy

b)

B. Trường hợp suy biến là điều kiện kết thúc đệ quy

c)

C. Trong đệ quy, không nên gọi chính hàm hiện tại

d)

D. Hàm giai thừa không thể viết bằng đệ quy

40.

Với bài toán "Tháp Hà Nội", để chuyển n đĩa từ cọc A sang cọc B (cọc trung gian C) cần:

a)

Chuyển n-1 đĩa từ A sang C

b)

Lặp lại thao tác 64 lần

c)

Chuyển n-1 đĩa từ C sang B

d)

Chuyển 2 đĩa từ C sang B

41.

Ví dụ nào sau đây là để quy đúng trong lập trình?

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 gọi chính nó với tham số giảm dần

d)

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

42.

Một chương trình con đệ quy bắt buộc phải có:

a)

A. Lời gọi đến chính nó

b)

B. Phần cơ sở và phần đệ quy

c)

C. Tham số đầu vào là số nguyên

d)

D. Vòng lặp while

43.

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

(Chọn 2 đáp án)

a)

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

b)

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

c)

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

d)

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

44.

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 đáp án)

a)

Câu lệnh gán

b)

Sử dụng vòng lặp

c)

Lời gọi đệ quy

d)

Điều kiện dừng

45.

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)

O(f(n)) với f(n) là hàm đa thức của n

b)

O(f(n)) với f(n) là hàm mũ của n

c)

O(f(n)) với f(n) là hàm logarit của n

d)

O(f(n)) với f(n) là hàm không xác định

46.

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)

tồn tại đa thức P(n) mà TA ∀ 0, với C và N0 là các hằng số

b)

tồn tại đa thức P(n) mà TA ∀ 0, với N0 là hằng số

c)

tồn tại đa thức P(n) mà TA ∀ 0, với C và N0 là các hằng số

d)

tồn tại đa thức P(n) mà TA ∀ 0, với C và N0 là các hằng số

47.

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

48.

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 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 trung bình của nó là đa thức

49.

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

50.

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

51.

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

52.

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ả

53.

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

54.

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

55.

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ũ

56.

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

57.

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)

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ũ

58.

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ũ

59.

đáp

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ũ

60.

đáp á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ũ

61.

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

62.

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

63.

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

64.

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

65.

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

66.

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

67.

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

a)

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

b)

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

c)

d)

không

68.

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)

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

69.

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)

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

70.

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)

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

71.

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)

b)

không

c)

Chỉ khi số rất nhỏ

d)

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

72.

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)

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