Hãy cho biết tư tưởng nào sau đây nói về của giải thuật tìm kiếm nhị phân?

Phát biểu sau đúng hay sai: Khi có lời gọi đệ quy, trạng thái hiện thời của chương trình (giá trị hiện thời của các biến, điểm ngắt thực hiện của chương trình) được lưu vào vùng bộ nhớ ngăn xếp?

Khi lưu trữ cây nhị phân dưới dạng mảng, phần tử ở vị trí số 9 đóng vai trò gì trong các phương án sau?

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: 

Độ cao của cây là gì?

Cho dãy số sau: 10 11 14 32 36 43 55 57 87 97 . Áp dụng phương pháp tìm kiếm nhị phân, sau bao nhiêu lần phân đoạn ta sẽ tìm thấy số 43?

Nút có khóa nhỏ nhất trong cây nhị phân tìm kiếm khác rỗng là:

Chỉ ra khái niệm có tính chất đệ quy?

Phát biểu sau đúng hay sai: Khi hết lời gọi đệ quy, chương trình chưa kết thúc. Chương trình được tiếp tục thực hiện từ "điểm ngắt" với những giá trị của các biến ở thời điểm ngắt?

Thời gian chạy chương trình phụ thuộc vào các yếu tố nào?

Thuật toán sắp xếp chèn trực tiếp (Straight Insertion Sort) được mô tả bằng đoạn mã giả như sau:

B1: K = 1

B2: IF (K = N) Thực hiện BKT

B3: X = M[K+1]

B4: Pos = 1

B5: IF (Pos > K) Thực hiện B7

B6: ELSE // Tìm vị trí chèn

B6.1: If (X <= M[Pos]) Thực hiện B7

B6.2: Pos++

B6.3: Lặp lại B6.1

B7: I = K+1 B8: IF (I > Pos)

B8.1: M[I] = M[I-1]

B8.2: I--

B8.3: Lặp lại B8

B9: ELSE

B9.1: M[Pos] = X

B9.2: K++

B9.3: Lặp lại B2

BKT: Kết thúc Trong đó B8 mô tả trường hợp

Cho thuật toán tìm nhị phân không đệ quy sau:

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

{ int First = 0;

int Last = N – 1;

while (First <= Last)

{

int Mid = (First + Last)/2;

if (X == M[Mid])

return(Mid);

if (X < M[Mid])

Last = Mid – 1;

else

First = Mid + 1;

}

return(-1);

} 

Chọn câu đúng nhất trong trường hợp tốt nhất khi phần tử ở giữa của mảng có giá trị bằng X: 

Nhân tố nào là nhân tố chính ảnh hưởng đến thời gian tính của một giải thuật:

Với dữ liệu đầu vào (n) đủ nhỏ, ta nên sử dụng phương pháp sắp xếp nào sau đây?

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

Với cấu trúc dữ liệu của danh sách liên kết đơn lưu trữ thông tin về phòng máy:

typedef struct PM

{

int maPM; int tongsoMay;

} PHONGMAY;

typedef struct Node { PHONGMAY Data; Node * NextNode;

} OneNode;

typedef OneNode * SLLPointer;

Để quản lý danh sách liên kết đơn bằng phần tử đầu và phần tử cuối, cần định nghĩa kiểu dữ liệu:

Tìm mệnh đề sai trong các mệnh đề sau: Một cấu trúc dữ liệu bao gồm…

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

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 trúc dữ liệu quản lý hàng đợi bằng hai phần tử đầu (Front) và 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, mã giả được mô tả như sau:

B1: NewElement = Khởi tạo nút mới có thà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

Chọn câu đúng nhất cho bước B4, B5

Cho dãy khoá 42,23,74,11,65,58 . Dùng phương pháp sắp xếp kiểu chọn (selection sort), sau 3 bước dãy có dạng nào?

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