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

Ký hiệu nào mô tả cận trên của tốc độ tăng?

1. ABig Omega
2. BLittle omega
3. CBig O
4. DBig Theta

Thời gian chạy trong trường hợp xấu nhất của một thuật toán mô tả điều gì?

1. AThời gian kỳ vọng nó mất trên một đầu vào ngẫu nhiên kích thước n
2. BThời gian nó mất trên đầu vào nhỏ nhất
3. CThời gian tối đa nó mất trên mọi đầu vào kích thước n
4. DThời gian nó mất trên một máy tính chậm

Độ phức tạp không gian đo lường:

1. ALượng bộ nhớ một thuật toán cần khi đầu vào tăng
2. BSố dòng mã
3. CKích thước vật lý của máy tính
4. DDung lượng đĩa của tệp chương trình sau khi được biên dịch

Đệ 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

Trong bài toán chọn hoạt động, quy tắc tham lam nào luôn cho số hoạt động không chồng lấn tối đa?

1. AChọn hoạt động bắt đầu sớm nhất
2. BChọn hoạt động có ít chồng lấn nhất trước, rồi lặp lại với các hoạt động tương thích
3. CChọn hoạt động ngắn nhất trước
4. DChọn hoạt động kết thúc sớm nhất, rồi lặp lại với các hoạt động tương thích

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(n)
2. BO(1)
3. CO(n²)
4. DO(log n)

Độ 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 log n)
2. BO(n √n)
3. CO(n²)
4. DO(n)

Phải chứng minh hai điều nào để chứng tỏ một bài toán quyết định X là NP-đầy đủ?

1. AX quy dẫn về một bài toán trong P, và X thuộc NP
2. BX không có thuật toán đa thức, và X quyết định được
3. CX thuộc P, và X quy dẫn về SAT
4. DX thuộc NP, và một bài toán NP-đầy đủ đã biết quy dẫn về X trong thời gian đa thức