Cấu trúc dữ liệu nào tương ứng với LIFO:

Queue

Linked List

Tree

Stack

Trả lời:

Đáp án đúng: D

LIFO là viết tắt của Last In, First Out, nghĩa là phần tử cuối cùng được thêm vào sẽ là phần tử đầu tiên được lấy ra. Cấu trúc dữ liệu Stack (ngăn xếp) hoạt động theo nguyên tắc này. Queue (hàng đợi) hoạt động theo nguyên tắc FIFO (First In, First Out). Linked List (danh sách liên kết) và Tree (cây) là các cấu trúc dữ liệu khác, không tuân theo nguyên tắc LIFO.

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

Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List):

Lời giải:

Đáp án đúng: C

Danh sách liên kết đôi (Doubly Linked List) là một cấu trúc dữ liệu trong đó mỗi phần tử (node) chứa dữ liệu và hai con trỏ: một con trỏ trỏ đến phần tử liền trước (previous) và một con trỏ trỏ đến phần tử liền sau (next). Do đó, vùng liên kết của một phần tử có 02 mối liên kết đến phần tử trước và sau nó trong danh sách. Vì vậy, đáp án đúng là phương án 3.

Câu 8:

Cho thuật toán sau:

int LinearSearch (float M[], int N, float X)

{

int k = 0;

M[N] = X;

while (M[k] != X) //n+1 lan

(M[k] != X) //n+1 lan k++;

if (k < N)

return (k);

return (-1);

}

Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:

Lời giải:

Đáp án đúng: B

Thuật toán LinearSearch tìm kiếm một giá trị X trong mảng M có N phần tử. Trường hợp xấu nhất xảy ra khi X không có trong mảng.

1. Số phép gán:
- `int k = 0;` (1 phép gán)
- `M[N] = X;` (1 phép gán). Phép gán này có mục đích để đảm bảo vòng lặp `while` luôn dừng lại, ngay cả khi X không tồn tại trong mảng M[0...N-1].
Vậy, số phép gán tối đa là Gmax = 2.

2. Số phép so sánh:
- Vòng lặp `while (M[k] != X)` sẽ được thực hiện N+1 lần (k chạy từ 0 đến N). Vì X không có trong mảng M[0...N-1], vòng lặp này sẽ chạy cho đến khi k = N và M[N] = X, lúc này điều kiện dừng. Do đó số phép so sánh là N + 1.
- Sau vòng lặp while, có một phép so sánh `if (k < N)` để kiểm tra xem X có được tìm thấy trong mảng hay không.
Vậy, số phép so sánh tối đa là Smax = N + 1.

Vậy, phương án đúng là: Số phép gán: Gmax = 2 và Số phép so sánh: Smax = N + 1.

Câu 9:

Cấu trúc dữ liệu biểu diễn hàng đợi bằng danh sách liên kết:

typedef struct QElement

{ T Key;

QElement *Next;

} QOneElement;

typedef QElement *QType;

Cấu trúc dữ liệu quản lý hàng đợi bằng hai phần tử đầu (Front) và cuối (Rear):

typedef struct QPElement

{ QType Font;

QType Rear;

} SQUEUE;

SQUEUE SQList;

Thêm phần tử vào sau phần tử Rear. Giả sử dữ liệu đưa vào hàng đợi là NewData, mã giả được mô tả như sau:

B1: NewElement = Khởi tạo nút mới có thành phần NewData

B2: IF (NewElement == NULL)

Thực hiện BKT

B3: IF (SQList.Front == NULL) // hàng đợi dang rỗng

B3.1: SQList.Front = SQList.Rear = NewElement

B3.2: Thực hiện BKT

B4: …………………………………………..

B5: …………………………………………..

BKT: Kết thúc

Chọn câu đúng nhất cho bước B4, B5

Lời giải:

Đáp án đúng: B

Câu hỏi yêu cầu hoàn thành đoạn mã giả thêm một phần tử vào cuối hàng đợi được biểu diễn bằng danh sách liên kết.

- B3 kiểm tra xem hàng đợi có rỗng không. Nếu có, cả Front và Rear đều trỏ đến phần tử mới.
- Nếu hàng đợi không rỗng (B3 sai), thì phần tử mới cần được thêm vào sau phần tử Rear hiện tại. Điều này được thực hiện bằng cách cho `SQList.Rear->Next` (con trỏ Next của phần tử cuối hàng đợi hiện tại) trỏ đến `NewElement`.
- Sau đó, `NewElement` trở thành phần tử cuối cùng mới, vì vậy `SQList.Rear` phải được cập nhật để trỏ đến `NewElement`.

Vậy nên:
- B4: `SQList.Rear->Next = NewElement` (Liên kết phần tử cuối hiện tại với phần tử mới)
- B5: `SQList.Rear = NewElement` (Cập nhật phần tử cuối thành phần tử mới)

Phương án 2 là đáp án đúng.

Câu 10:

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

Kết quả nào đúng khi thực hiện giải thuật sau:

long lt(int n)

{if (n==0) return 1;

else return (2*lt(n-1);

}

Lời giải:

Đáp án đúng: D

Đoạn code định nghĩa một hàm đệ quy `lt(n)`. Hàm này tính giá trị dựa trên công thức:
- `lt(0) = 1`
- `lt(n) = 2 * lt(n-1)` khi `n > 0`

Như vậy, hàm `lt(n)` thực chất tính `2^n`.

Xét các phương án:
- Phương án 1: `lt(12) = 2010` (Sai, vì 2^12 = 4096)
- Phương án 2: `lt(12) = 1024` (Sai, vì 2^12 = 4096, và 1024 = 2^10)
- Phương án 3: `lt(7) = 720` (Sai, vì 2^7 = 128)
- Phương án 4: `lt(6) = 64` (Đúng, vì 2^6 = 64)

Câu 12:

Kết quả nào đúng khi thực hiện giải thuật sau với a[]= {-3, -3, 15, -3}; n= 4; x= -3:

int FindX(int a[], int n, int x)

{int i;

for (i= n; i>= 1; i--) if (a[i]==x) return (i);

return (-1);

}

Lời giải: