Cấu trúc dữ liệu và giải thuật - IT05 (255)
Đoạn mã cài đặt hàm tìm kiếm nhị phân phần tử x trên dãy sắp xếp tăng dần:
int BinarySearch( int a[ ], int n, int x )
{
int left = ……….., right = ……………;
int middle;
do
{
middle = (left+right)/2;
if (x == a[middle]) break;
else if (x<a[middle]) right = middle - 1;
else left = middle + 1;
} while ( left <= right );
if ( left <= right ) return middle;
else return -1;//ko tìm thấy phần tử x
}
Giá trị được điền vào dấu ………... để đoạn mã cài đặt thực hiện đúng:
A. 0 và n-1
B. n và 1
C. n-1 và 0
D. 1 và n
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 5 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, 58, 74
C. 11, 23, 58, 65, 42, 74
D. 11, 23, 42, 58, 65, 74
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 2 lần lặp kết quả của dãy là thế nào?
A. 11, 23, 58, 65, 42, 74
B. 23, 42, 74, 11, 65, 58
C. 11, 23, 42, 74, 58, 65
D. 11, 23, 42, 65, 74, 58
Các phương pháp tìm kiếm là
A. Tất cả các đáp án đều sai
B. Tìm kiếm tuyến tính và nhị phân
C. Tìm kiếm nhị phân
D. Tìm kiếm tuyến tính
Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp đổi chỗ trực tiếp (Interchange 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, 58, 74, 65
B. 11, 23, 42, 74, 65, 58
C. 11, 23, 42, 65, 58, 74
D. 11, 23, 42, 58, 65, 74
Cho thuật toán sau:
int LinenearSearch( 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:
A. Số phép gán: Gmax = 1 Số phép so sánh: Smax = 2N + 2
B. Số phép gán: Gmax = 1 Số phép so sánh: Smax = 2N + 1
C. Số phép gán: Gmax = 1 Số phép so sánh: Smax = N + 2
D. Số phép gán: Gmax = 2 Số phép so sánh: Smax = 2N + 1
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
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
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();
}
Đâ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
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
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
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--)
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
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)
B. void Swap( int X, int Y)
C. void Swap( floatX, float Y)
D. void Swap( int &X, int &Y)
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);
B. QuickSort(a,i,R);
C. QuickSort(a,j,L);
D. QuickSort(a,L,j);
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--)
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)]
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à:
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
