400 câu Trắc nghiệm tổng hợp Cấu trúc dữ liệu và giải thuật có đáp án (Phần 1)
54 câu hỏi
Giải thuật đệ quy là:
Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả.
Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn.
Trong giải thuật của nó có lời gọi tới chính nó.
Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn.
Chọn đáp án D
Cho hàm đệ qui sau:
Function Factorial(n)
Begin
if n= 0 then Factorial:=1
else Factorial := n*Factorial(n-1); End;
Sau mỗi lần gọi đệ quy thì giá trị của n là:
Tăng lên 1
N=0
Giảm đi 1
N=1
Chọn đáp án D
Có Hàm đệ qui sau: Function Factorial(n)
Begin
if n=0 then Factorial:=1
else Factorial := n*Factorial(n-1); End;
Dòng lệnh "if n=0 then Factorial:=1" là:
Lặp vô hạn
Điều kiện dừng đệ quy
Điều kiện không thực hiện đệ quy
Lặp 1 lần
Chọn đáp án B
Có Hàm đệ qui sau giải bài toán gì?: Function Factorial(n)
Begin
if n=0 then Factorial:=1
else Factorial := n*Factorial(n-1); End;
Tính số cặp thỏ sau n tháng
Tính giai thừa n
Tính n^n (n mũ n).
Tính tích: 1*2*3*…*n
Chọn đáp án A
Có Hàm đệ qui sau: Function Factorial(n)
Begin
if n=0 then Factorial:=1
else Factorial := n*Factorial(n-1); End;
Kết quả bằng bao nhiêu khi n=3
6
9
2
8
Chọn đáp án A
Hàm đệ qui cho kết quả thế nào? Function Factorial(n)
Begin
Factorial := n*Factorial(n-1); End;
Lặp vô hạn vì không có điều kiện dừng
Tính giai thừa n
Tính số cặp thỏ sau n tháng.
Chương trình báo lỗi
Chọn đáp án A
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán được đặt ra như sau:
Các con thỏ không bao giờ chết.
Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con.
Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới. Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ 5 sẽ có bao nhiêu cặp?
9 cặp
5 cặp
12 cặp
10 cặp
Chọn đáp án B
Cho giải thuật đệ quy sau:
Function F(n)
Begin
if n<=2 then F:=1
else F := F(n-1) + F(n-2);
End;
Dòng lệnh “if n<=2 then F:=1” đóng vai trò:
=2>=2>
Điều kiện dừng đệ quy
Lặp 1 lần
Điều kiện không thực hiện đệ quy
Lặp vô hạn
Chọn đáp án A
Cho giải thuật đệ quy sau:
Function F(n:integer):integer;
Begin
if n<=2 then F:=1
else F := F(n-2) + F(n-1) End;
Khi n=4 kết quả của bài toán trên là:
=2>
3
8
11
10
Chọn đáp án A
Đặc điểm của giải thuật đệ quy:
Tất cả đều đúng
Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước.
Có một trường hợp đặc biệt, trường hợp suy biến Khi trường hợp này xảy ra thì bài toán còn lại sẽ được giải quyết theo một cách khác
Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
Chọn đáp án A
Giải thuật đệ quy của bài toán "Tháp Hà Nội" như sau:
Procedure Chuyen(n, A, B, C)
Begin
if n=1 then chuyển đĩa từ A sang C else begin
call Chuyen(n-1, a, C, B); call Chuyen(1, A, B, C); call Chuyen(n-1, B, A, C) ; end;
End;
Khi n=3 có bao nhiêu bước chuyển?
8 bước
14 bước
15 bước
16 bước
Chọn đáp án C
Danh sách tuyến tính là:
Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).
Danh sách mà quan hệ lân cận giữa các phần tử được xác định.
Danh sách dạng được lưu dưới dạng mảng.
Danh sách tuyến tính là một danh sách rỗng.
Chọn đáp án B
Ưu điểm của việc cài đặt danh sách bằng mảng:
việc truy nhập vào phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được (chỉ số), nên tốc độ nhanh và đồng đều đối với mọi phần tử.
Có thể thay đổi số lượng phần tử theo ý muốn của người dùng.
Có thể bổ sung hoặc xóa một phần tử bất kỳ trong mảng.
Tất cả các ý trên đều đúng.
Chọn đáp án A
Danh sách tuyến tính dạng ngăn xếp là:
Là một danh sách tuyến tính trong đó phép bổ sung sung một phần tử vào ngăn xếp được thực hiện ở một đầu, Và phép loại bỏ không thực hiện được.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở tại một vị trí bất kì trong danh sách.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được thực hiện ở một đầu , và phép loại bỏ được thực hiện ở đầu kia.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở một đầu gọi là đỉnh .
Chọn đáp án D
Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc:
FIFO( first in first out)
LILO(last in last out)
FOLO( fisrt out last out)
LIFO(last in first out)
Chọn đáp án D
Khi đổi một số nguyên từ hệ thập phân sang hệ nhị phân thì người ta dùng phép chia liên tiếp cho 2 và lấy các số dư (là các chữ số nhị phân) theo chiều ngược lại.
Cơ chế sắp xếp này chính là cơ chế hoạt động của cấu trúc dữ liệu:
Mảng (array)
Hàng đợi(Queue)
Ngăn xếp (stack)
Bản gCâu Record)
Chọn đáp án C
S là ngăn xếp , Phép toán thêm phần tử vào ngăn xếp Là Push, phép lấy ra một phần tử từ ngăn xếp là POP, thủ tục sau làm nhiệm vụ gì?
Procedure Chuyen_doi(N); While N <> 0 do
R := N mod 2; {tính số dư trong phép chia N cho 2} call PUSH(S, R);
N := N div 2; {thay N bằng thương của phép chia N cho 2} end;
While not Empty(S) do begin
call POP(S, R);
write(R); end
end.
ứng dụng ngăn xếp để đổi số N từ cơ số 10 sang cơ số 2
ứng dụng ngăn xếp để tính số dư trong phép chia N cho 2
ứng dụng ngăn xếp để Đưa giá trị N vào ngăn xếp và lấy ra giá trị N
ứng dụng ngăn xếp để thay N bằng thương của phép chia N cho 2
Chọn đáp án A
định nghĩa danh sách tuyến tính Hàng đợi (Queue)
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một phần tử được thực hiện ở tại một vị trí bất kì trong danh sách.
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được.
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung phần tử ở một đầu, gọi là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front).
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)
Chọn đáp án C
Hàng đợi còn được gọi là danh sách kiểu:
LOLO
FILO
LIFO
FIFO
Chọn đáp án D
Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là:
EMPTY(x).
TOP(x).
PUSH(x).
POP(x).
Chọn đáp án C
Để lấy loại bỏ một đối tượng ra khỏi Stack, thao tác thường dùng là: “
FULL(x)
EMPTY(x)
POP(x)
PUSH(x)
Chọn đáp án C
Để biểu diễn Stack, ta thường sử dụng kiểu dữ liệu nào sau đây?
Kiểu bản ghi
Danh sách móc nối và mảng dữ liệu
Danh sách móc nối
Mảng dữ liệu
Chọn đáp án B
Thao tác POP(x) dùng trong Stack là để:
Xóa bỏ một phần tử bất kì khỏi Stack
Xóa bỏ một dãy các phần tử ra khỏi Stack
Lấy phần tử đầu tiên ra khỏi Stack
Lấy một phần tử cuối cùng ra khỏi đỉnh Stack
Chọn đáp án D
Thao tác Push(x) dùng trong Stack là để:
Bổ sung một dãy các phần tử vào đỉnh Stack.
Bổ sung một phần tử bất kì vào Stack
Bổ sung một phần tử vào đỉnh Stack
Bổ sung một phần tử vào đầu Stack
Chọn đáp án C
Cho Stack gồm 5 phần tử {12, 5, 20, 23, 25}, trong đó 25 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 4 trong Stack ta phải làm thế nào?
POP(23),PUSH(25).
POP(25),PUSH(23)
POP(25),POP(23), PUSH(25)
POP(25),POP(23)
Chọn đáp án C
Cho Stack gồm 5 phần tử {12, 5, 20, 23, 25}, trong đó 25 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 5 trong Stack ta phải làm thế nào?
POP(25),POP(23), PUSH(23)
POP(25)
POP(23),PUSH(25)
POP(25),PUSH(23)
Chọn đáp án B
Cho Stack gồm 5 phần tử {12, 5, 20, 23, 25}, trong đó 25 là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 3 trong Stack ta phải làm thế nào?
POP(25), POP(23), POP(20), PUSH(23), PUSH(25)
POP(25), POP(23), PUSH(20), PUSH(25), PUSH(23)
POP(25), POP(23), POP(20)
POP(25), POP(23), POP(20), PUSH(25), PUSH(23)
Chọn đáp án A
Trong lưu trữ dữ liệu kiểu Stack, giải thuật sau thực hiện công việc gì? Procedure F(X)
Begin T:=T+1; S[T]:=X;
End;
Kiểm tra Stack có tràn không
Kiểm tra Stack có cạn không
Bổ sung một phần tử vào Stack
Loại bỏ một phân tử ra khỏi Stack
Chọn đáp án C
Trong lưu trữ dữ liệu kiểu Stack, giải thuật F chính là: Procedure F(X)
Begin T:=T+1; S[T]:=X;
End;
TOP
FULL
POP
PUSH
Chọn đáp án D
Trong lưu trữ dữ liệu kiểu Stack, giải thuật sau thực hiện công việc gì? Function P
Begin T:=T-1;
P:=S[t+1];
End;
Bổ sung một phần tử ra khỏi Stack
Kiểm tra Stack có cạn không
Loại bỏ một phần tử vào Stack
Kiểm tra Stack có tràn không
Chọn đáp án C
Trong lưu trữ dữ liệu kiểu Stack, giải thuật P chính là:
Function P Begin T:=T-1;
P:=S[t+1];
End;
NULL
PUSH
TOP
POP
Chọn đáp án D
Với đoạn mã sau, nếu n=13, trong Stack sẽ là:
While n<>0 do begin
R:=n mod 2; Push(R); n:=n div 2; end;
13
6
1101
1011
Chọn đáp án C
Với đoạn mã sau, nếu n=13, trong các phần tử được bổ sung vào Stack theo thứ tự:
While n<>0 do begin
R:=n mod 2; Push(R); n:=n div 2; end;
1 , 3 , 6
1 , 1 , 0 , 1
1 , 0 , 1 , 1
6 , 3 , 1
Chọn đáp án C
Với đoạn mã sau, nếu các phần tử được đưa vào Stack theo thứ tự " 1 1 0 1" thì các phần tử được loại khỏi Stack theo thứ tự nào?
While T>0 do begin
R:=POP(S[T]);
write(R); end;
1011
1101
1, 0 , 1 , 1
1, 1 , 0 , 1
Chọn đáp án C
Trong lưu trữ dữ liệu kiểu Queue (Q) dưới dạng mảng nối vòng, giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Điều kiện F=R=0 nghĩa là:
Queue rỗng
Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau không.
Queue tràn
Đặt phần tử đầu và phần tử cuối của Queue bằng 0
Chọn đáp án A
Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Khi thêm một phần tử vào Queue, thì R và F thay đổi thế nào?
F=F+1, R không thay đổi
F không thay đổi, R=R+1
F=F-1, R không thay đổi
F không thay đổi, R=R-1
Chọn đáp án B
Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Khi loại bỏ một phần tử vào Queue, thì R và F thay đổi thế nào?
F=F-1, R không thay đổi
F không thay đổi, R=R+1
F không thay đổi, R=R-1
F=F+1, R không thay đổi
Chọn đáp án D
Giải thuật sau thực hiện việc gì? Procedure Q(x)
Begin
if R=n then R:=1 else R:=R+1; if F=R then begin write(‘full’) return
end ; Q[R]:=X;
if F=0 then F:=1; End;
Kiểm tra Queue có rỗng không
Loại bỏ một phần tử vào Queue
Bổ sung một phần tử vào Queue
Kiểm tra Queue có tràn không
Chọn đáp án C
Giải thuật sau thực hiện việc gì? Function Q:kiểu dữ liệu;
Begin
if F=0 then begin write(‘NULL’) return
end;
Y:=Q[F];
if F=R then begin F:=R:=0;
return end;
if F=n then F:=1 else F:=F+1; Q:=Y;
End;
Bổ sung một phần tử vào Queue
Kiểm tra Queue có tràn không
Loại bỏ một phần tử vào Queue
Kiểm tra Queue có rỗng không
Chọn đáp án C
Giải thuật sau thực hiện việc gì? Function P(l:ds): boolean;
Begin
P:= (l.last =0); End;
Kiểm tra danh sách có rỗng không
Cho phần tử cuối cùng trong danh sách bằng 0
Làm rỗng danh sách
Không có đáp án nào đúng.
Chọn đáp án A
Giải thuật sau thực hiện việc gì? Procedure P( l:ds);
Begin l.last := 0; End;
Cho phần tử cuối cùng trong danh sách bằng 0
Kiểm tra danh sách có rỗng không
Làm rỗng danh sách”
Không có đáp án nào đúng.
Chọn đáp án C
Giải thuật sau thực hiện việc gì? Procedure F(x,P: integer);
Begin
for i:= (l.last+1) downto (P+1) do l.s[i]:=l.s[i-1];
l.s[P]:=x; l.last:=l.last + 1; End;
Chèn phần tử x vào vị trí P trong danh sách
Bổ sung phần tử x vào đầu danh sách
Bổ sung phần tử x vào cuối danh sách
Không đáp án nào đúng
Chọn đáp án A
Giải thuật sau thực hiện việc gì? Procedure F(P: integer);
Begin
for i:= P to (l.last-1) do l.s[i]:=l.s[i+1]; l.last:=l.last -1;
End;
Không đáp án nào đúng
Xoá phần tử cuối cùng trong danh sách
Xoá một phần tử tại vị trí P trong danh sách
Xoá phần tử đầu tiên trong danh sách
Chọn đáp án C
Trong biểu diễn dữ liệu dưới dạng cây, cấp của cây chính
Tổng số nút trên cây
Cấp cao nhất của nút gốc
Cấp cao nhất của nút lá
Cấp cao nhất của một nút trên cây
Chọn đáp án D
Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 gọi là:
Lá
Không có đáp án nào đúng
Phần tử cuối cùng trong cây
Gốc
Chọn đáp án A
Mỗi nút trong cây có tối đa:
3 nút con
1 nút con
2 nút con
Nhiều nút con
Chọn đáp án D
Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị trí của nút con trái là:
2*i + 1
i+1
2*i
i-1
Chọn đáp án C
Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị tí của nút con phải là:
2*i
i+1
i-1
2*i + 1
Chọn đáp án D
Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là 3 thì vị trí tương ứng của nút con sẽ là:
6
7
4
6 và 7
Chọn đáp án D
Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là 3 thì vị trí tương ứng của nút con trái sẽ là:
7
6
2
4
Chọn đáp án B
Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là 3 thì vị trí tương ứng của nút con phải sẽ là:
7
4
6
2
Chọn đáp án A
Duyệt cây nhị phân theo thứ tự trước được thực hiện theo thứ tự:
Duyệt cây con trái theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.
Thăm gốc, duyệt cây con trái theo thứ tự trước, duyệt cây con phải theo thứ tự trước.
Duyệt cây con trái theo thứ tự sau, thăm gốc trước, duyệt cây con phải theo thứ tự sau.
Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau.
Chọn đáp án B
Duyệt cây nhị phân theo thứ tự giữa được thực hiện theo thứ tự:
Thăm gốc, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự giữa.
Duyệt cây con trái theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.
Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau.
Duyệt cây con trái theo thứ tự giữa, thăm gốc, duyệt cây con phải theo thứ tự giữa.
Chọn đáp án D
Duyệt cây nhị phân theo thứ tự sau được thực hiện theo thứ tự:
Duyệt cây con trái theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.
Thăm gốc, duyệt cây con trái theo thứ tự sau, duyệt cây con phải theo thứ tự sau.
Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau.
Duyệt cây con trái theo thứ tự sau, duyệt cây con phải theo thứ tự sau, thăm gốc.
Chọn đáp án D
