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

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

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

Cho cây biểu thức sau:
Chọn biểu thức tương ứng với cây

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:

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 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 báo
SV sv1, *sv2;
Lựa chọn các câu đúng nhất để gán giá trị cho mã sinh viên của sv1 và sv2:

Với thủ tụ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 chọn câu đúng nhất để mô tả thủ tục trên

Biểu diễn và tổ chức ngăn xếp (Stack) bằng danh sách liên kết giả sử bề mặt của ngăn xếp là đầu danh sách liên kết:
typedef struct SElement
{ T Key;
SElement *Next;
} SOneElement;
typedef struct SOneElement *SSTACK;
SSTACK SSP;
Thêm 1 phần tử vào ngăn xếp (dùng cấu trúc dữ liệu mô tả ở trên)
B1: NewElement = Khởi tạo nút mới (dùng toán tử new)
B2: if (NewElement == NULL)
Thực hiện BKT
B3: if (SSP == NULL)
B3.1: SSP = NewElement
B3.2: Thực hiện BKT
B4: …………………………………………
B5: …………………………………………
BKT: Kết thúc
Chọn câu lệnh chính xác cho B4 và B5

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 về hàng đợi (Queue):

Chiều dài đường đi của một cây (path’s length of the tree) được định nghĩa là tổng tất cả các chiều dài đường đi của tất cả các nút trên cây. Xét cây sau:

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

Chọn định nghĩa đúng nhất về cây cân bằng tương đố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:
struct Node
{
int Key; Node *
NextNode;
} OneNode;
Trong đó, khai báo Node * NextNode; dùng để mô tả

Khi cần thêm một phần tử có giá trị thành phần dữ liệu là NewData (là một số nguyên) vào đầu của danh sách liên kết đơn dùng thuật toán có mã giả mô tả như dưới đây?
typedef struct Node
{
int Data; Node * NextNode;
} OneNode; typedef OneNode * SLLPointer;
SLLPointer SSList;
B1: NewNode = new OneNode
B2: IF (NewNode = NULL) Thực hiện BKT
B3: NewNode ->NextNode = NULL
B4: NewNode ->Data = NewData B5: NewNode->NextNode = SLList
B6: SLList = NewNode BKT: Kết thúc
Tìm mô tả chính xác cho B5

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
BKT: Kết thúc
Chọn điều kiện hợp lý cho mã giả ở B2

Cho cấu trúc dữ liệu như sau:
typedef struct Node
{
int Key;
Node *NextNode;
} OneNode;
typedef SLLOneNode * Type;
Thuật toán chọn trực tiếp viết trên ngôn ngữ C++ áp dụng cho danh sách liên kết đơn quản lý bởi một phần tử đầu tiên được mô tả:
void StraightSelection(Type &SList)
{
Type MinNode;
int Temp;
Type CurrNode,TempNode;
CurrNode = SList;
while (CurrNode!=NULL)
{
TempNode = CurrNode->NextNode;
MinNode = CurrNode;
while (TempNode!=NULL)
{
TempNode = CurrNode->NextNode;
MinNode = CurrNode;
while (TempNode!=NULL)
{
if (………………………………………………)
MinNode = TempNode;
TempNode = TempNode->NextNode;
}
[1] Temp = MinNode->Key;
[2] MinNode->Key = CurrNode->Key;
[3] CurrNode->Key = Temp CurrNode=CurrNode->NextNode;
}
}
Tìm mô tả chính xác cho [1], [2], [3]

Với cấu trúc dữ liệu như sau:
typedef struct DNode
{
int Key;
DNode * NextNode;
DNode * PreNode;
} DOneNode
typedef DLLOneNode * DPointerType;
typedef struct DPairNode
{ DPointerType DLLFirst;
DPointerType DLLLast;
} DPType;
Hàm thêm phần tử vào cuối danh sách liên kết đôi quản lý bởi 2 phần
tử đầu và cuối
DPointerType DLLAddLast(DPType &DList, int NewData)
{
DPointerType NewNode = gọi hàm tạo nút mới có vùng dữ liệu là
NewData ;
if (NewNode == NULL)
return (NULL);
if (DList.DLLLast == NULL)
DList.DLLFirst = DList.DLLLast = NewNode;
else
{
……………………………………………….
……………………………………………….
………………………………………………
}
return (NewNode);
} Hãy lựa chọn câu đúng nhất để điền vào chỗ trống ở trên