c Lc
1 Cu trúc d liu 1
1.1 Cu trúc d liu là gì? 2
1.2 Cu trúc d liu c s 3
1.2.1 Kiu d liu c s 3
1.2.2 Kiu có cu trúc 4
1.2.3 Kiu d liu tru tng 7
1.3 Cu trúc d liu hng vn  8
1.3.1 Cu trúc danh sách 8
1.3.2 Ngn xp 10
1.3.3 Hàng i 11
1.3.4 Cu trúc cây 12
1.3.5 Bm 17
2 Thut toán 23
2.1 C s v thut toán 24
2.1.1 Thut toán là gì? 24
2.1.2 Thut toán và cu trúc d liu 26
2.2 Các thut toán 30
2.2.1 Thut toán duyt 30
2.2.2 Thut toán sp xp 34
2.2.3 Thut toán  qui 49
2.2.4 X lí xâu kí t 51
2.2.5 X lí tp 55
2.2.6 V hình 63
2.2.7  th 67
2.2.8 Tính toán s 71
2.2.9 Thut toán i sánh 78
2.2.10 Thut toán xp x và xác sut 82
2.3 ánh giá thut toán 87
2.3.1 ánh giá theo  phc tp tính toán 87
2.3.2 ánh giá theo tính hp l 88

4.2.1 Th tc thit k có cu trúc 148
4.2.2 Các k thut phân hoch mô un n hình 151
4.2.3 Tiêu chí cho vic phân hoch mô un 160
4.2.4 Phân hoch chng trình 171
4.3 To ra c t mô un và c t kim th 173
4.3.1 To ra c t mô un 173
4.3.2 To ra c t kim th 175
4.4 To ra tài liu thit k chng trình 177
4.4.1 To ra tài liu thit k chng trình và ni dung 177
4.4.2 Nhng m cn lu ý khi to ra tài liu thit k chng trình 179
4.4.3 Hp kim m thit k 179
5 Thc hin chng trình 183
5.1 Lp trình 184
5.1.1 Mô thc lp trình 184
5.1.2 Phong cách lp trình 185
5.1.3 Dùng b x lí ngôn ng 186
5.1.4 Môi trng lp trình 187
5.2 Kim th 189
5.2.1 Tng quan v kim th 189
5.2.2 Kim thn v 190
5.2.3 Kim th tích hp 190
5.2.4 Kim th h thng 195
5.2.5 Các kim th khác 197
5.2.6 K hoch và nhim v kim th 197
6 Cp nht vn hành và phát trin h thng 204
6.1 Thit k chng trình 205
6.1.1 Thit k chng trình hng i tng 205
1 u trúc d liu
c ích ca chng
Vic chn cu trúc d liu thích hp nht và th tc mô

u trúc d
liu c s)
u trúc danh sách
Ngn xp
Hàng i
u trúc cây
m
Kiu d liu
 s
Kiu con tr
Kiu n
Kiu nguyên
Kiu thc
Kiu kí t
Kiu logic
Kiu lit kê
Kiu b phn
Kiu có
u trúc
Kiu mng
Kiu bn ghi
u trúc d
liu c s
Kiu d liu
tru tng
1.2 Cu trúc d liu c s 3
1.2 u trúc d liu c s
1.2.1 Kiu d liu c s
Kiu d liu c s là tp các d liu riêng l và thng c dùng  to ra chng trình. Nó
c phân loi thành các kiu n và con tr.

1.2.2 Kiu có cu trúc
u trúc d liu có cha mt cu trúc d liu c s hay bt kì kiu d liu c xác nh nào
nh phn t ca nó (d liu), c gi là kiu có cu trúc. Kiu có cu trúc c phân loi
thành kiu mng và kiu bn ghi.
(1) Kiu mng
ng c gi là bng. Kiu mng là d liu có cu trúc có cha d liu thuc cùng kiu và
kích c. Tng d liu cá nhân c gi là mt phn t mng, phn t bng hay phn t. Cách
ng c mô t hoc cách d liu c b trí có thay i tu theo ngôn ng lp trình c
dùng.
• Mng mt chiu
ng mt chiu có cu trúc d liu mà d liu c sp thành mng theo mt hàng.  xác
nh mt phn t trong mng này, trc ht a vào du ngoc tròn m ( hay du ngoc
vuông [ sau tên ca mng, ri a vào ch s và du ngoc tròn óng ) hay du ngoc vuông
óng ]. Ch s ch ra s th t tính tnh ca mng, ni phn t xác nh ó c nh v.
ng "A" có s phn tc kí hiu là "i" c biu din là A (i).
Hình 1-2-2 Mng mt chiu
Th 1 th 2 th 3
…
th I
…
Phn t Phn t Phn t
…
Phn t
…
A(1) A(2) A(3)
…
A(I)
…
‚ Mng hai chiu
t cu trúc d liu trong ó d liu c sp hàng theo c hai chiu ngang và ng c

A(1,1)
A(1,2)
A(2,1)
A(2,2)
A(3,1)
A(3,2)
A(1,1)
A(2,1)
A(3,1)
A(1,2)
A(2,2)
A(3,2)
 liu c D liu c
u tr lu tr
theo hàng theo ct
6 Chng 1 Cu trúc d liu
Hình 1-2-5 Xây dng mng ba chiu thành mng hai chiu
ng nhiu chiu nh các mng bn, nm hay nhiu chiu cng có thc nh ngha.
Tuy nhiên, có th có nhng gii hn nào ó v s chiu, tùy theo kiu ca ngôn ng lp trình
hay trình biên dch.
ng có thc phân loi thành mng tnh và mng ng theo phng pháp c dùng 
sit cht mt min.
- Mng tnh: Mng mà vùng c yêu cu do chng trình xác nh
- Mng ng: Mng mà vùng c yêu cu sc xác nh ra sau khi ch sc
dùng cho vic to mng c cung cp qua mt biu thc và biu
thc ó c tính trong khi thc hin chng trình
(2) Kiu bn ghi
c du d liu kiu có cu trúc là cao cp hn trong vic d tham chiu và thc hin thao tác
trên các phn t, nó cng có nhc m  ch nó ch có th gii quyt d liu thuc cùng mt
kiu. Do ó, d liu có cha các d liu vi kiu khác nhau phi ly dng ca d liu kiu bn

theo cùng cách nh mng mt chiu, tng d liu vn phi c t tên  nhn din vì tng
phn t cha nhiu d liu.
1.2.3 Kiu d liu tru tng
 liu cha cu trúc d liu nào ó và kiu ca các phép toán c gi là kiu d liu tru
ng.  truy nhp vào kiu d liu này, bn không cn bit v cu trúc bên trong ca nó. Tt
 các d liu u c che du ngoi tr d liu bn truy nhp  tham chiu, thêm vào hay
xoá i. u này c gi là che giu thông tin. Che giu thông tin hoc che giu d liu 
c  kiu d liu c gi là bao bc d liu.
Hình 1-2-7 Kiu d liu tru tng
(Các phép toán +
u trúc d liu)
Chng trình
t qu
 liu <Cu trúc d liu tru tng>
8 Chng 1 Cu trúc d liu
1.3 u trúc d liu hng vn

Các cu trúc d liu hng vn  khác nhau có thc trù tính bng vic dùng các kiu
ng, kiu con tr và các cu trúc d liu c s khác.
1.3.1 u trúc danh sách
Không ging kiu d liu c s gii quyt cho tng d liu riêng l, cu trúc danh sách cho
phép d liu c móc ni ln nhau và gii quyt c mt cc. D liu c b trí theo cu trúc
danh sách này c gi là mt danh sách.
(1) Cu trúc danh sách và các ô
ng vic dùng ch s cho tng phn t trong mng, có th truy nhp nhanh chóng vào bt kì
phn t nào. Tng t nh vy, vic thay i d liu có thc thc hin d dàng. Nu bn
chèn mt d liu vào âu ó trong mng, bn phi dch chuyn toàn b tng d liu sau ó lùi
i mt v trí. Nu bn xoá mt d liu trong mng, tng t, bn phi dch chuyn toàn b
ng d liu sau d liu b xoá ó nhích lên mt v trí.
Hình 1-3-1 Chèn thêm mt phn t mng

chèn d liu vào danh sách. Ô cha d liu (Inoue) vn còn trong vùng b nh nh rác sau khi
 liu ã b xoá, nhc v trong Hình 1-3-4.
Hình 1-3-4 Xoá d liu khi danh sách
c du cu trúc danh sách cho phép d liu c chèn thêm hay c xoá i ch bng cách
thay th các con tr, nó có nhc m là bn phi ln theo tng con tr mt tu nu bn
mun truy nhp vào d liu c bit.
(4) Kiu cu trúc danh sách
Các cu trúc danh sách tiêu biu bao gm:
- Danh sách mt chiu
- Danh sách hai chiu
- Danh sách vòng.
i vì nhng danh sách này c biu din di dng tuyn thng, nên nói chung chúng c
i là danh sách tuyn tính.
• Danh sách mt chiu
Danh sách mt chiu cng còn c gi là danh sách mt hng. Phn con tr ca ô cha
Phn d liu Phn con tr Phn d liu Phn con tr
InoueArai
Ueki
Phn d liu Phn con tr
Arai
Arai
Inoue
Ueki Endou
Endou Ueki
Ô c chèn
i d liu c chèn
Trc khi chèn
Sau khi chèn
Phn d liu Phn con tr
Inoue Endou Ueki Arai

Arai Inoue Wada NULL
u
Ô
Arai   Inoue   Wada

NULL
NULL
uôi
u
 Arai   Inoue   Wada 

u
 trí uôi
 trí u
1.3 Cu trúc d liu hng vn  11
Hình 1-3-8 Trò chi ném vòng
Trò chi ném vòng c chi bng cách ném các vòng mu theo th t, lc, vàng và lam
a vào d liu). Chúng c ly ra tng cái mt (a ra d liu) theo th to li vic ném
vào, tc là lam, vàng, lc và . Tc là vòng lam c ném vào cui cùng sc ly ra u
tiên.
Kiu cu trúc d liu này mà có thc so sánh vi trò chi ném vòng c gi là ngn xp.
 thng này còn có thut ng là h thng vào-sau-ra-trc (LIFO). Vic lu tr d liu trong
ngn xp c gi là "n vào (PUSH)" và vic ly d liu ra t ngn xp c gi là "bt ra
(POP)." Bin u khin vic n vào và bt ra c gi là con tr ngn xp.
n d liu vào ngn xp, t con tr ngn xp "sp" là +1 và lu gi d liu trong phn t
ng c vit là "sp."  làm bt ra d liu t ngn xp, hãy ly d liu ã c lu gi
trong mng c ch bi "sp" và t con tr ngn xp là sp-1.
Hình 1-3-9 Cu trúc ngn xp
1.3.3 Hàng i
Hàng i là cu trúc d liu da trên mng mt chiu. D liu c lu giu tiên c c

kiu làm vic bao gm phân loi tng bc.
Hình 1-3-12 S t chc
c du tng ô c sp theo th t tuyn tính trong cu trúc danh sách, d liu c sp
trong khi nó phân nhánh trong cu trúc cây.
u trúc cây bao gm các phn tc v di ây:
- Nút: Tng ng vi d liu
- Nhánh: Ni nút này vi nút khác
- Gc: Nút  cp cao nht, không có cha m
- Con: Nút r nhánh ra di mt nút khác
- Cha m: D liu gc trc khi nó chia nhánh
- Lá: Nút  cp thp nht không có con
Hình 1-3-13 v ra cu trúc cây
Hình 1-3-13 Cu trúc cây
 liu A D liu B D liu C D liu D
(1) (2) (3) (4) (5) (6)
p xp
Hàng i
Con tru Con tr cui
ng thng
Qun lý
hành chính
Qun lý
nhà máy
Qun lý
bán hàng
Qun lý b phn
hành chính
Qun lý b phn
 toán
Qun lý b phn

kéo dài sang bên trái và các nhánh ch ra trong khi phn con tr phi ch ra v trí ca nút kéo
dài sang bên phi và các nhánh ch ra.
Hình 1-3-14 Cu trúc cây nh phân
Phn con tr trái Phn d liu Phn con tr phi
Cây nh phân có cu trúc phân cp cha m - con, nhc v trong Hình 1-3-15.
Hình 1-3-15 Cu trúc cây nh phân c s
<Cách thc hin vic duyt d liu cây nh phân>
 duyt d liu c bit trong d liu cây nh phân, phi ln theo tng nút mt. Có ba
phng pháp thc hin duyt d liu cây nh phân. Vì khó gii thích bng li nên hãy kim li
Hình 1-3-16 và xem cách d liu c duyt bng vic dùng tng phng pháp.
Hình 1-3-16 Cách thc hin duyt d liu cây nh phân
- Th t gc trc (Pre-order): Vi gc là m bt u, nút bên trái ca mi nút c
duyt qua theo cách tun t.
- Th t gc gia (Mid-order): Vi lá ti áy bên trái làm m bt u, ri duyt qua nút
cha nó và tip ó duyt qua phn còn li ca nút ó theo cách tun t.
- Th t gc sau (Post order): Vi lá ti áy bên trái làm m bt u, phn bên phi mi
nút c duyt qua theo cách tun t ri mi n nút cha ca nó.
(2) Cây nh phân hoàn chnh
u cây nh phân c xây dng theo cách s các nhánh t gc ti tng lá dc theo mt
nhánh là bng hoc sai khác mt so vi s các nhánh t gc ti tng lá dc theo nhánh khác
(hoc nu chiu cao t gc ti tng lá là bng hay sai khác mt vi chiu cao t gc ti tng
lá thuc vào nhánh khác), thì cây ó c gi là cây nh phân hoàn chnh. Hình 1-3-17 v ra
cây nh phân hoàn chnh có mi nút.
Cha
Con
Con
14 Chng 1 Cu trúc d liu
Hình 1-3-17 Cây nh phân hoàn chnh
(3) Cây tìm kim nh phân
Cây tìm kim nh phân c dùng nh mt bin th ca cây nh phân. Trong trng hp ca

2 7
3 6 8 10
4 5 9
<Cây nh phân hoàn chnh> <Cu trúc d liu>
15
2
8 21
10 28
13
1) 15>10
2) 8<10
3) 10=10
1.3 Cu trúc d liu hng vn  15
a. c trng ca B-cây
-  tng vic s dng vùng b nh, s con tr mà mi nút có c t là m/2 hoc
nhiu hn và là m hoc ít hn. S con tr theo mt ng tuy vy c t là 2 hoc
nhiu hn.
- Mi lúc d liu b xoá hay c b sung thêm, vic ch ra và ghép li c thc hin
ng  cho s các phn t ca mt nút có th tr thành m/2 hay nhiu hn hoc m
hay ít hn. u này cho phép lá bao gi cng c duy trì trên cùng mc.
- Vic tìm kim bt u t gc.
- Vic thêm vào hay xoá i d liu bt u t lá.
Hình 1-3-19 ch ra B-cây b nm vi các phn t7, 6, 10, 2, 5, 12, 4, 9, 8, 11, 1, 3.
Hình 1-3-19 B-cây b nm
b. Xoá d liu
Hình 1-3-20 v ra trng hp d liu "4" b xoá khi B-cây c v trong Hình 1-3-19.
u mt mình "4" b xoá i, thì s các phn t b xoá ca mt nút tr thành mt và các
yêu cu ca B-cây không thc áp ng.
Hình 1-3-20 B-cây sai
Nút tó "4" b xoá i c gp vào mt nút k hoc  bên phi hoc  bên trái. Bi vì

6
53
41
9
87
3
56
41
ng ây không phi là ng
i quan h v kích c
trong hình ch nht chm
là khác nhau
6
4 5
1
3 2
6
5
4 2
1
3
5
3
1 2
3
1 2
4
4
3 2
1

+ 2 × 3
2
+ 3 × 3
1
+ 4 × 3
0
= 27 + 18 + 9 + 4
= 58 : a ch (ch s)
∗ Giá tr ca tng ch s theo h c s 3 là 3 hay nh hn. Tuy nhiên trong trng hp
này s kin này không cn c tính ti.
(2) ng ngha
Khi mt khoá c chuyn thành a ch bng vic dùng hàm bm, các khoá khác nhau có th
c chuyn vào cùng mt a ch. u này c gi là ng ngha (hay ng ) (xem Hình
1-3-24). Mt bn ghi có th dùng a chã chuyn i c gi là bn ghi nhà còn bn ghi
không th dùng c nó sc gi là bn ghi ng ngha.
18 Chng 1 Cu trúc d liu
Hình 1-3-24 Xut hin ng ngha
 gii quyt sng ngha, mt phng pháp c bit hay phng pháp dây chuyn c
dùng:
• Phng pháp tun t
ng vic dùng phng pháp tun t, bn ghi ng ngha c lu gi trong không gian t
do c nh v gn a ch mong mun. Có kh nng là sng ngha li có th xut hin
theo phn ng dây chuyn.
‚ Phng pháp dây chuyn
i vic dùng phng pháp dây chuyn, mt vùng b nh tách bit c thit lp và các
n ghi ng ngha c lu gi trong vùng này. Trong trng hp này, cn cung cp mt
con tr ch ra a ch ni các bn ghi ng ngha c ct gi.
n ghi có thc s
ng vi khóa 234
(Bn ghi nhà)

a. Cây nh phân b. Hàng i c. Ngn xp d. ng
Q4 Hai thao tác ngn xp c nh ngha nh sau:
PUSH n: D liu (nguyên "n") c y vào ngn xp.
POP: D liu c bt ra khi ngn xp.
u thao tác ngn xp c thc hin trên ngn xp rng theo th tc c nêu di ây, thì
có th thu c kt qu gì?
PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 →POP → POP → PUSH 3
a b C d e
1 3 3 3 6
7 4 4 7 4
3 5 6 1 3
a ch
100
101
102
103
a [1, 1]
a [1, 1]
20 Chng 1 Cu trúc d liu
Q5 Hình 2 là biu din mng cho cây nh phân c v trong Hình 1. Giá tr nào nên
c t vào ch "a"?
Ch s Giá tr
Con tr 1 Con tr 2
1 200 3 2
2 220 0 0
3 180 5
a
4 190 0 0
5 150 6 0
6 130 0 0

11
13
15
200
220
180
150
190
130
Bài tp 21
Q8 Cây nh phân c v di ây có thc biu din bng vic dùng biu thc s
c. Biu thc nào là úng?
a. A + B × C + (D + E) ÷ F b. A + B × C - (D + E) ÷ F
c. A + B × C - D + E ÷ F d. A× B + C + (D - E) ÷ F
e. A × B + C - D + E ÷ F
Q9 Xét ti vic lu gi d liu bng cách dùng B-cây, hãy chn câu chú thích úng t
nhng câu sau:
a. Chia ra và gp li các nút  cho phép chiu sâu phân cp tr thành nh nhau.
b. Nhn din v trí ni d liu c lu gi bng vic dùng mt hàm nào ó và giá tr khoá.
c. Ch có th truy nhp tun t ti d liu u và d liu tip ó.
d. Có danh mc và mt thành viên. Thành viên là tp c t chc tun t.
Q10 Có mt ng vi giá tr ca nút cha m nh hn giá tr ca nút con.  chèn thêm
 liu vào trong ng này, bn có th thêm mt phn t vào phn sau nht và lp
i vic trao i cha m vi con cái khi phn t này nh hn cha m. Khi phn t 7
c thêm vào v trí * ca ng tip, phn t nào s vào v trí A?
a. 7 b. 9 c. 11 d. 24 e. 25
Q11 Mt s có nm ch s (a
1
a
2

28
19
29 34
24
25
*
A
-
+
÷
F
+
XA
CB D
E
22 Chng 1 Cu trúc d liu
a. 1 b. 2 c. 7 d. 11
Q12 Nm d liu vi các giá tr khoá c phân bu và ngu nhiên trong phm vi t
1 ti 1,000,000 phi c ng kí vào bng bm kích c 10. Xác sut xp x cho
ng  xy ra là gì? ây, phn d thu c khi mt giá tr khoá c chia theo
kích c ca bng bm c dùng nh giá tr bm.
a. 0.2 b. 0.5 c. 0.7 d. 0.9
2 Thut toán
c ích ca chng
Các c s ca vic lp trình là thit k thut toán.
Trong thit k cu trúc logic ca chng trình, u
quan trng là dùng thut toán thích hp nht. Tng t
nh vy, trong vic chn chng trình t th vin,
thut toán nào c dùng là mt trong nhng tiêu
chun quan trng nht  chn chng trình thích hp