220 câu trắc nghiệm Cấu trúc dữ liệu và Giải thuật có giải thích chi tiết từng câu

Câu 1:

Đối với thuật toán sắp xếp chọn trực tiếp cho dãy các phần tử sau (10 pt) 16 60 2 25 15 45 5 30 33 20

Cần thực hiện ..................... chọn lựa phần tử nhỏ nhất để sắp xếp mảng M có thứ tự tăng dần.

Lời giải:

Đáp án đúng: C

Thuật toán sắp xếp chọn trực tiếp (Selection Sort) hoạt động bằng cách tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của dãy, sau đó hoán đổi nó với phần tử đầu tiên của phần chưa được sắp xếp đó. Quá trình này lặp lại cho đến khi toàn bộ dãy được sắp xếp.

Dãy số đã cho có 10 phần tử. Để sắp xếp một dãy có n phần tử bằng thuật toán sắp xếp chọn trực tiếp, ta cần thực hiện n-1 lần chọn phần tử nhỏ nhất và hoán đổi. Trong trường hợp này, n = 10, vậy số lần chọn lựa cần thiết là 10 - 1 = 9.

Vậy, cần thực hiện 9 lần chọn lựa phần tử nhỏ nhất để sắp xếp mảng có thứ tự tăng dần.

Câu 2:

Biểu diễn và tổ chức ngăn xếp (Stack) bằng danh sách liên kết giả sử bề mặt của ngăn xếp là đầu danh sách liên kết:

typedef struct SElement

{ T Key;

SElement *Next;

} SOneElement;

typedef struct SOneElement *SSTACK;

SSTACK SSP;

Thêm 1 phần tử vào ngăn xếp (dùng cấu trúc dữ liệu mô tả ở trên)

B1: NewElement = Khởi tạo nút mới (dùng toán tử new)

B2: if (NewElement == NULL)

Thực hiện BKT

B3: if (SSP == NULL)

B3.1: SSP = NewElement

B3.2: Thực hiện BKT

B4: …………………………………………

B5: …………………………………………

BKT: Kết thúc

Chọn câu lệnh chính xác cho B4 và B5

Lời giải:

Đáp án đúng: A

Câu hỏi này kiểm tra kiến thức về cách thêm một phần tử vào ngăn xếp (stack) được biểu diễn bằng danh sách liên kết, với đỉnh ngăn xếp là đầu danh sách.

Trong đoạn mã giả được cung cấp, B1 và B2 khởi tạo một nút mới và kiểm tra xem việc khởi tạo có thành công hay không. B3 kiểm tra xem ngăn xếp có rỗng hay không. Nếu rỗng, nút mới trở thành ngăn xếp. Nếu không rỗng, ta cần chèn nút mới vào đầu danh sách liên kết, tức là đỉnh ngăn xếp.

Để chèn một nút mới vào đầu danh sách liên kết, ta thực hiện như sau:
1. Gán con trỏ Next của nút mới (NewElement) trỏ đến đỉnh hiện tại của ngăn xếp (SSP). Điều này có nghĩa là `NewElement->Next = SSP;`
2. Cập nhật đỉnh ngăn xếp (SSP) để nó trỏ đến nút mới (NewElement). Điều này có nghĩa là `SSP = NewElement;`

Vì vậy, đáp án đúng là:
B4: NewElement ->Next = SSP
B5: SSP = NewElement

Câu 3:

Với cấu trúc dữ liệu như sau:

typedef struct DNode

{

int Key;

DNode * NextNode;

DNode * PreNode;

} DOneNode

typedef DLLOneNode * DPointerType;

typedef struct DPairNode

{ DPointerType DLLFirst;

DPointerType DLLLast;

} DPType;

Hàm thêm phần tử vào cuối danh sách liên kết đôi quản lý bởi 2 phần tử đầu và cuối

DPointerType DLLAddLast(DPType &DList, int NewData)

{

DPointerType NewNode = gọi hàm tạo nút mới có vùng dữ liệu là NewData ;

if (NewNode == NULL)

return (NULL);

if (DList.DLLLast == NULL)

DList.DLLFirst = DList.DLLLast = NewNode;

else

{

……………………………………………….

………………………………………………

}

return (NewNode);

} Hãy lựa chọn câu đúng nhất để điền vào chỗ trống ở trên

Lời giải:

Đáp án đúng: D

Đoạn code cần điền vào chỗ trống trong hàm `DLLAddLast` có nhiệm vụ thêm một nút mới vào cuối danh sách liên kết đôi. Để làm được điều này, chúng ta cần thực hiện các bước sau:

1. Liên kết nút cuối cùng hiện tại với nút mới: `DList.DLLLast->NextNode = NewNode;` (cho nút kế tiếp của nút cuối cùng hiện tại trỏ đến nút mới).
2. Liên kết nút mới với nút cuối cùng hiện tại: `NewNode->PreNode = DList.DLLLast;` (cho nút trước của nút mới trỏ đến nút cuối cùng hiện tại).
3. Cập nhật nút cuối cùng của danh sách: `DList.DLLLast = NewNode;` (nút cuối cùng của danh sách bây giờ là nút mới).

Như vậy, đáp án đúng là phương án 4.

Câu 4:

Thao tác nào dưới đây thực hiện trên hàng đợi (queue):

Lời giải:

Đáp án đúng: A

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 sẽ được loại bỏ trước. Thao tác thêm phần tử vào hàng đợi được thực hiện ở cuối hàng đợi (lối sau), và thao tác loại bỏ phần tử được thực hiện ở đầu hàng đợi (lối trước). Vì vậy, đáp án đúng là "Thêm phần tử vào lối sau".

Câu 5:

Cây nhị phân khác rỗng là cây:

Lời giải:

Đáp án đúng: C

Cây nhị phân là một cấu trúc dữ liệu dạng cây trong đó mỗi nút có tối đa hai nút con, thường được gọi là nút con trái và nút con phải. Một cây nhị phân khác rỗng có nghĩa là nó phải có ít nhất một nút (nút gốc). Do đó, đáp án đúng là mỗi nút có không quá 2 nút con.

Câu 6:

Cho danh sách đặc có 10 phần tử. Khi thêm phần tử vào vị trí 4 trong danh sách, vòng lặp dịch chuyển tịnh tiến nội dung các phần tử L->Elements[i]=L->Elements[i+1] sẽ thực hiện:

Lời giải: