Câu hỏi trắc nghiệm ôn thi môn Cấu trúc dữ liệu và giải thuật | Học viện Công Nghệ Bưu Chính Viễn Thông

EduQuiz - Thi trắc nghiệm 1
Cấu trúc dữ liệu và giải thuật
Nguyễn Quang Trường Phần 1: Câu 1: (1 đáp án)
CÂU 1 Hãy chọn định nghĩa đúng nhất về danh sách kiểu hàng đợi (Queue)?
* 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).
• 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à 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. Câu 2: (1 đáp án)
CÂU 2 Trong bốn kiểu ký hiệu sau đây, ký hiệu nào biểu thị cho
danh sách kiểu hàng đợi? • LIFO • FILO * FIFO • LOLO Câu 3: (1 đáp án)
CÂU 3 Để thêm một đối tượng x bất kỳ vào Stack, ta dùng hàm nào sau đây? • POP(x) * PUSH(x) • TOP(x) • EMPTY(x) Câu 4: (1 đáp án)
CÂU 4 Để loại bỏ một đối tượng ra khỏi Stack, ta dùng hàm nào sau đây? • PUSH(x) • EMPTY(x) • FULL(x) * POP(x)
EduQuiz - Thi trắc nghiệm 2 Câu 5: (1 đáp án)
CÂU 5 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à gì trong các phương án sau? • Queue tràn. * Queue rỗng.
• Đặt phần tử đầu và phần tử cuối của Queue bằng 0.
• Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau hay không. Câu 6: (1 đáp án)
CÂU 6 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 trong các phương án sau? * F không thay đổi, R=R+1.
• F không thay đổi, R=R-1.
• F=F+1, R không thay đổi.
• F=F-1, R không thay đổi. Câu 7: (1 đáp án)
CÂU 7 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 trong các phương án sau?
• F không thay đổi, R=R+1.
• F không thay đổi, R=R-1. * F=F+1, R không thay đổi.
• F=F-1, R không thay đổi. Câu 8: (1 đáp án)
CÂU 8 Cho cây nhị phân: A, B, C, D, E, F, G, H, I, J, K, L, M, N. Cây
con trái của cây B bao gồm những phần tử nào trong các phương án sau? • C, D • E, J, K * D, H, I • C, D, E Câu 9: (1 đáp án)
EduQuiz - Thi trắc nghiệm 3
CÂU 9 Cho cây nhị phân: A, B, C, D, E, F, G, H, I, J, K, L, M, N. Cây
con trái của cây C bao gồm những phần tử nào trong các phương án sau? * F, L, M • A, B • E, F, G • E, F Câu 10: (1 đáp án)
CÂU 10 Cho cây nhị phân: A, B, C, D, E, F, G, H, I, J, K, L, M, N. Cây
con phải của cây C bao gồm những phần tử nào trong các lựa chọn sau? • F, G, L * G, N • D, E, F • D, E Câu 11: (1 đáp án)
CÂU 11 Cho cây nhị phân: A, B, C, D, E, F, G, H, I, J, K, L, M, N. Cây
con phải của cây B bao gồm những phần tử nào trong các lựa chọn sau? • C, D * E, J, K • D, E, H • E,K Câu 12: (1 đáp án)
CÂU 12 Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự
trước trong các phương án sau?
* Duyệt 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ự trước; Duyệt gốc; Duyệt cây con
phải theo thứ tự trướ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 gốc
• Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự trước Câu 13: (1 đáp án)
CÂU 13 Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự
giữa trong các phương án sau?
• Duyệt 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
EduQuiz - Thi trắc nghiệm 4
* Duyệt cây con trái theo thứ tự giữa; Duyệt gốc; Duyệt cây con phải theo thứ tự giữa
• 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 gốc
• Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự giữa Câu 14: (1 đáp án)
CÂU 14 Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự
sau trong các phương án sau?
• Duyệt gốc; Duyệt cây con trái theo thứ tự sau; Duyệt cây con phải theo thứ tự sau.
• Duyệt cây con trái theo thứ tự sau; Duyệt gốc; 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; Duyệt gố
• Duyệt gốc, cây trái, cây phải đồng thời theo thứ tự sau. Câu 15: (1 đáp án)
CÂU 15 Yếu tố nào sau đây để xây dựng nên một chương trình hoàn chỉnh?
• Dữ liệu tốt, giải thuật đơn giản.
• Cấu trúc dữ liệu tốt.
• Giải thuật có thời gian thực hiện nhanh nhất .
* Cấu trúc dữ liệu thích hợp, giải thuật xử lý hiệu quả . Câu 16: (1 đáp án)
CÂU 16 Theo các phương án dưới đây, kích thước lưu trữ kiểu số
nguyên (Integer) bao nhiêu byte? • 1 byte * 2 byte • 4 byte • 6 byte Câu 17: (1 đáp án)
CÂU 19 Hãy chọn Câu trả lời đúng nhất về giải thuật?
• Giải thuật cần có một hoặc nhiều dữ liệu ra (output), dữ liệu vào (input).
* Giải thuật hay còn gọi là thuật toán dùng để chỉ phương pháp hay
cách thức giải quyết vấn đề( bao gồm một dãy các bước tính toán rõ ràng và chính xác) .
• Giải thuật là một dãy hữu hạn các bước, tất cả các phép toán có
mặt trong các bước của thuật toán phải đủ đơn giản.
• Giải thuật là nòng cốt của chương trình.
EduQuiz - Thi trắc nghiệm 5 Câu 18: (1 đáp án)
CÂU 20 Hãy cho biết đâu là đặc trưng của thuật toán trong các phương án sau?
• Mỗi thuật toán có bộ dữ liệu vào, ra tương ứng.
• Mỗi bước của thuật toán cần phải được mô tả một các chính xá
• Thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện.
* Tất cả các đặc trưng đã nêu. Câu 19: (1 đáp án)
CÂU 21 Dựa vào yếu tố nào sau đây để đánh giá thời gian thực hiện của giải thuật? • Tính xác định. • Tính dừng.
* Độ phức tạp tính toán của giải thuật.
• Thời gian khi chạy chương trình cụ thể. Câu 20: (1 đáp án)
CÂU 22 Hãy cho biết phương án đúng của để sắp xếp theo thứ tự
tăng dần của cấp thời gian thực hiện chương trình?
• O(1), O(nlogn), O(n), O(logn).
* O(1), O(logn), O(n), O(nlogn).
• O(nlogn), O(n), O(logn), O(1).
• O(logn), O(n), O(nlogn), O(1). Câu 21: (1 đáp án)
CÂU 23 Hãy cho biết Câu trả lời đúng nhất về đặc điểm của giải thuật đệ quy?
• Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó.
• 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ó 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á
* Tất cả các đáp án đều đúng. Câu 22: (1 đáp án)
CÂU 24 Hãy cho biết phương pháp nào sau đây để loại bỏ nút X
trên cây nhị phân tìm kiếm, với X là một phần tử bất kỳ?
• Tìm nút chứa khoá lớn nhất trong cây con phải, đưa giá trị chứa
trong đó sang nút X , rồi xoá X.
EduQuiz - Thi trắc nghiệm 6
* Tìm nút chứa khoá lớn nhất trong cây con trái, đưa giá trị chứa
trong đó sang nút X , rồi xoá X.
• Chỉ việc xoá X, vì X không liên quan đến phần tử nào khá
• Không thể xoá X ra khỏi cây nhị phân tìm kiếm. Câu 23: (1 đáp án)
CÂU 25 Với dữ liệu đầu vào (n) đủ nhỏ, ta nên sử dụng phương
pháp sắp xếp nào sau đây?
* Sắp xếp lựa chọn(selection sort).
• Sắp xếp trộn(Merge sort).
• Sắp xếp vun đống(Heap sort).
• Sắp xếp nhanh(quick sort). Câu 24: (1 đáp án)
CÂU 26 Trong các danh sách tuyến tính sau đây, danh sách nào
sau đây có dạng ngăn xếp?
• 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 ki
• 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 đượ
* 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.
• 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. Câu 25: (1 đáp án)
CÂU 27 Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc nào sau đây? • FIFO( first in first out). * LIFO(last in first out). • LILO(last in last out). • FOLO(fisrt out last out). Câu 26: (1 đáp án)
CÂU 28 Với dữ liệu đầu vào (n) lớn, ta nên sử dụng phương pháp sắp xếp nào sau đây?
• Sắp xếp trộn (Merge sort) hoặc Sắp xếp đống(Heap sort).
• Sắp xếp chọn(selection sort), sắp xếp chèn ( Insert sort).
• Sắp xếp nổi bọt ( bubble sort) hoặc Sắp xếp chọn(selection sort).
EduQuiz - Thi trắc nghiệm 7
* Sắp xếp đống(Heap sort) hoặc Sắp xếp nhanh(quick sort). Câu 27: (1 đáp án)
CÂU 29 Hãy cho biết phát biểu nào đúng nhất về Giải thuật đệ quy?
* 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.
• 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 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ó. Câu 28: (1 đáp án)
CÂU 30 Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai
đoạn chương trình P1 và P2 mà T1(n) = O(f(n)); T2(n) = O(g(n)).
Theo qui tắc tổng xác định độ phức tạp tính toán của giải thuật thì
thời gian thực hiện đoạn P1 rồi đến P2 là phương án nào sau đây?
• T1(n) + T2(n) = O((f(n)+g(n))).
* T1(n) + T2(n) = O(max(f(n),g(n))).
• T1(n) + T2(n) = O(Min(f(n),g(n))).
• T1(n) + T2(n) = O((f(n) or g(n))). Câu 29: (1 đáp án)
CÂU 31 Trong một chương trình có 3 bước thực hiện, mà thời gian
thực hiện từng bước lần lượt là O(n^2), O(n^3) và O(nlogn). Cho
biết thời gian thực hiện của chương trình là bao nhiêu trong các phương án sau? • O(n^2)+ O(n^3) + O(nlogn). • O(n^2). * O(n^3). • O(nlogn). Câu 30: (1 đáp án)
CÂU 32 Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) =
O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là bao nhiêu trong các phương án sau? • T1(n)T2(n) = O(f(n)+g(n)). * T1(n)T2(n) = O(f(n).g(n)).
• T1(n)T2(n) = O(f(n)and g(n)). • T1(n)T2(n) = O(f(n)/g(n)). Câu 31: (1 đáp án)
EduQuiz - Thi trắc nghiệm 8
CÂU 33 Thời gian thực hiện các lệnh đơn (gán, đọc, viết) là bao
nhiêu trong các phương án sau? * O(1). • O(2). • O(logn). • O(n). Câu 32: (1 đáp án)
CÂU 43 Cho Stack gồm 5 phần tử {12, 5, 20, 23, 72}, trong đó 72
là phần tử ở đỉnh Stack. Để lấy ra phần tử thứ 4 trong Stack ta phải
thực hiện theo phương án nào? • POP(72), POP(23), POP(72).
• POP(23), PUSH(23), POP(72). * POP(72), POP(23), PUSH(72).
• POP(23), PUSH(72), POP(72). Câu 33: (1 đáp án)
CÂU 49 Trong các giải thuật sắp xếp, giải thuật nào sau đây áp
dụng phương pháp Chia để trị? • Quick sort, Heap sort. • Quick sort, Bubble sort. * Quick sort, Merge sort. • Quick sort, Insert sort. Câu 34: (1 đáp án)
CÂU 51 Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp
xếp chọn tăng dần (select sort)?
• 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.
* 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 cho đến phần tử cuối cùng.
• 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.
• 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. Câu 35: (1 đáp án)
CÂU 52 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)?
• 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.
EduQuiz - Thi trắc nghiệm 9
• 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 cho đến phần tử cuối cùng.
* 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.
• 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. Câu 36: (1 đáp án)
CÂU 53 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)?
• 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.
• 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 cho đến phần tử cuối cùng.
• 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.
* 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âu 37: (1 đáp án)
CÂU 54 Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp nhanh (Quick sort)?
• 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.
* Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá
(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á).
• 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 cho đến phần tử cuối cùng.
• 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. Câu 38: (1 đáp án)
CÂU 55 Phương pháp nào sau đây chính là phương pháp sắp xếp nhanh (Quick sort)? • Phương phap trộn. • Phương pháp chèn.
* Phương pháp phân đoạn.
• Phương pháp vun đống.
EduQuiz - Thi trắc nghiệm 10 Câu 39: (1 đáp án)
CÂU 56 Hãy cho biết ý tưởng nào sau đây nói về tưởng phương
pháp sắp xếp Trộn (Merge sort)?
* 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.
• 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.
• 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 cho đến phần tử cuối cùng.
• Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá
(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á). Câu 40: (1 đáp án)
CÂU 57 Hãy cho biết ý tưởng nào sau đây nói về phương pháp sắp xếp vun đống (Heap sort)?
• Tạo đống cho cây nhị phân (cây nhị phân đã được sắp xếp giảm dần).
• 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.
• Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá
(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á).
* 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. Câu 41: (1 đáp án)
CÂU 58 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 sau đây?
• Insert – Upheap – Downheap – Remov
* Insert – Upheap – Remove – Downheap.
• Remove – Downheap – Insert – Upheap.
• Upheap – Downheap – Remove – Insert. Câu 42: (1 đáp án)
CÂU 59 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?
EduQuiz - Thi trắc nghiệm 11
• 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.
• 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 đã chi
* 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.
• Tìm kiếm dựa vào cây nhị tìm kiếm. Câu 43: (1 đáp án)
CÂU 60 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ự?
* 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.
• 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.
• 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 đã chi
• 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. Câu 44: (1 đáp án)
CÂU 61 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 trên cây nhị phân tìm kiếm?
• 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.
• 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.
• 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 đã chi
* 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. Câu 45: (1 đáp án)
CÂU 62 Hãy cho biết tính chất nào sau đây là của cây nhị phân tìm kiếm?
• 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 lớn hơn giá trị của hai nút con.
* 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ó.
EduQuiz - Thi trắc nghiệm 12
• Cây nhị phân thoả tính chất heap.
• Là cây nhị phân đầy đủ. Câu 46: (1 đáp án)
CÂU 69 Cho cây nhị phân: A B C D E F. Cho biết thứ tự các
phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự trước? • D, B, A, C, E, F • A, B, C, D, E, F • A, B, D, C, F, E * A, B, D, E, C, F Câu 47: (1 đáp án)
CÂU 70 Cho cây nhị phân: A B C D E F. Cho biết thứ tự các
phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự giữa? • A, B, D, C, E, F * D, B, E, A, C, F • D, B, E, F, C, A • D, B, E, C, F, A Câu 48: (1 đáp án)
CÂU 71 Cho cây nhị phân: A B C D E F. Cho biết thứ tự các
phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự sau? • D, B, A, E, C, F • A, B, D, C, E, F * D, E, B, F, C, A • D, B, E, F, A, C Câu 49: (1 đáp án)
CÂU 72 Khi lưu trữ cây nhị phân dưới dạng mảng, phần tử ở vị trí
số 9 đóng vai trò gì trong các phương án sau?
• Là nút con trái của nút có vị trí là 4.
* Là nút con phải của nút có vị trí là 4.
• Là nút con phải của nút có vị trí là 5.
• Là nút con trái của nút có vị trí là 5. Câu 50: (1 đáp án)
CÂU 73 Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút
cha là i thì vị trí của nút con trái là gì trong các phương án sau? • i+1 • i-1
EduQuiz - Thi trắc nghiệm 13 * 2*i • 2*i + 1 Câu 51: (1 đáp án)
CÂU 74 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 phải là gì trong các phương án sau? • i+1 • i-1 • 2*i * 2*i + 1 Câu 52: (1 đáp án)
CÂU 75 Trong biểu diễn dữ liệu dưới dạng cây, Khái niệm nào sau đây là cấp của cây?
• Là cấp cao nhất của nút lá.
• Là cấp cao nhất của nút gố
* Là cấp cao nhất của một nút trên cây.
• Là tổng số nút trên cây. Câu 53: (1 đáp án)
CÂU 76 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à nút gì trong các phương án sau? * Là nút lá. • Là nút gố
• Là phần tử cuối cùng trong cây.
• Là phần tử đầu cùng trong cây. Câu 54: (1 đáp án)
CÂU 77 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ẽ bao
nhiêu trong các phương án sau? • 2 • 4 • 6 * 7 Câu 55: (1 đáp án)
Câu 1: Giải thuật đệ quy là:
* 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.
• 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.
EduQuiz - Thi trắc nghiệm 14
• 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ó. Câu 56: (1 đáp án)
Câu 10: Đặc điểm của giải thuật đệ quy: * Tất cả đều đúng
• Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
• 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 Câu 57: (1 đáp án)
Câu 12: Danh sách tuyến tính là:
* Danh sách mà quan hệ lân cận giữa các phần tử được xác định.
• Danh sách tuyến tính là một danh sách rỗng.
• Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).
• Danh sách dạng được lưu dưới dạng mảng. Câu 58: (1 đáp án)
Câu 13: ư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. Câu 59: (1 đáp án)
Câu 14: 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 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 .
• 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 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.
EduQuiz - Thi trắc nghiệm 15 Câu 60: (1 đáp án)
Câu 15: Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc: * LIFO(last in first out) • FIFO( first in first out) • LILO(last in last out) • FOLO( fisrt out last out) Câu 61: (1 đáp án)
Câu 18: định nghĩa danh sách tuyến tính Hàng đợi (Queue)
* 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)
• 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.
• 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. Câu 62: (1 đáp án)
Câu 19: Hàng đợi còn được gọi là danh sách kiểu: * FIFO • LIFO • FILO • LOLO Câu 63: (1 đáp án)
Câu 20: Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là: * PUSH(x). • POP(x). • TOP(x). • EMPTY(x). Câu 64: (1 đáp án)
Câu 21: Để lấy loại bỏ một đối tượng ra khỏi Stack, thao tác thường dùng là: “ * POP(x)
EduQuiz - Thi trắc nghiệm 16 • PUSH(x) • EMPTY(x) • FULL(x) Câu 65: (1 đáp án)
Câu 22: Để biểu diễn Stack, ta thường sử dụng kiểu dữ liệu nào sau đây?
* Danh sách móc nối và mảng dữ liệu • Mảng dữ liệu • Danh sách móc nối • Kiểu bản ghi Câu 66: (1 đáp án)
Câu 23: Thao tác POP(x) dùng trong Stack là để:
* Lấy một phần tử cuối cùng ra khỏi đỉnh Stack
• Lấy phần tử đầu tiên ra khỏi Stack
• Xóa bỏ một dãy các phần tử ra khỏi Stack
• Xóa bỏ một phần tử bất kì khỏi Stack Câu 67: (1 đáp án)
Câu 24: Thao tác Push(x) dùng trong Stack là để:
* Bổ sung một phần tử vào đỉnh Stack
• Bổ sung một phần tử vào đầu Stack
• Bổ sung một phần tử bất kì vào Stack
• Bổ sung một dãy các phần tử vào đỉnh Stack. Câu 68: (1 đáp án)
Câu 25: 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(25),POP(23), PUSH(25) • POP(25),POP(23) • POP(25),PUSH(23) • POP(23),PUSH(25). Câu 69: (1 đáp án)
Câu 26: 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(25),POP(23), PUSH(23) • POP(25),PUSH(23)
EduQuiz - Thi trắc nghiệm 17 • POP(23),PUSH(25) Câu 70: (1 đáp án)
Câu 27: 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), POP(20), PUSH(25), PUSH(23) • POP(25), POP(23), POP(20)
• POP(25), POP(23), PUSH(20), PUSH(25), PUSH(23) Câu 71: (1 đáp án)
Câu 35: 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 • Queue tràn
• Đặt phần tử đầu và phần tử cuối của Queue bằng 0
• Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau không. Câu 72: (1 đáp án)
Câu 36: 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 không thay đổi, R=R+1
• F không thay đổi, R=R-1
• F=F+1, R không thay đổi
• F=F-1, R không thay đổi Câu 73: (1 đáp án)
Câu 37: 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 Câu 74: (1 đáp án)
Câu 44: Trong biểu diễn dữ liệu dưới dạng cây, cấp của cây chính
* Cấp cao nhất của một nút trên cây
• Cấp cao nhất của nút lá
EduQuiz - Thi trắc nghiệm 18
• Cấp cao nhất của nút gốc
• Tổng số nút trên cây Câu 75: (1 đáp án)
Câu 45: 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á • Gốc
• Phần tử cuối cùng trong cây
• Không có đáp án nào đúng Câu 76: (1 đáp án)
Câu 46: Mỗi nút trong cây có tối đa: * Nhiều nút con • 2 nút con • 3 nút con • 1 nút con Câu 77: (1 đáp án)
Câu 48: 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 • 2*i + 1 • i+1 • i-1 Câu 78: (1 đáp án)
Câu 49: 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 + 1 • 2*i • i+1 • i-1 Câu 79: (1 đáp án)
Câu 50: 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 và 7 • 6 • 4 • 7 Câu 80: (1 đáp án)
EduQuiz - Thi trắc nghiệm 19
Câu 51: 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à: * 6 • 7 • 4 • 2 Câu 81: (1 đáp án)
Câu 52: 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 • 6 • 4 • 2 Câu 82: (1 đáp án)
Câu 53: Duyệt cây nhị phân theo thứ tự trước được thực hiện theo thứ tự:
* 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.
• 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ự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.
• 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. Câu 83: (1 đáp án)
Câu 54: Duyệt cây nhị phân theo thứ tự giữa được thực hiện theo thứ tự:
* 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.
• 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ự 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ự giữa, duyệt cây con phải theo thứ tự giữa. Câu 84: (1 đáp án)
Câu 55: Duyệt cây nhị phân theo thứ tự sau được thực hiện theo thứ tự:
EduQuiz - Thi trắc nghiệm 20
* 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.
• 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ự 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. Câu 85: (1 đáp án)
Câu 1: ý tưởng phương pháp sắp xếp chọn tăng dần (select sort)
* 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...
• 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ắ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.
• 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. Câu 86: (1 đáp án)
Câu 2: ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:
* 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.
• 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.
• 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...
• 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. Câu 87: (1 đáp án)
Câu 3: ý tưởng phương pháp sắp xếp chèn (insertion sort) là:
* 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.
• 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.
• 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...