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
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 đề. Trang 2/3 — câu 21–40.
Danh sách câu hỏi
while(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 a, int n)
{ if(n == 0) return(1);
int t =fun(a,n/2);
if(n%2==0)
return(t*t);
else
return(t*t*a);
}For the call fun(3, 3), how many calls to fun will be made, including the original call?
int fun(int a, int n)
{ if(n == 0) return(1);
int t =fun(a,n/2);
if(n%2==0)
return(t*t);
else
return(t*t*a);
}What is the value of fun(3, 2)?
void quiz(int n)
{if (n > 1)
{quiz(n);
quiz(n);
}
System.out.print("* ");
}What will happen if the statement quiz(5); is run?
void fun(int n)
{if (n < 0)
{System.out.println(“-“);
fun(-n);
}
else if(n<24)
System.out.println(n);
else
{fun(n/24);
System.out.println(n%15);
}
}What values of n are directly handled by the stopping (base) case?
int fun(int n)
{if (n < 0)
return(fun(-n));
else if(n<5)
return(2);
else
return(n*fun(n/2));
}What is the value of fun(6)?
void foo(int n)
{int m = n/2;
int k = n%2;
if (m > 0)
{foo(m);
}
System.out.print(k + " ");
}What is the output when the statement foo(13); is run?
void fun(int n)
{int m = n/3;
int k = n%3;
System.out.print(k + " ");
if(m > 0)
{fun(m);
}
}What is the output when the statement fun(17); is run?
Node search(int x)
{ Node p = root;
while(p!=null && p.info != x)
{ if(x<p.info) p = p.left;
else p=p.right;
}
return(p);
}The complexity of this algorithm is:
O(n^2)O(n).O(log n).O(nlog n)void preOrder(Node p)
{ if (p != null) { visit(p); preOrder(p.left); preOrder(p.right); }
}void preOrder(Node p)
{ if (p != null) { preOrder(p.left); visit(p); preOrder(p.right); }
}void preOrder(Node p)
{ if (p == null) { visit(p); preOrder(p.left); preOrder(p.right); }
}void preOrder(Node p)
{ visit(p); preOrder(p.left); preOrder(p.right); }Đáp án đúng: "
void preOrder(Node p) {
if (p != null) {
visit(p);
preOrder(p.left);
preOrder(p.right);
}
}". Tiền thứ tự nghĩa là thăm gốc trước rồi mới xuống nhánh trái, sau đó nhánh phải, nên lệnh thăm phải đứng trước cả hai lời gọi đệ quy; thêm vào đó điều kiện p khác null chính là chỗ dừng, nó chặn lời gọi đi vào cây rỗng. Cách viết "
void preOrder(Node p) {
if (p != null) {
preOrder(p.left);
visit(p);
preOrder(p.right);
}
}" đặt lệnh thăm giữa hai lời gọi nên cho ra thứ tự trung tố, với cây tìm kiếm thì in dãy tăng dần chứ không phải tiền thứ tự. Cách viết "
void preOrder(Node p) {
if (p == null) {
visit(p);
preOrder(p.left);
preOrder(p.right);
}
}" đảo điều kiện thành p bằng null, tức chỉ làm việc khi con trỏ rỗng, nên nó thăm một nút không tồn tại và không bao giờ đi xuống cây thật. Cách viết "
void preOrder(Node p) {
visit(p);
preOrder(p.left);
preOrder(p.right);
}" đúng trật tự thăm nhưng bỏ hẳn chỗ dừng, mỗi lá vẫn gọi tiếp vào hai con rỗng nên đệ quy lún vô hạn và chương trình đổ vì truy cập trên con trỏ rỗng.