ĐỀ KT GHP GIẢI THUẬT (TIN20)

1/ Giải PT đệ quy bằng PP truy hồi, biết T(1)=1:
a) T(n)=T(n-1) + T(1) + n
b) T(n)=T(n-1)

2/ Giải PT đệ quy bằng PP tổng quát, biết T(1)=1:
a) T(n)=2T(n/2) + 1
b) T(n)= 2T(n/2) + logn
c) T(n)= 9T(n/3) + n

3/ Tính độ phức tạp đoạn code sau:
(1) int tim_kiem_nhi_phan(int x, int a[], int n) {
(2) int i = 0, j = n – 1;
(3)  while (i <= j) {
(4)    int m = (i + j)/2;
(5)    if (x == a[m])
(6)      return m;
(7)    if (x < a[m])
(8)      j = m – 1;
(9)    else
(10)      i = m + 1;
}
(11)  return -1; // khong tim thay
}

4/ Sắp xếp mảng giảm dần gồm 12 phần tử có khóa là các số nguyên: 5, 15, 12, 2, 10, 12,
9, 1, 9, 3, 2, 3 bằng cách sử dụng:
a) Sắp xếp chọn.
b) Sắp xếp xen.
c) Sắp xếp nổi bọt.