Câu hỏi về thuật toán và tìm kiếm CTDL

Câu 4: Đoạn mã giả dưới đây mô tả thuật toán gì?

Thuật toán:

B1: k = 1

B2: IF M[k] == X AND k != N

B2.1: k++

B2.2: Lặp lại B2

B3: IF k < N Thông báo tìm thấy tại vị trí k

B4: ELSE Không tìm thấy.

B5: Kết thúc

• Tìm nhị phân phân tử có giá trị X

• Tìm phần từ nhỏ nhất của măng M bao gồm N phần từ

• Tìm tuyến tính phân tử có giá trị X

• Cả a, b, c đều sai

Câu 5: Cho hàm tim 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

Câu 6: Xét thủ tục sau: int TimKiemNP (int M[], int First, int Last. int X)

 { if (First > Last)

return (-1);

int Mid (First + Last)/2;

if (X = M[Mid])

 return (Mid);

if (X < M[Mid])

 return(TimKiemNP (M, First, Mid-1, X));

else

  return(TimKiemNP (M, Mid + 1, Last, X)); }

Lựa chọn câu đúng nhất để mô tả thủ tục trên:

• Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần từ từ chỉ số từ First đến chỉ số Last

• Thủ tục hỗ trợ tim kiểm đệ quy phần tử có giá t giá trị là X trên màng các phần từ từ chỉ số từ First đến chỉ số Last

• Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần từ từ chỉ số từ Last đến chỉ số First

• Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

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

• 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ữachúng có một mối liên hệ nào đó

• B. Số phần tử của danh sách gọi là chiều dài của danh sách

• C. Một danh sách có chiều dài bằng 0 là một danh sách rỗng

• D. Cả a, b, c đều đúng

Câu 14: Tìm mô tả đúng cho hàm sau:

int SC (int M[], int Len, int CM[])

 { for (int i = 0; i < Len; i++)

 CM[i] = M[i];

return (Len);}

• A. Hàm thực hiện việc sao chép nội dung màng CM có chiều dài Len về mảng M có cùng chiều dài. Hàm trả về chiều dài của mảng M sau khi sao chép

• B. Hàm thực hiện việc sao chép nội dung mảng M có chiều dài Len -1 về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng CM sau khi sao chép

• C. Hàm thực hiện việc sao chép nội dung màng CM có chiều dài Len -1 về mảng M có cùng chiều dài. Hàm trả về chiều dài của măng M sau khi sao chép

• D. Hàm thực hiện việc sao chép nội dung màng M có chiều dài Len về mảng CM có cùng chiều dài. Hàm trả về chiều dài của màng CM sau khi sao chép

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

• Việc thêm, bớt các phần tử trong danh sách đặc có nhiều khó khăn do phải di dời các phần tử khác đi qua chỗ khác

• Việc truy xuất và tìm kiếm các phần tử của mảng là dễ dàng vì các phần tử đứng liền nhau nên chúng ta chỉ cần sử dụng chỉ số để định vị vị trí các phần tử trong danh sách (định vị địa chỉ các phần tử)

• Mật độ sử dụng bộ nhớ của mảng là tối ưu tuyệt đối

• Câu a, b, c đúng

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

• Danh sách liên kết là cấu trúc dữ liệu dạng cây

• Danh sách liên kết là cấu trúc dữ liệu tự định nghĩa

• Danh sách liên kết là tập hợp các phần tử mà giữa chúng có một sự nổi kết với nhau thông qua vùng liên kết của chúng

• Danh sách liên kết là tập hợp các phần tử mà đặt kề cận với nhau trong vùng nhớ

Câu hỏi: Định nghĩa cấu trúc dữ liệu của danh sách liên kết đơn được mô tả như sau:

typedef struct Node

{ int ElementType;

Node * Next;

} pNode;            

Trong đó, khai báo Node * Next; dùng để mô tả:

• Con trỏ trỏ tới phần dữ liệu

• Vùng liên kết quản lý địa chỉ phần tử kế tiếp

• Con trỏ trỏ tới địa chỉ vùng nhớ của phần từ trước đó trong danh sách liên kết đơn

• Con trỏ trỏ tới địa chỉ vùng nhớ của phần tử đầu tiên trong danh sách liên kết đơn

Câu 1: Cấu trúc dữ liệu nào tương ứng với LIFO/FILO?

• Queue

• Linked List

• Tree

• Stack

Câu 1.1: Cấu trúc dữ liệu nào tương ứng với FIFO/LILO?

• Queue

• Linked List

• Tree

• Stack