220 câu trắc nghiệm Cấu trúc dữ liệu và giải thuật có đáp án - Đề 2

Tìm mô tả đúng nhất cho hàm TinhTong sau:

int TinhTong(int N)
{ int so = 2; int tong = 0; int dem = 0;
while (dem <N)
{
if (KiemTra(so) == 1)
{
tong = tong + so;
dem ++;
}
so = so + 1;
}
return tong;
} Trong đó
int KiemTra(int so)
{
for (int i = 2; i<so; i++)
if (so%i == 0)
return 0;
return 1;
}

Các tiêu chuẩn đánh giá cấu trúc dữ liệu. Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí:

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

Tổ chức 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;

Mã giả thuật toán 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:

B1: NewNode = new OneNode

B2: IF (NewNode = NULL) Thực hiện BKT

B3: NewNode ->Link = NULL

B4: NewNode ->Data = NewData

B5: IF (InsNode-> Link = NULL)

B5.1: InsNode-> Link = NewNode

B5.2: Thực hiện BKT // Nối các nút kế sau InsNode vào sau NewNode

B6: ………………………………………………..

// Chuyển mối liên kết giữa InsNode với nút kế của nó về NewNode

B7: ………………………………………………..

BKT: Kết thúc

B6 và B7 dùng để nối nút kế sau InsNode vào sau NewNode và chuyển mối liên kết giữa InsNode với nút kế nó về NewNode.

Hãy chọn câu đúng nhất cho B6 và B7

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:

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

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

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

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

Chọn định nghĩa đúng nhất đối với cây nhị phân tìm kiếm:

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);

}

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);

}

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

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

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

Danh sách duyệt hậu tự của biểu thức trong câu 3 là:

Chỉ ra kiểu dữ liệu cơ bản:

Chỉ ra kiểu dữ liệu không cơ bản:

Chỉ ra kiểu dữ liệu trừu tượng:

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh hoạ bằng đẳng thức:

Phát biểu sau đúng hay sai: khi nói tới dữ liệu thì cũng phải xem xét dữ liệu đó cần được thực hiện bằng giải thuật gì để đạt được kết quả mong muốn?

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

Phát biểu sau đúng hay sai: Chương trình đệ quy là những chương trình máy tính có sử dụng giải thuật đệ quy?

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?

Hãy chọn định nghĩa đúng nhất về danh sách kiểu hàng đợi (Queue)?

Trong lưu trữ dữ liệu kiểu Queue (Q) dưới dạng mảng nối vòng, giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Điều kiện F=R=0 nghĩa là gì trong các phương án sau?

Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối sau của Q. Khi thêm một phần tử vào Queue, thì R và F thay đổi thế nào trong các phương án sau?

Hãy cho biết quy tắc đúng của phép duyệt cây theo thứ tự sau trong các phương án sau?

Thời gian thực hiện các lệnh đơn (gán, đọc, viết) là bao nhiêu trong các phương án sau?

Trong các giải thuật sắp xếp, giải thuật nào sau đây áp dụng phương pháp Chia để trị?

Cho cây nhị phân: A B C D E F. Cho biết thứ tự các phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự giữa?

Cho cây nhị phân: A B C D E F. Cho biết thứ tự các phần tử được duyệt nào sau đây là đúng khi sử dụng phép duyệt cây theo thứ tự sau?

Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha là i thì vị trí của nút con trái là gì trong các phương án sau?

Trong biểu diễn dữ liệu dưới dạng cây, Khái niệm nào sau đây là cấp của cây?

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ năm là:

Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ sáu là:

Cho dãy số sau: 40 25 75 15 65 55 90 30 95 85. Áp dụng phương pháp sắp xếp hòa nhập (Merge_Sort) trực tiếp, sau lượt 1 dãy sẽ được sắp xếp lại như thế nào?

Cho dãy số sau: 14 32 10 43 57 87 55 36 97 11. Áp dụng phương pháp tìm kiếm tuần tự, sau bao nhiều lần thực hiện phép so sánh ta sẽ tìm thấy số 43?

Để viết chương trình chỉ để sử dụng một số ít lần và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chương trình thì ta chọn thuật toán:

Thế nào là sắp xếp ngoài?

Đâu là phương pháp sắp xếp trong, trong các phương pháp sau:

Đâu là phương pháp sắp xếp ngoài, trong các phương pháp sau:

Thế nào là ngôn ngữ giả?

Cho lệnh gán X := F với F = 5X + 7Y , X=6, Y =X + 2. Sau lệnh này X có giá trị:

Trong giải thuật xếp 8 con hậu, nếu đã có con hậu ở ô (5,3) thì không con hậu nào được nằm ở ô:

Cây 5 phân có nghĩa là gì?

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?

Phương pháp sắp xếp nhanh (Quick sort) chính là phương pháp:

Giả sử có hàm tính số Fibonaci là fibo(int n), cho biết lệnh nào đúng khi tính giá trị Fibonaci của n và gán cho biến kết quả?
 

Bài toán tháp Hà Nội được phát biểu như sau:

Input: có 3 cái cọc và n cái đĩa xếp tại cọc 1

Output: Chỉ ra các bước thực hiện di chuyển n cái đĩa từ cọc 1 sang cọc

Nếu sử dụng giải thuật đệ quy, chỉ ra trường hợp gọi đệ quy: