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

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)

Trả lời:

Đáp án đúng: D

Hàng đợi (Queue) là một cấu trúc dữ liệu tuyến tính tuân 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 loại bỏ trước. Phép bổ sung (enqueue) được thực hiện ở cuối hàng đợi (rear), và phép loại bỏ (dequeue) được thực hiện ở đầu hàng đợi (front). Vì vậy, đáp án chính xác nhất là phương án 4.

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

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?

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

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: