Câu hỏi: CSD201 Cấu trúc dữ liệu và giải thuật – Bộ ôn tập thi lại số 1

Đáp án đúng: "Object dequeue() { if(isEmpty()) return(null); Node p = head; head=head.next;

if(head==null) tail=null;
return(p.info);

}". Hàng đợi cài bằng danh sách liên kết đơn lấy phần tử ra ở đầu, nên trình tự phải là giữ lại nút đầu để còn đọc dữ liệu, dời head sang nút kế tiếp, và vì tail vẫn trỏ tới nút vừa bị tách khi hàng đợi thành rỗng, phải kiểm head bằng null để đặt tail về null. "Object dequeue() { if(isEmpty()) return(null); Node p = head; head=head.next;

if(head==tail) tail=null;
return(p.info);

}" so head với tail: với hàng đợi hai phần tử, sau khi dời head thì head và tail cùng trỏ nút cuối nên nó xoá tail trong khi hàng đợi vẫn còn một phần tử; còn khi hàng đợi chỉ còn một phần tử thì head thành null mà tail vẫn trỏ nút cũ nên không được dọn. "Object dequeue() { if(isEmpty()) return(null); Node p = head; head=head.next; return(p.info); }" trả về đúng giá trị nhưng không bao giờ dọn tail, nên khi hàng đợi rỗng tail còn treo ở nút đã bị tách và lần thêm vào sau đó sẽ nối phần tử mới vào chỗ không còn ai trỏ tới. "Object dequeue() { if(isEmpty()) return(null); head=head.next;

if(head.next==null) tail=null;
return(head.info);

}" dời head trước khi đọc dữ liệu nên trả về phần tử thứ hai chứ không phải phần tử đầu, và khi hàng đợi chỉ còn một phần tử thì head thành null nên head.next gây lỗi truy cập null.

Đáp án đúng: "Node q = new Node(x); q.next = p.next; p.next = q;". Thứ tự hai lệnh gán là điểm cốt yếu: trước hết cho nút mới nhận phần đuôi cũ bằng q.next = p.next, sau đó mới cho p trỏ sang nút mới; nhờ vậy không mắt nối nào bị mất và chi phí là hằng số. Bản "p.next = new Node(x); p=p.next;" ghi đè p.next trước khi lưu lại nút kế, nên toàn bộ phần sau p rơi khỏi danh sách. Bản "Node q = new Node(x); q.next = null; p.next = q;" biến nút mới thành nút cuối, cắt đứt mọi nút phía sau p dù đề nói rõ p có nút kế. Bản "Node q = new Node(x); p.next = q; q.next = p.next;" đảo thứ tự: sau lệnh đầu thì p.next đã là q, nên lệnh sau gán q.next = q tạo vòng tự trỏ và phần đuôi cũ mất hẳn.