Ban đầu, hàng đợi là rỗng. Em hãy cho biết giá trị của phần tử ở đầu front

Giải Chuyên đề Tin 12 Bài 4: Kiểu dữ liệu hàng đợi - Kết nối tri thức

Câu hỏi 2 trang 17 Chuyên đề Tin học 12: Ban đầu, hàng đợi là rỗng. Em hãy cho biết giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán enqueue(Q,2); enqueue(Q,19); dequeue(Q), enaqueue (Q, 6); dequeue(Q); enqueue(Q, 9); enqueue(Q,1).

Lời giải:

Để xác định giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán trên hàng đợi (queue), ta sẽ theo dõi từng phép toán một cách chi tiết. Giả sử hàng đợi ban đầu có dung lượng đủ lớn để chứa tất cả các phần tử được thêm vào mà không cần phải xử lý trường hợp tràn (overflow).

Ban đầu, hàng đợi là rỗng:

front = 0

rear = -1

size = 0

Các bước thực hiện tuần tự các phép toán như sau:

1. enqueue(Q, 2)

Thêm 2 vào cuối hàng đợi.

rear tăng lên 0.

size tăng lên 1.

queue = [2]

front = 0

rear = 0

2.  enqueue(Q, 19)

Thêm 19 vào cuối hàng đợi.

rear tăng lên 1.

size tăng lên 2.

queue = [2, 19]

front = 0

rear = 1

3.  dequeue(Q)

Lấy 2 ra từ đầu hàng đợi.

front tăng lên 1.

size giảm xuống 1.

queue = [2, 19] (phần tử tại front không còn được sử dụng)

front = 1

rear = 1

4.  enqueue(Q, 6)

Thêm 6 vào cuối hàng đợi.

rear tăng lên 2.

size tăng lên 2.

queue = [2, 19, 6]

front = 1

rear = 2

5.  dequeue(Q)

Lấy 19 ra từ đầu hàng đợi.

front tăng lên 2.

size giảm xuống 1.

queue = [2, 19, 6] (phần tử tại front không còn được sử dụng)

front = 2

rear = 2

6. enqueue(Q, 9)

Thêm 9 vào cuối hàng đợi.

rear tăng lên 3.

size tăng lên 2.

queue = [2, 19, 6, 9]

front = 2

rear = 3

7. enqueue(Q, 1)

Thêm 1 vào cuối hàng đợi.

rear tăng lên 4.

size tăng lên 3.

queue = [2, 19, 6, 9, 1]

front = 2

rear = 4

- Sau khi thực hiện tuần tự các phép toán, trạng thái của hàng đợi sẽ như sau:

queue = [2, 19, 6, 9, 1]

front = 2 (phần tử ở đầu hàng đợi là 6)

rear = 4 (phần tử ở cuối hàng đợi là 1)

Lời giải bài tập Chuyên đề Tin 12 Bài 4: Kiểu dữ liệu hàng đợi hay, ngắn gọn khác:

• Khởi động trang 16 Chuyên đề Tin học 12: Từ các bài học trước, em đã biết viết chương trình đơn giản để sử dụng các hàm cơ bản ....

• Hoạt động 1 trang 16 Chuyên đề Tin học 12: Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn hàng đợi bằng mảng một chiều ....

• Câu hỏi 1 trang 17 Chuyên đề Tin học 12: Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết ....

• Hoạt động 2 trang 17 Chuyên đề Tin học 12: Đọc, trao đổi để biết các hàm cơ bản của hàng đợi được cài đặt bằng danh sách ....

• Câu hỏi 1 trang 19 Chuyên đề Tin học 12: Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết ....

• Câu hỏi 2 trang 19 Chuyên đề Tin học 12: Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi ....

• Luyện tập 1 trang 19 Chuyên đề Tin học 12: Sửa lại hàm dequeue(Q) và front(Q) trong chương trình trên như sau ....

• Luyện tập 2 trang 19 Chuyên đề Tin học 12: Viết hàm length(Q) trả về số phần tử của hàng đợi ....

• Vận dụng 1 trang 19 Chuyên đề Tin học 12: Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n) ....

• Vận dụng 2 trang 19 Chuyên đề Tin học 12: Cho trước mảng T gồm N phần tử T[0], T[1], ..., T[N-1]. Hãy viết hàm thiết lập hàng đợi ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi

• Chuyên đề Tin học 12 Bài 6: Cây nhị phân

• Chuyên đề Tin học 12 Bài 7: Cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 8: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin học 12 Bài 9: Các thuật toán duyệt trên cây tìm kiếm nhị phân

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều

---