Loading [MathJax]/jax/output/CommonHTML/jax.js

Cho hàm tìm kiếm tuyến tính như sau:

int TimKiem (int M[], int N, int X)

{ int k = 0;

M[N] = X;

while (M[k] != X)

k++;

if (k < N)

return (k);

return (-1);

}

Chọn câu đúng nhất:

Hàm sẽ trả về 0 nếu không tìm thấy phần tử có giá trị là X

Hàm sẽ trả về 1 nếu tìm thấy phần tử có giá trị là X

Hàm sẽ trả về -1 nếu không tìm thấy phần tử có giá trị là X

Hàm sẽ trả về 1 nếu không tìm thấy phần tử có giá trị là X

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

Trả lời:

Đáp án đúng: C

Đoạn code cung cấp một hàm tìm kiếm tuyến tính

$TimKiem$ trong một mảng

$M$ có kích thước

$N$ để tìm giá trị

$X$ . Hàm này hoạt động bằng cách gán

$X$ vào vị trí

$M[N]$ (vượt quá kích thước mảng ban đầu) để đảm bảo vòng lặp

$while$ luôn kết thúc. Sau đó, nó duyệt qua mảng từ đầu đến khi tìm thấy

$X$ . Nếu

$X$ được tìm thấy trước vị trí

$N$ , hàm trả về chỉ số

$k$ của vị trí đó. Nếu không (tức là

$X$ chỉ được tìm thấy tại vị trí

$M[N]$ mà ta đã gán), hàm trả về -1. Vậy, nếu không tìm thấy

$X$ trong

$N$ phần tử đầu tiên của mảng, hàm sẽ trả về -1. Do đó, phương án đúng là "Hàm sẽ trả về -1 nếu không tìm thấy phần tử có giá trị là X".

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

Lựa chọn định nghĩa về danh sách đúng nhất?

Lời giải:

Đáp án đúng: D

Câu hỏi yêu cầu tìm định nghĩa đúng nhất về danh sách. Ta xét từng phương án:

Phương án a: "Danh sách là tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó" - Đây là một định nghĩa đúng về danh sách. Các phần tử trong danh sách thường có cùng kiểu dữ liệu (ví dụ: danh sách số nguyên, danh sách chuỗi) và có một thứ tự hoặc quan hệ nào đó giữa chúng.
Phương án b: "Số phần tử của danh sách gọi là chiều dài của danh sách" - Đây cũng là một định nghĩa chính xác. Chiều dài của danh sách là số lượng các phần tử mà nó chứa.
Phương án c: "Một danh sách có chiều dài bằng 0 là một danh sách rỗng" - Hoàn toàn chính xác. Danh sách rỗng là danh sách không chứa bất kỳ phần tử nào.
Phương án d: "Cả a, b, c đều đúng" - Vì cả a, b, và c đều đúng, nên đây là đáp án chính xác nhất.

Vậy đáp án đúng là d.

Câu 3:

Cấu trúc dữ liệu mảng có các ưu điểm nào?

Lời giải:

Đáp án đúng: D

Câu hỏi này kiểm tra kiến thức về ưu điểm của cấu trúc dữ liệu mảng. Chúng ta cùng phân tích từng đáp án:

Đáp án 1: Đúng. Mảng có nhược điểm là việc chèn hoặc xóa phần tử ở giữa mảng đòi hỏi phải dịch chuyển các phần tử khác, gây tốn thời gian.
Đáp án 2: Đúng. Ưu điểm lớn nhất của mảng là khả năng truy xuất ngẫu nhiên (random access) thông qua chỉ số, giúp việc tìm kiếm và truy cập phần tử nhanh chóng.
Đáp án 3: Sai. Mảng có thể lãng phí bộ nhớ nếu kích thước mảng được khai báo lớn hơn số lượng phần tử thực tế được sử dụng.
Đáp án 4: Sai. Vì đáp án c sai.

Vậy, đáp án đúng nhất là đáp án b.

Câu 4:

Định nghĩa nào là đúng với danh sách liên kết?

Lời giải:

Đáp án đúng: C

Danh sách liên kết là một cấu trúc dữ liệu trong đó các phần tử được liên kết với nhau thông qua các con trỏ (vùng liên kết). Mỗi phần tử chứa dữ liệu và một con trỏ đến phần tử tiếp theo trong danh sách. Điều này khác với mảng, nơi các phần tử được lưu trữ liên tiếp trong bộ nhớ. Phương án 1 sai vì danh sách liên kết không phải là cấu trúc dữ liệu dạng cây. Phương án 4 sai vì nó mô tả mảng, không phải danh sách liên kết. Phương án 2 đúng, nhưng chưa đủ ý. Phương án 3 mô tả chính xác bản chất của danh sách liên kết, trong đó các phần tử được kết nối thông qua vùng liên kết.

Câu 5:

Với định nghĩa cấu trúc dữ liệu cho danh sách liên kết đơn:

typedef struct Node

{

int Data; Node * Link;

} OneNode;

typedef OneNode * SLLPointer;

Hàm dưới đây để thêm một phần tử có giá trị thành phần dữ liệu là NewData vào trong danh sách liên kết đơn SLList vào ngay sau nút có địa chỉ InsNode.

SLLPointer ThemGiua(SLLPointer &SList, int NewData, SLLPointer &InsNode)

{ SLLPointer NewNode = new OneNode;

if (NewNode != NULL)

NewNode ->NextNode = NULL;

NewNode ->Data = NewData;

else

return (NULL);

if (InsNode->Link == NULL)

{

InsNode-> Link = NewNode; return (SList);

}

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

return (SList);

}

Hãy lựa chọn câu đúng nhất:

Lời giải:

Đáp án đúng: B

Câu 6:

Cho thuật toán sau:

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

{ int k = 0;

while (M[k] != X k < N )

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

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, thuật toán

$LinearSearch$ sẽ duyệt qua toàn bộ mảng

$M$ có

$N$ phần tử. * **Số phép gán:** Phép gán

$k = 0$ được thực hiện một lần duy nhất trước vòng lặp

$while$ . Vậy

$Gmax = 1$ . * **Số phép so sánh:** * Trong vòng lặp

$while$ , điều kiện

$M[k] != X && k < N$ được kiểm tra. Điều này bao gồm hai phép so sánh:

$M[k] != X$ và

$k < N$ . Vòng lặp này sẽ thực hiện

$N$ lần (vì

$X$ không tồn tại trong mảng). Vì vậy, số phép so sánh trong vòng lặp là

$2N$ . * Sau vòng lặp, điều kiện

$k < N$ trong câu lệnh

$if$ được kiểm tra một lần nữa. Điều này thực hiện phép so sánh thêm 1 lần. * Vậy tổng số phép so sánh là:

$Smax = 2N + 1$ . Vì vậy, phương án đúng nhất là: * Số phép gán:

$Gmax = 1$ * Số phép so sánh:

$Smax = 2N + 1$

Câu 7:

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

Lời giải: