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

Ba bước của một thuật toán chia để trị là gì?

1. ASắp xếp, tìm kiếm, trả về
2. BĐọc, tính toán, ghi
3. CĐoán, kiểm tra, lặp lại
4. DChia, trị, kết hợp

Big O của 3n² + 5n + 2 là gì?

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

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 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
3. CNó liên tục hoán đổi các phần tử kề nhau đang sai thứ tự
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

Độ phức tạp thời gian của: for i = 1 to n: (j = 1; while j < n: j = j × 2) là gì?

1. AO(n log n)
2. BO(log n)
3. CO(n)
4. DO(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(log 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 log₂ n
2. BKhoảng √n
3. CKhoảng n / 2
4. DKhoảng n

Công thức truy hồi T(n) = 2T(n/2) + n log n có nghiệm là gì?

1. AΘ(n)
2. BΘ(n²)
3. CΘ(n log² n)
4. DΘ(n log n)

Độ phức tạp thời gian của việc xây dựng một đống nhị phân từ n phần tử chưa sắp xếp bằng phương pháp từ dưới lên là gì?

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