Đề kiểm tra giữa kỳ Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

Câu 1: Cho danh sách kiểu mảng có 10 phần tử. Khi thêm phần tử
vào vị trí 4 trong danh sách, vòng lặp dịch chuyển tịnh tiến nội dung
các phần tử L→Elements[i]=L→Element[i+1] sẽ thực hiện: A. 4 lần B. 5 lần C. 6 lần D. Tất cả đều sai
Câu 2: Giải thuật là gì:
A. Sử dụng khi có vấn đề giải quyết
B. Hay đi kèm với cấu trúc dữ liệu
C. Thường được coi là vấn đề cốt lỗi ngành CNTT
D. Là một chuỗi các chỉ thị được định nghĩa rõ ràng dùng để giải một
lớp các bài toán có sử dụng thuật toán
Câu 3: Cho Stack gồm 5 phần tử {12,5,20,23,25}, trong đó 25 là
phần tử ở đỉnh Strack. Để lấy ra phần tử thứ 4 (từ đáy lên) trong
Stack và giữ các phần tử khác trong Stack ta phải làm như thế nào? A. POP(25),POP(23)
B. POP(12),POP(5),POP(20),POP(23) C. POP(25),POP(23),PUSH(25) D. POP(25),PUSH(23)
Câu 4: Cho đoạn mã nguồn ngôn ngữ lập trình C sau: int ham12(unsigned int n) { if(n<=1) return n;
else return ham12(n-1) + ham 12(n-2); }
Biết hàm trả lại giá trị 987 hãy cho biết ham12(n) được gọi giá trị đúng là? A. n=20 B. n=16 C. n=24 D. n=12
Câu 5: Một thuật toán bao gồm 2 thao tác độc lập có độ phức tạp
tính toán là f(n) và g(n). Độ phức tạp của giải thuật là: A.f(n)*g(n) B.Max(f(n),g(n)) C.Min(f(n),g(n)) D.f(n)+g(n)
Câu 6: Cho biểu thức dạng trung tổ sau A+B*C/D-G*H, biểu thức
dạng hậu tố tương ứng là: A. ABC*D/+GH*- B. ABC*D/+-GH* C. ABC*D/GH*-+ D. ABC*/D+-GH*
Câu 7: Cho hàm độ phức tạp tính toán của một giải thuật như sau:
f(n) = -24nlogn + n2 - 4n + 6 n ∈ N A. O(n2) B. O(nlogn) C. O(logn) D. O(n3)
Câu 8: Cho biểu thức hậu tố Balan như sau: a b – c / d – b / +
Hãy tính giá trị biểu thức trên sử dụng ngăn xếp biết a = 25, b = 5, c = 4 và d = 19 A.8 B.6 C.15 D.12
Câu 9: Cho hàm đệ quy có định nghĩa bước cơ sở và bước đệ qui như sau:
Bước cơ sở: F(0)=1, F(1)=1
Bước đệ quy: F(n)=F(n-1)+F(n-2) n>2
Hãy cho biết kết quả của hàm F(17) là A.1597 B.2584 C.987 D.610
Câu 10: Giả thiết ta thực hiện chuỗi các thao tác cơ bản đối với cấu
trúc dữ liệu danh sách liên kết gồm các số nguyên như sau:
InsertHead(4) → InsertHead(1) → InsertLast(3) → InsertLast(5) → DeleteHead() → InsertHead(7)
Hãy cho biết kết quả của chuỗi thao tác là danh sách nào dưới đây
Ghi chú: → dùng ký hiệu liên kết con trỏ giữa các ô dữ liệu số nguyên A. 7→4→3→5 B. 7→4→5→3 C. 1→4→3→7 D. 1→4→3→5
Câu 11: Giả sử cho hàm enq(a) là hàm thực hiện nạp a vào hàng đợi
và hàm deq() là hàm thực hiện lấy phần tử ra khỏi hàng đợi. Giả sử
cho dãy các thao tác sau đây, biết rằng hàng đợi ban đầu được khởi tạo rỗng:
enq(5), enq(3), deq(), enq(2), enq(8), deq(), enq(9), enq(1), deq(),
enq(7), enq(6), deq(), deq(), enq(4), deq(), deq().
Hãy viết ra dãy các phần tử của hàng đợi (chỉ rõ vị trí đầu và cuối
của hàng đợi) sau khi thực hiện thao tác A.{5,2} B.{5,3,2,8,9} C.{5,3} D.{5,2,8,9}
Câu 12: Thao tác nào sau đây được thực hiện hiệu quả hơn bởi danh
sách liên kết đôi so với danh sách được liên kết đơn?
A. Xóa một nút có vị trí đã cho
B. Tìm kiếm một phần tử trong danh sách chưa được sắp xếp
C. Đảo một nút sau nút có vị trí nhất định
D. Duyệt qua danh sách để xử lý từng nút
Câu 13: Đoạn chương trình sau cho ra kết quả nào? int f(int x){ if(x==2) return 2; else { printf(“+”); f(x-1);} } int main(){ int n; n= f(6); printf(“%d”,n); return 0; } A.2 B.+++++2 C.++++2 D.+++++
Câu 14: Cho đoạn mã nguồn ngôn ngữ lập trình C của ham1 như sau: int ham1(unsigned int n){ int i,j,s=0; for(i=0; i < n; i++) for(j = i;j < n; j++)
s+=i;//Câu lệnh cần đếm return S; }
Hãy cho biết câu lệnh S+=i được thực hiện bao nhiêu lần khi gọi ham1(10)? A.110 B.100 C.55 D.50
Câu 15: Khi thêm phần tử vào hàng đợi cài đặt bằng mảng vòng thì:
A. Front luôn không đổi, Rear = Rear - 1
B. Front luôn không đổi, Rear = Rear + 1
C. Front = Front + 1, Rear không thay đổi
D. Front = Front - 1, Rear không thay đổi
Câu 16: Cho đoạn mã nguồn ngôn ngữ lập trình C sau: int ham1(char str[], int n){ int i,tp=0;
for(i=0; i < n; i++) tp = tp*5 + (str[i]-48); return tp; }
Biết giá trị trả lại khi gọi ham1(str,n) là 260, hãy cho biết tham số đầu vào là đúng? A. str=”2004”,n=4 B. str=”3474”,n=4 C. str=”2020”,n=4 D. str=”3744”,n=4
Câu 17: Hãy tính giá trị của ký pháp hậu tố sau: 6 3 6 + 5*90/- A.5.5 B.4 C.-4 D.Kết quả khác
Câu 18: Đoạn chương trình sau cho ra kết quả nào? int f(int n) { if(n>0) returnn(n+f(n-2)); } int main() { int n=10; printf(“%d”,f(n)); return 0; } A.28 B.10 C.80 D.30
Câu 19: Khi đổi một số nguyên tố từ hệ thập phân sang hệ nhị phân
thì người ta dùng phép chia liêp 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: A. Stack (Ngăn xếp) B. Hàng đợi (Queue)
C. Danh sách liên kết đơn D. Bản ghi
Câu 20: Giả sử cho hàm push(a) là hàm thực hiện nạp a vào ngăn
xếp và hàm pop() là hàm lấy phần tử ra khỏi ngăn xếp. Giả sử cho
dãy thao tác sau đây, biết rằng ngăn xếp ban đầu được khởi tạo rỗng:
push(5),push(3),pop(),push(2),push(8),pop(),pop(),pop(),push(9),pus
h(1),pop(),push(7),push(6),pop(),pop(),push(4),pop().
Hãy viết ra dãy phần tử của ngăn xếp (vị trí đầu ngăn xếp ở bên trái
nhất) sau khi thực hiện các thao tác A.{9} B.{5,3,2,8,9,1,7,6,4} C.{5} D.{4,6,7,9}
Câu 21: Cho đoạn mã nguồn ngôn ngữ lập trình C của hàm như sau:
unsigned int ham(unsigned int n) { if(n==0) return 0;
else return ham(n-1)+ham(n-1);//Đếm số phép toán cộng }
Hãy cho biết phép cộng được thực hiện bao nhiêu lần sau khi gọi ham(6)? A.22 B.63 C.85 D.74
Câu 22: Cho chương trình sau: #include #include struct Node { int val; struct Node*next; }*head; int get_max() {
struct Node*temp = head->next; int max_num = temp->val; while(temp!=0) { if(temp->val > max_num) max_num = temp->val; temp = temp->next; } return max_num; } int get_min() {
struct Node*temp = head->next; int min_num = temp->val; while(temp!=0) { if(temp->val < min_num) min_num = temp->val; temp = temp->next; } return min_num; } int main() {
int i,n = 9, arr[9]={8,3,3,4,5,2,5,6,7}; struct Node *temp, *newNode;
head = (struct Node*)malloc(sizeof(struct Node)); head -> next =0; temp = head; for(i=0;i{
newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->next = 0; newNode->val = arr[i]; temp->next=newNode; temp = temp->next; } int max_num = get_max(); int min_num = get_min();
printf("%d %d", max_num, min_num); return 0; } A.O(n) B.O(nlogn) C.O(n2) D.O(logn)
Câu 23: Biểu thức nào thể hiện hàng đợi cài đặt bằng mảng theo vòng tròn đang đầy: A. Front=1 B. Front=(rear+1)%MAXSIZE C. Front=(front+1)%MAXSIZE D. Rear=(rear+1)%MAXSIZE
Câu 24: Nhân tố nào là nhân số chính ảnh hưởng đến thời gian tính của một giải thuật A. Máy tính B. Chương trình dịch
C. Kích thước của dữ liệu đầu vào của thuật toán D. Thuật toán sử dụng
Câu 25: Cho đoạn mã nguồn ngôn ngữ lập trình C sau: int ham15(unsigned int n){ if(n==0) return 0; else return 3+ham15(n/2); }
Biết hàm đệ quy được gọi 5 lần hãy cho biết ham15(n) được gọi giá trị đúng là? A. n=12 B. n=16 C. n=10 D. n=8
Câu 26: Cho giải thuật cài đặt bằng đoạn chương trình sau: sum = 0; for(i=0;isum++; val = 1; for(j=0;jval = val * j; A. O(n) B. O(nlogn) C. O(n2) D. O(n3)
Câu 27: Ưu điểm của việc cài đặt danh sách bằng mảng:
A. Có thể bổ sung hoặc xóa phần tử bất kỳ trong mảng
B. Việc truy nhập vào phần tử trong mảng dựa trên chỉ số nên tốc độ
thực hiện nhanh và đồng đều với mọi phần tử trong mảng
C. Có thể thay đổi hoặc bổ sung phần tử theo ý muốn người dùng D. Tất cả đều sai
Câu 28: Định nghĩa nào là đúng với danh sách liên kết:
A. Danh sách liên kết là tập hợp các phần tử mà đặt kề cận với nhau trong vùng nhớ
B. Danh sách liên kết là cấu trúc dữ liệu dạng cây
C. Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một
sự nối kết với nhau thông qua vùng liên kết của chúng
D. Danh sách liên kết là cấu trúc dữ liệu định nghĩa
Câu 29: Thuật toán tìm kiếm nhị phân có thể áp dụng được trên:
A. Mảng đã sắp xếp thứ tự
B. Danh sách liên kết đã sắp thứ tự
C. Mảng không cần có thứ tự
D. Danh sách liên kết không có thứ tự
Câu 30: Biểu thức hậu tố của biết thức sau: (A+B)*(C*D-E)*F/G là: A. AB+CD*E-FG/** B. AB+CD*E-F**G/ C. AB+CD*E-*F*G/ D. AB+CDE*-*F*G/
Câu 31: Thao tác nào dưới đây thực hiện trên hàng đợi (queue):
A. Thêm phần tử vào lối sau
B. Thêm phần tử vào lối trước
C. Loại bỏ phần tử ở lối sau
D. Thêm và loại bỏ phần tử tại vị trí bất kỳ
Câu 32: Có bao nhiêu phép so sánh sẽ được thực hiện để sắp xếp
mảng arr = {1,5,3,8,2} bằng cách sử dụng thuật toán sắp xếp bầy chim (pigeonhole sort)? A. 5 B. 7 C. 9 D. 0
Câu 33: 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 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? A. 16 B. 15 C. 8 D. 14
Câu 34: Đâu là dấu hiệu cho biết danh sách liên kết L là rỗng: A. (L->left==NULL) B. (L->next==NULL) C. (L==NULL) D. (L->infor==NULL)
Câu 35: Cho hàm độ phức tạp tính toán của một giải thuật sau. Hãy
cho biết giải thuật thuộc lớp độ phức tạp tính toán nào sau đây? f(n)=34n3 -24n2 +4logn n ∈ N A. O(logn) B. O(n2) C. O(n3) D. O(nlogn)
Câu 36: Cho đoạn mã nguồn ngôn ngữ lập trình C của hàm như sau:
unsigned int ham5(unsigned int n) { if(n==0) return 0;
else return 2*ham5(n/2);// Đếm số phép toán nhân }
Hãy cho biết phép toán nhân * được thực hiện bao nhiêu lần sau khi gọi ham5(10)? A. 4 B. 5 C. 6 D. 3
Câu 37: Sử dụng định lý thợ để xác định xem hàm truy hồi của giải thuật đệ quy sau: T(n) = 2T(n/2) +10n n > n0 A. O(2n) B. O(nlogn) C. O(n2) D. O(n)
Câu 38: 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 làm nhiệm vụ gì? Procedure Thu_tuc(N); While N <> 0 do
R := N mod 2; {tính số dư trong phép chia N cho 2} 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 beginPOP(S,R); write(R); end end.
A. Thay N bằng thương phép chia cho 2
B. Đổi số từ hệ thập phân sang hệ nhị phân
C. Đưa N vào ngăn xếp và lấy ra thương của N chia 2 D. Tính lũy thừa N^2
Câu 39: Điều nào sau đây là không đúng về danh sách liên kết đôi?
A. Có thể duyệt danh sách theo 2 chiều
B. Nó đòi hỏi nhiều không gian bộ nhớ hơn danh sách liên kết đơn
C. Thao tác chèn và xóa một mode lâu hơn danh sách liên kết đơn
D. Cài đặt danh sách liên kết đôi dễ hơn so với danh sách liên kết đơn
Câu 40: Kết luận 1000n2 - 6n + 7 = O(n2) là đúng hay sai? A. Đúng B. Sai Câu 41: int f(int n){ int s = 1; int i = 1; int a = 2; while(s <= n){ s = s * a; i++; } } A. O(logn) B. O(n) C. O(nlogn) D. O(n2)
Câu 42: Cho hai hàm thể hiện độ phức tạp tính toán của hai thuật toán: f1(n) = n1/2 f2(n) = 1000log(n)
Hỏi hàm nào có độ tăng nhanh hơn?
A. Hàm f1 tăng nhanh hơn f2 B. Hàm f2 tăng nhanh hơn f1
Câu 43: Kết luận nào sau đây đúng với ngăn xếp?
A. Phần tử nào được đưa vào ngăn xếp đầu tiên thì sẽ được lấy ra cuối cùng.
B. Phần từ nào đưa vào ngăn xếp cuối cùng thì sẽ được lấy ra cuối cùng.
Câu 44: Kết luận nào sau đây đúng với hàng đợi?
A. Phần tử nào được đưa vào hàng đợi cuối cùng thì sẽ được lấy ra cuối cùng.
B. Phần tử nào được đưa vào hàng đợi đầu tiên thì sẽ được lấy ra cuối cùng.
Câu 45: Mỗi nút (Node) của danh sách liên kết có cấu trúc như sau
(biểu diễn bằng mã giả) Node{
value;// giá trị của nút
next;// con trỏ đến phần tử tiếp theo }
Xét hàm sau (viết bằng mã giả): F(h,v){ T = 0;
For(p = h; p != NULL; p = p.next){ T = T*v + p.value; } Return T; }
h là con trỏ trỏ đến nút đầu của danh sách liên kết mà các nút có giá
trị theo thứ tự từ đầu đến cuối là 4, 2, 1. Hỏi hàm F(h,2) cho kết quả bằng bao nhiêu? A. 13 B. 21 C. 18 D. 31
Câu 46: S là một ngăn xếp ban đầu rỗng trong đó có 2 thao tác là
S.PUSH(x) – đưa phần từ x vào ngăn xếp và S.POP() – lấy ra một
phần tử khỏi ngăn xếp và trả về phần tử này. Hỏi đoạn chương trình
sau đây (mã giả) hiển thị kết quả gì? main(){
Khởi tạo ngăn xếp S ban đầu là rỗng;
For i = 1 to 5 do S.PUSH(i+2);
e1 = S.POP(); S.PUSH(8); e2 = S.POP(); print(e2); } A. 8 B. 7 C. 6 D. 5
Câu 47: Phát biểu "Trong việc lưu trữ các đối tượng, chỉ khi nào
khóa của các đối tượng là số nguyên dương thì mới áp dụng được cơ
chế bảng băm" là đúng hay sai? A. Đúng B. Sai
Câu 48: Thuật toán Dijkstra để giải bài toán nào?
A. Tìm đường đi ngắn nhất từ 1 đỉnh đến tất cả các đỉnh còn lại trên
đồ thị trọng số trên cạnh không âm
B. Tìm đường đi ngắn nhất từ 1 đỉnh đến tất cả các đỉnh còn lại trên
đồ thị trọng số trên cạnh bất kỳ
C. Tìm cây khung nhỏ nhất của đồ thị vô hướng trọng số trên cạnh
D. Tìm luồng cực đại trên mạng
Câu 49: Hãy cho biết số nghiệm nguyên dương của phương trình
2x1 + 4x2 + 3x3 + 5x4 = 60 thỏa mãn điều kiện x1 + x2 = 6 A. 13 B. 11 C. 16 D. 23
Câu 50: Mỗi nút của 1 danh sách liên kết đơn có cấu trúc dữ liệu như sau: typedef struct Node{ int id; // id cua nut
struct Node* next; // con tro tro den nut tiep theo }Node;
Hỏi hàm proc sau đây thực hiện công việc gì? Node* proc(Node* f, int v){ if(f==NULL) return NULL; if(f->id == v){
Node* tm = f; f = f->next; free(tm); return f; }
f->next = proc(f->next,v); return f; }
A. Thực hiện loại bỏ nút đầu tiên (kể từ trái qua phải) có id bằng v ra
khỏi danh sách có con trỏ đầu là f, trả về con trỏ đến đầu danh sách thu được
B. Loại bỏ hết tất cả các nút có id bằng v ra khỏi danh sách liên kết
có con trỏ đầu là f, trả về con trỏ đến đầu danh sách thu được.
C. Tìm và trả về con trỏ đến nút có id bằng v
Câu 51: Mỗi nút của 1 danh sách liên kết đơn có cấu trúc dữ liệu như sau: typedef struct Node{ int id; struct Node* next; }Node;
Hỏi hàm proc sau đây thực hiện công việc gì? Node* proc(Node* f, int v){ if(f==NULL) return NULL; if(f->id == v){ Node* tm = f; f = f->next;
free(tm); f = proc(f,v); return f; }
f->next = proc(f->next,v); return f; }
f->next = proc(f->next,v); return f; }
A. Thực hiện loại bỏ nút đầu tiên (kể từ trái qua phải) có id bằng v ra
khỏi danh sách có con trỏ đầu là f, trả về con trỏ đến đầu danh sách thu được
B. Loại bỏ hết tất cả các nút có id bằng v ra khỏi danh sách liên kết
có con trỏ đầu là f, trả về con trỏ đến đầu danh sách thu được.
C. Tìm và trả về con trỏ đến nút có id bằng v
Câu 52: Mỗi nút của 1 danh sách liên kết đơn có cấu trúc dữ liệu như sau: typedef struct Node{ int id; struct Node* next; }Node;
Hàm makeNode sau đây thực hiện cấp phát bộ nhớ cho 1 nút của danh sách Node* makeNode(int v){
Node* p = (Node*)malloc(sizeof(Node));
p->id = v; p->next = NULL; return p; }
Hỏi hàm proc sau đây thực hiện công việc gì? Node* proc(Node* f, int v){
if(f == NULL) return makeNode(v); Node* p = makeNode(v); p->next = f; return p; }
A. Tạo mới 1 nút có id bằng v và chèn vào đầu danh sách có con trỏ
đầu là f, trả về con trỏ đến đầu danh sách thu được.
B. Tạo mới 1 nút có id bằng v, chèn vào cuối danh sách liên kết có
con trỏ đầu là f, trả về con trỏ đến đầu danh sách thu được.
C. Tìm và trả về nút đầu tiên (kể từ trái) có id bằng v của danh sách
liên kết có con trỏ đầu là f.
Câu 53: Kết luận nào sau đây đúng với danh sách liên kết.
A. Các phần tử trong danh sách liên kết được cấp phát kế tiếp nhau trong bộ nhớ.
B. Các phần tử của danh sách liên kết không được cấp phát kế tiếp
nhau trong bộ nhớ, các phần tử được liên kết với nhau thông qua
con trỏ (mỗi phần tử sẽ có 1 trường con trỏ trỏ tới phần tử tiếp theo trong danh sách).
Câu 54: Độ phức tạp thời gian tính của hàm sau đây: int f(int n){ int s = 0; int a = 1; int i = 1; while(s <= n){ s = s + a; a = a + 1; i++; } } A. O(logn) B. O(n) C. O(n1/2) D. O(nlogn)
Câu 55: Xác định độ phức tạp thời gian tính của hàm sau: int f(int n){ int s = 0; int a = 1; int i = 1; while(s <= n){ s = s + a; a = 2*a; i++; } } A. O(logn) B. O(n) C. O(n1/2) D. O(nlogn)
Câu 56: Cho T là 1 BST thu được bằng cách chèn liên tiếp dãy khóa
sau vào (bắt đầu từ cây rỗng): 3, 4, 8, 20, 5, 1, 15, 2.
Thứ tự các khóa thu được trong phép duyệt theo thứ tự trước là: A. 3, 1, 2, 4, 8, 5, 20, 15 B. 1, 2, 3, 4, 5, 8, 15, 20 C. 5, 1, 4, 8, 15, 20, 3, 2
Câu 57: Cho T là 1 BST thu được bằng cách chèn liên tiếp dãy khóa
sau vào (bắt đầu từ cây rỗng): 3, 4, 8, 20, 5, 1, 15, 2.
Thứ tự các khóa thu được trong phép duyệt theo thứ tự sau là: A. · 2, 1, 5, 15, 20, 8, 4, 3 B. · 1, 2, 3, 4, 5, 8, 15, 20 C. · 20, 15, 8, 5, 4, 3, 2, 1
Câu 58: Cho T là 1 BST thu được bằng cách chèn liên tiếp dãy khóa
sau vào (bắt đầu từ cây rỗng): 3, 4, 8, 20, 5, 1, 15, 2.
Thứ tự các khóa thu được trong phép duyệt theo thứ tự giữa là: A. · 5, 8, 1, 4, 3, 15, 20, 2 B. · 1, 2, 3, 4, 5, 8, 15, 20 C. · 15, 20, 8, 3, 4, 2, 1, 5
Câu 59: Cho T là 1 BST thu được bằng cách chèn liên tiếp dãy khóa
sau vào T (bắt đầu từ cây rỗng): 3, 4, 8, 20, 5, 1, 15, 2.
Hỏi kết luận nào sau đây là đúng? A. 5 là con phải của 4 B. 5 là con trái của 8
C. 5 và 3 là hai nút anh em.
Câu 60: Kết luận nào sau đây đúng với thuật toán sắp xếp lựa chọn?
A. Độ phức tạp trong tình huống tốt nhất là O(n) và trong tình huống tồi nhất là O(n2)
B. Độ phức tạp trong tình huống tốt nhất là O(n) và tình huống tồi nhất là O(nlogn)
C. Độ phức tạp trong tình huống tốt nhất là O(n2) và tồi nhất cũng là O(n2)
D. Độ phức tạp trong tình huống tốt nhất là O(nlogn) và tình huống tồi nhất là O(n2)
Câu 61: Kết luận nào sau đây đúng?
A. Cây AVL là cây nhị phân tìm kiếm trong đó số nút của cây con trái
và số nút của cây con phải của mỗi nút đều bằng nhau.
B. Cây AVL là cây nhị phân tìm kiếm cân bằng trong đó chênh lệch
độ cao giữa 2 nút con của mỗi nút không quá 1 đơn vị
Câu 62: Kết luận nào sau đây đúng?
A. Thao tác tìm kiếm trên cây nhị phân tìm kiếm chứa n khóa có thời
gian tính trong tình huống tồi nhất là O(logn)
B. Thao tác tìm kiếm trên cây nhị phân tìm kiếm chứa n khóa có thời
gian tính trong tình huống tồi nhất là O(n)
Câu 63: Kết luận nào sau đây đúng?
A. Thao tác tìm kiếm trên cây AVL chứa n khóa có thời gian tính
trong tình huống tồi nhất là O(logn)
B. Thao tác tìm kiếm trên cây AVL chứa n khóa có thời gian tính
trong tình huống tồi nhất là O(n)
Câu 64: Kết luận “Độ cao của cây AVL chứa n khóa luôn là O(logn)” có đúng không? A. Đúng B. Sai