Phiếu bài tập Thuật toán và độ phức tạp có đáp án

Thuật toán là gì?

1. AMột cấu trúc dữ liệu lưu trữ các số
2. BMột ngôn ngữ lập trình được thiết kế để viết các công thức toán học
3. CBất kỳ chương trình máy tính nào có giao diện đồ họa
4. DMột dãy hữu hạn các bước được xác định rõ để giải một bài toán

Ghi nhớ (memoisation) là gì?

1. AGiải phóng bộ nhớ sau khi một hàm trả về
2. BTự động chuyển đệ quy thành vòng lặp tương đương để không cần ngăn xếp lời gọi
3. CLưu kết quả của các lời gọi hàm để các lời gọi lặp lại được trả lời từ bộ nhớ
4. DViết chú thích bên cạnh từng dòng mã

Một vòng lặp bắt đầu với i = 1 và nhân đôi i mỗi lần lặp cho đến khi i > n. Nó chạy bao nhiêu lần lặp?

1. AKhoảng n / 2
2. BKhoảng n
3. CKhoảng n²
4. DKhoảng log₂ n

Thuật toán sắp xếp nào là ổn định?

1. ASắp xếp chọn (phiên bản điển hình)
2. BSắp xếp vun đống
3. CSắp xếp trộn
4. DQuicksort (phiên bản tại chỗ điển hình)

Vì sao quy hoạch động không đem lại sự tăng tốc thực sự cho sắp xếp trộn?

1. ASắp xếp trộn đã là O(n)
2. BSắp xếp trộn không có cấu trúc đệ quy
3. CQuy hoạch động chỉ hoạt động trên các bài toán đồ thị, không dùng được trên mảng
4. DCác bài toán con của nó không chồng lặp, nên không có gì để tái sử dụng

Độ phức tạp thời gian của việc tính số Fibonacci thứ n bằng bảng từ dưới lên là gì?

1. AO(log n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(n)

Kỹ thuật nào cho thời gian chạy kỳ vọng O(n log n) của quicksort trên mọi đầu vào?

1. ALuôn chọn phần tử đầu tiên
2. BChọn pivot đồng đều ngẫu nhiên
3. CSắp xếp đầu vào trước khi chạy quicksort
4. DChỉ dùng đệ quy ở phía bên trái

Vì sao mọi tìm kiếm dựa trên so sánh trong một mảng đã sắp xếp cần Ω(log n) phép so sánh trong trường hợp xấu nhất?

1. AMọi phần tử phải được so sánh ít nhất một lần
2. BMỗi phép so sánh mất thời gian logarit
3. CMột cây quyết định với n kết quả có thể phải có độ sâu ít nhất log₂ n
4. DTìm kiếm nhị phân là thuật toán khả dĩ duy nhất, và nó cần log₂ n phép so sánh