Cấu trúc dữ liệu và giải thuật: bài tập và câu hỏi ôn thi

Ký hiệu Big-O, thời gian chạy của các thuật toán thông dụng và sự đánh đổi giữa mảng, danh sách liên kết, cây, bảng băm và đồ thị.

Gói ôn nước rút (PDF)Bảng công thức, các bước phương pháp và bài tập có lời giải đầy đủ, sẵn sàng để in.

Các chủ đề trong môn học này

Với các vòng lặp lồng nhau, nhân số lần lặp; với các vòng lặp nối tiếp, giữ số hạng lớn hơn.
Biết chi phí tìm kiếm, chèn và xóa của từng cấu trúc dữ liệu.
Chia đôi dữ liệu vào ở mỗi bước cho thời gian logarit.

Thuật toán và độ phức tạpDễ

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

Hiện các gợi ý

Hiện đáp án và phần giải thích

O cho cận trên, Ω cho cận dưới và Θ cho cận chặt.

C · Big O

Cấu trúc dữ liệuTrung bình

Extract-min hoạt động thế nào trong đống min nhị phân?

Hiện các gợi ý

Hiện đáp án và phần giải thích

Phần tử cuối lấp chỗ trống ở gốc và được hoán đổi với con nhỏ hơn cho đến khi tính chất đống được thỏa, tốn O(log n).

B · Chuyển phần tử cuối lên gốc và đẩy xuống

“Luyện tập môn học này” trộn các bài từ mọi chủ đề của nó, giống một kỳ thi thật.
Mỗi bài tập có số liệu mới, nên bạn học phương pháp chứ không học thuộc đáp án.
Bí rồi? Hãy mở một gợi ý nhỏ trước, và chỉ xem giải thích đầy đủ khi cần.
Đề thi thử có tính giờ và không có gợi ý, và bạn nhận được điểm số cùng phần xem lại đầy đủ ở cuối.