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

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

Trả lời:

Đáp án đúng: C

Phép duyệt cây theo thứ tự sau (postorder traversal) là một phương pháp duyệt cây trong đó thứ tự duyệt là: duyệt cây con trái, duyệt cây con phải, sau đó duyệt gốc. Vì vậy, đáp án đúng là phương án 3.

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

Đề 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 29:

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?

Lời giải:

Đáp án đúng: D

Các lệnh gán, đọc, và viết (đặc biệt là trong bộ nhớ hoặc thanh ghi) là các thao tác cơ bản và thường được thực hiện trong một khoảng thời gian cố định. Do đó, thời gian thực hiện của chúng là hằng số, được biểu diễn bằng O(1). Các phương án khác như O(logn), O(n), và O(2) không phù hợp vì chúng biểu thị thời gian thực hiện tăng theo logarit, tuyến tính hoặc hằng số lớn hơn, không phản ánh đúng bản chất của các lệnh đơn giản này.

Câu 30:

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

Lời giải:

Đáp án đúng: B

Phương pháp Chia để trị (Divide and Conquer) là một kỹ thuật thiết kế thuật toán bằng cách chia nhỏ bài toán thành các bài toán con tương tự nhưng nhỏ hơn, giải quyết các bài toán con này một cách đệ quy, và sau đó kết hợp các kết quả để có được lời giải cho bài toán ban đầu.

Quick Sort:

Chia: Chọn một phần tử làm chốt (pivot) và chia mảng thành hai mảng con: một mảng chứa các phần tử nhỏ hơn chốt và một mảng chứa các phần tử lớn hơn chốt.
Trị: Sắp xếp đệ quy hai mảng con này.
Kết hợp: Không cần kết hợp vì quá trình chia đã đảm bảo vị trí đúng của các phần tử.

Merge Sort:

Chia: Chia mảng thành hai nửa bằng nhau.
Trị: Sắp xếp đệ quy hai nửa này.
Kết hợp: Trộn hai nửa đã sắp xếp để tạo thành một mảng đã sắp xếp hoàn chỉnh.

Heap Sort, Bubble Sort, Insert Sort: Các thuật toán này không sử dụng phương pháp chia để trị.

Vậy, đáp án đúng là Quick sort và Merge sort.

Câu 31:

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?

Lời giải:

Đáp án đúng: D

Duyệt cây theo thứ tự giữa (inorder traversal) thực hiện theo thứ tự: (1) duyệt cây con trái, (2) thăm nút gốc, (3) duyệt cây con phải. Với cây đã cho A B C D E F, ta có thể biểu diễn cây như sau (giả sử đây là cây nhị phân đầy đủ và các nút được thêm vào theo thứ tự): A là gốc, B là con trái của A, C là con phải của A, D là con trái của B, E là con phải của B, F là con phải của C. Như vậy, thứ tự duyệt giữa sẽ là: D (cây con trái của B), B (nút gốc của cây con trái của A), E (cây con phải của B), A (nút gốc), C (cây con phải của A), F (cây con phải của C).

Câu 32:

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?

Lời giải:

Đáp án đúng: D

Câu hỏi này yêu cầu xác định thứ tự duyệt cây nhị phân. Tuy nhiên, câu hỏi không chỉ rõ kiểu duyệt cây nào (ví dụ: duyệt trước, duyệt giữa, duyệt sau). Do đó, không thể xác định đáp án chính xác dựa trên thông tin được cung cấp. Để trả lời câu hỏi này, cần biết rõ phương pháp duyệt cây nào được sử dụng.

Câu 33:

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?

Lời giải:

Đáp án đúng: C

Khi lưu trữ cây nhị phân dưới dạng mảng, nút gốc (root) thường được lưu ở vị trí có chỉ số là 0 hoặc 1. Giả sử nút cha nằm ở vị trí i, thì nút con trái của nó sẽ nằm ở vị trí 2*i + 1 (nếu nút gốc ở vị trí 0) hoặc 2*i (nếu nút gốc ở vị trí 1). Vì phương án có 2*i+1, nên đây là đáp án đúng trong trường hợp nút gốc ở vị trí 0.

Câu 34:

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ời giải: