Free Printable Phân tích thiết kế thuật toán

1.

Tìm thời gian chậm nhất. Chọn một đáp án:

a)

O(n)

b)

$O(n^2)$

c)

O(n!)

d)

$O(2^n)$

2.

Để đơn giản trong đánh giá, yếu tố thời gian khi xác định hiệu quả của thuật toán thường được đo bằng. Chọn một đáp án:

a)

Đếm micro giây

b)

Đếm số các câu lệnh chính

c)

Đếm chính xác số câu lệnh

d)

Đếm số kilobyte của thuật toán

3.

Với đoạn mã giả dưới đây, hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp xấu nhất:

a)

O(n)

b)

O(2)

c)

O(n-2)

d)

$O(n^2)$

4.

Cái nào sau đây không phải là $O(n^2)$ ? Chọn một đáp án:

a)

$15^{10} \cdot n + 12099$

b)

$n^3/sqrt\left(n\right)$

c)

$(2^{20}) \cdot n$

d)

$n^{1.98}$

5.

Tính độ phức tạp của giải thuật sau fun()?

a)

Θ(n)

b)

$Θ(n^2)$

c)

$Θ(n^2 log(n))$

d)

Θ(n log(n))

6.

Với đoạn chương trình dưới đây hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp xấu nhất. Chú ý: (logn) = Log cơ số 2 của n.

a)

O(1)

b)

O(n)

c)

O(log(n))

d)

O(n log(n))

7.

Chúng ta nói rằng thuật toán X hiệu quả hơn về mặt độ phức tạp thuật toán với thuật toán Y? Chọn một đáp án:

a)

X là lựa chọn tốt hơn cho mọi đầu vào (inputs)

b)

X là lựa chọn tốt hơn cho mọi đầu vào (inputs) trừ một số các đầu vào kích cỡ nhỏ

c)

X là lựa chọn tốt hơn cho mọi đầu vào (inputs) trừ một số các đầu vào kích cỡ lớn

d)

Y là sự lựa chọn tốt hơn cho đầu vào cỡ nhỏ

8.

T(n) = 2T(n-1) + 17. Khẳng định nào sau đây đúng? Chọn một đáp án:

a)

$Θ(n^2)$

b)

Θ(n log(n))

c)

$Θ(2^n)$

d)

Θ(n)

9.

Kết quả bằng bao nhiêu khi n = 4.

a)

8

b)

9

c)

10

d)

11

10.

Với đoạn mã giả dưới đây hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp xấu nhất:

a)

O(n)

b)

O(log N)

c)

O(n log N)

d)

$O(n^2)$

11.

Kết quả bằng bao nhiêu khi n = 4

a)

110

b)

120

c)

130

d)

140

12.

Thời gian chạy trường hợp xấu nhất của mã giả sau là gì?

a)

O(2)

b)

O(n-2)

c)

O(n)

d)

$O(n^2)$

13.

Hệ thức truy hồi xác định thời gian tối ưu của bài toán Tháp Hà Nội với n đĩa là. Chọn một đáp án:

a)

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

b)

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

c)

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

d)

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

14.

Điều kiện để áp dụng được thuật toán tìm kiếm nhị phân là. Chọn một đáp án:

a)

Danh sách các phần tử phải được sắp xếp

b)

Danh sách các phần tử không cần phải sắp xếp

c)

Danh sách các phần tử phải được sắp xếp tăng dần

d)

Danh sách các phần tử phải được sắp xếp giảm dần

15.

Chọn chốt ngẫu nhiên trong thuật toán QuickSort là. Chọn một đáp án:

a)

Phần tử bên trái nhất được chọn làm chốt

b)

Phần tử bên phải nhất được chọn làm chốt

c)

Bất kỳ phần tử nào trong mảng cũng được chọn làm chốt

d)

Phần tử có giá trị trung bình trong mảng được chọn làm chốt

16.

Với công thức đệ quy f(n) = 4 f(n/2) + 1, thuật toán chia để trị sẽ chia bài toán ban đầu thành bao nhiêu bài toán con và kích thước của các bài toán con đó sẽ là bao nhiêu? Chọn một đáp án:

a)

4 bài toán con, mỗi bài toán kích thước là 2

b)

4 bài toán con, mỗi bài toán kích thước là n/2

c)

2 bài toán con, mỗi bài toán kích thước là 4

d)

2 bài toán con, mỗi bài toán kích thước là n/4

17.

Điều nào sau đây nói về tìm kiếm nhị phân? Chọn một đáp án:

a)

So sánh 2 giá trị đầu tiên và đổi chỗ

b)

Mỗi phần tử được kiểm tra khi sắp xếp

c)

Chia danh sách thành 2 phần và so sánh

d)

So sánh lần lượt các phần tử trong danh sách

18.

Phương pháp nào sau đây là hiệu quả nhất để chọn phần tử chốt trong thuật toán QuickSort? Chọn một:

a)

Phần tử đầu tiên

b)

Phần tử cuối cùng

c)

Phần tử có giá trị trung bình của phần tử đầu, giữa và cuối

d)

Phần tử ngẫu nhiên

19.

Tìm phần tử chốt nào để thuật toán QuickSort hiệu quả nhất cho mảng sau: 8, 1, 4, 9, 6, 3, 5, 2, 7, 0 Chọn một:

a)

8

b)

7

c)

9

d)

6

20.

Thời gian chạy của Quicksort phụ thuộc vào việc lựa chọn _______. Chọn một:

a)

Kích thước của mảng

b)

Phần tử chốt

c)

Giá trị của các phần tử

d)

Không xác định

21.

Độ phức tạp thời gian trung bình của tìm kiếm nhị phân sử dụng đệ quy là bao nhiêu? Chọn một:

a)

$O(n \log n)$

b)

$O(\log n)$

c)

$O(n)$

d)

$O(n^2)$

22.

Chọn lệnh gọi đệ quy thích hợp cho QuickSort. (Arr là mảng, low là chỉ số bắt đầu và high là chỉ số kết thúc của mảng, hàm partition)

a)

b)

c)

d)

23.

Thiết kế giải thuật chia để trị cho bài toán: Viết chương trình tính biểu thức $S = \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{4}} + \cdots + \frac{1}{\sqrt{n}}$ với $n \ge 2$ và $n$ là số chẵn. Ta có, công thức đệ quy sau:

a)

$S(n)=\begin{cases} \frac{1}{\sqrt{2}} & \text{nếu } n=2\ S(n-1) + \frac{1}{\sqrt{n}} & \text{nếu } n>2 \end{cases}$

b)

$S(n)=\begin{cases} \frac{1}{\sqrt{2}} & \text{nếu } n=2\ S(n-2) + \frac{1}{\sqrt{n}} & \text{nếu } n>2 \end{cases}$

c)

$S(n)=\begin{cases} \frac{1}{\sqrt{2}} & \text{nếu } n=2\ S(n+1) + \frac{1}{\sqrt{n}} & \text{nếu } n>2 \end{cases}$

d)

$S(n)=\begin{cases} \frac{1}{\sqrt{2}} & \text{nếu } n=2\ S(n+2) + \frac{1}{\sqrt{n}} & \text{nếu } n>2 \end{cases}$

24.

Điều nào sau đây là đặc điểm của thuật toán quy hoạch động? Chọn một:

a)

Cấu trúc con tối ưu

b)

Các bài toán con lồng nhau

c)

Chiến lược tham lam

d)

Cả cấu trúc con tối ưu và các bài toán con lồng nhau

25.

Chúng ta sử dụng thuật toán quy hoạch động khi: Chọn một:

a)

Chúng ta cần một giải pháp tối ưu

b)

Giải pháp có cấu trúc con tối ưu

c)

Nó nhanh hơn giải thuật tham lam

d)

Nó nhanh hơn giải thuật chia để trị

26.

Chỉ ra tên bài toán có dữ liệu đầu vào là hai dãy $X = \{x_1, x_2, \ldots, x_m\}$ và $Y = \{y_1, y_2, \ldots, y_n\}$ . Chọn một:

a)

Bài toán trình tự nhân dãy ma trận tối ưu

b)

Bài toán tập con độc lập lớn nhất trên cây

c)

Bài toán dây con có trọng lượng lớn nhất

d)

Bài toán dây con chung dài nhất

27.

Chỉ ra độ phức tạp thuật toán quy hoạch động giải bài toán dây con chung dài nhất. Chọn một:

a)

$O(n)$

b)

$O(n^2)$

c)

$O(mn)$

d)

$O(2^n)$

28.

Xét các ma trận $P$ , $Q$ , $R$ và $S$ lần lượt là các ma trận $20\times15$ , $15\times30$ , $30\times5$ và $5\times40$ . Số phép nhân tối thiểu cần thiết để nhân bốn ma trận là bao nhiêu? Chọn một:

a)

6050

b)

7500

c)

7750

d)

12000

29.

Điều gì xảy ra khi phương pháp tiếp cận từ trên xuống của quy hoạch động được áp dụng cho bất kỳ bài toán nào? Chọn một:

a)

Nó làm tăng cả độ phức tạp về thời gian và độ phức tạp về không gian

b)

Nó làm tăng độ phức tạp về không gian và giảm độ phức tạp về thời gian

c)

Nó làm tăng độ phức tạp về thời gian và giảm độ phức tạp về không gian

d)

Nó làm giảm cả độ phức tạp về thời gian và độ phức tạp về không gian

30.

Tìm trình tự nhân và số cách tính tối ưu cho tích của ba ma trận $M_1M_2M_3$ với các kích thước $= (2, 5, 4, 3)$ . Chọn một:

a)

$(M_1)(M_2M_3)$ , số phép tính 90

b)

$(M_1)(M_2M_3)$ , số phép tính 64

c)

$(M_1M_2)(M_3)$ , số phép tính 64

d)

$(M_1M_2)(M_3)$ , số phép tính 90

31.

Bốn ma trận $M_1$ , $M_2$ , $M_3$ và $M_4$ có kích thước lần lượt là $p\times q$ , $q\times r$ , $r\times s$ và $s\times t$ có thể được nhân bằng một số cách với tổng số phép nhân vô hướng khác nhau. Ví dụ: khi nhân với $((M_1 \times M_2) \times (M_3 \times M_4))$ , tổng số phép nhân là $pqr + rst + prt$ . Khi nhân với $((M_1 \times M_2) \times M_3) \times M_4$ , tổng số phép nhân vô hướng là $pqr + prs + pst$ . Nếu $p = 10$ , $q = 100$ , $r = 20$ , $s = 5$ và $t = 80$ thì số phép nhân vô hướng ít nhất cần thiết là: Chọn một:

a)

248000

b)

44000

c)

19000

d)

25000

32.

Tìm cách tính tối ưu cho tích của bốn ma trận có kích thước lưu trữ d vector $d = (13, 5, 89, 3, 34)$ . Với $s = 1$ , $m_{12} = 5785$ , $m_{23} = 1335$ và $m_{34} = 9078$ . Với $s = 2$ , hãy tìm $m_{13}$ và $m_{24}$ .

a)

9256 và 1845

b)

1530 và 1845

c)

1530 và 24208

d)

9256 và 24208

33.

Chọn phát biểu đúng về đặc điểm khác nhau trong cách giải các bài toán con của kỹ thuật thiết kế quy hoạch động và chia để trị.

a)

Quy hoạch động dùng lời gọi đệ quy, chia để trị lưu lại lời giải của các bài toán con

b)

Chia để trị dùng lời gọi đệ quy, quy hoạch động lưu lại lời giải của các bài toán con

c)

Chia để trị dùng lời gọi đệ quy, quy hoạch động không cần phải giải các bài toán con

d)

Quy hoạch động lưu lại lời giải của các bài toán con, chia để trị có thể không có bài toán con nào

34.

Hạn chế chính của thuật toán tham lam là gì?

a)

Khó cài đặt bằng lập trình

b)

Thường cho kết quả sai trong mọi trường hợp

c)

Dễ thực hiện nhưng không đảm bảo lời giải tối ưu toàn cục

d)

Tốn nhiều bộ nhớ

35.

Thuật toán tham lam được xây dựng dựa trên nguyên tắc nào?

a)

Chia nhỏ bài toán thành các bài toán con và giải bằng quy hoạch động

b)

Luôn chọn phương án tối ưu tại thời điểm hiện tại

c)

Duyệt tất cả các khả năng để chọn kết quả tốt nhất

d)

Quay lui để tìm lời giải đúng

36.

Tính chất nào sau đây KHÔNG đúng với thuật toán tham lam?

a)

Quyết định tại mỗi bước dựa trên lợi ích cục bộ

b)

Kết quả thu được luôn là tối ưu toàn cục

c)

Có thể áp dụng cho bài toán cái túi hoặc đổi tiền

d)

Không cần quay lui

37.

Bài toán cái túi (Knapsack) có thể giải bằng thuật toán tham lam nếu:

a)

Đồ vật chỉ có hai loại trọng lượng

b)

Là bài toán cái túi 0-1

c)

Là bài toán cái túi phân số (Fractional Knapsack)

d)

Mỗi đồ vật có giá trị bằng trọng lượng

38.

Nhược điểm chính của Chiến lược thiết kế Tham Lam (so với các chiến lược khác) là gì?

a)

Khó chứng minh một lời giải tham lam là kết quả tối ưu

b)

Khó cài đặt

c)

Khó phân tích

d)

Khó hiểu

39.

Cho biết bước phân ra giải bài toán con độc lập lớn nhất trên cây theo thuật toán quy hoạch động, bài toán tổng quát được chia thành bao nhiêu bài toán con.

a)

1

b)

2

c)

n

d)

(m+1)(n+1)

40.

Khẳng định nào sau đây là phù hợp nhất của Chiến lược thiết kế Tham Lam?

a)

Các lời giải theo phương pháp tham lam là tối ưu

b)

Các lời giải theo phương pháp tham lam chưa chắc là tối ưu

c)

Các lời giải theo phương pháp tham lam cho kết quả giống quy hoạch động

d)

Các lời giải theo phương pháp tham lam cho kết quả giống chia để trị

41.

Khẳng định nào sau đây phù hợp nhất?

a)

Chiến lược Tham Lam tốt hơn chia để trị

b)

Chiến lược Tham Lam tốt hơn quy hoạch động

c)

Chiến lược Chia để trị tốt hơn quy hoạch động

d)

Chiến lược Tham Lam dùng cho giải các bài toán tối ưu tổ hợp

42.

Xét bài toán lập lịch với 4 công việc J1, J2, J3, J4 và deadline tương ứng (d1, d2, d3, d4) = (4, 2, 4, 2). Điều nào sau đây là lịch tối ưu mà không vi phạm bất kỳ lịch trình công việc nào?

a)

J2, J4, J1, J3

b)

J4, J1, J2, J3

c)

J4, J2, J1, J3

d)

J4, J2, J3, J1

43.

Thành phần có vai trò quan trọng nhất tới quyết định tham lam là gì?

a)

Tính chất lựa chọn (hàm) tham lam

b)

Tính chất phức tạp của bài toán

c)

Tính chất lựa chọn cấu trúc dữ liệu

d)

Tính chất lựa chọn nghiệm

44.

Thuật toán có độ phức tạp $O$ (👎) nghĩa là gì?

a)

Thời gian chạy tăng theo bậc n

b)

Thời gian chạy không phụ thuộc vào n

c)

Thời gian chạy tăng tuyến tính theo n

d)

Thời gian chạy giảm khi n tăng

45.

Cho các hàm: Trật tự nào dưới đây thể hiện sự tăng dần của các hàm?

a)

A, D, C, E, B

b)

D, A, C, E, B

c)

A, C, D, E, B

d)

A, C, D, B, E

46.

Làm thế nào bạn có thể đo lường hiệu quả của một thuật toán?

a)

Bộ vi xử lý và bộ nhớ

b)

Độ phức tạp và năng lực

c)

Thời gian và không gian

d)

Dữ liệu và không gian

47.

Ký hiệu nào phù hợp để phân tích cận trên và cận dưới của độ phức tạp thuật toán?

a)

$O$ - lớn

b)

$T$ - lớn

c)

$\Omega$ - lớn

d)

$\Theta$ - lớn

48.

Khẳng định nào sau đây sai?

a)

Nếu $f(n)=O(g(n))$ thì $g(n)=\Omega(f(n))$

b)

Nếu $f(n)=\Theta(g(n))$ thì $g(n)=\Theta(f(n))$

c)

Nếu $f(n)=\Theta(g(n))$ thì $g(n)=\Omega(f(n))$

d)

Nếu $f(n)=\Omega(g(n))$ thì $g(n)=O(f(n))$

49.

Giải thuật đệ quy là gì?

a)

Trong giải thuật có lời gọi của chính nó

b)

Trong giải thuật có lời gọi của chính nó nhưng với quy mô nhỏ hơn

c)

Trong giải thuật có lời gọi của chính nó nhưng với quy mô lớn hơn

d)

Trong giải thuật có lời gọi tới một giải thuật khác đã biết kết quả

50.

$T(n) = 2T(n/2) + 2200$ . Khẳng định nào sau đây đúng?

a)

$\Theta(n^2)$

b)

$\Theta(n\log n)$

c)

$\Theta(\log n)$

d)

$\Theta(n)$

51.

Có hàm đệ quy sau: Kết quả bằng bao nhiêu khi $n = 4$ ?

a)

21

b)

22

c)

23

d)

24

52.

$T(n)=7T(n/2)+3n^2+2$ . Khẳng định nào sau đây đúng?

a)

$O(n^{2.8})$

b)

$O(n)$

c)

$O(n^2)$

d)

$O(n^2\log(n))$

53.

Gọi $W(n)$ và $A(n)$ lần lượt là thời gian chạy trường hợp xấu nhất và trường hợp trung bình của thuật toán được thực hiện trên đầu vào có kích thước $n$ . Điều nào sau đây luôn đúng?

a)

$A(n)=\Omega(W(n))$

b)

$A(n)=\Theta(W(n))$

c)

$A(n)=O(W(n))$

d)

$A(n)=o(W(n))$

54.

Cho giải thuật: Để thực hiện câu lệnh S = F(3), chương trình cần gọi đệ quy mấy lần?

a)

1

b)

2

c)

3

d)

4

55.

Độ phức tạp của thuật toán tìm kiếm nhị phân là gì?

a)

O(n)

b)

O(log n)

c)

$O(n^2)$

d)

O(n log n)

56.

Trong đệ quy, điều kiện mà hàm sẽ ngừng gọi chính nó là.............?

a)

Best case

b)

Worst case

c)

Base case

d)

Average case

57.

Thời gian chạy đối với trường hợp xấu nhất của QuickSort là gì và độ phức tạp thời gian trong trường hợp xấu nhất là gì?

a)

Thời gian chạy là T(n) = $T(n-2)$ + $O(n)$ và độ phức tạp thời gian là $O(n^2)$

b)

Thời gian chạy là T(n) = $T(n-1) + O(n)$ và độ phức tạp thời gian là $O(n^2)$

c)

Thời gian chạy là T(n) = T(n/2) + O(n) và độ phức tạp thời gian là O(n log n)

d)

Thời gian chạy là T(n) = T(n-1) + O(n) và độ phức tạp thời gian là O(n)

58.

Cho một đầu vào arr = {2, 5, 7, 99, 899}; khóa = 899; cấp độ đệ quy trong thuật toán tìm kiếm nhị phân là bao nhiêu?

a)

5

b)

2

c)

3

d)

4

59.

Độ phức tạp của thuật toán tìm kiếm nhị phân được tính là:

a)

T(n) = T(n/2) + k , trong đó k là hằng số

b)

T(n) = 2T(n/2) + k , trong đó k là hằng số

c)

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

d)

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

60.

Cho đoạn chương trình sau: Hãy cho biết đoạn chương trình trên tính toán gì?

a)

Sử dụng x+y phép trừ lặp lại

b)

Sử dụng x mod y phép trừ lặp lại

c)

Ước số chung lớn nhất của x và y

d)

Bội số chung nhỏ nhất của x và y

61.

Cho dãy số: 30, 11, 31, 43, 25, 17, 28, 39, 16, 12, 59, 8. Áp dụng thuật toán QuickSort để sắp xếp dãy số trên, nếu chọn phần tử đầu tiên có giá trị 30 làm chốt, sau lần phân đoạn thứ nhất thu được kết quả là:

a)

Đoạn 1: 16, 11, 8, 12, 25, 17, 28 | Chốt: 30 | Đoạn 2: 39, 43, 59, 31

b)

Đoạn 1: 28, 11, 8, 12, 25, 17, 16 | Chốt: 30 | Đoạn 2: 39, 43, 59, 31

c)

Đoạn 1: 17, 11, 8, 12, 25, 28, 16 | Chốt: 30 | Đoạn 2: 39, 43, 59, 31

d)

Đoạn 1: 25, 11, 8, 12, 17, 28, 16 | Chốt: 30 | Đoạn 2: 39, 43, 59, 31

62.

Kỹ thuật chia để trị chia thành a không gian để trị có kích thước là n/b và phát sinh các phép toán theo hàm f(n), thì ta có công thức truy hồi tổng quát như sau:

a)

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

b)

T(n) = aT(n/b) + f(n)

c)

T(n) = bT(n/a) + f(n)

d)

T(n) = aT(n/a) + f(n)

63.

Trong quy hoạch động, kỹ thuật lưu trữ các giá trị đã tính toán trước đó được gọi là

a)

Lưu lại giá trị

b)

Lưu trữ giá trị

c)

Ghi nhớ

d)

Lập bản đồ

64.

Chỉ ra tên của bài toán tối ưu được giải bằng kỹ thuật thiết kế quy hoạch động

a)

Bài toán tập con độc lập lớn nhất trên cây

b)

Bài toán tìm kiếm nhị phân

c)

Bài toán tìm giá trị lớn nhất

d)

Bài toán sắp xếp nổi bọt

65.

Chỉ ra độ phức tạp thuật toán quy hoạch động giải bài toán dãy con trọng lượng lớn nhất

a)

O(log n)

b)

$O(n^2)$

c)

O(n log n)

d)

O(n)

66.

Cho 2 dãy như sau: X = ⟨ B, C, D, C, A, B, C ⟩; Y = ⟨ C, A, D, B, C, B ⟩. Hãy tìm độ dài của dãy con chung dài nhất của X và Y.

a)

5

b)

3

c)

4

d)

2

67.

Xét hai ma trận P và Q lần lượt là các ma trận 10 x 20 và 20 x 30. Số phép nhân cần thiết để nhân hai ma trận là bao nhiêu?

a)

10*20

b)

10*30

c)

20*30

d)

10*20*30

68.

Chỉ ra công thức tính m[i][j] là số phép nhân ít nhất đầy ma trận Mi+1 Mi+2 … Mj với 1 ≤ i ≤ j ≤ n trong bước tổng hợp lời giải của bài toán trình tự nhân dãy ma trận khi giải bằng thuật toán quy hoạch động.

a)

Biểu thức công thức tại hình (a)

b)

Biểu thức công thức tại hình (b)

c)

Biểu thức công thức tại hình (c)

d)

Biểu thức công thức tại hình (d)

69.

Công thức nào sau đây tính dãy con chung dài nhất:

l(i, j) = 0 nếu i = 0 hoặc j = 0; = expr1, nếu i > 0 và X[i−1] = Y[j−1]; = expr2, nếu i > 0 và X[i−1] ≠ Y[j−1].

a)

expr1 = l(i, j−1)

b)

expr1 = l(i−1, j) + 1

c)

expr2 = max(l(i−1, j−1), l(i, j))

d)

expr2 = max(l(i−1, j), l(i, j−1))

70.

Cho đoạn mã sau để tìm dãy con chung dài nhất của 2 dãy Xi và Yi (0 ≤ i ≤ m, 0 ≤ j ≤ n):

Chọn dòng lệnh thích hợp để điền vào chỗ trống:

a)

L[i, j] = L[i, j] + 1;

b)

L[i, j] = L[i - 1, j - 1] + 1;

c)

L[i, j] = L[i - 1, j - 1];

d)

L[i, j] = L[i, j];

71.

Phát biểu nào sau đây đúng về kỹ thuật thiết kế thuật toán Quy hoạch động và Chia để trị (chọn 2 đáp án)?

a)

Cả quy hoạch động và chia để trị thì bài toán con kích thước nhỏ nhất đều có thể giải một cách trực tiếp

b)

Bài toán tổng quát phải được giải thông qua ít nhất 2 bài toán con

c)

Hai kỹ thuật có cách giải các bài toán con khác nhau

d)

Cả quy hoạch động và chia để trị trước tiên đều chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu

72.

Bước đầu tiên khi áp dụng thuật toán tham lam là gì?

a)

Chọn bài toán con có kết quả tốt nhất

b)

Xác định tiêu chí lựa chọn tham lam

c)

Tính tất cả các phương án có thể xảy ra

d)

Tìm lời giải tối ưu bằng đệ quy

73.

Trong bài toán đổi tiền bằng thuật toán tham lam, ta chọn tờ tiền nào trước?

a)

Tờ tiền có mệnh giá nhỏ nhất

b)

Tờ tiền có mệnh giá lớn nhất nhưng không vượt quá số tiền cần đổi

c)

Tờ tiền ngẫu nhiên

d)

Tờ tiền xuất hiện ít nhất trong cây ATM

74.

Thuật toán tham lam thường được dùng để giải loại bài toán nào?

a)

Bài toán tối ưu

b)

Bài toán tìm kiếm

c)

Bài toán sắp xếp

d)

Bài toán quy hoạch

75.

Chỉ ra công thức tính độ dài của dãy con chung lớn nhất C[i, j] trong bước tổng hợp lời giải của bài toán dãy con chung dài nhất khi giải bằng thuật toán quy hoạch động.

a)

Biểu thức công thức tại hình (a)

b)

Biểu thức công thức tại hình (b)

c)

Biểu thức công thức tại hình (c)

d)

Biểu thức công thức tại hình (d)

76.

Cho biết đoạn chương trình sau giải bài toán nào bằng kỹ thuật thiết kế quy hoạch động: Mã giả hiển thị một thuật toán với các vòng lặp for cho i từ 1 đến m, for j từ 1 đến n và các kiểm tra so sánh x[i] với y[j], cập nhật c[i][j] dựa trên c[i-1][j-1], c[i-1][j], c[i][j-1].

a)

Bài toán trình tự nhân dãy ma trận tối ưu

b)

Bài toán tập con độc lập lớn nhất trên cây

c)

Bài toán dãy con có trọng lượng lớn nhất

d)

Bài toán dãy con chung dài nhất

77.

Độ phức tạp thời gian được đo lường như thế nào?

a)

Bằng cách đếm số câu lệnh trong một thuật toán

b)

Bằng cách đếm số lượng hoạt động nguyên thủy được thực hiện bởi thuật toán trên một kích thước đầu vào nhất định

c)

Bằng cách đếm kích thước của dữ liệu đầu vào cho thuật toán

d)

Bằng cách đếm kích thước của dữ liệu đầu ra cho thuật toán

78.

Cái nào sau đây KHÔNG thuộc các ký hiệu độ phức tạp thuật toán?

a)

O - lớn

b)

T - lớn

c)

Ω - lớn

d)

Θ - lớn

79.

Chọn câu trả lời đúng nhất về thuật toán.

a)

Thuật toán rất quan trọng với chương trình

b)

Thuật toán cần nhiều dữ liệu ra và vào

c)

Thuật toán là một dãy các bước hữu hạn, tất cả các phép toán phải đơn giản

d)

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác phép toán hoặc hành động để thực hiện vấn đề đặt ra

80.

Cho T(n) = 2T(n/2) + 2020. Khẳng định nào sau đây đúng?

a)

$Θ(n^2)$

b)

Θ(n log n)

c)

Θ(log n)

d)

Θ(n)

81.

Với đoạn mã dưới đây hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp xấu nhất:

a)

O(n)

b)

O(log N)

c)

O(n log N)

d)

$O(n^2)$

82.

Với đoạn mã giả sau hãy xác định độ phức tạp tính toán của giải thuật bằng ký pháp chữ O lớn trong trường hợp xấu nhất:

a)

O(n)

b)

O(Nlog N)

c)

O(N*N)

d)

O(log N)

83.

Có hàm đệ quy sau: public static long F(int n) { if (n == 0) return 2; else return ... } Kết quả bằng bao nhiêu khi n = 4 (theo đoạn mã hiển thị)?

a)

48

b)

49

c)

50

d)

51

84.

Độ phức tạp của hai hàm sau? fun1(int n) { if (n < 1) return n; return 2*fun1(n-1); } fun2(int n) { if (n < 1) return n; return fun2(n-1) + fun2(n-1); }

a)

O(2^n) cho cả fun1() và fun2()

b)

O(n) cho fun1() và O(2^n) cho fun2()

c)

O(2^n) cho fun1() và O(n) cho fun2()

d)

O(n) cho cả fun1() và fun2()

85.

Trường hợp nào sau đây không tồn tại trong lý thuyết độ phức tạp?

a)

Trường hợp tốt nhất

b)

Trường hợp xấu nhất

c)

Trường hợp rỗng

d)

Trường hợp trung bình

86.

Khi thiết kế giải thuật đệ quy, bước đầu tiên ta phải:

a)

Xác định điều kiện dừng đệ quy và lời giải ứng với trường hợp này

b)

Xác định trường hợp đệ quy

c)

Xây dựng công thức đệ quy

d)

Tìm cách khử đệ quy

87.

Thuật toán nào sau đây KHÔNG phải là thuật toán chia để trị?

a)

Thuật toán Euclid tìm ước số chung lớn nhất của 2 số nguyên dương

b)

Thuật toán sắp xếp QuickSort

c)

Thuật toán sắp xếp Bubble Sort

d)

Thuật toán sắp xếp Merge Sort

88.

Độ phức tạp của thuật toán QuickSort trong trường hợp tốt nhất là:

a)

$O(n^2)$

b)

O(n log n)

c)

O(n)

d)

O(log n)

89.

Độ phức tạp của thuật toán QuickSort trong trường hợp xấu nhất là:

a)

$O(n^2)$

b)

O(n log n)

c)

O(n)

d)

O(log n)

90.

Cho một mảng arr = {5, 6, 77, 88, 99} và key = 88; Có bao nhiêu lần lặp được thực hiện cho đến khi phần tử được tìm thấy?

a)

1

b)

3

c)

4

d)

2

91.

Cho mảng a = {2, 6, 1}. Các chốt được trả về do kết quả của việc phân vùng tiếp theo là gì?

a)

1 và 6

b)

2 và 6

c)

6 và 1

d)

1

92.

Chỉ ra tên bài toán không được giải bằng kỹ thuật thiết kế quy hoạch động.

a)

Bài toán sắp xếp chọn và sắp xếp chèn

b)

Bài toán tìm trình tự nhân tối ưu dãy ma trận

c)

Bài toán dãy con có trọng lượng lớn nhất

d)

Bài toán dãy con chung dài nhất

93.

Chỉ ra độ phức tạp thuật toán quy hoạch động tìm số Fibonacci thứ n (fn = fn-1 + fn-2, f1 = f2 = 1).

a)

O(log n)

b)

$O(n^2)$

c)

O(1)

d)

O(n)

94.

Các bài toán con trong thuật toán quy hoạch động được giải quyết:

a)

Độc lập nhau

b)

Phụ thuộc nhau

c)

Song song

d)

Đồng thời

95.

Chuỗi nào sau đây là dãy con chung dài nhất giữa các chuỗi "hbcfgmnq" và "hbcfgmnapq"?

a)

hgm

b)

cqnf

c)

bmfq

d)

cgnq

96.

Hai tính chất quan trọng mà một bài toán tối ưu cần phải thỏa mãn để có thể áp dụng quy hoạch động (chọn 2 đáp án).

a)

Đệ quy và Cấu trúc con tối ưu

b)

Số lượng các bài toán con phải không quá lớn và Đệ quy

c)

Cấu trúc con tối ưu và Số lượng các bài toán con phải không quá lớn

d)

Bài toán tổng quát có thể giải bằng độ phức tạp hằng số và đệ quy

97.

Xem xét các chuỗi "PQRSTPQRS" và "PRATPBQPRS". Độ dài của dãy con chung dài nhất là bao nhiêu?

a)

9

b)

8

c)

7

d)

6

98.

Theo bước phân rã bài toán dãy con chung dài nhất (LCS) bằng quy hoạch động, bài toán tổng quát được chia thành bao nhiêu bài toán con?

a)

1

b)

2

c)

n

d)

$(m+1)(n+1)$

99.

Cho đoạn mã trong hình minh họa để tìm dãy con chung dài nhất của hai dãy X_i và Y_i (chỉ số thoả mãn 0 < i ≤ m, 0 ≤ j ≤ n). Hãy chọn dòng lệnh thích hợp để điền vào chỗ trống trong phần xử lý trường hợp X[i] ≠ Y[j].

a)

L[i, j] = Math.Max(L[i - 1, j - 1], L[i, j - 1]);

b)

L[i, j] = Math.Max(L[i - 1, j], L[i - 1, j - 1]);

c)

L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]);

d)

L[i, j] = Math.Max(L[i, j], L[i - 1, j - 1]);

100.

Thuật toán tham lam thường không đảm bảo tối ưu toàn cục vì lý do nào?

a)

Nó dựa vào các lựa chọn cục bộ

b)

Nó không sử dụng quay lui

c)

Nó không có điều kiện dừng

d)

Nó phụ thuộc vào ngôn ngữ lập trình

101.

Trong sơ đồ tổng quát của thuật toán tham lam, bước “Select(C)” có ý nghĩa gì?

a)

Chọn phần tử cuối cùng của danh sách

b)

Lựa chọn ứng cử viên tiềm năng nhất để thêm vào lời giải

c)

Loại bỏ phần tử lớn nhất khỏi danh sách

d)

Thực hiện phép đệ quy trên các phần tử còn lại

Phân tích thiết kế thuật toán

Total questions: 101

Worksheet time: 51mins

Similar Resources on Wayground