Ôn tập trắc nghiệm tổng hợp – 8 tuần sau môn Tin học | Trường đại học Kinh Doanh và Công Nghệ Hà Nội

lOMoAR cPSD| 48641284
ÔN TẬP TRẮC NGHIỆM TỔNG HỢP – 8 TUẦN SAU
1. Mệnh đề nào là ý tưởng của phương pháp sắp xếp vun đống (Heap sort) ?
A. Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại
phần tử gốc ra khỏi cây đưa vào dãy sắp xếp.
B. Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy. Dựa vào bước so
sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.
C. “ Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khóa (dãy con
trước khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).”
D. “ Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.”
2. Cơ chế heap trong sắp xếp vun đống là ?
A. Cây nhị phân đầy đủ với tính chất : giá trị của nút cha luôn lớn hơn giá trị hai nút con.
B. Cây nhị phân đầy đủ với tính chất : cây con trái có giá trị lớn hơn giá trị của cây con phải
C. Cây nhị phân đầy đủ với tính chất : các nút lá chỉ ở mức i và mức i-1
D. Cây nhị phân đầy đủ với tính chất : giá trị nút con trái nhỏ hơn giá trị nút con phải
3. Trong giải thuật sắp xếp vun đống, ta có 4 thủ tục con :
- Insert - thêm 1 phần tử vào cây;
- Downheap - vun đống lại sau khi loại một phần tử
khỏi Heap ; - Upheap - vun đống sau khi thêm
một phần tử vào cây; - Remove - loại 1 phần tử khỏi cây nhị phân.
Để sắp xếp các phần tử trong dãy theo phương pháp vun đống, ta thực hiện 4
thủ tục trên theo thứ tự như thế nào?
A. Upheap – Downheap – Insernt – Remove
B. Insert – Downheap – Remove – Upheap C. Insert – Upheap – Remove – Downheap
D. Upheap – Insert – Downheap - Remove
4. Mệnh đề nào là Tư tưởng của giải thuật tìm kiếm trên cây nhị phân tìm kiếm ?
A. Tại mỗi bước tiến hành so sánh X với phần tử cây con trái. Dựa vào bước so
sánh này quyết định tìm kiếm nằm ở cây con phải hoặc gốc. lOMoAR cPSD| 48641284
B. Nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con phải,
ngược lại thì việc tìm kiếm được thực hiện trên cây con trái.
C. So sánh X lần lượt với các phần tử cây con trái, cây con phải, gốc của cây cho
đến khi gặp phần tử có khoá cần tìm.
D. Nếu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược
lại thì việc tìm kiếm được thực hiện trên cây con phải.
5. Khái niệm Cây nhị phân tìm kiếm?
A. Là cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha
nhỏ hơn mọi nút trên cây con trái và lớn hơn mọi nút trên cây con phải của nó.
B. Là cây nhị phân mà mỗi nút trong cây đều thoả tính chất: tất cả các nút ứng với
các mức trừ mức cuối cùng đều đạt tối đa.
C. Là cây nhị phân mà mỗi nút trong cây đều thoả tính chất: các nút tương ứng
với các mức đều đạt về phía trái hoặc phía phải.
D. Là cây nhị phân mà mỗi nút trong cây đều thoả tính chất: nếu nút thứ i đạt về
phía trái thì nút i+1 sẽ đạt về phía phải
6. Giải thuật sau thực hiện việc gì trong phương pháp sắp xếp vun đống?
Procedure Upheap(k:integer); Begin
V:=a[k]; a[0]:=maxint; while a[k div 2] <= v do begin a[k]:= a[k div 2]; k:=k div 2; end; a[k]:=v; End;
A. Vun đống cho cây sau khi thêm phần tử
B. Vun đống cho cây sau khi loại bỏ phần tử
C. Thêm một phần tử vào cây nhị phân
D. Loại bỏ một phần tử khỏi cây nhị phân
7. Giải thuật sau thực hiện việc gì trong phương pháp sắp xếp vun đống?
Procedure Downheap(k:integer); Label 0; Begin v:=a[k];
While k<= n div 2 do begin j:=k*2; if a[j] lOMoAR cPSD| 48641284
j:=j+1; if v>=a[j] then goto 0; a[k]:=a[j]; k:=j; end; 0: a[k]:=v; End;
A. Vun đống cho cây sau khi thêm phần tử
B. Vun đống cho cây sau khi loại bỏ phần tử
C. Thêm một phần tử vào cây nhị phân
D. Loại bỏ một phần tử khỏi cây nhị phân
8. Giải thuật sau thực hiện việc gì trong phương pháp sắp xếp vun đống? Function P: integer; Begin P:=a[1]; a[1]:=a[n]; n: =n-1; Downheap(1); End;
A. Vun đống cho cây sau khi thêm phần tử
B. Vun đống cho cây sau khi loại bỏ phần tử
C. Thêm một phần tử vào cây nhị phân
D. Loại bỏ một phần tử khỏi cây nhị phân
9. Tính chất nào sau đây là tính chất của cây nhị phân tìm kiếm? A. Mọi khóa
thuộc cây con nút trái đều lớn hơn khóa nút gốc.
B. Mọi khóa thuộc cây con trái đều nhỏ hơn khóa nút gốc.
C. Mọi khóa thuộc cây con nút trái đều lớn hơn khóa cây con nút phải
D. Mọi khóa thuộc cây con nút trái đều lớn hơn khóa nút gốc và khóa cây con nút phải
10. Tính chất nào sau đây là tính chất của cây nhị phân tìm kiếm? A. Mọi khóa
thuộc cây con nút phải đều lớn hơn khóa nút gốc.
B. Mọi khóa thuộc cây con nút phải đều nhỏ hơn khóa nút gốc.
C. Mọi khóa thuộc cây con nút phải đều nhỏ hơn khóa cây con nút trái
D. Mọi khóa thuộc cây con nút phải đều nhỏ hơn khóa nút gốc và khóa cây con nút trái
11. Cho cây nhị phân tìm kiếm biểu diễn dạng mảng: 20. 13. 25. 12. 15. 23. 27. 10.
12. 14. 16. 21. 24. Nếu tìm số 26 thì ta phải thực hiện bao nhiêu phép so sánh? lOMoAR cPSD| 48641284 A. 2 lần B. 3 lần C. 4 lần D. Không thực hiện
12. Tính chất của Heap (đống)?
A. Giá trị khóa nút con trái lớn hơn khóa nút gốc và nút con phải B. Giá trị khóa
nút con phải lớn hơn khóa nút gốc và nút con trái C. Giá trị khóa nút gốc lớn
hơn khóa nút con trái và nút con phải
D. Giá trị khóa nút gốc nhỏ hơn khóa nút con trái và nút con phải
13. Định nghĩa cây nhị phân tìm kiếm ứng với n khóa k1,..,kn?
A. k[2i] > k[i] > k[2i+1] với mọi i = 1..n
B. B. k[2i] < k[i] < k[2i+1] với mọi i = 1..n
C. C. k[i] < k[2i] < k[2i+1] với mọi i = 1..n
D. k[i] > k[2i+1] > k[2i] với mọi i = 1..n
14. Điều kiện của một cây nhị phân tìm kiếm?
A. Là cây nhị phân hoàn chỉnh (đầy đủ) và mỗi nút trong cây đều thoả tính chất:
giá trị của nút cha nhỏ hơn mọi nút trên cây con trái và lớn hơn mọi nút trên cây con phải của nó.
B. Là cây nhị phân hoàn chỉnh (đầy đủ) và mỗi nút trong cây đều thỏa tính chất:
giá trị của nút cha lớn hơn mọi nút trên cây con trái và nhỏ hơn mọi nút trên cây con phải của nó.
C. Là cây nhị phân hoàn chỉnh (đầy đủ) và mỗi nút trong cây đều thoả tính chất:
giá trị của mọi nút trên cây con trái lớn hơn giá trị của nút cha và nhỏ hơn mọi nút trên cây con phải.
D. Là cây nhị phân hoàn chỉnh (đầy đủ) và mỗi nút trong cây đều thỏa tính chất:
giá trị của mọi nút trên cây con phải nhỏ hơn giá trị nút cha và lớn hơn mọi nút trên cây con phải.
15. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) Else If x
tree_search(2*k,x) Else tree_search(2*k+1,x); End;
Cho biết câu lệnh dừng đệ quy? lOMoAR cPSD| 48641284
A. If (a[k]=null) or (a[k]=x) then return(k) B. If x
C. Else tree_search(2*k+1,x)
D. Không có lệnh đệ quy
16. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) Else If x tree_search(2*k,x) Else
tree_search(2*k+1,x); End;
Khi phần tử x cần tìm bằng a[k] thì thủ tục trả về giá trị nào? A. Giá trị k B. Giá trị x C. Giá trị 0 D. Giá trị rỗng (null)
17. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) Else If x tree_search(2*k,x) Else
tree_search(2*k+1,x); End;
Khi phần tử x< a[k] thì thủ tục thực hiện tiếp lệnh nào?
A. Lệnh tìm trên cây con phải
B. Lệnh tìm trên cây con trái
C. Lệnh trả về giá trị k
D. Lệnh trả về giá trị rỗng (null)
18. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) lOMoAR cPSD| 48641284 Else If x tree_search(2*k,x) Else
tree_search(2*k+1,x); End;
Đâu là lời gọi tìm kiếm x trong cây con trái? A. Tree_search(k,x) B. Tree_search(2*k,x) C. Tree_search(2*k+1, x) D. Return(k)
19. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) Else If x tree_search(2*k,x) Else
tree_search(2*k+1,x); End;
Khi phần tử x> a[k] thì thủ tục thực hiện tiếp lệnh nào?
A. Lệnh tìm trên cây con phải
B. Lệnh tìm trên cây con trái
C. Lệnh trả về giá trị k
D. Lệnh trả về giá trị rỗng (null)
20. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) Else If x then
tree_search(2*k,x) Else
tree_search(2*k+1,x); End;
Đâu là lời gọi tìm kiếm x trong cây con phải? A. Tree_search(k,x) B. Tree_search(2*k,x) C. Tree_search(2*k+1, x) D. Return(k)
21. Cho giải thuật tìm kiếm phần tử trong cây nhị phân tìm kiếm có gốc k: lOMoAR cPSD| 48641284 Procedure tree_search(k,x); Begin
If (a[k]=null) or (a[k]=x) then return(k) Else If x tree_search(2*k,x) Else
tree_search(2*k+1,x); End; Đánh giá
Độ phức tạp thuật toán trên? A. O(logn). B. O(n) C. O(n2) D. O(nlogn)
22. Giải thuật sau thực hiện việc gì trong phương pháp sắp xếp vun đống?
Procedure Insert (v: integer) Begin n:=n+1; a[n]:=v; Upheap(n); End;
A. Vun đống cho cây sau khi thêm phần tử
B. Vun đống cho cây sau khi loại bỏ phần tử
C. Thêm một phần tử vào cây nhị phân
D. Loại bỏ một phần tử khỏi cây nhị phân
23. Tính chất nào không phải là của cây nhị phân tìm kiếm ? A. Tất cả các cây con
của nó cũng đều là cây nhị phân tìm kiếm
B. Cấp cao nhất của cây là bằng 2
C. Mỗi nút của cây được gán một khóa
D. Nếu nút thứ i đạt về phía trái thì nút i+1 sẽ đạt về phía phải
24. Tính chất nào không phải là tính chất của Heap?
A. Giá trị nút gốc là giá trị lớn nhất trong cây
B. Giá trị nút gốc là giá trị nhỏ nhất trong cây
C. Bỏ phần tử hai đầu của Heap thì dãy còn lại vẫn là Heap. D. Mọi cây con trong Heap cũng là một Heap.
25. Hãy cho biết tư tưởng nào sau đây nói về của giải thuật tìm kiếm nhị phân? lOMoAR cPSD| 48641284
A. So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp
phần tử có khoá cần tìm.
B. Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc
tìm kiếm trên hai đoạn đã chia.
C. Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, dựa vào bước so sánh
này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.
D. Tìm kiếm dựa vào cây nhị tìm kiếm.
26. Hãy cho biết tư tưởng nào sau đây nói về của giải thuật tìm kiếm tuần tự? A.
So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp
phần tử có khoá cần tìm. B.
Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy, dựa vào bước so
sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành. C.
Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc
tìm kiếm trên hai đoạn đã chia. D.
Tìm kiếm dựa vào cây nhị tìm kiếm: Nếu giá trị cần tìm nhỏ hơn gốc thì thực
hiện tìm kiếm trên cây con trái, ngược lại ta việc tìm kiếm được thực hiện trên cây con phải.
27. Cho dãy số sau: {10, 11, 14, 32, 36, 43, 55, 57, 87, 97}. Áp dụng phương pháp tìm
kiếm nhị phân, để tìm kiếm giá trị X= 10, sau lần phân đoạn thứ nhất, phạm vi tìm
kiếm mới của dãy sẽ gồm những phần tử nào? A. 10, 11, 14, 32 B. 10, 11, 14, 32, 43 C. 10, 11, 14 D. 10, 11
28. Cho dãy số sau: {10, 11, 14, 32, 36, 43, 55, 57, 87, 92}. Áp dụng phương pháp tìm
kiếm nhị phân, để tìm kiếm giá trị X= 92, sau lần phân đoạn thứ hai, phạm vi tìm
kiếm mới của dãy gồm những phần tử nào? A. 87, 92 B. 57, 87, 92 C. 55, 57, 87, 92 D. 43, 57, 87, 92
29. Ưu điểm lớn nhất của giải thuật tìm kiếm tuần tự là gì?
A. Áp dụng với số lượng dữ liệu lớn
B. Không phải kiểm tra tất cả các phần tử
C. Rút ngắn thời gian thực hiện
D. Dãy không cần phải sắp xếp thứ tự
30. Ưu điểm lớn nhất của giải thuật tìm kiếm nhị phân là gì? lOMoAR cPSD| 48641284
A. Dãy không cần phải sắp xếp thứ tự B. Dễ dàng thêm, bớt các phần tử
C. Giải thuật đơn giản, dễ hiểu
D. Không phải kiểm tra tất cả các phần tử
31. Cho dãy n phần tử. Áp dụng giải thuật tìm kiếm tuần tự. Trường hợp xấu nhất phải
thực hiện bao nhiêu lần so sánh? A. n lần B. (n+1) lần C. (n+1)/2 lần D. (n-1) lần
32. Cho dãy n phần tử. Áp dụng giải thuật tìm kiếm nhị phân. Tính trung bình phải
thực hiện bao nhiêu lần so sánh? A. log n lần B. 2 (log n +1) lần 2 C. (log n +1)/2 lần 2 D. (log n)/2 lần 2
33. Độ phức tạp của thuật toán tìm kiếm nhị phân T(n)=? A. O(log2n) B. O(log2n +1) C. O((log2n +1)/2) D. O((log2n)/2)
34. Độ phức tạp của thuật toán tìm kiếm tuần tự T(n)=? A. O(n) B. O(n+1) C. O(n/2) D. O((n+1)/2)
35. Khẳng định nào sau đây không phải là nhược điểm của giải thuật tìm kiếm nhị phân?
A. Dãy khóa luôn biến động
B. Phải sắp xếp dãy trước khi thực hiện tìm kiếm
C. Giải thuật phức tạp
D. Phải thực hiện kiểm tra tất cả các phần tử
36. Khẳng định nào sau đây không phải là nhược điểm của giải thuật tìm kiếm tuần tự?
A. Chỉ áp dụng với số lượng dữ liệu ít
B. Phải sắp xếp dãy trước khi thực hiện tìm kiếm
C. Tất cả các khẳng định
D. Phải thực hiện kiểm tra tất cả các phần tử lOMoAR cPSD| 48641284
37. Cho giải thuật sau:
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=12. Áp dụng giải thuật trên, hàm trả về giá trị bao nhiêu? A. 12 B. 6 C. 1 D. 0
38. Cho giải thuật sau:
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=4. Áp dụng giải thuật trên, hàm trả về giá trị bao nhiêu? A. 8 B. 9 C. 1 D. 0
39. Cho giải thuật sau: lOMoAR cPSD| 48641284
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=12. Giải thuật trên phải thực hiện bao nhiêu lần so sánh? A. 12 B. 6 C. 1 D. 2
40. Cho giải thuật sau:
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=4. Giải thuật trên phải thực hiện bao nhiêu lần so sánh? A. 8 B. 9 C. 7 D. 6
41. Cho giải thuật sau:
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=12. Áp dụng giải thuật trên, khi kết thúc chương
trình, giá trị của l và r bằng bao nhiêu? A. l=1, r=8 B. l=1, r=4 C. l=5, r=8 D. l=r=6
42. Cho giải thuật sau: lOMoAR cPSD| 48641284
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=4. Áp dụng giải thuật trên, khi kết thúc chương
trình, giá trị của l và r bằng bao nhiêu?
A. l=1, r=8 B. l=1, r=3 C. l=1, r=2 D. l=2, r=1
43. Cho giải thuật sau:
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=12. Giải thuật trên phải thực hiện bao nhiêu lần so sánh? A. 2 B. 6 C. 1 D. 3
44. Cho giải thuật sau: lOMoAR cPSD| 48641284
Với n=8, k=[1, 5, 6, 8, 10, 12, 15, 17], X=4. Giải thuật trên phải thực hiện bao nhiêu lần so sánh? A. 2 B. 3 C. 1 D. 6
45. Cho dãy số sau: {14, 32, 10, 43, 57, 87, 55, 36, 97, 11}. Áp dụng phương
pháp tìm kiếm tuần tự, sau bao nhiều lần thực hiện phép so sánh sẽ tìm thấy số 43? A. 4 B. 3 C. 5 D. 2
46. Cho dãy số sau: {10, 11, 14, 32, 36, 43, 55, 57, 87, 97 }. Áp dụng phương
pháp tìm kiếm nhị phân, sau bao nhiêu lần phân đoạn sẽ tìm thấy số 43? A. 4 B. 3 C. 5 D. 2
47. Cho dãy số sau: {10, 11, 14, 32, 36, 43, 55, 57, 87, 97}. Áp dụng phương
pháp tìm kiếm nhị phân, để tìm kiếm số 10, sau lần phân đoạn thứ nhất sẽ tìm kiếm trên dãy nào ? A. {10, 11} B. {10, 11, 14} C. {10, 11, 14, 32} D. {10, 11, 14, 32, 36}
48. Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chọn trực tiếp (select sort)? lOMoAR cPSD| 48641284
A. Ở lượt thứ i, chọn trong dãy a[i], …., a[n] phần tử nhỏ nhất và đổi chỗ nó với a[i]
B. Ở lượt thứ i, chọn trong dãy a[i+1], …., a[n] phần tử nhỏ nhất và đổi chỗ nó với a[i]
C. Ở lượt thứ i, xét lần lượt các phần tử trong dãy a[i], …., a[n] phần tử nào
nhỏ hơn thì đổi chỗ nó với a[i]
D. Ở lượt thứ i, xét lần lượt các phần tử trong dãy a[i+1], …., a[n] phần tử nào
nhỏ hơn thì đổi chỗ nó với a[i]
49. Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp đổi chỗ trực
tiếp (interchange sort)?
A. Ở lượt thứ i, chọn trong dãy a[i], …., a[n-1] phần tử nhỏ nhất và đổi chỗ nó với a[i]
B. Ở lượt thứ i, chọn trong dãy a[i+1], …., a[n] phần tử nhỏ nhất và đổi chỗ nó với a[i]
C. Ở lượt thứ i, xét lần lượt các phần tử trong dãy a[i+1], …., a[n] phần tử nào
nhỏ hơn thì đổi chỗ nó với a[i]
D. Ở lượt thứ i, xét lần lượt các phần tử trong dãy a[i], …., a[n-1] phần tử nào
nhỏ hơn thì đổi chỗ nó với a[i]
50. Cho dãy số {6. 1. 3. 0. 5. 7. 9. 2. 8. 4}. Áp dụng phương pháp sắp xếp lựa
chọn (Select sort) sau lần lặp thứ hai của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 3. 6. 5. 7. 9. 2. 8. 4}
B. {0. 1. 2. 6. 5. 7. 9. 3. 8. 4} C. {0. 1. 2. 3. 6. 5. 7. 9. 8. 4}
D. {0. 1. 6. 3. 5. 7. 9. 2. 8. 4}
51. Cho dãy số {6. 1. 3. 0. 5. 7. 9. 2. 8. 4}. Áp dụng phương pháp sắp xếp lựa
chọn (Select sort) sau lần lặp thứ năm của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 2. 6. 5. 7. 9. 3. 8. 4} B. {0. 1. 2. 3. 4. 5. 9. 6. 8. 7} C. {0. 1. 2. 3. 4. 5. 6. 9. 8. 7}
D. {0. 1. 2. 3. 4. 7. 9. 6. 8. 5}
52. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
sắp xếp lựa chọn (Select sort) sau lần lặp thứ nhất của giải thuật, dãy số thu được là dãy nào?
A. {15. 25. 75. 40. 65. 55. 90. 30. 95. 85}
B. {15. 25. 30. 40. 65. 55. 90. 75. 95. 85} C. {15. 40. 75. 25. 65. 55. 90. 30. 95. 85}
D. {15. 40. 25. 75. 65. 55. 90. 30. 95. 85} lOMoAR cPSD| 48641284
53. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
sắp xếp lựa chọn (Select sort) sau lần lặp thứ tư của giải thuật, dãy số thu được là dãy nào?
A. {15. 25. 75. 40. 65. 55. 90. 30. 95. 85}
B. {15. 25. 30. 40. 65. 55. 90. 75. 95. 85}
C. {15. 40. 75. 25. 65. 55. 90. 30. 95. 85}
D. {15. 25. 30. 40. 55. 65. 90. 75. 95. 85}
55. Cho dãy số {6. 1. 3. 0. 5. 7. 9. 2. 8. 4}. Áp dụng phương pháp đổi chỗ trực
tiếp (Interchange sort) sau lần lặp thứ nhất của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 2. 6. 5. 7. 9. 3. 8. 4}
B. {0. 6. 3. 1. 5. 7. 9. 2. 8. 4}
C. {0. 1. 6. 3. 5. 7. 9. 2. 8. 4}
D. {0. 1. 2. 3. 4. 7. 9. 6. 8. 5}
54. Cho dãy số {6. 1. 3. 0. 5. 7. 9. 2. 8. 4}. Áp dụng phương pháp đổi chỗ trực
tiếp (Interchange sort) sau lần lặp thứ ba của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 2. 5. 6. 7. 9. 3. 8. 4} B. {0. 6. 3. 1. 5. 7. 9. 2. 8. 4} C. {0. 1. 2. 6. 5. 7. 9. 3. 8. 4}
D. {0. 1. 2. 3. 4. 7. 9. 6. 8. 5}
55. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
đổi chỗ trực tiếp (Interchange sort) sau lần lặp thứ hai của giải thuật, dãy số
thu được là dãy nào?
A. {15. 25. 75. 40. 65. 55. 90. 30. 95. 85} B. {15. 25. 30. 40. 65. 55.
90. 75. 95. 85} C. {15. 40. 75. 25. 65. 55. 90. 30. 95. 85}
D. {15. 25. 30. 40. 55. 65. 90. 75. 95. 85}
56. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
đổi chỗ trực tiếp (Interchange sort) sau lần lặp thứ tư của giải thuật, dãy số
thu được là dãy nào?
A. {15. 25. 75. 40. 65. 55. 90. 30. 95. 85} B. {15. 25. 30. 40. 65. 55.
90. 75. 95. 85} C. {15. 40. 75. 25. 65. 55. 90. 30. 95. 85}
D. {15. 25. 30. 40. 75. 65. 90. 55. 95. 85}
57. Cách thực hiện nào sau đây là của phương pháp sắp xếp chọn tăng dần (select sort)? lOMoAR cPSD| 48641284
A. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé
nhất với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai, ba … cho
đến phần tử cuối cùng.
B. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy.
C. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau,
nếu phần tử nào bé hơn được cho lên vị trí trên.
D. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy
lớn hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
58. Giải thuật sau thực hiện việc gì? A. Tìm kiếm tuần tự B. Tìm kiếm nhị phân
C. Sắp xếp chọn tăng dần
D. Sắp xếp đổi chỗ trực tiếp
59. Giải thuật sau thực hiện việc gì? A. Tìm kiếm tuần tự B. Tìm kiếm nhị phân
C. Sắp xếp chọn tăng dần
D. Sắp xếp đổi chỗ trực tiếp lOMoAR cPSD| 48641284
60. Giải thuật sau thực hiện việc gì? A. Tìm kiếm tuần tự B. Tìm kiếm nhị phân
C. Sắp xếp chọn tăng dần
D. Sắp xếp đổi chỗ trực tiếp
61. Giải thuật sau thực hiện việc gì? A. Tìm kiếm tuần tự B. Tìm kiếm nhị phân
C. Sắp xếp chọn tăng dần
D. Sắp xếp đổi chỗ trực tiếp
62. Cho dãy số sau: {14, 32, 10, 43, 57, 87, 55, 36, 97, 11}. Áp dụng phương
pháp tìm kiếm tuần tự, sau bao nhiều lần thực hiện phép so sánh sẽ tìm thấy số 43? A. 4 B. 3 C. 5 D. 2 lOMoAR cPSD| 48641284
63. Cho dãy số sau: {10, 11, 14, 32, 36, 43, 55, 57, 87, 97 }. Áp dụng phương
pháp tìm kiếm nhị phân, sau bao nhiêu lần phân đoạn sẽ tìm thấy số 43? A. 4 B. 3 C. 5 D. 2
64. Cho dãy số sau: {10, 11, 14, 32, 36, 43, 55, 57, 87, 97}. Áp dụng phương
pháp tìm kiếm nhị phân, để tìm kiếm số 10, sau lần phân đoạn thứ nhất sẽ tìm kiếm trên dãy nào ? A. {10, 11} B. {10, 11, 14} C. {10, 11, 14, 32} D. {10, 11, 14, 32, 36}
65. Đánh giá độ phức tạp của giải thuật sắp xếp chọn tăng dần (selection sort) là? A. O(n) B. O(n2) C. O(logn) D. O(log2n)
66. Cho dãy số: {20. 26. 10. 14. 06. 01. 19. 98}. Sau lần sắp xếp thứ nhất được dãy
số {01. 26. 10. 14. 06. 20. 19. 98}. Hỏi đã áp dụng phương pháp sắp xếp nào? A. Selection sort B. Interchange sort C. Bubble sort D. Merge sort.
67. Cho dãy số: {20. 26. 10. 14. 06. 01. 19. 98}. Sau lần sắp xếp thứ nhất được dãy
số {01. 26. 20. 14. 10. 06. 19. 98}. Hỏi đã áp dụng phương pháp sắp xếp nào? A. Selection sort B. Interchange sort C. Bubble sort D. D. Merge sort.
68. Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nổi bọt (Bubble sort)? lOMoAR cPSD| 48641284
A. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau,
nếu phần tử nào nhỏ hơn được đứng vị trí trên.
B. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng
cách đẩy các phần tử lớn hơn xuống.
C. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba...
D. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
69. Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp chèn (Insertion sort)?
A. Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau,
nếu phần tử nào nhỏ hơn được đứng vị trí trên.
B. Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng
cách đẩy các phần tử lớn hơn xuống.
C. Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba...
D. Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
70. Cho dãy số {6. 1. 3. 0. 5. 7. 9. 2. 8. 4}. Áp dụng phương pháp sắp xếp lựa
chọn (Select sort) sau lần lặp thứ ba của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 3. 6. 5. 7. 9. 2. 8. 4} B.
{0. 1. 2. 6. 5. 7. 9. 3. 8. 4} C.
{0. 1. 2. 3. 6. 5. 7. 9. 8. 4}
D. {0. 1. 6. 3. 5. 7. 9. 2. 8. 4}
71. Cho dãy số {4. 0. 2. 8. 5. 9. 6. 1. 3. 7}. Áp dụng phương pháp sắp xếp chèn
trực tiếp (Insertion sort) sau lần lặp thứ tư của giải thuật, dãy số thu được là dãy nào?
A. {0. 4. 2. 8. 5. 9. 6. 1. 3. 7} B.
{0. 2. 4. 8. 5. 9. 6. 1. 3. 7} C.
{0. 2. 4. 5. 6. 9. 8. 1. 3. 7}
D. {0. 2. 4. 5. 8. 9. 6. 1. 3. 7}
72. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
sắp xếp chèn trực tiếp (Insertion sort) sau lần lặp i=3 của giải thuật, dãy số
thu được là dãy nào?
A. {25. 40. 75. 15. 65. 55. 90. 30. 95. 85}
B. {15. 40. 75. 25. 65. 55. 90. 30. 95. 85} lOMoAR cPSD| 48641284
C. {25. 15. 40. 75. 65. 55. 90. 30. 95. 85}
D. {15. 40. 25. 75. 65. 55. 90. 30. 95. 85}
73. Cho dãy số {6. 1. 3. 0. 5. 7. 9. 2. 8. 4}. Áp dụng phương pháp sắp xếp đổi
chỗ trực tiếp (Interchange sort) sau lần lặp thứ hai của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 2. 6. 5. 7. 9. 3. 8. 4} B.
{0. 6. 3. 1. 5. 7. 9. 2. 8. 4} C.
{0. 1. 6. 3. 5. 7. 9. 2. 8. 4}
D. {0. 1. 2. 3. 4. 7. 9. 6. 8. 5}
74. Cho dãy số {4. 7. 0. 9. 2. 5. 3. 1. 8. 6}. Áp dụng phương pháp sắp xếp nổi
bọt (Bubble sort) sau lần lặp thứ ba của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 2. 4. 7. 3. 9. 5. 6. 8} B.
{0. 4. 7. 1. 9. 2. 5. 3. 6. 8} C.
{0. 1. 2. 6. 5. 7. 9. 3. 4. 8}
D. {0. 1. 2. 3. 4. 7. 9. 6. 5. 8}
75. Cho dãy số {4. 7. 0. 9. 2. 5. 3. 1. 8. 6}. Áp dụng phương pháp sắp xếp nổi
bọt (Bubble sort) sau lần lặp thứ năm của giải thuật, dãy số thu được là dãy nào?
A. {0. 1. 2. 4. 7. 3. 9. 5. 6. 8} B.
{0. 4. 7. 1. 9. 2. 5. 3. 6. 8} C.
{0. 1. 2. 3. 4. 7. 5. 9. 6. 8}
D. {0. 1. 2. 3. 4. 7. 9. 5. 6. 8}
E. 0 , 1, 2, 3, 4, 5, 7, 6, 9, 8
76. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
sắp xếp chèn trực tiếp (Insertion sort) sau lần lặp thứ năm của giải thuật, dãy
số thu được là dãy nào?
A. {25. 40. 75. 15. 65. 55. 90. 30. 95. 85} B.
{15. 40. 75. 25. 65. 55. 90. 30. 95. 85} C.
{25. 15. 40. 75. 65. 55. 90. 30. 95. 85}
D. {15. 25. 40. 55. 65. 70. 90. 30. 95. 85}
E. 15 , 25, 40, 65, 75, 55, 90, 30, 95, 85
77. Cho dãy số {40. 25. 75. 15. 65. 55. 90. 30. 95. 85}. Áp dụng phương pháp
sắp xếp nổi bọt (Bubble sort) sau lần lặp thứ hai của giải thuật, dãy số thu được là dãy nào?