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ố 2

Đáp án đúng: "Object dequeue() {

if (isEmpty()) return(null);
return(pool.removeFirst());

}". Đề quy ước đầu danh sách chính là đầu hàng đợi, mà hàng đợi lấy ra ở đầu, nên phép dequeue phải gỡ phần tử đầu; với java.util.LinkedList thì removeFirst làm đúng việc đó trong thời gian hằng số, lại trả về đối tượng vừa gỡ nên kiểu trả về Object là hợp. "Object dequeue() {

if (isEmpty()) return(null);
return(pool.removeLast());

}" sai vì removeLast gỡ ở cuối, biến hàng đợi thành ngăn xếp vào sau ra trước. "

void dequeue(Object x) {
  if (isEmpty()) return(null);
  pool.remove(pool.size()-1);
}

" sai ngay ở chữ ký: hàm void không được trả về giá trị null, dequeue lại không cần tham số đầu vào, và nó cũng gỡ ở cuối. "Object dequeue() {

if (isEmpty()) return;
return(pool.remove(pool.size()-1));

}" sai vì lệnh return trống không biên dịch được trong hàm có kiểu trả về Object, ngoài ra nó vẫn gỡ phần tử cuối thay vì phần tử đầu.

Đáp án đúng: "Object pop() {

if (isEmpty()) return(null);
return(pool.remove(pool.size()-1));

}". Cuối danh sách được coi là đỉnh ngăn xếp, mà java.util.ArrayList truy cập theo chỉ số nên phần tử đỉnh có chỉ số size()-1; lệnh remove(pool.size()-1) vừa tháo phần tử đó vừa trả chính nó về, đúng ngữ nghĩa pop là lấy ra và trả về, và xoá ở cuối mảng không phải dồn phần tử nào nên vẫn rẻ. Vì vậy "Object pop() {

if (isEmpty()) return;
return(pool.remove(pool.size()-1));

}" sai vì hàm khai báo trả Object mà lại có lệnh return trống, không biên dịch được. "

void pop(Object x) {
  if (isEmpty()) return(null);
  pool.remove(pool.size()-1);
}

" sai vì hàm void không thể return(null), lại nhận tham số và không trả gì nên phần tử ở đỉnh bị mất luôn thay vì được giao cho người gọi. "Object pop() {

if (isEmpty()) return(null);
return(pool.remove(pool.size()));

}" sai vì chỉ số hợp lệ chỉ tới size()-1, nên remove(pool.size()) luôn ném IndexOutOfBoundsException.

Đáp án đúng: "

void push(Object x) {
  Node p = new Node(x);
  p.next = head;
  head=p;
}

". Với danh sách liên kết đơn mà nút đầu là đỉnh ngăn xếp, phép đẩy phải làm đúng hai việc theo đúng thứ tự: cho nút mới trỏ sang đỉnh cũ bằng p.next = head, rồi dời chính đỉnh về nút mới bằng head = p; nhờ vậy toàn bộ phần dưới của ngăn xếp vẫn liền mạch. Bản "

void push(Object x) {
  Node p = new Node(x);
  p.next = head;
}

" thiếu lệnh dời đỉnh, nên head vẫn chỉ vào nút cũ và nút vừa tạo không ai trỏ tới, ngăn xếp coi như không thay đổi. Bản "

void push(Object x) {
  Node p = new Node(x);
  p.next = null;
  head=p;
}

" cắt liên kết tới phần cũ: head chỉ vào nút mới nhưng nút mới trỏ vào null, nên mọi phần tử đã đẩy trước đó mất hết. Bản "

void push(Object x) {
  Node p = new Node(x);
  p.next = head;
  head=p.next;
}

" gán head bằng p.next, mà p.next vừa được đặt bằng head, nên head giữ nguyên giá trị cũ và nút mới bị bỏ rơi.