Trọng tâm HL được hỗ trợ. Mục tiêu đánh giá 2027 đầu tiên; PDF chính thức trả về 403; brief thu hồi cũ là đánh giá cuối cùng 2026. Hướng dẫn còn lại, yêu cầu đánh giá và thực tiễn đều giữ nguyên các mức lưu trữ đã ghi.
Yêu cầu tiên quyết: đọc các đại lượng và đơn vị được nêu, sử dụng phép tính toán và các điều kiện mô hình dưới đây. Mỗi bài học sẽ phát triển phương pháp riêng trước khi chuyển giao độc lập.
Đây là các ví dụ giảng dạy gốc hoặc được ghi rõ là hư cấu, không phải là các phép đo thực tế hay các nghiên cứu đánh giá học viên đã hoàn tất.
8.2
Kiểu dữ liệu trừu tượng: hợp đồng thao tác
Giải thích hiện tượng này là gì?
Một mô phỏng hàng đợi cần xử lý mục đang chờ lâu nhất trước. Một ngăn xếp ưu tiên mục mới nhất, do đó hợp đồng thao tác rất quan trọng.
Bắt đầu bằng một dự đoán. Nêu rõ các đại lượng hoặc đặc điểm bạn sẽ so sánh, sau đó quyết định bằng chứng nào có thể phân biệt hai lời giải thích.
Xây dựng mô hình
Một kiểu dữ liệu trừu tượng (ADT) xác định các giá trị và thao tác độc lập với một triển khai cụ thể. Ngăn xếp là vào sau ra trước; hàng đợi là vào trước ra trước. Giao diện bộ thu thập cần có hành vi được xác định rõ ràng cho các trường hợp rỗng và thao tác không hợp lệ.
ngăn xếp (stack): Loại dữ liệu trừu tượng theo nguyên tắc sau cùng vào trước ra (LIFO); hàng đợi (queue): Loại dữ liệu trừu tượng theo nguyên tắc đầu vào trước ra (FIFO).
Chọn bằng chứng để kiểm định mô hình
Chọn cấu trúc phù hợp với mẫu truy cập yêu cầu. Độ phức tạp phụ thuộc vào triển khai và giả thiết: việc xóa mục đầu tiên khỏi mảng dịch chuyển khác với việc di chuyển con trỏ đầu trong hàng đợi.
Theo dõi chuỗi thao tác bằng tay, sau đó so sánh chương trình với các trạng thái mong đợi. Kiểm tra các trường hợp rỗng, đơn phần tử và các thao tác lặp lại. Mô tả hành vi tràn nếu dung lượng cố định.
Bắt đầu từ các đại lượng đã biết
Nêu các giá trị đã biết và đơn vị của chúng. Chọn công thức vì các giả thiết của nó phù hợp với trường hợp này, sau đó biến đổi trước khi thay số.
Đã biết: enqueue A, B và C, sau đó dequeue hai lần. A và B rời đi; C còn lại. Sau khi enqueue D, có hai mục đang chờ, C rồi đến D. Các phép push tương tự trên ngăn xếp sẽ loại bỏ C rồi đến B.
Ví dụ:
Hàng đợi bắt đầu rỗng, nhận 7 mục và loại bỏ 4. Tìm số lượng còn lại. Sử dụng cùng quy trình: các đại lượng đã biết → mô hình → mối liên hệ → thay thế → đơn vị và diễn giải.
Kiểm tra kết luận và giới hạn của nó
Một ADT không phải là bố trí bộ nhớ cụ thể. Hàng đợi không sắp xếp theo mức độ ưu tiên trừ khi hợp đồng của nó xác định là hàng đợi ưu tiên.
Quay trở lại quan sát ban đầu. Giải thích kết quả hỗ trợ điều gì, những điều kiện nào mà nó giả định, và một cách để kiểm chứng một giải thích cạnh tranh.
Cảnh báo:
Mọi hàng đợi tự động sắp xếp các mục theo mức độ ưu tiên. tuyên bố này là sai: Một ADT không phải là một bố trí bộ nhớ cụ thể. Hàng đợi sẽ chỉ sắp xếp theo mức độ ưu tiên nếu hợp đồng của nó định nghĩa một hàng đợi có thứ tự ưu tiên.
Tóm tắt:
Các loại dữ liệu trừu tượng (ADT): Hợp đồng thao tác: Chọn cấu trúc phù hợp với mô hình truy cập yêu cầu. Độ phức tạp phụ thuộc vào cách triển khai và các giả định: việc xóa phần tử đầu tiên khỏi mảng dịch chuyển khác với việc di chuyển con trỏ đầu trong hàng đợi.
Chuỗi thực thi chạy được và ranh giới
from collections import deque
queue = deque()
queue.extend(["A", "B"])
print(queue.popleft())
queue.append("C")
print(queue.popleft())
print(list(queue))
queue.clear()
print(queue.popleft() if queue else "EMPTY")
Kết quả mong đợi:
A
B
['C']
EMPTY
Xử lý từ bên trái tuân theo nguyên tắc FIFO. Guard trống rõ ràng xác định kết quả biên; deque.popleft nếu không có guard sẽ gây lỗi IndexError. Ngược lại, một ngăn xếp xử lý từ bên phải.
