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

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:

Đáp án đúng: D

Đề bài yêu cầu tìm vị trí xuất hiện cuối cùng của phần tử `x` trong mảng `a`. Đoạn code duyệt mảng `a` từ cuối về đầu (từ `n` về 1). Vòng lặp dừng khi `i >= 1`. Nếu `a[i]` bằng `x` thì trả về `i`. Nếu duyệt hết mảng mà không tìm thấy `x` thì trả về -1.

Mảng `a` có các phần tử: a[1] = -3, a[2] = -3, a[3] = 15, a[4] = -3.
`n = 4`, `x = -3`.

- Vòng lặp 1: `i = 4`. `a[4] == x` (-3 == -3) là đúng. Trả về 4.

Vậy kết quả đúng là 4.

Câu 13:

Dấu hiệu nào dưới đây cho biết danh sách liên kết đơn L là rỗng:

Lời giải:

Đáp án đúng: D

Trong danh sách liên kết đơn, con trỏ L đại diện cho con trỏ đầu danh sách. Nếu L == NULL, điều đó có nghĩa là danh sách chưa được khởi tạo hoặc danh sách rỗng. Các phương án còn lại liên quan đến các thuộc tính bên trong một nút của danh sách (left, infor, next), và do đó không thể dùng để xác định danh sách rỗng.

Câu 14:

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: