Câu hỏi ôn tập Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

Câu hỏi ôn tập Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!

110 55 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (ET2100)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

5 trang 6 tháng trước

Tác giả:

Profile Thùy Dương
CÂU HỎI
ĐÁP ÁN
1. Vớ ệi cấu trúc dữ li u cây – ột nút không có nút con Tree, m
được gọi là
Nút lá
2. m vTrong một cây nhị phân Sm kiế ới nút gố ủ c có đ 2 con,
nút có giá trị ỏ ất trên cây là nút nằnh nh m tại
Nút bên trái nhất của gốc
3. Nếu ệt cây nhị phân theo thứ tự trướduy c preOrder và thứ
tự sau postOrder mà cùng cho ra một kết quả ống nhau thì gi
cây đó có tối đa mấy nút
1 nút
4. T m nhhuật toán Sm kiế ị phân có thể áp dụ ợc trên ng đư
Mảng đã sắp thứ tự
5. Cho thuật toán sắp xếp Bubble Sort như sau:
Void BubbleSort(int M[], int N){
For (int i = 0; i < N; i++)
For (int j=N-1; j>i; j ) --
If (M[j]<M[j- 1])
Swap(M[j],M[j-1]);
}
Chọn câu đúng nhất cho hàm Swap.
Void Swap(int &X, int&Y){int Temp=X; X=Y;
Y=Temp; return;
6. Trong các thuật toán sắp xếp sau thuật toán nào phù hợp
nhất để sắp xếp các phầ ử ợc lưu trữ bằ danh sách n t đư ng
liên kết đơn
Thuật toán sắp xếp chèn
7. Sử dụ ịnh lý thợ để xác đị xem hàm truy hồ ủa giảng đ nh i c i
thuật đệ quy sau
T(n)=T(n/2) +45n n>n
0
Có độ ạp •nh toán ‘ệphức t m cận là
𝜃(𝑛)
8. Sử dụng hàm BUILD-MAX-HEAP trong sắ ể p xếp vun đ ng đố
xây dựng max-heap cho mà cho mả ồm các số nguyên sau ng g
14 11 13 12 26 19 20 24 18, , , , , , , , , 27. Cha của phầ ử n t 19 là
20
9. Định nghĩa nào là đúng với danh sách liên kết
Danh sách liên kết là tậ ợp các phầ ử p h 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.
10. Cấu trúc dữ nào tương ứ ới LIFO liệu ng v
Stack
11. Cho biết trong các công thứ ộ ạp •nh toán sau, c đ phức t
công thức nào là không hợ ệ? p l
𝑓
(
𝑛
)
= −2𝑛
!
+ 100𝑛𝑙𝑜𝑔
(
𝑛
)
+ 10
"
(𝑛 ∈ 𝑁)
12. Trong các từ ‘ếng anh sa từ nào đúng vớ ủa u, i tên g i cọ
cấu trúc dữ ệu FIFO? li
First-In First- Out
13. Trong thuật toán duyệt đồ thị theo chiề Breadth u rộng
First Traversal, cấu trúc dữ ử dụ ể lưu trữ dữ liệu được s ng đ
liệu trong quá trình duyệt là
hàng đợi – Queue
14. Cho đoạn mã nguồ ữ lập trình C của hàm như n ngôn ng
sau:
Unsigned int ham6(unsigned int n)
{
If (n==0) return 0;
Else return ham6(n-1)+ham6(n- ố phép toán cộ 1);//đếm s ng
}
Hãy cho biết phép cộ ợc thự ện bao nhiêu lần sau ng + đư c hi
khi gọi ham6(6)
63
15. Cho đoạn mã nguồ ữ lập trình C của ải thuật n ngôn ng gi
đệ như sau: quy
Void ham7(unsigned int n)
{
If (n==0) return 0;
Else{
Ham7(--n);
Prinž(“%d”,n);
}
}
Hãy cho biết kết quả in ra màn hình ọi ham khi g 7(4)
0. 1. 2. 3.
16.
17. Để ột bài toá thuật toán có thời gian trong giải m n, A
trường h p ợ tồi nhất là thuật toán B có thời gian trong O(n),
trường h p tợ ồi nhất là O(n^2) ết luận nào sau đây là đúng . K
thuật toán B có thể nhanh hơn thuật toán A
trong một số trườ ợp ng h
18. Đố ới thuật toán sắ ãy các phầ ử sau: i v p xếp ch n cho dọ n t
16 60 20 2 25 5 45 1 5 30 33 .
Cần thự ện bao nhiêu lầ lựa phầ ử ỏ ất để c hi n ch n ọ n t nh nh
sắp xếp mảng mà có thứ tự tăng dần
9 lần
19. Lựa chọn câu đúng nhất về danh sách liên kết đôi
vùng liên kết của một phầ ử trong danh n t
sách liên đôi có 2 mối liên kết với 2 trước và
sau nó trong danh sách
20. Từ ết tắt ‘ếng anh FIFO có nghĩa là gì trong ‘ế ệt vi ng vi
Vào trướ - ra trước c
21. Cho một cây nhị phân trong đó một nút bất kì hoặc là nút
lá hoặc có 2 con nếu duyệt cây theo thứ tự trước là A B D C E
thì thứ tự sau sẽ phải là
D C B E A
22. Cho biểu thứ ố 3 lan như sau c hậu t
a b - / c - / + c d b
Hãy •nh giá trị ểu thức trên sử dụng ngăn xế ết a= 2 b= bi p bi 5,
5, c= 4 và d= 19
8
23. Số ợng nút tối đa trên một cây nhị phân Sm kiếlư m có
chi chiều cao h ( ều cao •nh từ 0) là
2
!"#
− 1$
24. Cấu trúc dữ ảng có các ưu điểm nào liệu m
việc thêm bớt các phầ ử trong danh sách n t
đang có nhiề khó khăn do phả ời các u i di d
phần tử khác đi qua chỗ khác
25. Hãy sắp xếp các hàm độ phức tạp •nh toán ‘ệ ận theo m c
thứ tự ủa tố ộ tăng không giảm c c đ
𝐴 = 𝑛
!
log
(
𝑛
)
, 𝐵 = 10
"
, 𝐶 =
√
𝑛,9
𝐷 =
log 𝑛 , 𝐸 =
√
𝑛 log
(
𝑛
!
)
B < D < C < E < A
26. Cho hàm đệ ịnh nghĩa bướ ở và bướ ệ quy có đ c cơ s c đ quy
như sau
Bước cơ sở: F(0)=1, F(1)=1
Bước đệ : F(n)=F(n-1)+F(n-2) n>2 quy
Hãy cho biết kết quả của hàm ) F(17 là
2584
27. Các từ ‘ếng anh sau, từ nào đúng với tên gọi của cấu trúc
dữ liệu FILO
First-In Last- Out
28. Độ phức tạp về thời gian trong trườ ất của ng h p tợ ồi nh
thuật toán Sm kiế ị phân là m nh
O(nlogn)
29. Cho thuật toán Sm kiế ị phân không để quy sau: m nh
Int NrecBinarySearch (int M[], int N, int X){
Int First=0;
Int Last =N- 1;
While (First <= Last){
Int Mid=(First +Last)/2;
If (X==M[Mid])
Return (Mid);
If (X<M[Mid])
Last=Mid-1;
Else
First=Mid+1;
}
Return(-1);
}
Chọn câu đúng nhất trong trườ ốt nhất khi phầ ử ở ng h p tợ n t
giữa của mảng có giá trị bằ ng X
số phép gán là 3; số phép so sánh là 2
30. Cho đoạn mã nguồ ữ lập trình C của hamn ngôn ng 2() như
sau:
Int ham2(unsigned int n)
{
Int i,j,S=0;
For (i=0;i<n;i++)
For (j=n;j>0;j/=2)
S++;// câu lệ ếm nh c n đầ
Return s;
}
Hãy cho biết câu lệ S++ sau khi gọ ) thự ện bao nh i ham2(10 c hi
nhiêu lần
40
31. Cấu trúc dữ ệu là gì li
là cách thứ ổ ức, c t ch quản lý, lưu trữ dữ liệu
sao cho quá trình truy cập hay thay đổi
được hiệu quả
32. Mô tả đúng cho hàm sau
Int SC (int M[], int Len, int CM[]){
For (int i=0;i<Len;i++)
CM[i]=M[i];
Return(Len);
}
Hàm thự ệc sao chép nội c hiện vi dung mảng
M ều dài ề mảng CM có cùng có chi Len v
chiều dài. Hàm trả về ều dài của mảchi ng
CM sau khi sao chép
33. Vớ ột cây Sm kiế ị phân bạ ệt theo thứ tự nào i m m nh n duy
sẽ thu đượ ột danh sách theo thứ tự tăng c m
duyệt cây theo thứ tự ữa – gi inOrder
Traversal
34. Có cây nhị phân như sau với cách duyệt Inorder (Le- – ,
Root – Right) cho ra kết quả là dãy nào?
Tìm lựa chọ ất. n đúng nh
13 5; 40 169; 11;2; 5 ; ; 20; 34; 50; 90; 22
35. Chọn định nghĩa đúng nhất đối v i cây nhớ ị phân Sm kiếm
cây nhị phân Sm kiếm là cây nhị phân có
thành phần khóa của mọi nút lớn hơn thành
phần khoá của tất cả các nút trong cây con
trái của nó và nhỏ hơn thành phầ á của n kho
tất cả các nút trong cây con phả ủa nó i c
36. Thao tác dequeue() là thao tác cơ bả ủa cấu trúc dữ n c liệu
nào sau đây
Hàng đợi
37. Kiểu d ng đúng nhữ ệu trừu tượli ất vớ ểm nào liệt i đặc đi
kê dưới đây
Chỉ gồm các mô tả thuộ(descrip‘on) c •nh
kèm thao tác
38. Đoạn mã nguồ ữ lập trình C của ham1()như sau n ngôn ng
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ệ ếm nh c n đầ
Return s;
}
Hãy cho biết câu lệnh S+=i ợc thự ện bao nhiêu lầđư c hi n khi
gọi ham1(10)
55
39. Thao tác là thao tác cơ bả ủa cấu trúc dữ ệu nào pop() n c li
sau đây
ngăn xếp
40. Cho biểu thứ ạng trung tố sau A+B*C/D-G*H ểu thức d bi c
dạng h u t ng làậ ố tương ứ
ABC*D/+GH*-
41. Giả sử cần s p xắ ếp m ng n tả M có n phầ ử theo phương
pháp sắp xếp chèn
11 73 98 ;16; 12; 75; 51; 54; 5; ;36; 52;
Cần thự ện bao nhiêu lần chen các ử vào dãy con đã c hi phần t
có thứ tự tăng đứng lúc đ p xầu dãy mà để sắ ếp mảng mà có
thứ tự tăng dần
10 lần
42. Giả thiết ta thự ỗi các thao tác cơ bảc hiện chu n với cấu
trúc dữ ệu danh sách liên kết gồm các số nguyên như sau: li
InsertHead(4) => InsertHead(1) => InsertLast(3) =>
InsertLast(5) => DeleteHead() => InsertHead(7)
H ết kết quả của chuỗi thao tác là danh sách nào ãy cho bi
dưới đây
G ệhi chú dùng ký hi: -> u liên kết con trỏ ữa các ô dữ ố gi liệu s
nguyên
7 3 -> 4 -> -> 5
43. Để ối quan hệ ữa các phầ ử theo kiểu thứ biểu diễn m gi n t
bậc, ta dùng cấu trúc dữ ệu nào li
Cây- tree
44. Những thuật toán nào sau đây áp dụ ỹ thuật chia để ng k
trị
sắp xếp nhanh - quicksort
45. Trong thuật toán Sm quãng đườ ất giữa 2 ng đi ngắn nh
đỉnh trong đồ thị có trọ ố ta phả ử dụ ấu trúc dữ ệu ng s i s ng c li
hàng đợ – Priority Queue i ưu ‘ên
46. Cho thuật toán sau
47. Hãy •nh giá trị của ký pháp hậu tố sau:
6 3 6 + 5 * 90 / -
5. 5
48. Cho hàm đệ ịnh nghĩa như sau: quy được đ
Bước cơ sở: F(0)=1
Bước đệ chia thành 2 Snh huố ới n>0 quy: F(n) ng v
Tình huống n chẵn: F(n)=F(n/2)*F(n/2)
Tình huống n lẻ: F(n)=3*F((n-1)/2)*F((n-1)/2)
729
Cho biết kết quả trả lạ ọi hàm 6) là bao nhiêu i khi g F(
49. Cho hàm đệ ịnh nghĩa như sau: quy được đ
Bước cơ sở: F(0)=0
Bước đệ chia thành 2 Snh huố ới n>0 quy: F(n) ng v
Tình huống n chẵn: F(n)=F(n/2) + F(n/2)
Tình huống n lẻ: F(n)=3 + F((n-1)/2) + F((n-1)/2)
Cho biết kết quả trả lạ ọi hàm 6) là bao nhiêu i khi g F(
18
50. Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt
(Bubble Sort) trên mảng M N ử có phần t
đi từ ề đầ trong quá cuối mảng v u mảng,
trình đi nế ử ở ới (đứng phía sauu phần t dư )
nhỏ ử đứng ngay trên (trướchơn phần t ) nó
thì 2 phầ ử ẽ n t này s được đổi chỗ cho nhau.
Sau mỗ ần đi chúng ta đưa đượ ột phầi l c m n
tử trồi lên đúng chỗ. Sau N- lần đi thì tất cả 1
các phầ ử trong mả M sẽ có thứ tự n t ng
tăng.
Trong công thức tổng quát về bài toán A-> B ,thành phần nào
liên quan nhiề ải thuật u đến gi
Cả 2
Trong công thức tổng quát về bài toán A-> B ,thành phần nào
liên quan nhiề ấu trúc dữ ệu u đến C li
Thành phần A
Cho hàm độ ạp •nh toán của một giải thuật như sau phức t
f(n)=34n^3-24n^2+4log(n). n∈9N
O(n^3)
| 1/5
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

CÂU HỎI ĐÁP ÁN
1. Với cấu trúc dữ liệu cây – Tree, ột nút không có nút con m Nút lá được gọi là 2. Trong m m
ột cây nhị phân Sm kiế với nút gốc có đủ 2 con,
Nút bên trái nhất của gốc
nút có giá trị nhỏ nhất trên cây là nút nằm tại
3. Nếu duyệt cây nhị phân theo thứ tự trước preOrder và thứ 1 nút
tự sau postOrder mà cùng cho ra một kết quả g ống nhau thì i
cây đó có tối đa mấy nút
4. Thuật toán Sm kiếm nhị phân có thể áp dụng được trên Mảng đã sắp thứ tự
5. Cho thuật toán sắp xếp Bubble Sort như sau:
Void Swap(int &X, int&Y){int Temp=X; X=Y;
Void BubbleSort(int M[], int N){ Y=Temp; return;
For (int i = 0; i < N; i++) For (int j=N-1; j>i; j--) If (M[j] Swap(M[j],M[j-1]); }
Chọn câu đúng nhất cho hàm Swap.
6. Trong các thuật toán sắp xếp sau thuật toán nào phù hợp
Thuật toán sắp xếp chèn
nhất để sắp xếp các phần tử được lưu trữ bằng danh sách liên kết đơn
7. 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)=T(n/2) +45n n>n0
Có độ phức tạp •nh toán ‘ệm cận là
8. Sử dụng hàm BUILD-MAX-HEAP trong sắp xếp vun đống để 20
xây dựng max-heap cho mà cho mảng gồm các số nguyên sau 14, 1 1, 1
3, 12, 26, 19, 20, 24, 18, 27. Cha của phần tử 19 l à
9. Định nghĩa nào là đúng với danh sách liên kết
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.
10. Cấu trúc dữ liệu nào tương ứng với LIFO Stack
11. Cho biết trong các công thức độ phức tạp •nh toán sau,
𝑓(𝑛) = −2𝑛! + 100𝑛𝑙𝑜𝑔(𝑛) + 10"(𝑛 ∈ 𝑁)
công thức nào là không hợp lệ?
12. Trong các từ ‘ếng anh sau, từ nào đúng với tên gọi của First-In First-Out cấu trúc dữ liệu FIFO?
13. Trong thuật toán duyệt đồ thị theo chiều rộng Breadth hàng đợi – Queue
First Traversal, cấu trúc dữ liệu được sử dụng để lưu trữ dữ
liệu trong quá trình duyệt là
14. Cho đoạn mã nguồn ngôn ngữ lập trình C của hàm như 63 sau:
Unsigned int ham6(unsigned int n) { If (n==0) return 0;
Else return ham6(n-1)+ham6(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 ham6(6)
15. Cho đoạn mã nguồn ngôn ngữ lập trình C của g ải thuật i 0. 1. 2. 3. đệ quy như sau: Void ham7(unsigned int n) { If (n==0) return 0; Else{ Ham7(--n); Prinž(“%d”,n); } }
Hãy cho biết kết quả in ra màn hình khi gọi ham7(4 ) 16.
17. Để giải một bài toán, thuật toán A có thời gian trong
thuật toán B có thể nhanh hơn thuật toán A
trường hợp tồi nhất là O(n), thuật toán B có thời gian trong
trong một số trường hợp
trường hợp tồi nhất là O(n^2). Kết luận nào sau đây là đúng
18. Đối với thuật toán sắp xếp chọn cho dãy các phần tử sau: 9 lần 16 60 2 25 15 45 5 30 33 20.
Cần thực hiện bao nhiêu lần chọn lựa phần tử nhỏ nhất để
sắp xếp mảng mà có thứ tự tăng dần
19. Lựa chọn câu đúng nhất về danh sách liên kết đôi
vùng liên kết của một phần tử trong danh
sách liên đôi có 2 mối liên kết với 2 trước và sau nó trong danh sách
20. Từ v ết tắt ‘ếng anh FIF i
O có nghĩa là gì trong ‘ếng việt Vào trước - ra trước
21. Cho một cây nhị phân trong đó một nút bất kì hoặc là nút D C B E A
lá hoặc có 2 con nếu duyệt cây theo thứ tự trước là A B D C E
thì thứ tự sau sẽ phải là
22. Cho biểu thức hậu tố 3 lan như sau 8 a b - c / d c - b / +
Hãy •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
23. Số lượng nút tối đa trên một cây nhị phân Sm kiếm có 2!"# − 1$ chi c
ều cao h ( hiều cao •nh từ 0) là
24. Cấu trúc dữ liệu mảng có các ưu điểm nào
việc thêm bớt các phần tử trong danh sách
đang có nhiều khó khăn do phải di dời các
phần tử khác đi qua chỗ khác
25. Hãy sắp xếp các hàm độ phức tạp •nh toán ‘ệm ận theo c B < D < C < E < A
thứ tự không giảm ủa tố c c độ tăng
𝐴 = 𝑛! log(𝑛) , 𝐵 = 10", 𝐶 = √𝑛,9
𝐷 = log 𝑛 , 𝐸 = √𝑛 log(𝑛!)
26. Cho hàm đệ quy có định nghĩa bước cơ sở và bước đệ quy 2584 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(1 ) 7 là
27. Các từ ‘ếng anh sau, từ nào đúng với tên gọi của cấu trúc First-In Last-Out dữ liệu FIL O
28. Độ phức tạp về thời gian trong trường hợp tồi nhất của O(nlogn)
thuật toán Sm kiếm nhị phân là
29. Cho thuật toán Sm kiếm nhị phân không để quy sau:
số phép gán là 3; số phép so sánh là 2
Int NrecBinarySearch (int M[], int N, int X){ Int First=0; Int Last =N-1; While (First <= Last){ Int Mid=(First +Last)/2; If (X==M[Mid]) Return (Mid); If (X Last=Mid-1; Else First=Mid+1; } Return(-1); }
Chọn câu đúng nhất trong trường hợp tốt nhất khi phần tử ở
giữa của mảng có giá trị bằng X
30. Cho đoạn mã nguồn ngôn ngữ lập trình C của ham2() như 40 sau: Int ham2(unsigned int n) { Int i,j,S=0;
For (i=0;i For (j=n;j>0;j/=2)
S++;// câu lệnh cần đếm Return s; }
Hãy cho biết câu lệnh S++ sau khi gọi ham2(1 ) thự 0 c hiện bao nhiêu lần
31. Cấu trúc dữ liệu là gì là cách thức tổ c ức, h
quản lý, lưu trữ dữ liệu
sao cho quá trình truy cập hay thay đổi được hiệu quả
32. Mô tả đúng cho hàm sau
Hàm thực hiện việc sao chép nội dung mảng
Int SC (int M[], int Len, int CM[]){ M có ch ều dài i Len về mảng CM có cùng
For (int i=0;ichiều dài. Hàm trả về chiều dài của mảng CM[i]=M[i]; CM sau khi sao chép Return(Len); }
33. Với một cây Sm kiếm nhị phân bạn duyệt theo thứ tự nào duyệt cây theo thứ tự g ữa – i inOrder
sẽ thu được một danh sách theo thứ tự tăng Traversal
34. Có cây nhị phân như sau, với cách duyệt Inor der (Le- – 13 ;2; 55; 40 1 ; 69; 11; 20; 34; 50; 90; 22
Root – Right) cho ra kết quả là dãy nào?
Tìm lựa chọn đúng nhất.
35. Chọn định nghĩa đúng nhất đối với cây nhị phân Sm kiếm
cây nhị phân Sm kiếm là cây nhị phân có
thành phần khóa của mọi nút lớn hơn thành
phần khoá của tất cả các nút trong cây con
trái của nó và nhỏ hơn thành phần kh á của o
tất cả các nút trong cây con phải của nó
36. Thao tác dequeue() là thao tác cơ bản của cấu trúc dữ liệu Hàng đợi nào sau đây
37. Kiểu dữ liệu trừu tượng đúng nhất với đặc đ ểm nào liệt i
Chỉ gồm các mô tả (descrip‘on) thuộc •nh kê dưới đây kèm thao tác
38. Đoạn mã nguồn ngôn ngữ lập trình C của ham1()như sau 55 Int ham1(unsigned int n) { Int i,j,S=0;
For (i=0;i For (j=i;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)
39. Thao tác pop() là thao tác cơ bản của cấu trúc dữ liệu nào ngăn xếp sau đây
40. Cho biểu thức dạng trung tố sau A+B*C/D-G*H biểu thức ABC*D/+GH*-
dạng hậu tố tương ứng là
41. Giả sử cần sắp xếp mảng M có n phần tử theo phương 10 lần pháp sắp xếp chèn
11 ;16; 12; 75; 51; 54; 5; 73 ;36; 52 9 ; 8
Cần thực hiện bao nhiêu lần chen các phần tử vào dãy con đã
có thứ tự tăng đứng lúc đầu dãy mà để sắp xếp mảng mà có thứ tự tăng dần
42. Giả thiết ta thực hiện chuỗi các thao tác cơ bản với cấu 7 -> 4 -> 3 -> 5
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ỏ g ữa các ô dữ i liệu số nguyên
43. Để biểu diễn mối quan hệ g ữa các phầ i n tử theo kiểu thứ Cây- tree
bậc, ta dùng cấu trúc dữ liệu nào
44. Những thuật toán nào sau đây áp dụng kỹ thuật chia để sắp xếp nhanh - quicksort trị
45. Trong thuật toán Sm quãng đường đi ngắn nhất giữa 2
hàng đợi ưu ‘ên – Priority Queue
đỉnh trong đồ thị có trọng số ta phải sử dụng cấu trúc dữ liệu 46. Cho thuật toán sau
47. Hãy •nh giá trị của ký pháp hậu tố sau: 5. 5 6 3 6 + 5 * 90 / -
48. Cho hàm đệ quy được định nghĩa như sau: 729 Bước cơ sở: F(0)=1
Bước đệ quy: F(n) chia thành 2 Snh huống với n>0
Tình huống n chẵn: F(n)=F(n/2)*F(n/2)
Tình huống n lẻ: F(n)=3*F((n-1)/2)*F((n-1)/2)
Cho biết kết quả trả lại khi gọi hàm F(6) là bao nhiêu
49. Cho hàm đệ quy được định nghĩa như sau: 18 Bước cơ sở: F(0)=0
Bước đệ quy: F(n) chia thành 2 Snh huống với n>0
Tình huống n chẵn: F(n)=F(n/2) + F(n/2)
Tình huống n lẻ: F(n)=3 + F((n-1)/2) + F((n-1)/2)
Cho biết kết quả trả lại khi gọi hàm F(6) là bao nhiêu
50. Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt
đi từ cuối mảng về đầu mảng, trong quá
(Bubble Sort) trên mảng M có N phần tử
trình đi nếu phần tử ở dưới (đứng phía sau)
nhỏ hơn phần tử đứng ngay trên (trước) nó
thì 2 phần tử này sẽ được đổi chỗ cho nhau.
Sau mỗi lần đi chúng ta đưa được một phần
tử trồi lên đúng chỗ. Sau N-1 lần đi thì tất cả
các phần tử trong mảng M sẽ có thứ tự tăng.
Trong công thức tổng quát về bài toán A-> B ,thành phần nào Cả 2
liên quan nhiều đến giải thuật
Trong công thức tổng quát về bài toán A-> B ,thành phần nào Thành phần A
liên quan nhiều đến Cấu trúc dữ liệu
Cho hàm độ phức tạp •nh toán của một giải thuật như sau O(n^3)
f(n)=34n^3-24n^2+4log(n). n∈9N