Câu hỏi: CSD201 Cấu trúc dữ liệu và giải thuật – Bộ ôn tập cuối kỳ số 3
50 câu trắc nghiệm kèm lời giải của môn CSD201 - Cấu trúc dữ liệu và giải thuật, xếp đúng thứ tự trong đề.
Danh sách câu hỏi
Node f = head;
while(f.next != null) f = f.next;
f.next = p.next;Node f = head;
while(f != p) f = f.next;
f.next = p.next;Node f = head;
while(f.next != p) f = f.next;
f.next = p.next;Node f = head;
while(f != null) f = f.next;
f.next = p.next;Đáp án đúng: "Node f = head; while(f.next != p) f = f.next; f.next = p.next;". Danh sách liên kết đơn không có liên kết lùi, nên muốn tháo p ta buộc phải dò từ head để tìm nút tiền nhiệm; điều kiện f.next khác p dừng đúng lúc f là nút đứng ngay trước p, và f.next bằng p.next nối tiền nhiệm sang hậu nhiệm, đưa p ra khỏi chuỗi. Vì vậy "Node f = head; while(f.next != null) f = f.next; f.next = p.next;" sai vì vòng lặp chạy tới nút cuối rồi cho nút cuối trỏ về một nút nằm phía trước nó, tạo vòng tròn trong danh sách mà p vẫn còn nguyên. "Node f = head; while(f != p) f = f.next; f.next = p.next;" sai vì vòng lặp dừng khi f chính là p, nên f.next bằng p.next là gán cho chính nó, không liên kết nào thay đổi. "Node f = head; while(f != null) f = f.next; f.next = p.next;" sai vì vòng lặp chỉ kết thúc khi f đã bằng null, nên lệnh f.next ngay sau đó ném NullPointerException.
O(n^2)O(n)O(log n)O(1)Node p1,p2; p1 = p.next;
p2 = p1.next;
p.next = p2;
if(p2!=null) p2.prev=p;Node f = head;
while(f.next != p) f = f.next;
f.next = p.next;Node p1,p2; p1 = p.next;
p2 = p1.next;
p.next = p2;
if(p2!=null) p2.prev=p;int x = 13;
Node f = p.prev; //prev is a link to predecessor node
Node q = new Node(x);
q.prev = f; q.next = p;
f.next = q; p.prev = q;int x = 9;
Node q = new Node(x);
q.prev=null;
q.next = head;
head.prev = q;
head = q;Object pop()
{ if(isEmpty()) return(null);
Node p = head;
head=head.next;
if(head==tail) tail=null;
return(p.info);
}Object pop()
{ if(isEmpty()) return(null);
Node p = head;
head=head.next;
return(p.info);
}Object pop()
{ if(isEmpty()) return(null);
Node p = head;
head=head.next;
if(head==null) tail=null;
return(p.info);
}Object pop()
{ if(isEmpty()) return(null);
head=head.next;
if(head.next==null) tail=null;
return(head.info);
}Đáp án đúng: "Object pop() { if(isEmpty()) return(null); Node p = head; head=head.next;
if(head==null) tail=null;
return(p.info);}". Phép lấy ra phải giữ nút đỉnh vào biến p trước khi dời head rồi trả về p.info, và khi head trở thành null tức danh sách vừa hết thì phải xoá luôn tail để hai con trỏ không còn chỉ vào nút đã bỏ. Bản "Object pop() { if(isEmpty()) return(null); Node p = head; head=head.next;
if(head==tail) tail=null;
return(p.info);}" kiểm sai điều kiện: khi danh sách còn đúng một nút thì head và tail trùng nhau một cách hợp lệ, xoá tail lúc đó làm hỏng một danh sách chưa rỗng. Bản "Object pop() { if(isEmpty()) return(null); Node p = head; head=head.next; return(p.info); }" trả về đúng giá trị nhưng bỏ quên tail, nên khi ngăn xếp rỗng tail vẫn trỏ vào nút đã bị loại. Bản "Object pop() { if(isEmpty()) return(null); head=head.next;
if(head.next==null) tail=null;
return(head.info);}" dời head trước rồi trả head.info nên trả về phần tử thứ hai chứ không phải đỉnh vừa lấy, và khi danh sách chỉ có một nút thì head thành null nên head.next gây lỗi con trỏ rỗng.
void enqueue(Object x)
{ Node p = new Node(x);
p.next = null;
tail.next = p;
tail = p;
}void enqueue(Object x)
{ Node p = new Node(x);
p.next = null;
if(isEmpty())
head = tail = p;
else
{ tail.next = p;
tail = p;
}
}void enqueue(Object x)
{ Node p = new Node(x);
p.next = null;
if(isEmpty())
head = tail = p;
else
tail.next = p;
}void enqueue(Object x)
{ Node p = new Node(x);
p.next = null;
if(isEmpty())
head = tail = p;
else
tail = p;
}Đáp án đúng: "
void enqueue(Object x) {
Node p = new Node(x);
p.next = null;
if(isEmpty()) head = tail = p;
else {
tail.next = p;
tail = p;
}
}". Thêm vào đuôi hàng đợi phải xử lý hai tình huống: khi danh sách rỗng chưa có tail nào để nối vào nên cả head và tail cùng trỏ vào nút mới; khi đã có phần tử thì nối tail.next = p để nút mới vào sau cùng rồi dời tail = p để đuôi luôn là nút cuối thật. Bản này làm đủ cả hai, còn p.next = null giữ cho đuôi kết thúc đúng. Phương án "
void enqueue(Object x) {
Node p = new Node(x);
p.next = null;
tail.next = p;
tail = p;
}" bỏ hẳn nhánh rỗng, nên khi hàng đợi chưa có gì thì tail là null và lệnh tail.next gây lỗi truy cập null. Phương án "
void enqueue(Object x) {
Node p = new Node(x);
p.next = null;
if(isEmpty()) head = tail = p;
else tail.next = p;
}" nối đúng nhưng quên dời tail, nên lần thêm sau lại nối vào đúng nút cũ và phần tử vừa thêm trước đó bị mất khỏi chuỗi. Phương án "
void enqueue(Object x) {
Node p = new Node(x);
p.next = null;
if(isEmpty()) head = tail = p;
else tail = p;
}" chỉ dời tail mà không nối tail.next, nên nút mới trôi ra ngoài danh sách và đi từ head sẽ không bao giờ tới được nó.
while(there are more characters in the word to read){read a character if a character is '*' then pop and write the poped character to the screen
else
push the character into the stack
}What is written to the screen for the input "GoodA**fter*****Noo*n" ?
while(there are more characters in the word to read){read a character if a character is '*' then pop the stack
else
push the character into the stack
}
while(the stack is not empty)pop and write the poped character to the screen What is written to the screen for the input "Good**Mor*ni***ng" ?
gnMoGgnMoognoMoGoMngInteger pop()
{if (isEmpty()) return;
return((Integer) pool.remove(pool.size()-1));
}Integer pop()
{ if (isEmpty()) return(null);
return((Integer) pool.remove(pool.size()-1));
}void pop(Integer x)
{ if (isEmpty()) return(null);
pool.remove(pool.size()-1);
}Integer pop()
{ if (isEmpty()) return(null);
return(pool.remove(pool.size()));
}Đáp án đúng: "Integer pop() {
if (isEmpty()) return(null);
return((Integer) pool.remove(pool.size()-1));}". Đỉnh ngăn xếp là cuối danh sách, nên lấy ra phải xoá phần tử ở chỉ số pool.size()-1 rồi trả về chính phần tử vừa xoá; khi ngăn xếp rỗng thì trả null để người gọi biết không có gì lấy, vẫn khớp kiểu trả về Integer đã khai báo. Phương án "Integer pop() {
if (isEmpty()) return;
return((Integer) pool.remove(pool.size()-1));}" dùng lệnh return trống trong hàm có kiểu trả về nên không biên dịch được. Phương án "
void pop(Integer x) {
if (isEmpty()) return(null);
pool.remove(pool.size()-1);
}" vừa trả giá trị trong hàm void, vừa nhận tham số vô nghĩa, lại không đưa phần tử lấy ra cho người gọi. Phương án "Integer pop() {
if (isEmpty()) return(null);
return(pool.remove(pool.size()));}" lấy ở chỉ số pool.size(), vượt quá chỉ số hợp lệ cuối cùng là pool.size()-1, nên luôn gây lỗi chỉ số ngoài phạm vi.
void pop(Integer x)
{ if (isEmpty()) return(null);
pool.remove(pool.size()-1);
}Integer pop()
{ if (isEmpty()) return(null);
return((Integer) pool.removeLast());
}Integer pop()
{if (isEmpty()) return;
return((Integer) pool.remove(pool.size()-1));
}Integer pop()
{ if (isEmpty()) return(null);
return((Integer) pool.remove(pool.size()));
}Đáp án đúng: "Integer pop() {
if (isEmpty()) return(null);
return((Integer) pool.removeLast());}". Cuối danh sách là đỉnh ngăn xếp, và java.util.LinkedList có sẵn removeLast() tháo nút cuối rồi trả về phần tử đó, đúng ngữ nghĩa pop là lấy ra và trả về; kiểu trả Integer cho phép trả null khi rỗng, còn phép ép sang Integer hợp với việc danh sách thô lưu Object. Vì vậy "
void pop(Integer x) {
if (isEmpty()) return(null);
pool.remove(pool.size()-1);
}" sai vì hàm void không được return(null), lại nhận tham số và không trả gì nên phần tử đỉnh không bao giờ tới tay người gọi. "Integer pop() {
if (isEmpty()) return;
return((Integer) pool.remove(pool.size()-1));}" sai vì hàm khai báo trả Integer mà có lệnh return trống, trình biên dịch báo thiếu giá trị trả về. "Integer pop() {
if (isEmpty()) return(null);
return((Integer) pool.remove(pool.size()));}" sai vì chỉ số hợp lệ chỉ đến size()-1, nên remove(pool.size()) luôn vượt biên và ném IndexOutOfBoundsException.
while(there are more characters in the word to read){read a character if a character is '*' then dequeue and write the dequeued character to the screen
else
enqueue the character into the queue
}What is written to the screen for the input "Goo**dAft***erno*on" ?
GoodATGoodAfGoodAEfAdooGwhile(there are more characters in the word to read){read a character if a character is '*' then dequeue the queue
else
enqueue the character into the queue
}How the queue looks like after processing the input "Goo**dMor***ning**"?
int fun(int n)
{if(n==0)
return(1);
else
return(n + fun(n/2));
}What is the output when the statement:
System.out.println(fun(9));is run?
void fun(int n)
{if(n<=0)
return;
else if (n<7)
{System.out.print(" " + n);
fun(n-2);
}
else
fun(n-2);
}What is the output when the statement fun(9); is run?