Algorithm Design Analysis

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)

• Θ(n² )

• Θ(n² log(n))

• Θ(nlog(n))

Hàm nào sau đây không thuộc O(n²)?

• 15¹⁰.n +2020

• 2020.n^1.98 + 2002

• n³/log(n)

• 15¹⁰.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(n²)

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

• O(n)

• O(logn)

• O(n²)

• 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