Free Printable Phân tích và thiết kế thuật toán (Tiếp)

Worksheets

Phân tích và thiết kế thuật toán (Tiếp)

Total questions: 87

Worksheet time: 44mins

Name

Class

Date

Sáu tệp F1, F2, F3, F4, F5, F6 có số bản ghi lần lượt là 100, 200, 50, 80, 120, 150. Chúng nên được lưu trữ theo thứ tự nào để lưu trữ được nhiều tệp nhất, giả sử mỗi tệp được truy cập với cùng tần suất. Chọn một đáp án đúng.

F3, F4, F1, F5, F6, F2

F2, F6, F5, F1, F4, F3

F1, F2, F3, F4, F5, F6

F3, F4, F5, F1, F6, F2

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

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

Đệ quy

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

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

Ưu đ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ì? Chọn một đáp án đúng.

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

Độ phức tạp nhỏ (thực hiện nhanh)

Cho nhiều nghiệm

Cho nghiệm tối ưu

Chiến lược thiết kế nào sau đây lựa chọn tối ưu cục bộ (tại thời điểm lựa chọn) và hi vọng nó sẽ dẫn tới tối ưu toàn cục? Chọn một đáp án đúng.

Quy hoạch động

Chia để trị

Tham lam

Quy hoạch động và Tham lam

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 $O$ lớn trong trường hợp xấu nhất.

$O(1)$

$O(n)$

$O(\log(n))$

$O(n\log(n))$

Cho hàm đệ quy có độ phức tạp $T(n) = 3T(n/4) + n^2$ . Khẳng định nào sau đây đúng? Chọn một đáp án đúng.

$\Theta(n^2)$

$\Theta(n\log n)$

$\Theta(\log n)$

$\Theta(n)$

Điều đó có nghĩa là gì khi nói rằng thuật toán X hiệu quả hơn Y một cách tiệm cận? Chọn một đáp án đúng.

X sẽ luôn là lựa chọn tốt hơn cho đầu vào nhỏ

X sẽ luôn là lựa chọn tốt hơn cho đầu vào lớn

X sẽ luôn là lựa chọn tốt hơn cho mọi đầu vào

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

Đệ quy là một phương pháp trong đó lời giải của một bài toán phụ thuộc vào ______. Chọn một đáp án đúng.

Các trường hợp lớn hơn của các bài toán khác nhau

Các trường hợp lớn hơn của các bài toán giống nhau

Các trường hợp nhỏ hơn của các bài toán giống nhau

Các trường hợp nhỏ hơn của các bài toán khác nhau

Cho giả thuật đệ quy sau. Hãy cho biết giá trị của biến S sau khi thực hiện câu lệnh: S = F(3).

10.

Trong thuật toán QuickSort, độ phức tạp trong trường hợp tốt nhất và xấu nhất là gì? Chọn một đáp án đúng.

Tốt nhất: $O(n)$ , Xấu nhất $O(n^2)$

Tốt nhất: $O(n)$ , Xấu nhất $O(n\log n)$

Tốt nhất: $O(n\log n)$ , Xấu nhất $O(n\log n)$

Tốt nhất: $O(n\log n)$ , Xấu nhất $O(n^2)$

11.

Bài toán nào sau đây được giải quyết bằng thuật toán quy hoạch động? Chọn một đáp án đúng.

Merge Sort

Bubble Sort

Dãy con chung dài nhất

QuickSort

12.

Bài toán có dữ liệu đầu vào: n ma trận M1, M2, …, Mn; dãy số nguyên do, d1, …, dn; ma trận Mi có kích thước là d(i−1)×di. Tên bài toán là gì? Chọn một đáp án đúng.

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

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

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

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

13.

Ba giai đoạn chính của thuật toán quy hoạch động là gì? Chọn một đáp án đúng.

1 – Phân rã, 2 – Giải bài toán con, 3 – Tổng hợp lời giải

1 – Giải bài toán con, 2 – Ghi nhận kết quả, 3 – Tổng hợp lời giải

1 – Phân rã, 2 – Giải các bài toán con và ghi nhận lời giải, 3 – Tổng hợp lời giải

1 – Phân rã, 2 – Giải bài toán con, 3 – Ghi nhận kết quả

14.

Cho hai dãy X và Y: X = ⟨a, b, c, b, d, a, b⟩, Y = ⟨b, d, c, a, b, a⟩. Dãy con chung dài nhất của X và Y là gì? Chọn một đáp án đúng.

⟨b, c, a⟩

⟨c, a, b⟩

⟨b, c, a, a⟩

⟨b, c, b, a⟩

15.

Chọn phát biểu đúng về kỹ thuật thiết kế thuật toán quy hoạch động (chọn 2 đáp án).

Giải các bài toán con của quy hoạch động là quá trình đi từ trên xuống (top-down), các bài toán con được giải đệ quy từ lời gọi giải bài toán tổng quát

Các bài toán con chung phải được giải nhiều lần, tùy vào từng bài toán

Mỗi một bài toán con chỉ giải một lần duy nhất, kể cả các bài toán con chung

Giải các bài toán con của quy hoạch động là quá trình đi từ dưới lên (bottom–up), giải bài toán kích thước nhỏ hơn đến bài toán kích thước lớn hơn

16.

Trong bài toán lập lịch hội nghị, tiêu chí chọn cuộc họp tiếp theo là gì? Chọn một đáp án đúng.

Hội nghị có thời gian bắt đầu sớm nhất

Hội nghị có thời gian kết thúc muộn nhất

Hội nghị có thời gian kết thúc sớm nhất mà không trùng với cuộc họp trước

Hội nghị có thời gian dài nhất

17.

Khẳng định nào sau đây phù hợp nhất với Chiến lược thiết kế Tham Lam? Chọn một đáp án đúng.

Giải thuật thiết kế kiểu từ trên xuống (top-down)

Đưa ra quyết định tốt nhất trong hiện tại, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ

Giải thuật thiết kế kiểu từ dưới lên (bottom–up)

Phân chia bài toán ban đầu thành các bài toán con để giải

18.

Giá trị nào là tối ưu trong trường hợp bài toán trình tự công việc sau đây? Chọn một đáp án đúng. Mục: 1 2 3 4 5 Lợi nhuận: 20 15 10 5 1 Hạn: 2 2 3 3 3

1, 3, 4

1, 2, 4

4, 2, 3

1, 5, 2

19.

Ký hiệu nào phù hợp để phân tích cận dưới của độ phức tạp thuật toán? Chọn một đáp án đúng.

$O$ - lớn

$T$ - lớn

$\Omega$ - lớn

$\theta$ - lớn

20.

Cho đoạn code sau: Cho biết độ phức tạp của thuật toán trên.

$O(n)$

$O(n\log n)$

$O(\log n)$

$O(1)$

21.

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, D, C, E, B

D, A, C, E, B

A, C, D, E, B

A, C, D, B, E

22.

Cho biết độ phức tạp thời gian không đổi theo ký hiệu Big-O.

O(n)

O(1)

O(log N)

$O(n^2)$

23.

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

24.

Trong một cuộc thi, bốn hàm khác nhau được thực thi. Tất cả các hàm sử dụng một vòng lặp for duy nhất và trong vòng lặp for cùng một tập hợp các câu lệnh được thực thi. Hãy xem xét những điều sau cho các vòng lặp ở hình ảnh. Nếu n là kích thước của đầu vào (dương), thì hàm nào hiệu quả nhất?

25.

Nếu một vòng lặp for chạy với kích thước N và vòng lặp kia chạy với kích thước M và các vòng lặp tuân theo một hàm tuyến tính, thì độ phức tạp thời gian dự kiến là bao nhiêu?

O(M+N)

O(log n)

O(log M)

O(1)

26.

Bước nào trong quy trình chia để trị sử dụng cách tiếp cận đệ quy?

Giải quyết

Phân chia

Trộn

Tổng hợp

27.

Trường hợp suy biến (neo) của giải thuật tính $n!$ là:

n=0

n=1

n=2

n>2

28.

Bài toán nào sau đây không được giải quyết bằng thuật toán quy hoạch động

Dãy con chung dài nhất

Trình tự nhân dãy ma trận

Tìm kiếm nhị phân

Dãy con có tổng lớn nhất

29.

Chiến lược thiết kế quy hoạch động gần giống:

Thuật toán tham lam

Thuật toán chia để trị

Bảng băm

Phân tích cú pháp

30.

Cho biết bài toán nào có thể cần sử dụng đoạn chương trình sau:

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

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

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

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

31.

Thuật toán quy hoạch động thường được dùng để giải quyết bài toán “Dãy con có trọng lượng lớn nhất”. Áp dụng thuật toán này, tìm dãy con có trọng lượng lớn nhất của dãy số sau (trọng lượng của dãy bằng tổng giá trị các phần tử trong dãy, dãy phải đảm bảo tính liên tiếp và có thứ tự): 13, -16, 2, 18, 4, 8, 0, -5, -8

13, -16, 2, 18, 4, 8

2, 18, 4, 8

2, 18, 4, 8, 0, -5

18, 4, 8, 0, -5, -8

32.

Ưu điểm nổi trội nhất của kỹ thuật thiết kế thuật toán Quy hoạch động so với kỹ thuật thiết kế chia để trị là gì?

Lời giải của các bài toán con được lưu lại

Giải các bài toán con bằng lời gọi đệ quy

Mỗi bài toán con chỉ giải một lần duy nhất, kể cả các bài toán con chung

Các bài toán con chung có thể được giải lại nhiều lần

33.

Trong bài toán chọn hoạt động (Activity Selection), tiêu chí chọn hoạt động là gì?

Thời gian bắt đầu sớm nhất

Thời gian kết thúc muộn nhất

Thời gian kết thúc sớm nhất

Thời gian dài nhất

34.

Cho biết bước phân rã giải bài toán dãy con có trọng lượng lớn nhất 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.

(m+1)(n+1)

35.

Độ phức tạp thời gian Big-O của đoạn chương trình sau là gì?

O(n)

O(1)

O(log n)

O(n log n)

36.

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

O(f(n)*g(n)) = min(f(n), g(n))

O(f(n)*g(n)) = max(f(n), g(n))

O(f(n)+g(n)) = min(f(n), g(n))

O(f(n)+g(n)) = max(f(n), g(n))

37.

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:

O(n)

O(Nlog N)

O(N*N)

O(log N)

38.

Độ phức tạp về thời gian của đoạn mã sau là bao nhiêu:

O(n)

O(Sqrt(n))

$O(N^2)$

O(log n)

39.

Cho giải thuật với hàm f nguyên: Hãy cho biết giá trị của biến S sau khi thực hiện câu lệnh S = F(3).

40.

Một hàm đệ quy h được định nghĩa: Nếu giá trị của h(4) là 88 thì giá trị của k là bao nhiêu?

-1

41.

Gọi A1, A2, A3 và A4 là bốn ma trận có kích thước lần lượt là $6\times5$ , $5\times10$ , $10\times4$ và $4\times5$ . Số phép nhân vô hướng tối thiểu cần thiết để tính $A1\,A2\,A3\,A4$ bằng phương pháp nhân ma trận cơ bản là bao nhiêu? Chọn một đáp án đúng.

440

450

460

340

42.

Trong bài toán sắp xếp balo 0/1, bước nào được thực hiện đầu tiên? Chọn một đáp án đúng.

Sắp xếp các đồ vật theo chiều giảm tỉ lệ Giá trị / Khối lượng

Sắp xếp các đồ vật theo chiều giảm tỉ lệ Khối lượng / Giá trị

Sắp xếp các đồ vật theo chiều giảm tỉ lệ Giá trị + Khối lượng

Sắp xếp các đồ vật theo chiều giảm tỉ lệ Khối lượng

43.

Điều nào sau đây mô tả đúng nhất tiêu chí hữu ích để so sánh hiệu quả của các thuật toán? Chọn một đáp án đúng.

Thời gian

Bộ nhớ

Câu lệnh

Thời gian và bộ nhớ

44.

Ký hiệu nào phù hợp để phân tích cận trên của độ phức tạp thuật toán? Chọn một đáp án đúng.

$O$ - lớn

$T$ - lớn

$\Omega$ - lớn

$\Theta$ - lớn

45.

Hàm nào sau đây không thuộc $O(n^2)$ ? Chọn một đáp án đúng.

$15^{10}\cdot n^{1.98} + 2002$

$2020\cdot n^{1.98} + 2002$

$\dfrac{n^3}{\log(n)}$

$15^{10}\cdot n\log(n)$

46.

Để viết chương trình chỉ để sử dụng một số ít lần và giá giá của thời gian viết chương trình chạy nhanh hoặc tiết kiệm nguồn tài nguyên vượt xa giá giá của chạy chương trình thì ta chọn thuật toán nào? Chọn một đáp án đúng.

Thuật toán đơn giản, dễ hiểu, dễ cài đặt

Thuật toán sử dụng tiết kiệm nhất nguồn tài nguyên của máy tính

Thuật toán chạy nhanh nhất có thể được

Tất cả yêu cầu

47.

Cho $T(n) = 3T(n/2) + n^2$ . Chọn một đáp án đúng.

$\Theta(n^{2.8})$

$\Theta(n)$

$\Theta(n^{2})$

$\Theta(n^{2}\log n)$

48.

Cho biết độ phức tạp thời gian hàm mũ theo ký hiệu big-O. Chọn một đáp án đúng.

$O(n)$

$O(n^2)$

$O(2^n)$

$O(\log n)$

49.

Độ phức tạp trường hợp xấu nhất của thuật toán Merge sort là gì? Chọn một đáp án đúng.

$O(n\log n)$

$O(n)$

$O(\log n)$

$O(n^2)$

50.

Cho P là chương trình sắp xếp bằng thuật toán QuickSort sắp xếp các số theo thứ tự tăng dần. Giả sử $t_1$ và $t_2$ là thời gian tương ứng khi thực hiện chương trình trên để sắp xếp với dữ liệu vào lần lượt là {1,2,3,4} và {5,4,3,2}. Hãy chọn biểu thức đúng. Chọn một đáp án đúng.

$t_1 = t_2$

$t_1 > t_2$

$t_1 < t_2$

$t_1 = t_2 + 5\log 5$

51.

Điều nào sau đây mô tả đúng nhất tiêu chí hữu ích để so sánh hiệu quả của các thuật toán? Chọn một đáp án đúng.

Thời gian

Bộ nhớ

Câu lệnh

Thời gian và bộ nhớ

52.

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

53.

Cho $T(n) = 2T(n/4) + n^{0.5}$ . Khẳng định nào sau đây đúng? Chọn một đáp án đúng.

$\Theta(n^{2})$

$\Theta(n)$

$\Theta(n^{0.5}\log n)$

$\Theta(n\log^{2} n)$

54.

Độ phức tạp về thời gian và không gian của đoạn mã sau là bao nhiêu?

$O(N\cdot M)$ thời gian, $O(1)$ không gian

Thời gian $O(N + M)$ , không gian $O(N + M)$

$O(N + M)$ thời gian, $O(1)$ không gian

Thời gian $O(N\cdot M)$ , không gian $O(N + M)$

55.

Các thuật toán như sắp xếp trộn, sắp xếp nhanh hay tìm kiếm nhị phân thuộc về loại nào? Chọn một đáp án đúng.

Thuật toán tham lam

Thuật toán Chia để trị

Thuật toán quy hoạch động

Bảng băm

56.

Phương pháp Chia để trị để giải quyết vấn đề rất hữu ích khi nào? Chọn một đáp án đúng.

Chúng ta có thể chia bài toán thành nhiều bài toán con tương tự như bài toán ban đầu nhưng kích thước nhỏ hơn

Các vấn đề con chồng chéo lên nhau nên chúng ta không phải giải quyết chúng nhiều lần

Độ phức tạp là cấp số nhân để giải quyết toàn bộ vấn đề

Chia bài toán ban đầu thành các bài toán con lồng nhau

57.

Cho một mảng arr = {45, 77, 89, 90, 94, 99, 100} và key = 99; giá trị giữa (phần tử mảng tương ứng) trong lần gọi đệ quy thứ nhất và thứ hai là gì?

90 và 99

90 và 94

89 và 99

89 và 94

58.

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

59.

Tùy chọn nào dưới đây cung cấp thứ tự độ phức tạp tiệm cận tăng dần của các hàm f1, f2, f3, f4? f1(n) = $2^n$ , f2(n) = $n^{3/2}$ , f3(n) = $n\,\log n$ , f4(n) = $n^{\log n}$ .

f3, f2, f4, f1

f3, f2, f1, f4

f2, f3, f1, f4

f2, f3, f4, f1

60.

Chỉ ra tên của thuật toán không được thiết kế theo chiến lược chia để trị (Divide and Conquer).

Sequence Search

Binary Search

Quick Sort

Merge Sort

61.

Sắp xếp trộn (Merge Sort) thuộc loại kỹ thuật nào?

Thuật toán chia để trị

Thuật toán tham lam

Thuật toán quy hoạch động

Thuật toán quay lui

62.

Độ phức tạp thời gian của hàm sau là (giả sử n > 0).

$O(n)$

$O(n\log n)$

$O(n^2)$

$O(2^n)$

63.

Kỹ thuật thiết kế thuật toán Quy hoạch động và Chia để trị có những đặc điểm hay phân đoạn nào giống nhau (chọn 2 đáp án).

Cách giải các bài toán con

Chia bài toán tổng quát thành những bài toán con kích thước nhỏ hơn

Thường được áp dụng để giải các bài toán tối ưu

Phát triển 2 giải thuật đều có thể chia làm 3 giai đoạn

64.

Chỉ ra tên bài toán giải bằng kỹ thuật thiết kế quy hoạch động, phân rã bài toán tổng quát như sau: a1, a2, ..., ai, i = 1, 2, ..., n. Rõ ràng s_n là giá trị cần tìm. Với s_i là tổng của dãy con lớn nhất trong dãy.

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

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

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

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

65.

Cho các thuật toán và độ phức tạp sau:

66.

Thuật toán sắp xếp nhanh (QuickSort) chia toàn bộ mảng thành bao nhiêu mảng con?

67.

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

68.

Xét các ma trận P, Q, R lần lượt có kích thước $10\times20$ , $20\times30$ và $30\times40$ . Số phép nhân tối thiểu cần thiết để nhân ba ma trận là bao nhiêu?

18000

12000

24000

32000

69.

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

f3, f2, f4, f1

f3, f2, f1, f4

f2, f3, f1, f4

f2, f3, f4, f1

70.

Phát biểu nào sau đây đúng về tính chất của thuật toán?

Tính đúng đắn, tính dừng, tính rõ ràng (xác định)

Tính hạn chế, tính dừng, tính rõ ràng (xác định)

Tính đúng đắn, tính phức tạp, tính rõ ràng (xác định)

Tính đúng đắn, tính dừng, tính phức tạp

71.

Cho dãy số A[0..9] gồm các số: 1, 10, 16, 21, 29, 30, 49, 77, 80, 101. Áp dụng thuật toán tìm kiếm nhị phân để kiểm tra phần tử có giá trị x = 32 có trong dãy; sau lần gọi đệ quy thứ nhất, thuật toán tìm x = 32 ở đoạn nào?

Tìm x ở đoạn A[0..4]

Tìm x ở đoạn A[4..9]

Tìm x ở đoạn A[0..3]

Tìm x ở đoạn A[5..9]

72.

Đặc điểm nổi bật nhất của thuật toán tham lam là gì?

Luôn xét tất cả các trường hợp có thể để tìm lời giải tối ưu

Lựa chọn phương án tốt nhất tại mỗi bước mà không xét đến tương lai

Sử dụng đệ quy để giải bài toán con

Dùng kỹ thuật quay lui để tìm lời giải

73.

Hai thành phần chính để đánh giá độ phức tạp của một thuật toán là

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

Độ phức tạp và không gian

Thời gian và không gian

Dữ liệu và không gian

74.

Dãy số Fibonacci bắt nguồn từ bài toán sinh sản của các cặp thỏ. Bài toán được đặt ra như sau: Các con thỏ không bao giờ chết. Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con. Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới. Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ 5 sẽ có bao nhiêu cặp? Chọn một đáp án.

75.

Cho đoạn mã hàm đệ quy sau và hỏi kết quả bằng bao nhiêu khi n = 5? Chọn một đáp án.

76.

Trong các thuật toán sau, chỉ ra tên của thuật toán có độ phức tạp thuật toán nhỏ nhất trong 4 thuật toán sắp xếp. Chọn một đáp án.

Selection Sort

Bubble Sort

Quick Sort

Insertion Sort

77.

Sử dụng tìm kiếm nhị phân, tại sao số 9 không bao giờ được tìm thấy trong danh sách sau: 11, 8, 13, 9, 7, 3? Chọn một đáp án.

Nó không tồn tại trong danh sách

Danh sách chưa được sắp xếp

Nó không nằm ở đầu danh sách

Nó không nằm ở cuối danh sách

78.

Cho hàm truy hồi T(n) = 8T(n/2) + 7n. Xác định độ phức tạp của hàm trên. Chọn một đáp án.

Θ(n)

$Θ(n^2)$

Θ(log n)

$Θ(n^3)$

79.

Khẳng định nào sau đây đúng? Chọn một đáp án.

Nếu f(n) = O(g(n)) thì g(n) = Ω(f(n))

Nếu f(n) = Ω(g(n)) thì g(n) = Θ(f(n))

Nếu f(n) = Θ(g(n)) thì g(n) = Ω(f(n))

Nếu f(n) = Ω(g(n)) thì g(n) = Ω(f(n))

80.

Độ phức tạp thời gian Big O của đoạn chương trình sau là gì?

O(n)

O(m)

O(n * m)

O(n + m)

81.

Chỉ ra tên bài toán giải bằng kỹ thuật thiết kế quy hoạch động: bài toán con có kích thước lớn nhất C(m,n), bài toán cần giải được phân rã ra thành (m+1)(n+1) bài toán con. Chọn một đáp án.

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

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

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

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

82.

Xem xét các hàm sau: Khẳng định nào sau đây là đúng?

f(n) = O(g(n)); g(n) = O(h(n))

f(n) = Ω(g(n)); g(n) = O(h(n))

g(n) = O(f(n)); h(n) = O(f(n))

h(n) = O(f(n)); g(n) = Ω(f(n))

83.

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(n) = Ω(W(n))

A(n) = Θ(W(n))

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

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

84.

Sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình (logn là log cơ số 2 của n). Chọn một đáp án.

O(1), O(logn), O(n), O(nlogn)

O(logn), O(nlogn), O(n), O(1)

O(1), O(n), O(log n), O(nlog n)

O(1), O(log n), O(nlog n), O(n)

85.

Xét hai chuỗi A = "bgqpr" và B = "pqqprq". Gọi x là độ dài của chuỗi con chung dài nhất (không nhất thiết phải liền kề) giữa A và B và gọi y là số lượng các chuỗi con chung dài nhất như vậy giữa A và B. Tính giá trị của x + 10y =................. Chọn một đáp án.

86.

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

O(n)

O(log n)

$O(n^2)$

O(nlog n)

87.

Ba bước cơ bản của một thuật toán quy hoạch động bao gồm những giai đoạn nào? Chọn một đáp án.

Phân rã → Giải bài toán con → Tổng hợp lời giải

Phân rã → Giải bài toán con → Ghi nhận kết quả

Phân rã → Giải và lưu lời giải các bài toán con → Tổng hợp lời giải

Giải bài toán con → Lưu kết quả → Tổng hợp lời giải

Reset

Phân tích và thiết kế thuật toán (Tiếp)

Total questions: 87

Worksheet time: 44mins

Similar Resources on Wayground