Cho thuật toán sắp xếp Bubble Sort như sau: void BubbleSort(int M[], int N) { for (int I = 0; I for (int J = N-1; J > I; J--) if (M[J] Swap(M[J], M[J-1]); return; } Chọn câu đúng nhất cho hàm Swap

Câu 8:

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

Cấu trúc dữ liệu cho kiểu dữ liệu sinh viên như sau:

typedef struct tagSV{

char MSSV[8];

char Ten[30];

char NgaySinh[11];

float DTB;

}SV;

Khai báo

SV sv1, *sv2;

Lựa chọn các câu đúng nhất để gán giá trị cho mã sinh viên của sv1 và sv2:

Lời giải:

Đáp án đúng: B

sv1 là một biến kiểu SV, do đó truy cập vào thành viên của nó (ví dụ MSSV) sử dụng toán tử chấm (.). sv2 là một con trỏ tới kiểu SV, do đó truy cập vào thành viên của nó sử dụng toán tử mũi tên (->). Ngoài ra, MSSV là một mảng các kí tự (string), vì vậy không thể gán trực tiếp bằng dấu = mà cần sử dụng hàm strcpy.

Câu 10:

Với thủ tục như sau:

void operation()

{

int x,a[10],n;

int x,m,l,h,flag=0;

cout<<"Enter the element to be searched:";

cin>>x;

l=0; h=n-1;

while(l<=h)

{

m=(l+h)/2;

if(x==a[m]) {

lag=1; break;

}

else if(x>a[m])

l=m+1;

else if(x<a[m])

h=m-1;

}

if(flag==0)

cout<<"ABSENT";

else

cout<<"PRESENT";

}

Lựa chọn câu đúng nhất để mô tả thủ tục trên

Lời giải:

Đáp án đúng: B

Thủ tục được đưa ra là thuật toán tìm kiếm nhị phân (binary search). Thuật toán này hoạt động bằng cách liên tục chia đôi khoảng tìm kiếm. Nếu phần tử cần tìm (x) được tìm thấy trong mảng (a), thủ tục sẽ thông báo "PRESENT". Nếu sau khi xét hết mảng mà không tìm thấy x, thủ tục sẽ thông báo "ABSENT". Do đó, phương án đúng là "Thủ tục tìm nhị phân phần tử được nhập từ bàn phím, nếu không tìm thấy sẽ thông báo ABSENT".

Câu 11:

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

Lời giả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.

Câu 12:

Chọn định nghĩa đúng nhất về cây cân bằng tương đối:

Lời giải:

Đáp án đúng: C

Cây cân bằng tương đối, hay còn gọi là cây AVL, là một cây nhị phân đặc biệt. Điều kiện cân bằng của cây AVL là: với mọi nút trên cây, chiều cao của cây con trái và chiều cao của cây con phải của nút đó phải hơn kém nhau không quá 1. Điều này đảm bảo cây không bị lệch quá nhiều, giúp cho các thao tác tìm kiếm, thêm, xóa nút có độ phức tạp thời gian là O(log n), với n là số nút của cây.

Phương án 1 sai vì điều kiện cân bằng của cây AVL dựa trên chiều cao, không phải số nút.
Phương án 2 sai vì cây AVL là cây nhị phân, không phải cây N phân, và điều kiện chiều cao cũng sai.
Phương án 4 sai vì cây cân bằng tương đối (AVL) không phải là cây cân bằng hoàn toàn. Cây cân bằng hoàn toàn là một trường hợp đặc biệt của cây nhị phân mà tất cả các mức đều được lấp đầy hoàn toàn, ngoại trừ có thể mức cuối cùng không đầy đủ và các nút ở mức cuối cùng được dồn về bên trái.

Câu 13:

Tìm kiếm xem trong danh sách liên kết đơn có tồn tại nút có thành phần dữ liệu là SearchData hay không. Thao tác này chúng ta vận dụng thuật toán tìm tuyến tính để tìm kiếm:

typedef struct Node

{

int Data;

Node * Link;

} OneNode;'

typedef OneNode * Pointer;

Pointer SSList; // Quản lý danh sách liên kết đơn bởi 1 phần tử đầu

B1: CurNode = SLList

B2: IF (………………………………………………)

Thực hiện BKT

B3: CurNode = CurNode->Link

B4: Lặp lại B2