Font size
WorksheetsAlgorithm Design Analysis
Total questions: 89
Worksheet time: 45mins
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
Tính độ phức tạp của giải thuật sau test()?
Θ(n)
Θ(n2 )
Θ(n2 log(n))
Θ(nlog(n))
Hàm nào sau đây không thuộc O(n2)?
1510.n +2020
2020.n1.98 + 2002
n3/log(n)
1510.nlog(n)
Cho đoạn code sau. Cho biết độ phức tạp của thuật toán trên
O(n)
O(nlog(n)
O(log(n))
O(n2)
Độ phức tạp của thuật toán tìm kiếm nhị phân là:
O(n)
O(logn)
O(n2)
O(n logn)
Chọn chốt ngẫu nhiên trong thuật toán QuickSort là:
Phần tử bên trái nhất được chọn làm chốt
Phần tử bên phải nhất được chọn làm chốt
Bất kỳ phần tử nào trong mảng cũng được chọn làm chốt
Phần tử có giá trị trung bình trong mảng được chọn làm chốt
Ba giai đoạn chính của thuật toán quy hoạch động là:
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ả
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à:
< b, c, a>
< c, a, b>
< b, c, a, a>
< b, c, b, a>
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 M1M2M3 với các kích thước d = (2, 5, 4, 3)
(M1)(M2M3), số phép tính 90
(M1)(M2M3), số phép tính 64
(M1M2)(M3), số phép tính 64
(M1M2)(M3), số phép tính 90
Gọi A1, A2, A3 và A4 là bốn ma trận có kích thước lần lượt là 10 x 5, 5 x 20, 20 x 10 và 10 x 5. Số phép nhân vô hướng tối thiểu cần thiết để tìm tích A1A2A3A4 bằng phương pháp nhân ma trận cơ bản là
1500
2000
500
100
Đ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?
Nó làm tăng cả hai, độ phức tạp về thời gian và độ phức tạp về không gian
Nó làm tăng độ phức tạp về không gian và giảm độ phức tạp về thời gian.
Nó làm tăng độ phức tạp về thời gian và giảm độ phức tạp về không gian
Nó làm giảm cả hai, độ phức tạp về thời gian và độ phức tạp về không gian
Khẳng định nào sau đây là phù hợp nhất của Chiến lược thiết kế Tham Lam?
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
Trong bài toán sắp xếp balo 0/1. Bước nào được thực hiện đầu tiên?
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.
Bốn ma trận M1, M2, M3 và M4 có kích thước lần lượt là p x q, q x r, r x s và s x 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 ((M1 X M2) X (M3 X M4)), tổng số phép nhân là pqr + rst + prt. Khi nhân với (((M1 X M2) X M3) X M4), 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à:
248000
44000
19000
25000
a
b
c
d
Cho dãy số A[0..9] gồm 10 số sau: 1 10 16 21 29 30 49 77 80 101. Áp dụng thuật toán tìm kiếm nhị phân để tìm phần tử có giá trị x=32 xem có trong dãy đã cho hay không? Hỏi 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]
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 quan như sau
T(n)=2T(n/2)+f(n)
T(n)=aT(n/b) + f(n).
T(n)=bT(n/a) + f(n).
T(n)=aT(n/a) + f(n).
a
b
c
d
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
Thành phần có vai trò quan trọng nhất tới quyết định tham lam
Tính chất lựa chọn (hàm) tham lam
Tính chất phức tạp của bài toán
Tính chất lựa chọn cấu trúc dữ liệu
Tính chất lựa chọn nghiệm
Bài toán Sinh các dãy nhị phân độ dài n có thể được giải bằng chiến lược nào sau đây?
Tham Lam
Vét cạn Quay lui
Quy hoạch động
Chia để trị
Cho biết đoạn mã giả sau là thuật toán quay lui giải bài toán nào?
Bài toán liệt kê các dãy nhị phân
Bài toán liệt kê hoán vị tổ hợp
Bài toán liệt kê tổ hợp chập k của n phần tử
Không phải bài toán nào
Thuật toán nào sau đây không dùng chiến lược thiết kế vét cạn để giải quyết?
Thuật toán tìm đường đi ngắn nhất Dijkstra
Thuật toán tìm cây khung cực tiểu Kruskal
Thuật toán tìm cây khung cực tiểu Prim
Thuật toán nhân chuỗi ma trận.
Độ phức tạp về thời gian và không gian của đoạn mã sau là bao nhiêu:
O(N 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 M), không gian O(N + M)
T(n)=2T(n/2)+2020 Khẳng định nào sau đây đúng?
Θ (n2)
Θ (n log n)
Θ (log n)
Θ (n)
Có Hàm đệ qui sau:
9
10
11
12
Xét các ma trận P, Q và R lần lượt là các ma trận 10 x 20, 20 x 30 và 30 x 40. 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
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 về thời gian trong trường hợp xấu nhất là gì?
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)
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)
Thời gian chạy là T(n) = T(n/2) + O(n) và độ phức tạp thời gian là O(nlogn)
Thời gian chạy là T(n) = T(n-1) + O(n) và độ phức tạp thời gian là O(n)
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(N*Sqrt(n))
Đ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?
Thời gian
Bộ nhớ
Câu lệnh
Thời gian và bộ nhớ
Công thức nào sau đây tính dãy con chung dài nhất
l(i,j) = 0, if either i=0 or j=0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] != Y[j-1]
expr1 = l(i, j-1)
expr1 = l(i-1, j) + 1
expr2 = max(l(i-1, j-1), l(i,j))
expr2 = max(l(i-1, j), l(i, j-1))
Độ phức tạp về thời gian của đoạn mã sau là bao nhiêu:
O(n)
O(nlog n)
O(n^2)
O(log n)
Độ phức tạp trường hợp xấu nhất của thuật toán Merge sort là gì?
O(nlog n)
O(n)
O(log n)
O(n^2)
Khẳng định nào sau đây đúng.
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))
Bài toán ba lô (hay cái túi) 0/1 có thể được giải bằng chiến lược nào sau đây?
Tham Lam và Quy hoạch động
Chia để trị và Quy hoạch động
Quy hoạch động
Chia để trị
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)
L[i, j] = Math.Max(L[i - 1, j-1], L[i, j - 1]);
L[i, j] = Math.Max(L[i - 1, j], L[i-1, j - 1]);
L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]);
L[i, j] = Math.Max(L[i, j], L[i-1, j - 1]);
Độ phức tạp về thời gian của hàm sau là (giả sử n > 0):
O(n)
O(nlog n)
O(n^2)
O(2^n)
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.
Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai đoạn chương trình P1 và P2 mà T1(n) = O(f(n)) và T2(n) = O(g(n)) thì thời gian thực hiện đoạn P1 rồi P2 tiếp theo sẽ là
T1(n) + T2(n) = O(max(f(n), g(n)))
T1(n) + T2(n) = O(f(n) hoặc g(n))
T1(n) + T2(n) = O(min(f(n), g(n)))
T1(n) + T2(n) = O(f(n) + g(n))
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))
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(2)
O(n-2)
O(n^2)
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:
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
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
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
Tại sao?
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
Chỉ ra công thức tính m[i,j] là số phép nhân ít nhất dãy ma trận Mi Mi+1 M i+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.
s=0; m[i,i]=0 ... m[i,j] = max{m[i,k] + m[k+1, j] + d[i-1]*d[k]*d[j]} ...
s=0; m[i,i]=0 ... m[i,j] = min{m[i,k] + m[k+1, j] + d[i-1]*d[k]*d[j]} ...
s=0; m[i,i]=0 ... m[i,j] = max{m[i,k] + m[k+1, j] + d[i-1]*d[k]*d[j]} ...
s=0; m[i,i]=0 ... m[i,j] = max{m[i,k] + m[k+1, j] + d[i-1]*d[k]*d[j]} ...
Để viết chương trình chỉ để sử dụng một số ít lần và cái 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 cái giá của chạy chương trình thì ta chọn thuật toán:
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
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?
Phần tử đầu tiên
Phần tử cuối cùng
Phần tử có giá trị trung bình của phần tử đầu, giữa và cuối
Phần tử ngẫu nhiên
Độ phức tạp của thời gian được đo lường như thế nào?
Bằng cách đếm số câu lệnh trong một thuật toán
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
Bằng cách đếm kích thước của dữ liệu đầu vào cho thuật toán
Bằng cách đếm kích thước của dữ liệu đầu ra cho thuật toán
Ký hiệu O-lớn f(n) = O(g(n)) mô tả điều gì?
f(n) luôn bằng g(n).
g(n) là chặn dưới của f(n).
f(n) tăng trưởng không nhanh hơn g(n) (chặn trên).
f(n) và g(n) có tốc độ tăng trưởng chính xác như nhau.
Cho f(n) = 2ⁿ và g(n) = n!. Khẳng định nào sau đây là đúng khi n rất lớn?
f(n) = O(g(n))
g(n) = O(f(n))
f(n) = Θ(g(n))
Không thể so sánh
Phương trình đệ quy T(n) = 2T(n/2) + n mô tả độ phức tạp của thuật toán nào sau đây?
Tìm kiếm nhị phân
Tháp Hà Nội
Sắp xếp trộn (Merge Sort)
Nhân ma trận thông thường
Độ phức tạp của thuật toán nhân hai ma trận vuông cấp n bằng phương pháp thông thường là gì?
O(n log n)
O(n²)
O(n³)
O(2ⁿ)
Trường hợp nào sau đây KHÔNG phải là một đặc tính của một thuật toán tốt?
Tính đúng đắn (Correctness)
Tính hiệu quả (Efficiency)
Tính dừng (Finiteness)
Tính phức tạp (Complexity)
Điều kiện cần để áp dụng thuật toán tìm kiếm nhị phân (Binary Search) là gì?
Mảng phải có số phần tử là lũy thừa của 2.
Mảng phải chứa các số dương.
Mảng phải được sắp xếp.
Mảng không được chứa phần tử trùng lặp.
Phương trình đệ quy nào mô tả đúng nhất thời gian chạy của thuật toán tìm kiếm nhị phân?
T(n) = 2T(n/2) + O(1)
T(n) = T(n/2) + O(1)
T(n) = T(n-1) + O(n)
T(n) = 2T(n-1) + O(1)
Bước "Chia" trong thuật toán QuickSort là gì?
Chia mảng thành hai nửa bằng nhau.
Chia mảng thành n mảng con, mỗi mảng 1 phần tử.
Tìm phần tử nhỏ nhất và lớn nhất.
Phân hoạch (partition) mảng dựa trên một phần tử chốt (pivot).
Thuật toán tìm cặp điểm gần nhất (Closest-Pair Problem) trên mặt phẳng 2D là một ứng dụng của:
Quy hoạch động
Thuật toán tham lam
Chia để trị
Quay lui
Tại sao bước "Tổng hợp" trong QuickSort lại rất đơn giản (thường không cần làm gì)?
Vì bước "Chia" đã thực hiện tất cả công việc.
Vì việc sắp xếp được thực hiện tại chỗ (in-place) trong quá trình phân hoạch.
Vì các mảng con luôn rỗng sau khi chia.
Vì QuickSort không phải là thuật toán chia để trị.
Ý tưởng cốt lõi của thuật toán Quay lui (Backtracking) là gì?
Luôn đưa ra lựa chọn tốt nhất tại mỗi bước.
Chia bài toán thành các bài toán con độc lập.
Thử tất cả các khả năng một cách có hệ thống và từ bỏ một hướng đi nếu nó không có triển vọng.
Giải các bài toán con trước rồi lưu kết quả vào bảng.
Thuật toán Tham lam (Greedy) hoạt động dựa trên nguyên tắc nào?
Tối ưu toàn cục (Global Optimum)
Tối ưu cục bộ (Local Optimum)
Lựa chọn ngẫu nhiên
Duyệt toàn bộ không gian trạng thái
Bài toán nào sau đây thường được giải bằng thuật toán Quay lui?
Bài toán 8 quân hậu (N-Queens Problem)
Bài toán tìm đường đi ngắn nhất (Dijkstra)
Bài toán sắp xếp
Bài toán nhân chuỗi ma trận
Điểm khác biệt cơ bản giữa Quay lui và Tham lam là gì?
Tham lam sử dụng đệ quy, Quay lui thì không.
Quay lui có thể "hủy bỏ" một quyết định, trong khi Tham lam thì không.
Quay lui luôn tìm ra lời giải tối ưu, Tham lam thì không.
Tham lam có độ phức tạp cao hơn Quay lui.
Đối với bài toán đổi tiền với các mệnh giá {1, 5, 10, 25}, chiến lược tham lam nào sau đây sẽ cho kết quả tối ưu?
Luôn chọn đồng xu có mệnh giá nhỏ nhất.
Luôn chọn đồng xu có mệnh giá lớn nhất mà không vượt quá số tiền còn lại.
Chọn ngẫu nhiên một đồng xu.
Thử tất cả các cách kết hợp.
Cây không gian trạng thái (State-space Tree) là một khái niệm liên quan chặt chẽ đến chiến lược nào?
Tham lam
Chia để trị
Quay lui
Quy hoạch động
Trong trường hợp nào thuật toán Tham lam có thể không đưa ra lời giải tối ưu?
Khi bài toán có cấu trúc con tối ưu.
Khi lựa chọn tối ưu cục bộ không dẫn đến tối ưu toàn cục.
Khi không gian tìm kiếm quá lớn.
Thuật toán Tham lam luôn đưa ra lời giải tối ưu.
Độ phức tạp thời gian của thuật toán liệt kê tất cả các hoán vị của n phần tử bằng Quay lui là gì?
O(n²)
O(n log n)
O(n!)
O(2ⁿ)
Hai đặc điểm chính của một bài toán có thể giải hiệu quả bằng Quy hoạch động là gì?
Cấu trúc con tối ưu và các bài toán con độc lập.
Tính chất lựa chọn tham lam và các bài toán con chồng lấn.
Cấu trúc con tối ưu và các bài toán con chồng lấn (overlapping subproblems).
Tính dừng và tính đúng đắn.
Quy hoạch động giải quyết vấn đề "các bài toán con chồng lấn" bằng cách nào?
Giải mỗi bài toán con nhiều lần để đảm bảo tính chính xác.
Bỏ qua các bài toán con chồng lấn.
Sử dụng một chiến lược tham lam để chọn một bài toán con duy nhất.
Lưu trữ kết quả của mỗi bài toán con sau khi giải lần đầu và tra cứu lại khi cần.
Phương pháp tiếp cận "Bottom-up" (Lập bảng) trong Quy hoạch động hoạt động như thế nào?
Bắt đầu từ bài toán lớn, dùng đệ quy để giải các bài toán con.
Bắt đầu từ các bài toán con nhỏ nhất, giải chúng rồi dùng kết quả đó để giải các bài toán con lớn hơn.
Chia bài toán thành các phần độc lập rồi giải riêng lẻ.
Chọn giải pháp tốt nhất tại mỗi bước mà không cần xem xét các bước tiếp theo.
Bài toán "Dãy con chung dài nhất" (Longest Common Subsequence - LCS) là một ứng dụng kinh điển của:
Thuật toán tham lam
Quay lui
Chia để trị
Quy hoạch động
Trong bài toán Nhân chuỗi ma trận, mục tiêu của quy hoạch động là gì?
Tìm ra ma trận kết quả cuối cùng.
Giảm số lượng ma trận cần nhân.
Tìm thứ tự đặt ngoặc để số phép nhân vô hướng là tối thiểu.
Tăng tốc độ nhân hai ma trận đơn lẻ.
So với cách tiếp cận đệ quy đơn thuần (naive recursion) để tính số Fibonacci thứ n, Quy hoạch động (dùng ghi nhớ hoặc lập bảng) cải thiện độ phức tạp từ O(2ⁿ) xuống còn bao nhiêu?
O(log n)
O(n)
O(n log n)
O(n²)
Trong bài toán "Cái túi 0-1" (0-1 Knapsack), dp[i][w] thường được định nghĩa là gì?
Giá trị lớn nhất có thể lấy được từ i vật phẩm đầu tiên với giới hạn trọng lượng là w.
Trọng lượng nhỏ nhất cần thiết để đạt được giá trị i với w vật phẩm.
Số cách để chọn i vật phẩm sao cho tổng trọng lượng là w.
Liệu có thể chọn vật phẩm thứ i với trọng lượng w hay không.
Điểm khác biệt cốt lõi giữa Quy hoạch động và Chia để trị là gì?
Quy hoạch động dùng vòng lặp, Chia để trị dùng đệ quy.
Quy hoạch động xử lý các bài toán con chồng lấn, trong khi Chia để trị xử lý các bài toán con độc lập.
Quy hoạch động chỉ giải các bài toán sắp xếp.
Chia để trị luôn nhanh hơn Quy hoạch động.
Cách tiếp cận "Top-down" với "Ghi nhớ" (Memoization) trong quy hoạch động có ưu điểm gì so với "Bottom-up"?
Luôn nhanh hơn.
Không sử dụng thêm bộ nhớ.
Chỉ tính toán các bài toán con thực sự cần thiết cho lời giải cuối cùng.
Dễ cài đặt hơn bằng vòng lặp.
Bài toán tìm "Dãy con tăng dài nhất" (Longest Increasing Subsequence - LIS) có thể được giải bằng quy hoạch động với độ phức tạp thời gian là:
A. O(n)
B. O(n log n)
C. O(n²)
D. Cả B và C đều là độ phức tạp của các thuật toán DP khác nhau cho bài toán này.
Ký hiệu nào được dùng để mô tả chặn dưới (lower bound) của một thuật toán?
O (O-lớn)
θ (Theta)
ω (Omega-nhỏ)
Ω (Omega-lớn)
Độ phức tạp không gian (Space Complexity) của một thuật toán đo lường điều gì?
Thời gian thuật toán cần để chạy xong.
Số lượng bộ nhớ tối đa mà thuật toán cần trong quá trình thực thi.
Số dòng code của thuật toán.
Số phép toán cơ bản mà thuật toán thực hiện.
Nếu một thuật toán có độ phức tạp O(1), điều đó có nghĩa là gì?
Thuật toán thực hiện đúng 1 phép toán.
Thời gian chạy của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào.
Thuật toán luôn chạy rất nhanh.
Thuật toán không sử dụng bộ nhớ.
Lựa chọn phần tử chốt (pivot) trong QuickSort ảnh hưởng đến yếu tố nào nhất?
Độ phức tạp không gian.
Tính đúng đắn của thuật toán.
Sự cân bằng của các bài toán con và hiệu suất thuật toán.
Loại dữ liệu mà thuật toán có thể sắp xếp.
Việc truy vết (backtracking) trên bảng kết quả của quy hoạch động dùng để làm gì?
Để tối ưu hóa thời gian thực hiện.
Để xây dựng lại lời giải cụ thể (ví dụ: chuỗi ngoặc, dãy con chung).
Để phân tích độ phức tạp của thuật toán.
Để tìm kiếm các giải pháp ngẫu nhiên.
Cho biết độ phức tạp thời gian hàm mũ theo ký hiệu big-O?
O(n)
O(n^2)
O(2^n)
O(log n)
T(n) = 8T(n/2) + 7n
Xác định độ phức tạp của hàm trên
Θ(n)
Θ(n^2)
Θ(log(n))
Θ(n^3) or Θ(nlog(n))
Tùy chọn nào trong số các tùy chọn đã cho 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 và f4?
Các hàm:
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nlog n
f4(n) = n^(log n)
f3, f2, f4, f1
f3, f2, f1, f4
f2, f3, f1, f4
f2, f3, f4, f1
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
Bài toán sắp xếp chọn và sắp xếp chèn
Bài toán tìm trình tự nhân tối ưu dãy ma trận
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
Có Hàm đệ qui sau:
Kết quả của hàm sau khi n = 5
14
15
16
17
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)
Tính độ phức tạp của giải thuật sau fun()?
Θ(n)
Θ(n²)
Θ(n²log(n))
Θ(nlog(n))
Cho biết bước phân rã giải bài toán dãy con chung dài 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?
1
2
n
(m+1)(n+1)
