Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 0 TRƯỜNG ĐẠI HỌC SÀI GÒN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN KHOA HỌC MÁY TÍNH
o0o BÀI TẬP
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
(lưu hành nội bộ)
Năm 2010

Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 1

Chương 1
TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

A.Tóm tắt lý thuyết
1.Cấu trúc dữ liệu và giải thuật
Xuyên suốt trong giáo trình này, chúng tôi muốn đề cập đến hai mặt quan
trọng của một vấn đề bài toán là cách thức tổ chức dữ liệu của bài toán và các phép
xử lý trên các dữ liệu đó.
1.1.Cấu trúc dữ liệu
Cấu trúc dữ liệu của bài toán là cách thức tổ chức dữ liệu sao cho phản ánh
chính xác dữ liệu của bài toán và có thể dùng máy tính để xử lý các dữ liệu đó một
cách hiệu quả.
Một cấu trúc dữ liệu được đánh giá là tốt nếu nó thỏa mãn được các yêu cầu
như: Phản ánh đúng thực tế bài toán, phù hợp với các thao tác xử lý trên đó, tiết
kiệm được tài nguyên hệ thống,…
1.2.Giải thuật (trong giáo trình này chúng tôi đồng nhất khái niệm thuật toán
và giải thuật)
Giải thuật là một bảng liệt kê các chỉ dẫn (hay các qui tắc) cần thực hiện theo
từng bước xác định nhằm giải quyết một vấn đề bài toán.
Các đặc trưng của giải thuật
Tính xác định: Ở mỗi bước các chỉ dẫn phải rõ ràng.
Tính kết thúc: Giải thuật phải dừng sau một số hữu hạn bước.
Tính đúng đắn: Giải thuật phải cho ra kết quả đúng theo yêu cầu của
bài toán.
Tính tổng quát: Giải thuật phải áp dụng được cho các bài toán cùng
loại.
1.3.Sự liên hệ giữa giải thuật và cấu trúc dữ liệu
Giải thuật và cấu trúc dữ liệu có mối liên hệ chặt chẽ với nhau. Giải thuật

(C, n, k là các hằng số nào đó), thì khi n khá lớn, thời gian thực hiện giải thuật t
2
ít
hơn so với giải thuật T
1
, như vậy nếu nói thời gian thực hiện giải thuật T(n) tỉ lệ với
với n
2
hay tỉ lệ với n cũng cho ta ý niệm về tốc độ thực hiện giải thuật đó khi n khá
lớn (với n nhỏ thì việc xét T(n) không có ý nghĩa). Cách đánh giá thời gian thực hiện
giải thuật độc lập với máy tính và các yếu tố liên quan tới máy như vậy sẽ dẫn tới
khái niệm về “cấp độ lớn của thời gian thực hiện giải thuật” hay còn gọi là “độ phức
tạp tính toán của giải thuật”.
2.2.Thời gian chạy của các lệnh
Lệnh gán
Lệnh gán có dạng
X = <biểu thức>
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 4 Thời gian chạy của lệnh gán là thời gian thực hiện biểu thức. Trường hợp hay
gặp nhất là biểu thức chỉ chứa các phép toán sơ cấp, và thời gian thực hiện nó là
O(1). Nếu biểu thức chứa các lời gọi hàm thì ta phải tính đến thời gian thực hiện
hàm, và do đó trong trường hợp này thời gian thực hiện biểu thức có thể không còn
phải O(1).
Lệnh lựa chọn
if (<điều kiện>)
<lệnh 1>;
else
<lệnh 2>;

Để đánh giá thời gian thực hiện một lệnh lặp, trước hết ta cần đánh giá số tối
đa các lần lặp, giả sử đó là L(n). Sau đó đánh giá thời gian chạy của mỗi lần lặp, chú
ý rằng thời gian thực hiện thân của một lệnh lặp ở các lần lặp khác nhau có thể khác
nhau, giả sử thời gian thực hiện thân lệnh lặp ở lần thứ i (i=1,2, , L(n)) là T
i
(n). Mỗi
lần lặp, chúng ta cần kiểm tra điều kiện lặp, giả sử thời gian kiểm tra là T
0
(n). Như
vậy thời gian chạy của lệnh lặp là:
() ()()
∑
=
+
)(
1
0
nL
i
i
nTnT
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 5 Công đoạn khó nhất trong đánh giá thời gian chạy của một lệnh lặp là đánh
giá số lần lặp. Trong nhiều lệnh lặp, đặc biệt là trong các lệnh lặp for, ta có thể thấy
ngay số lần lặp tối đa là bao nhiêu. Nhưng cũng không ít các lệnh lặp, từ điều kiện
lặp để suy ra số tối đa các lần lặp, cần phải tiến hành các suy diễn không đơn giản.
Trường hợp hay gặp là: kiểm tra điều kiện lặp (thông thường là đánh giá một
biểu thức) chỉ cần thời gian O(1), thời gian thực hiện các lần lặp là như nhau và giả

(n) và T
2
(n) là thời gian thực hiện của hai đoạn chương trình P
1
và
P
2
mà T
1
(n) = O(f(n)) và T
2
(n)=O(g(n)), thì thời gian thực hiện P
1
rồi P
2
tiếp theo sẽ
là T
1
(n)+ T
2
(n) = O( max(f(n), g(n))
Chẳng hạn đoạn lệnh
for (int i=1;i<=n;i++)
x=x+1;
có thời gian thực hiện là O(n.1) = O(n)
Quy tắc nhân
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 6 Nếu tương ứng với P

thước của dữ liệu vào mà còn phụ thuộc vào chính tính trạng của dữ liệu đó nữa.
Chẳng hạn việc sắp xếp một dãy số theo thứ tự tăng dần nếu gặp dãy số đưa vào đã
có đúng thứ tự thì sẽ khác với trường hợp dãy số đưa vào chưa có thứ tự hoặc có thứ
tự ngược lại, lúc đó khi phân tích thời gian thực hiện giải thuật ta sẽ phải xét tới: đối
với mọi dữ liệu vào có kích thước n thì T(n) trong trường hợp thuật lợi nhất là thế
nào? rồi T(n) trong trường hợp xấu nhất và T(n) trung bình ? Việc xác định T(n)
trung bình thường khó vì sẽ phải dùng tới những công cụ toán phức tạp. Trong các
trường hợp mà T(n) trung bình khó xác định người ta thường đánh giá giải thuật qua
giá trị xấu nhất của T(n).
2.4.Sự phân lớp các giải thuật
Thông thường các hàm thể hiện độ phức tạp tính toán của giải thuật có dạng
hằng số, log
2
n, n, nlogn, n
2
, n
3
, 2
n
, n!, n
n
,…
Hằng số:Hầu hết các chỉ thị của các chương trình đều được thực hiện một lần
hay một số số lần nhất định không phụ thuộc vào n
Các hàm như 2
n
, n!, n
n
được gọi là hàm mũ. Một giải thuật mà thời gian thực
hiện của nó có cấp là các hàm loại mũ thì tốc độ rất chậm. Các hàm log

bình phương
lập phương
Mũ
B.Các dạng bài tập
Dạng 1: Bài toán với cấu trúc dữ liệu là mảng một chiều
Ví dụ 1.1: Cộng hai số nguyên lớn
Cho hai số nguyên lớn a và b; a có m chữ số và b có n chữ số. Hãy viết
chương trình tính tổng a+b.
Giải thuật
Số nguyên lớn ở đây là số có thể có đến vài nghìn chữ số. Để lưu trữ các số
nguyên lớn này ta có thể dùng chuỗi (mỗi ký tự của chuỗi là một chữ số) hoặc dùng
mảng một chiều (mỗi phần tử của mảng một chiều là một chữ số). Tuy nhiên trong
hai phương án này thì phương án dùng mảng một chiều để lưu trữ sẽ có giải thuật tốt
hơn.
Giải thuật này có thể trình bày ngắn gọn như sau:
Bước 1:Nhập hai số nguyên lớn a,b. Để có thể thực hiện được phép a+b một
cách tự nhiên thì khi nhập a,b thì a và b phải được giống hàng bên phải.
Ví dụ: Giả sử a có m=5 chữ số, b có n=4 chữ số như sau:
a = 97895
b = 6478
Thì việc lưu trữ hai số này là như sau:
a[1] = 9, a[2]=7, a[3]=8, a[4]=9, a[5]=5
b[2] = 6, b[3]=4, b[4]=7, b[5]=8
Việc giống hàng bên phải cho a và b có thể tiến hành bằng cách đặt max là số
lớn nhất trong hai số m và n.
for i=max-m+1 to max
cin>>a[i];
for i=max-n+1 to max
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 8


{
int tuso;
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 9 int mauso;
};
-Phân số tối giản là phân số mà ước số chung lớn nhất của tử số và mẫu số
bằng 1. Để tìm bảng phân số tối giản ta chỉ cần tối giản từng phân số.
Lưu ý là để so sánh phân số 1 có lớn phân số 2 hay không ta dùng điều kiện:
ps1.tu*ps2.mau>ps2.tu*ps1.mau
Chương trình 1-2
#include <conio.h>
#include <math.h>
#include <iostream.h>
#include <stdio.h>
#define maxm 50
#define maxn 50
struct phanso
{
int tu;
int mau;
};
void nhapmangps(phanso ps[maxm][maxn], int &m, int &n);
void xuatmangps(phanso ps[maxm][maxn], int m, int n);
int sosanhps(phanso ps1, phanso ps2);
void bangphansotoigian(phanso ps[maxm][maxn], int m, int n);
void timpslonnhat(phanso ps[maxm][maxn], int m, int n);
void main()
{

cout<<endl;
}
}
int sosanhps(phanso ps1, phanso ps2)
{
return ps1.tu*ps2.mau>ps2.tu*ps1.mau>0;
}

int uscln(int a, int b)
{
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 11 int r=a%b;
while (r!=0)
{
a=b;
b=r;
r=a%b;
}
return b;
}
void bangphansotoigian(phanso ps[maxm][maxn], int m, int n)
{
for (int i=0; i<m;i++)
for (int j=0; j<n;j++)
{
int uc=uscln(ps[i][j].tu,ps[i][j].mau);
ps[i][j].tu=ps[i][j].tu/uc;
ps[i][j].mau=ps[i][j].mau/uc;

d.In danh sách các nhân viên tăng dần theo phòng ban, nếu phòng ban trùng
nhau thì giảm dần theo mã nhân viên.
Chương trình 1-3
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
struct nhanvien
{
char manv[8];
char hoten[20];
char phongban[16];
float luongcb;
float thuong;
float thuclanh;
};
int n;
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 13 struct nhanvien nv[100],temp;
void nhap(nhanvien nv[], int &n);
void xuat(nhanvien nv[], int n);
void tongthuclanh(nhanvien nv[], int n);
void luongcbthapnhat(nhanvien nv[], int n);
void mucthuong(nhanvien nv[], int n);
void sapxep(nhanvien nv[], int n);

void main()

void xuat(nhanvien nv[], int n)
{
for(int i=0;i<n;i++)
cout<<nv[i].manv<<nv[i].hoten<<nv[i].phongban<<nv[i].luongcb
<<nv[i].thuong<<nv[i].thuclanh;
}

void tongthuclanh(nhanvien nv[], int n)
{
long tong=0;
for(int i=0;i<n;i++)
tong=tong +nv[i].thuclanh;
cout<<"\nTong thuc lanh la "<<tong;
}
void luongcbthapnhat(nhanvien nv[], int n)
{
long min=nv[0].luongcb;
for(int i=1;i<n;i++)
if (nv[i].luongcb<min)
min=nv[i].luongcb;
cout<<"\nLuong co ban thap nhat la:"<<min;
}
void mucthuong(nhanvien nv[], int n)
{
int dem=0;
for(int i=0;i<n;i++)
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 15 if (nv[i].thuong>=1200000)

Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 16 0 0 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 1
Khi đó dãy cần tìm là dãy ứng với đường đi xuống dài nhất trong ma trận kề:
Là phần tử ở các vị trí 2, 4, 5 của dãy a hoặc là các vị trí 3, 4, 7 của dãy b.
Dạng 5: Tối ưu hóa cấu trúc
Ví dụ 1.5.Dãy con có tổng lớn nhất
Cho dãy n số nguyên {a} Dãy con liên tiếp là dãy mà thành phần của nó là các thành
phần liên tiếp nhau trong {a}, ta gọi tổng của dãy con là tổng tất cả các thành phần
của nó. Tìm tổng lớn nhất trong tất cả các tổng của các dãy con của {a}
Chẳng hạn n = 7 số sau:
4 –5 6 –4 2 3 -7
Thì kết quả tổng dãy con cần tìm là 7.
Giải thuật 1:
Giải thuật đơn giản nhất có thể viết ngay là: xét tất cả các cặp số nguyên L
và U thỏa mãn 1 ≤ L ≤ U ≤ n; đối với mỗi cặp như vậy ta tính tổng của dãy con
a[L U] và so sánh tổng này với giá trị lớn nhất hiện có:
for (L=1;L<=n;L++)
for (U=L;U<=n;U++)
{
sum=0;
for (int I=L;I<=U;I++)
sum=sum+a[I];
maxsofar=max(maxsofar,sum);
}
chương trình này tuy ngắn và dễ hiểu, tuy nhiên giải thuật này có độ phức tạp là

maxendinghere=0;
for (i=1; i<=n;i++)
{
maxendinghere=max(maxendinghere+a[i],0);
maxsofar=max(maxsofar,maxendinghere);
}
Minh họa cho Giải thuật 3:
1 2 3 4 5 6 7
a[i] 4 -5 6 -4 2 3 -7
maxendinghere
4 0 6 2 4 7 0
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 18 maxsofar
4 4 6 6 6 7 7
Giải thuật 3 này có độ phức tạp là O(n).
#include <iostream.h>
#include <conio.h>

void algorithm1(int a[], int n);
void algorithm2(int a[], int n);
void algorithm3(int a[], int n);
int max(int a,int b);
void input(int a[],int &n);

void main()
{
int a[100],n;
input(a,n);

{
int maxsofar=0;
for (int L=1;L<=n;L++)
{
int sum=0;
for (int U=L;U<=n;U++)
{
sum=sum+a[U];
maxsofar=max(maxsofar,sum);
}
}
cout<<maxsofar;
}

void algorithm3(int a[], int n)
{ int maxsofar=0;
int maxendinghere=0;
for (int i=1; i<=n;i++)
{
maxendinghere=max(maxendinghere+a[i],0);
Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 20 maxsofar=max(maxsofar,maxendinghere);
}
cout<<maxsofar;
}

int max(int a,int b)
{

Viết chương trình thực hiện các phép cộng, trừ, nhân hai số nguyên lớn.
BT1-4.Xây dựng cấu trúc dữ liệu để lưu trữ đa thức có bậc tự nhiên n (0 ≤ n ≤ 100)
trên trường số nguyên (a
i
, x ∈ Z).
∑
=
=
n
i
i
in
xaxf
0
)(

Với cấu trúc dữ liệu được xây dựng, hãy viết chương trình thực hiện các công việc
sau:
a.Tính giá trị của đa thức tại giá trị x
0
nào đó.
b.Tính tổng, hiệu, tích, thương hai đa thức p và q.
BT1-5.Cho mảng một chiều gồm n tọa độ điểm (giả sử hoành độ và tung độ của các
điểm là các số nguyên).
a.Tìm một điểm trong mảng xa gốc tọa độ nhất.
b.Tìm tọa độ hai điểm gần nhau nhất.
c.Xác định tọa độ của hình chữ nhật nhỏ nhất (tọa độ góc trên bên trái và tọa
độ góc dưới bên phải của hình chữ nhật) bao hết cả n điểm trên.
Ví dụ n = 5 và tọa độ 5 điểm là: (0,0); (0,3); (3,3); (4,1); (4,4).
Thì kết quả câu a là điểm (4,4), kết quả câu b là (3,3) và (4,4), kết quả câu c

BT1-9.Khai báo kiểu cấu trúc dữ liệu mảng mà mỗi phần tử chứa thông tin về một
quyển sách bao gồm các trường: Mã số sách, tên sách, tác giả, năm xuất bản.
a.Đếm số sách xuất bản năm X.
b.Sắp xếp danh sách theo mã số sách tăng.
BT1-10.Trong mặt phẳng OXY cho đa giác lồi A
1
,A
2
,…,A
n

Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 23 a.Tính chu vi của đa giác.
b.Tính diện tích của đa giác.
BT1-11.Xét tập tất cả phân số tối giản (số hữu tỉ) giữa 0 và 1 với mẫu số nhỏ hơn
hoặc bằng N.
Ví dụ, với N = 5, ta có tập sau:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Cho số nguyên N (1 <= N <= 500), viết chương trình in ra số lượng các phân
số và in ra một phần các phân số đó để chứng tỏ bạn làm đúng.
BT1-12.Tìm độ phức tạp của các thuật toán sau:
a.Tìm giá trị lớn nhất của một dãy số.
b.Tìm ước số chung lớn nhất của 2 số nguyên dương a,b.
c.Kiểm tra xem n có phải là số nguyên tố hay không ?

Bài tập cấu trúc dữ liệu và giải thuật–SGU2010 Trang 24
(sentinel) ở cuối mảng (a[n]=x) để bảo đảm rằng trong dãy a[i] lúc này luôn có phần
tử bằng x và vòng lặp while luôn kết thúc. Do đó không cần kiểm tra điều kiện (i<n)
nữa.
int LinearSearch ( int a[], int n, int x )
{
int i = 0; // mảng gồm n phần tử từ a[0] a[n-1]
a[n] = x; // thêm phần tử thứ n+1