Chọn định nghĩa đúng nhất về hàng đợi (Queue):

Hàng đợi còn được gọi là danh sách FILO và cấu trúc dữ liệu này còn được gọi cấu trúc FILO (First In Last Out)

Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử vào trong danh sách được thực hiện 1 đầu này và lấy 1 phần tử trong danh sách lại thực hiện bởi đầu kia

Hàng đợi là một danh sách mà trong đó thao tác thêm 1 phần tử hay hủy một phần tử trong danh sách được thực hiện 1 đầu

Hàng đợi phải là một danh sách liên kết đơn

Hãy suy nghĩ và trả lời câu hỏi trước khi xem đáp án

Trả lời:

Đáp án đúng: B

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 thì sẽ được lấy ra trước. Điều này có nghĩa là việc thêm một phần tử vào hàng đợi được thực hiện ở một đầu (thường gọi là 'cuối' hoặc 'rear'), và việc lấy một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia (thường gọi là 'đầu' hoặc 'front'). Phương án 1 sai vì hàng đợi là FILO là sai, hàng đợi là FIFO. Phương án 3 sai vì hàng đợi thêm một phần tử ở một đầu và xóa ở một đầu khác. Phương án 4 sai vì hàng đợi có thể được triển khai bằng nhiều cấu trúc dữ liệu khác nhau, không nhất thiết phải là danh sách liên kết đơn. Do đó, phương án 2 là định nghĩa chính xác nhất về hàng đợi.

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

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

Chọn định nghĩa đúng nhất đối với cây nhị phân tìm kiếm:

Lời giải:

Đáp án đúng: A

Cây nhị phân tìm kiếm (Binary Search Tree - BST) là một cấu trúc dữ liệu cây nhị phân đặc biệt. Đặc điểm quan trọng nhất của nó là tính chất sắp xếp: với mỗi nút, tất cả các nút trong cây con trái của nó phải có khóa nhỏ hơn khóa của nút đó, và tất cả các nút trong cây con phải của nó phải có khóa lớn hơn khóa của nút đó. Điều này đảm bảo rằng việc tìm kiếm một khóa trong cây có thể được thực hiện một cách hiệu quả bằng cách so sánh khóa cần tìm với khóa của nút hiện tại và rẽ nhánh sang cây con trái hoặc cây con phải tùy thuộc vào kết quả so sánh. Do đó, đáp án đúng phải thể hiện chính xác tính chất này. Phương án 1 mô tả chính xác tính chất này.

Câu 9:

Dấu hiệu nào dưới đây cho biết hàng đợi đã có thao tác thêm và loại bỏ phần tử là rỗng:

Lời giải:

Đáp án đúng: A

Khi một hàng đợi (queue) đã trải qua các thao tác thêm (enqueue) và loại bỏ (dequeue) phần tử, và hiện tại đang ở trạng thái rỗng, điều này có nghĩa là các phần tử đã được thêm vào trước đó đều đã được lấy ra hết. Trong cấu trúc hàng đợi sử dụng mảng hoặc danh sách liên kết, thông thường, chúng ta sử dụng hai biến (hoặc con trỏ) là `front` (lối trước) và `rear` (lối sau) để theo dõi vị trí của phần tử đầu tiên và phần tử cuối cùng trong hàng đợi. Khi hàng đợi rỗng, có hai trường hợp xảy ra: 1. **Hàng đợi rỗng ngay từ đầu:** Cả `front` và `rear` đều được khởi tạo là một giá trị đặc biệt (thường là 0 hoặc -1) để biểu thị hàng đợi rỗng. 2. **Hàng đợi rỗng sau khi thực hiện các thao tác:** Sau khi thêm và loại bỏ các phần tử, nếu số lượng phần tử được loại bỏ bằng số lượng phần tử đã thêm vào, hàng đợi sẽ trở về trạng thái rỗng. Trong trường hợp này, `front` và `rear` có thể trở về giá trị ban đầu (ví dụ: 0) hoặc có thể bằng nhau tại một vị trí nào đó trong mảng/danh sách, tùy thuộc vào cách cài đặt. Phương án 4, "Lối trước nhận giá trị = 0", là phù hợp nhất vì nó thể hiện trạng thái ban đầu hoặc trạng thái sau khi các phần tử đã được loại bỏ hết và `front` quay trở về giá trị khởi tạo ban đầu là 0 (hoặc một giá trị tương đương tùy vào cách cài đặt). Các phương án khác không mô tả chính xác trạng thái rỗng của hàng đợi sau các thao tác thêm và loại bỏ.

Câu 10:

Nhân tố nào là nhân tố chính ảnh hưởng đến thời gian tính của một giải thuật:

Lời giải:

Đáp án đúng: D

Thời gian tính của một giải thuật (hay độ phức tạp thời gian) chủ yếu phụ thuộc vào số lượng các phép toán mà giải thuật đó thực hiện. Số lượng phép toán này thường tăng lên khi kích thước dữ liệu đầu vào tăng. Do đó, kích thước dữ liệu đầu vào là nhân tố chính ảnh hưởng đến thời gian tính của giải thuật. Các yếu tố khác như máy tính, chương trình dịch, hoặc thuật toán được sử dụng cũng có ảnh hưởng, nhưng ảnh hưởng của kích thước dữ liệu đầu vào là đáng kể nhất.

Câu 11:

Chọn phát biểu đúng trong các phát biểu dưới đây: bằng cách chạy thử 1 thuật toán với 1 bộ dữ liệu, ta có thể:

Lời giải:

Đáp án đúng: B

Câu hỏi này kiểm tra sự hiểu biết về cách kiểm tra và đánh giá thuật toán. Việc chạy thử một thuật toán với một bộ dữ liệu có thể giúp ta phát hiện ra lỗi nếu thuật toán cho kết quả sai. Tuy nhiên, việc thuật toán cho kết quả đúng trong một trường hợp cụ thể không đảm bảo nó luôn đúng trong mọi trường hợp khác. Do đó, chỉ khi thuật toán cho kết quả sai, ta mới có thể khẳng định chắc chắn rằng thuật toán đó sai.

Câu 12:

Trong các mệnh đề sau đây, mệnh đề nào sai:

Lời giải:

Đáp án đúng: D

Mệnh đề sai là: "Cấu trúc dữ liệu là các dữ liệu phức tạp, được xây dựng nên từ các kiểu dữ liệu đã có, đơn giản hơn bằng các phương pháp liên kết nào đó". Cấu trúc dữ liệu không làm cho dữ liệu trở nên đơn giản hơn. Ngược lại, nó tổ chức dữ liệu phức tạp theo một cách có cấu trúc và hiệu quả, cho phép truy cập và thao tác dữ liệu dễ dàng hơn. Các cấu trúc dữ liệu như mảng, danh sách liên kết, cây, đồ thị đều là những cách để tổ chức và quản lý dữ liệu phức tạp.

Câu 13:

Sau một số … bước thực hiện giải thuật cho chúng ta đạt được kết quả mong muốn:

Lời giải: