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

Để tính biểu thức s = ½ + 2/3 + ¾ + … + n/(n+1) ta chọn hàm

Để tính biểu thức s = ½ + ¼ + … + 1/(2n) với n>=1 ta chọn hàm

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

long F(int n)

{

if ((2*n+1) ==1)

return 1;

else

return (2*n+1)+F(n-1);

}

void main()

{

long x=F(3);

printf("%ld", x);

}

Trong giải thuật đệ quy thì lời giải trực tiếp mà không phải nhờ đến một bài toán con nào đó là thành phần nào?

** Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp nổi bọt (Bubble Sort) để sắp xếp giảm dần, sau lần lặp thứ ba kết quả của dãy là thế nào?

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

3126

Số lần hoán vị 2 phần tử khác nhau khi áp dụng thuật toán nổi bọt để sắp xếp mảng giảm dần là:

Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần, sau 4 lần lặp kết quả của dãy là thế nào?

Cho dãy sau: 23, 78, 45, 8, 32, 56. Dùng phương pháp sắp xếp chọn trực tiếp (Selection Sort) để sắp xếp tăng dần, sau 3 lần lặp thì kết quả của dãy là thế nào?

Cho dãy sau: 42, 23, 74, 11, 65, 58. Dùng phương pháp sắp xếp nổi bọt (Bubble Sort) để sắp xếp tăng dần, sau 1 lần lặp kết quả của dãy là thế nào?

Cho dãy 10, 5, 7, 3, 9, 2, 15, 1. Dùng thuật toán sắp xếp tăng dần bằng QuickSort, cho biết ở lần duyệt thứ nhất giá trị của x, L và R là gì?

Cho dãy sau: 23, 78, 45, 8, 32, 56. Dùng phương pháp sắp xếp chọn trực tiếp (Selection Sort) để sắp xếp tăng dần, sau 2 lần lặp thì kết quả của dãy là thế nào?

** 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 (Selection Sort) để sắp xếp giảm dần, sau lần lặp thứ tư kết quả của dãy là thế nào?

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

1356

Số lần hoán vị 2 phần tử khác nhau khi áp dụng thuật toán nổi bọt để sắp xếp mảng giảm dần là:

Cho dãy sau: 23, 78, 45, 8, 32, 56. Dùng phương pháp sắp xếp chọn trực tiếp (Selection Sort) để sắp xếp tăng dần, sau 5 lần lặp thì kết quả của dãy là thế nào?

Giả sử cần sắp xếp mảng M có N phần tử sau theo phưuơng pháp sắp xếp chèn trực tiếp:

11 16 12 75 51 54 5 73 36 52 98

Cần thực hiện bao nhiêu lần chèn các phần tử vào dãy con đã có thứ tự tăng dần đứng đầu dãy M để sắp xếp mảng tăng dần:

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 Selection tăng dần trên mảng các phần tử trên.

Đoạn mã sau đây sử dụng thuật toán Sắp xếp gì?

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

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

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?

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

}