BÀI TẬP THỰC HÀNH MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Khái niệm câu lệnh đặc trưng
Câu lệnh đặc trưng là câu lệnh được thực hiện thường xuyên ít nhất là cũng
như bất kỳ câu lệnh nào trong thuật toán.
Nếu giả thiết thời gian thực hiện mỗi câu lệnh là bị chặn bởi hằng số thì thời
gian tính của thuật toán sẽ cùng cỡ với số lần thực hiện câu lệnh đặc trưng. Do đó
để đánh giá thời gian tính có thể đếm số lần thực hiện câu lệnh đặc trưng.
I. Độ phức tạp của giải thuật:
Bài 1: Sắp xếp nổi bọt
1 // bubble sort
2
int bubbleSort(int a[], int n)
{
3
int i, j,
temp;
4
for (i = (n - 1); i > 0; i )
{
5
for (j = 1; j <= i; j++)
{
6
if (a[j-1] > a[j])
{
7 temp = a[j-1];
8 a[j-1] = a[j];
9 a[j] = temp;
10 }
11 }
12 }

13 return min
14 else
15 return NOT_FOUND
Ta chọn phép so sánh phần tử ở giữa danh sách với x làm câu lệnh đặc trưng.
Dễ thấy sau mỗi bước số phần tử của danh sách giảm đi một nữa nên số lần thực
hiện câu lệnh này sẽ là log(n) trong trường hợp tồi nhất.
Từ đó ta có thể kết luận độ phức tạp của thuật toán này là O(log(n))
Bài 3: Giải thuật Fibonacci
Giải thuật này trả về số thứ n trong dãy số Fibonacci
1
int Fibo(int
n)
{
2 if (n <= 1) return n;
3 else
4 return Fibo(n - 1) + Fibo(n - 2); (*)
5 }
Chọn phép cộng (*) làm câu lệnh đặc trưng. T(n) là số lần thực hiện câu lệnh này.
Dễ thấy:
T(n) = 0 với n <= 1
T(n) = T(n-1) + T(n-2) + 1 với n > 1
Nhận xét: T(n) là hàm tăng theo số mũ. T(n) = O( )
Suy ra: O( ) = O( ) + O( ) + O(1)
Bỏ qua O(1): = + ⇒ = a + 1 ⇒ a = 1.618
Vậy T(n) =
Định lý thợ rút gọn – Áp dụng với một số thuật toán đệ quy
Đối với các thuật toán đệ quy mà công thức đánh giá thuật toán có dạng:
với a >= 1, b > 1, c > 0 là các hằng số thì
• Nếu thì
• Nếu thì

- Danh sách được cài đặt bằng mảng(DS đặc)
- Danh sách được cài đặt bằng con trỏ(DS liên kết)
Bài 3. Viết chương trình con tìm kiếm và xóa 1 phần tử trong danh sách liên kết có thứ
tự.
Bài 4. Viết chương trình con đếm số lần xuất hiện của mỗi ký tự trong 1 chuỗi ký tự.
Bài 5. Viết chương trình con đảo ngược 1 danh sách trong cả 2 trường hợp là lưu bằng
mảng và lưu bằng con trỏ.
Bài 6. Viết chương trình con trộn 2 danh sách liên kết chứa các số nguyên theo thứ tự
tăng để được 1 danh sách cũng có thứ tự
Bài 7.Viết chương trình con tách 1 danh sách chứa các số nguyên các phần tử thành 2
danh sách : 1 danh sách gồm các số chẵn còn danh sách kia gồm các số lẻ.
Bài 8. Hãy cài đặt 1 ngăn xếp theo cách dùng con trỏ.
Bài 9. Dùng ngăn xếp để viết chương trình con đổi 1 số thập phân sang số nhị phân.
Bài 10. Cho 1 Queue Q . Hãy viết chương trình con thực hiện các công việc sau:
- Đếm số phần tử của Queue Q
- Xuất nội dung của Queue Q
IV Sắp xếp và tìm kiếm
Bài 1. Viết chương trình nhập vào một danh sách(đặc) có n phần tử, sắp xếp danh
sách đó theo thứ tự tăng dần(sử dụng selection sort)
Bài 2. Viết chương trình nhập vào một danh sách(đặc) có n phần tử, sắp xếp danh
sách đó theo thứ tự tăng dần(sử dụng Insertion sort)
Bài 3. Viết chương trình nhập vào một danh sách(đặc) có n phần tử, sắp xếp danh
sách đó theo thứ tự tăng dần(sử dụng Bubble sort)
Bài 4. Viết chương trình nhập vào một danh sách(đặc) có n phần tử, sắp xếp danh
sách đó theo thứ tự tăng dần(sử dụng Quick sort)
Bài 5. Viết chương trình nhập vào một danh sách(đặc) có n phần tử, nhập vào 1
phần tử có giá trị x. Tìm vị trí xuất hiện đầu tiên của x trong danh sách. Xuất kết
quả nếu tìm thấy, nếu không xuất Not Found.(sử dụng tìm nhị phân)
Bài 6. Viết chương trình nhập vào một danh sách(đặc) có n phần tử, nhập vào 1
phần tử có giá trị x. Tìm vị trí xuất hiện đầu tiên của x trong danh sách. Xuất kết