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

Ghi nhớ (memoisation) là gì?

1. AViết chú thích bên cạnh từng dòng mã
2. BGiải phóng bộ nhớ sau khi một hàm trả về
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. DTự độ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

Một thuật toán O(n²) mất 1 giây khi n = 1000. Khoảng bao lâu khi n = 2000?

1. A2 giây
2. B8 giây
3. C4 giây
4. D1 giây

Sắp xếp chọn hoạt động như thế nào?

1. ANó chia mảng làm đôi rồi trộn lại
2. BNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
3. CNó liên tục tìm phần tử nhỏ nhất của phần chưa sắp xếp và hoán đổi nó lên đầu
4. DNó chèn từng phần tử vào phần đã sắp xếp đang lớn dần bằng cách dịch chuyển

Một hàm giai thừa đệ quy đơn giản fact(n) = n × fact(n − 1) dùng bao nhiêu không gian ngăn xếp?

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

Đệ quy của sắp xếp trộn có bao nhiêu tầng đối với một mảng n phần tử?

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

Độ phức tạp thời gian trong trường hợp xấu nhất của quicksort là gì?

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

Thuật toán nào tìm cây khung nhỏ nhất bằng cách liên tục thêm cạnh rẻ nhất không tạo chu trình?

1. AThuật toán Prim bắt đầu từ một nút
2. BFloyd–Warshall
3. CThuật toán Kruskal
4. DThuật toán Dijkstra

Độ phức tạp thời gian của: for i = 1 to n: for (j = i; j ≤ n; j = j + i) thực hiện công việc O(1) là gì?

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