Đề cương Môn Cấu trúc dữ liệu và thuật toán | Trường Đại học Khoa học, Đại học Huế

lOMoAR cPSD| 58702377 CÂU HỎI ĐÁP ÁN
1. Với cấu trúc dữ liệu cây – Tree, một nút không có nút con Nút lá được gọi là
2. Trong một cây nhị phân Sm kiếm 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ả giống nhau thì
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, 11, 13, 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 cấu First-In First-Out 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à lOMoAR cPSD| 58702377
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 giải thuật đệ 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ừ viết tắt ếng anh FIFO 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ều cao h (chiều cao nh từ 0) là lOMoAR cPSD| 58702377
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 cận theo B < D < C < E < A
thứ tự không giảm của tốc độ tăng
𝐴 = 𝑛! log(𝑛) , 𝐵 = 10", 𝐶 = √𝑛,
𝐷 = 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(17) 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 FILO
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 lOMoAR cPSD| 58702377
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(10) thực hiện bao nhiêu lần
31. Cấu trúc dữ liệu là gì
là cách thức tổ chức, 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ó chiều dà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ự giữa – 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 Inorder (Le› –
13 ;2; 55; 40; 169; 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 khoá của
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 điểm nào liệt
Chỉ gồm các mô tả (descrip on) thuộc nh kèm kê dưới đây thao tác lOMoAR cPSD| 58702377
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; 98
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ỏ giữa các ô dữ liệu số nguyên
43. Để biểu diễn mối quan hệ giữa các phầ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 để trị sắp xếp nhanh - quicksort
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) lOMoAR cPSD| 58702377
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 O(n^3) của một giải thuật như sau f(n)=34n^3-