Cấu trúc dữ liệu và giải thuật - IT05 - HOU

Câu hỏi 114188:

Các bước thực hiện tìm kiếm nhị phân phần tử x trên dẫy sắp xếp tăng dần được mô tả như sau:

Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy c left = …………… và right = ………………

Bước 2: Tính middle = (left + right)/2. So sánh a[middle] với x. Có 3 khả năng:

- a[middle] = x => Tìm thấy => Dừng

- a[middle] > x => tiếp tục tìm x trong dãy con mới với right = middle - 1 (tìm trong nửa đầu)

- a[middle] < x => tiếp tục tìm x trong dãy con mới với left = middle + 1 (tìm trong nửa cuối)

Bước 3:

- Nếu left <= right => dãy còn phần tử, tiếp tục quay lại bước 2 để tìm kiếm tiếp

- Ngược lại => Dãy hiện hành hết phần tử và dừng thuật toán

Giá trị cần điền vào dấu ………….. là bao nhiêu để thuật toán thực hiện đúng

A. n và 0

B. 0 và n-1

C. n-1 và 0

D. 0 và n

Câu hỏi 114189:

Cho thông tin của SV gồm: MaSV, HoTen, Tuoi, DTB

Đâu là đoạn mã để Sắp xếp danh sách SV theo ĐTB tăng dần bằng thuật toán Selection Sort

A. void SXDSSV( int n, SV ds[]){ int min, i, j; SV tg; for( i=0 ; i<n-1 ; i++ ) { min = i; for( j=i+1 ; j<n ; j++ ) if ( ds[j].DTB > ds[min].DTB ) min = j; if( min != i )
{ tg = ds[min];
ds[min] = ds[i];
ds[i] = tg; } }}

B. void SXDSSV( int n, SV ds[]){ int min, i, j; SV tg; for( i=0 ; i<n-1 ; i++ ) { min = i; for( j=i+1 ; j<n ; j++ ) if ( ds[j].DTB < ds[min].DTB ) min = j; if( min != i )
{ tg = ds[min];
ds[min] = ds[i];
ds[i] = tg; } }}

C. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].DTB<x.DTB)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}

D. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].DTB>x.DTB)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}

Câu hỏi 114190:

Cho đoạn mô tả sau:

Bước 1: Khởi đầu tìm kiếm trên tất cả các phần tử của dãy

(left = 0 và right = n - 1)

Bước 2: Tính middle = (left + right)/2. So sánh a[middle] với x. Có 3 khả năng:

a[middle] = x thì thông báo Tìm thấy => Dừng

a[middle] > x thì right = middle - 1

a[middle] < x thì left = middle + 1

Bước 3:

Nếu left <= right và quay lại bước 2 để tìm kiếm tiếp

Ngược lại thông báo không tìm thấy và dừng thuật toán

A. Các đáp án đưa ra đều sai

B. Mô tả thuật toán tìm kiếm tuyến tính

C. Mô tả thuật toán tìm kiếm nhị phân

D. Các đáp án trên đều đúng

Câu hỏi 114191:

Cho thông tin của SV gồm: MaSV, HoTen, Tuoi, DTB

Đâu là đoạn mã để Sắp xếp danh sách SV theo Tuổi tăng dần bằng thuật toán Selection Sort

A. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].Tuoi<x.Tuoi)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}

B. void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].Tuoi>x.Tuoi)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}

C. void SXDSSV( int n, SV ds[]){ int min, i, j; SV tg; for( i=0 ; i<n-1 ; i++ ) { min = i; for( j=i+1 ; j<n ; j++ ) if ( ds[j].Tuoi < ds[min].Tuoi ) min = j; if( min != i )
{ tg = ds[min];
ds[min] = ds[i];
ds[i] = tg; } }}

D. void SXDSSV( int n, SV ds[]){ int max, i, j; SV tg; for( i=0 ; i<n-1 ; i++ ) { max = i; for( j=i+1 ; j<n ; j++ ) if ( ds[j].Tuoi > ds[max].Tuoi) max = j; if(max!= i )
{ tg = ds[max];
ds[max] = ds[i];
ds[i] = tg; } }}

Câu hỏi 114192:

Đoạn mã sau đây thực hiện nhiệm vụ gì

void SXDSV_InsertionSort( int n, SV ds[]){ int pos,i; SV x; for(i=1;i<n;i++) { x = ds[i]; pos = i-1; while((pos>=0)&&(ds[pos].Tuoi>x.Tuoi)) { ds[pos+1] = ds[pos]; pos--; } ds[pos+1] = x; //chèn x vào dãy }}

A. Thực hiện sắp xếp danh sách SV theo Tuoi giảm dần bằng thuật toán Insertion

B. Thực hiện sắp xếp danh sách SV theo Tuoi giảm dần bằng thuật toán Selection

C. Thực hiện sắp xếp danh sách SV theo Tuoi tăng dần bằng thuật toán Insertion

D. Thực hiện sắp xếp danh sách SV theo Tuoi tăng dần bằng thuật toán Selection

Câu hỏi 114193:

Đoạn mã dưới đây mô tả thuật toán gì: B1: k = 1 B2: if M[k] == X and k !=n

B2.1: k++

B2.2: Lặp lại bước 2

B3: if (k<N) thông báo tìm thấy tại vị trí thứ k

B4: else thông báo không tìm thấy

B5: Kết thúc

A. Tìm kiếm tuyến tính phần tử X trong mảng

B. Tìm kiếm nhị phân phần tử có giá trị X

C. Tất cả các lựa chọn trên đều sai

D. Tìm phần tử nhỏ nhất của mảng M gồm N phần tử

Câu hỏi 114194:

Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp chèn trực tiếp (Insertion Sort) để sắp xếp tăng dần, sau 3 lần lặp kết quả của dãy là thế nào?

A. 11, 23, 42, 74, 58, 65

B. 11, 23, 42, 65, 74, 58

C. 11, 23, 42, 74, 65, 58

D. 11, 23, 58, 65, 42, 74

Câu hỏi 114195:

Cho mảng a gồm các phẩn tử có giá trị như sau:

74326

Số lần hoán vị 2 phần tử khác nhau khi áp dụng thuật toán chọn trực tiếp để sắp xếp mảng tăng dần là:

A. 2

B. 5

C. 4

D. 3

Câu hỏi 114196:

Cho đoạn chương trình:

void QuickSort( int a[ ], int L , int R )

{

int i,j,x;

x=……..;

i = L; j = R;

do

{

while ( a[i] < x ) i++;

while ( a[j] > x ) j--;

if ( i <= j )

{

Hoanvi (a[i], a[j]);

i++; j--;

}

} while(i<j);

if (L<j) QuickSort(a,L,j);

if (i<R) QuickSort(a,i,R);

}

Điền giá trị nào vào đoạn …. cho đúng

A. a[R/2]

B. a[(L-R)/2]

C. a[(L+R)/2]

D. a[(L+R)]

Câu hỏi 114197:

Hàm mô tả sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử:

1. void BubbleSort(int M[ ], int N)

2. {

3.int i,j,tg;

4.for( i = 0 ; i < N-1 ; i++ )

5.........................................

6.if ( M[j] < M[j-1] )

7.{

8.tg = M[j];

9.M[ j] = M[j-1];

10.M[ j-1] = tg;

11.}

12.}

Lệnh nào sau đây sẽ được đưa vào dòng số [5] của đoạn mã trên

A. for( j = N-1; j>i; j++)

B. Không có dòng lệnh nào phù hợp, không cần thêm thuật toán vẫn chạy đúng

C. for( j = N; j< i; j--)

D. for( j = N-1; j>i; j--)

Câu hỏi 114198:

Cho đoạn chương trình:

void QuickSort( int a[ ], int L , int R )

{

int i,j,x;

x= a[(L+R)/2];

i = L; j = R;

do

{

while ( a[i] < x ) i++;

while ( a[j] > x ) j--;

if ( i <= j )

{

Hoanvi (a[i], a[j]);

i++; j--;

}

} while(i<j);

if (L<j) ….

if (i<R) ….

}

Điền giá trị nào vào đoạn …. cho đúng

A. QuickSort(a,L,j);
QuickSort(a,R,i);

B. QuickSort(a,i,R);
QuickSort(a,L,j);

C. QuickSort(a,j,L);
QuickSort(a,i,R);

D. QuickSort(a,L,j);
QuickSort(a,i,R);

Câu hỏi 114199:

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:

A. void Swap( int *X, int *Y)
{
int Temp = X;
X=Y;
Y = Temp;
return ;
}

B. void Swap( int X, int Y)
{
int Temp = X;
X=Y;
Y = Temp;
return ;
}

C. void Swap( floatX, float Y)
{
int Temp = X;
X=Y;
Y = Temp;
return ;
}

D. void Swap( int &X, int &Y)
{
int Temp = X;
X=Y;
Y = Temp;
return ;
}

Câu hỏi 114200:

Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp phân hoạch (Quick Sort), điểm chốt a[middle] ban đầu là:

A. Các đáp án đưa ra đều không đúng

B. a[middle] = 11

C. a[middle] = 23

D. a[middle] = 74

Câu hỏi 114201:

Thủ tục mô tả thuật toán sắp xếp chọn trực tiếp:

void SapXepChonTrucTiep( T M[], int N)

{

int K = 0, posmin;

int Temp;

................................................

{

T Min = M[K];

Posmin = K;

for( int pos = K+1; pos<N; pos++)

if( Min > M[pos])

{

Min = M[pos];

Posmin = pos;

}

Temp = M[k];

M[k] = m[posmin];

M[posmin] = Temp;

}

return;

}

Đoạn mã cần thiết để đặt vào dòng .....................để chương trình sắp xếp đúng

A. for ( k =0; k<n-1; k++)

B. for ( k =n-1; k>0; k--)

C. for ( k =n; k>0; k--)

D. for ( k =0; k<n-1; k--)

Câu hỏi 114202:

Cho dãy 10, 5, 7, 3, 9, 2, 15, 1. Cho biết kết quả sau lần duyệt thứ nhất của thuật toán sắp xếp tăng dần bằng QuickSort

A. 1, 2, 3, 5, 9, 7, 15, 10

B. 1, 2, 3, 5, 7, 9, 15, 10

C. 1, 2, 5, 7, 9, 3, 15, 10

D. 1, 2, 3,7,9, 5, 15, 10

Câu hỏi 114203:

Một chương trình cài đặt trên máy tính được xác định bởi thành phần nào

A. Cấu trúc dữ liệu

B. Cả hai thành phần

C. Không phải là các thành phần

D. Thuật toán

Câu hỏi 114204:

Đây là định nghĩa của độ phức nào? “được tính là tổng số chi phí về mặt tổng thời gian cần thiết để hoàn thành thuật toán, được đánh giá dựa vào số lượng các thao tác được sử dụng trong thuật toán dựa trên bộ dữ liệu đầu vào

”

A. Thời gian

B. Cả hai lựa chọn đều đúng

C. Cả hai lựa chọn đều sai

D. Không gian

Câu hỏi 114205:

Cho biết kết quả của đoạn chương trình sau:

int F(int a[], int n)

{

if (n==1)

return a[0];

else

return a[n-1] + F(a,n-1);

}

int main()

{

int a[] = {2, 3, 4, 5, 6};

printf("%d",F(a,5));

getch();

}

A. 14

B. 20

C. 18

D. 2

Câu hỏi 114206:

Cho biết kết quả sau khi thực hiện đoạn chương trình sau:

int main()

{

int a[20], n,i,k;

k = a[0];

for(i=0; i<n; i++)

if (a[i] > k)

k = a[i];

}

A. k có giá trị lớn nhất

B. a[k] có giá trị nhỏ nhất

C. a[k] có giá trị lớn nhất

D. k có giá trị nhỏ nhất

Câu hỏi 241678:

Cho mảng a gồm các phần tử: 8, 3, 7, 6, 4,2.

Cho biết kết quả ở bước thứ 3 khi áp dụng thuật toán sắp xếp Insertion tăng dần trên mảng các phần tử trên.

A. 3 4 6 7 8 2

B. 2 3 4 6 7 8

C. 3 8 7 6 4 2

D. 3 6 7 8 4 2

Cấu trúc dữ liệu và giải thuật - IT05 (255)