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?

FIFO

LIFO

FILO

LOLO

Trả lời:

Đáp án đúng: A

Hàng đợi (Queue) là một cấu trúc dữ liệu hoạt động theo nguyên tắc FIFO (First-In, First-Out), nghĩa là phần tử nào được thêm vào trước sẽ được lấy ra trước. Do đó, ký hiệu FIFO biểu thị cho danh sách kiểu hàng đợi.

220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án - Phần 1

Đề cương ôn thi với 220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án được chọn lọc và chia sẻ dưới đây, nhằm giúp bạn sinh viên hệ thống kiến thức chuẩn bị cho kì thi sắp diễn ra.

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 13:

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?

Lời giải:

Đáp án đúng: D

Cây con phải của một nút trong cây nhị phân bao gồm tất cả các nút nằm trong cây con bắt nguồn từ nút con phải của nút đó. Dựa vào thông tin đề bài, cây con phải của C bao gồm các phần tử G, N. Do đó, đáp án đúng là 'G, N'.

Câu 14:

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?

Lời giải:

Đáp án đúng: B

Duyệt cây theo thứ tự trước (pre-order traversal) là một phương pháp duyệt cây trong đó chúng ta thăm (duyệt) nút gốc trước, sau đó duyệt cây con bên trái, và cuối cùng duyệt cây con bên phải. Phương án 2 mô tả chính xác quy tắc này: "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". Các phương án khác mô tả sai thứ tự duyệt.

Câu 15:

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?

Lời giải:

Đáp án đúng: D

Phép duyệt cây theo thứ tự giữa (inorder traversal) tuân theo quy tắc: duyệt cây con trái, sau đó duyệt gốc, và cuối cùng duyệt cây con phải. Phương án 4 mô tả chính xác quy tắc này. Các phương án khác không tuân theo đúng thứ tự duyệt cây theo thứ tự giữa.

Câu 16:

Hãy cho biết đâu là đặc trưng của thuật toán trong các phương án sau?

Lời giải:

Đáp án đúng: D

Câu hỏi yêu cầu xác định đặc trưng của thuật toán.
- Phương án 1: "Mỗi thuật toán có bộ dữ liệu vào, ra tương ứng" là đúng. Thuật toán nhận dữ liệu đầu vào và tạo ra kết quả đầu ra.
- Phương án 2: "Mỗi bước của thuật toán cần phải được mô tả một các chính xác" là đúng. Tính xác định là một đặc trưng quan trọng của thuật toán.
- Phương án 3: "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" là đúng. Tính hữu hạn là một đặc trưng bắt buộc của thuật toán.
Vì cả ba phương án đều đúng, phương án "Tất cả các đặc trưng đã nêu" là đáp án chính xác nhất.

Câu 17:

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?

Lời giải:

Đáp án đúng: B

Khi kích thước dữ liệu (n) lớn, các thuật toán sắp xếp có độ phức tạp thời gian trung bình hoặc tốt nhất là O(n log n) thường được ưu tiên hơn vì chúng có hiệu suất tốt hơn so với các thuật toán có độ phức tạp O(n^2).

Sắp xếp trộn (Merge sort) và Sắp xếp đống (Heap sort) đều có độ phức tạp thời gian O(n log n) trong trường hợp xấu nhất, trung bình và tốt nhất, làm cho chúng phù hợp với dữ liệu lớn. Sắp xếp nhanh (Quick sort) cũng có độ phức tạp trung bình là O(n log n), nhưng trong trường hợp xấu nhất (ví dụ: khi dữ liệu đã được sắp xếp), nó có thể xuống đến O(n^2).

Sắp xếp chọn (Selection sort), sắp xếp chèn (Insert sort) và sắp xếp nổi bọt (Bubble sort) đều có độ phức tạp thời gian O(n^2), do đó không hiệu quả với dữ liệu lớn.

Vậy nên đáp án chính xác nhất là "Sắp xếp trộn (Merge sort) hoặc Sắp xếp đống(Heap sort)"

Câu 18:

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?

Lời giải: