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

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

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

Độ phức tạp thời gian của tìm kiếm nhị phân trên một mảng đã sắp xếp là gì?

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

Độ phức tạp thời gian của việc tìm giá trị lớn nhất trong một mảng chưa sắp xếp gồm n số là gì?

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

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

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

Phân tích khấu hao đo lường điều gì?

1. AChi phí của một thuật toán trên đầu vào tốt nhất
2. BChi phí kỳ vọng trên các đầu vào ngẫu nhiên
3. CChi phí của thao tác đơn lẻ tốn kém nhất ở bất kỳ đâu trong chuỗi
4. DChi phí trung bình mỗi thao tác trên một chuỗi thao tác xấu nhất

Tìm kiếm nhị phân cần khoảng bao nhiêu phép so sánh trong trường hợp xấu nhất trên một mảng đã sắp xếp có 1,000,000 phần tử?

1. AKhoảng 500,000
2. BKhoảng 100
3. CKhoảng 1,000
4. DKhoảng 20

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 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
2. BX quy dẫn về một bài toán trong P, và X thuộc NP
3. CX thuộc P, và X quy dẫn về SAT
4. DX không có thuật toán đa thức, và X quyết định được

Thuật toán Strassen nhân ma trận bằng 7 thay vì 8 phép nhân đệ quy các khối nửa kích thước. Thời gian chạy của nó là bao nhiêu?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 7}), khoảng n^2,81
4. DΘ(n³)