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 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; 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, cây trái, cây phải đồng thờ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

Trả lờ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.

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 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:

Đáp án đúng: A

Thời gian thực hiện của chương trình là tổng thời gian thực hiện của các bước. Trong trường hợp này, chúng ta có ba bước với thời gian thực hiện lần lượt là O(n^2), O(n^3) và O(nlogn). Khi tính tổng độ phức tạp, chúng ta chỉ giữ lại thành phần có tốc độ tăng trưởng lớn nhất khi n tiến tới vô cùng. Trong ba thành phần trên, O(n^3) có tốc độ tăng trưởng lớn nhất. Do đó, thời gian thực hiện của chương trình là O(n^3).

Câu 19:

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?

Lời giải:

Đáp án đúng: B

Khi hai đoạn chương trình P1 và P2 lồng nhau, thời gian thực hiện sẽ là tích của thời gian thực hiện của mỗi đoạn. Vì T1(n) = O(f(n)) và T2(n) = O(g(n)), nên thời gian thực hiện lồng nhau sẽ là T1(n) * T2(n) = O(f(n) * g(n)).

Câu 20:

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)?

Lời giải: