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

Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau hay không

Đặt phần tử đầu và phần tử cuối của Queue bằng 0

Trả lời:

Đáp án đúng: B

Trong hàng đợi (Queue) thực hiện bằng mảng vòng, F (Front) trỏ đến vị trí trước phần tử đầu và R (Rear) trỏ đến vị trí cuối. Khi F = R = 0, điều này có nghĩa là hàng đợi đang rỗng. Khi hàng đợi rỗng, cả con trỏ đầu và con trỏ cuối đều ở cùng một vị trí (trong trường hợp này là 0). Khi hàng đợi đầy, con trỏ R đuổi kịp con trỏ F, nhưng cần có thêm một biến hoặc một vài kỹ thuật khác để phân biệt queue đầy và queue rỗng (ví dụ: đếm số lượng phần tử trong queue hoặc để trống một ô nhớ). Trong trường hợp này, F=R=0 chỉ ra queue rỗng.

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

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?

Lời giải:

Đáp án đúng: A

Trong cấu trúc dữ liệu Queue (hàng đợi), F (Front) là con trỏ trỏ đến đầu hàng đợi (nơi phần tử sẽ được lấy ra), và R (Rear) là con trỏ trỏ đến cuối hàng đợi (nơi phần tử mới sẽ được thêm vào). Khi thêm một phần tử mới vào Queue, chúng ta cần cập nhật con trỏ R để nó trỏ đến vị trí mới của phần tử cuối cùng. Con trỏ F không thay đổi vì vị trí đầu hàng đợi không đổi. Do đó, con trỏ R sẽ tăng lên (R = R + 1) để trỏ đến vị trí mới sau khi thêm phần tử.

Câu 28:

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?

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

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: