Giáo trình Cấu trúc dững liệu và giải thuật 1

 TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT 
 KHOA TOAÙN - TIN HOÏC 
 Y 	 Z 
 TRÖÔNG CHÍ TÍN 
CAÁU TRUÙC DÖÕ LIEÄU VAØ GIAÛI THUAÄT 1 
 (Giaùo Trình) 
 -- Löu haønh noäi boä -- 
 Y Ñaø Laït 2008 Z 
LỜI MỞ ĐẦU 
Giáo trình này nhằm cung cấp cho sinh viên các kiến thức căn bản về các 
cấu trúc dữ liệu cơ sở có cấu trúc tuyến tính tĩnh, động (danh sách liên kết), cấu 
trúc cây và các giải thuật cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ 
nhớ trong, cũng như so sánh độ phức tạp của các giải thuật này. Để có thể nắm bắt 
các kiến thức trình bày học phần này, sinh viên cần nắm được các kiến thức về tin 
học đại cương, nhập môn lập trình. Ngôn ngữ lập trình được chọn để minh họa các 
kiến thức trên là C++. Các kiến thức này sẽ tạo điều kiện cho học viên tiếp tục dễ 
dàng nắm bắt các kiến thức các học phần tin học về sau như: cấu trúc dữ liệu và 
giải thuật nâng cao, phân tích và thiết kế giải thuật, đồ hoạ, hệ điều hành, trí tuệ 
nhân tạo, ... 
 Nội dung giáo trình gồm 4 chương: 
 - Chương 1: Giới thiệu các khái niệm ban đầu về mối liên hệ mật thiết giữa 
cấu trúc dữ liệu và giải thuật, kiểu dữ liệu, thiết kế và phân tích giải thuật, độ 
phức tạp giải thuật, ... 
 - Chương 2: Giới thiệu các phương pháp cơ bản về tìm kiếm và sắp xếp trong 
trên kiểu dữ liệu tuyến tính mảng. Thông qua đó, trình bày một số ý tưởng và kỹ 
thuật cơ bản nhằm cải tiến các giải thuật. 
 - Chương 3: Trình bày kiểu dữ liệu con trỏ. Trên cơ sở đó, trình bày các kiểu 
dữ liệu động tuyến tính và có nhiều ứng dụng trong tin học là các kiểu danh sách 
liên kết khác nhau, ngăn xếp, hàng đợi, cũng như một số ứng dụng của chúng. 
 - Chương 4: Giới thiệu một loại cấu trúc dữ liệu động khác là cây và các thao 
tác cơ bản trên cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng AVL. 
 Nhằm mục đích dành thời gian nhiều hơn cho sinh viên để làm các bài tập 
lớn, nên trong một số phần tác giả đã trình bày khá chi tiết các dạng cài đặt biến 
thể khác nhau cho các giải thuật. Các phần thứ yếu hoặc khá phức tạp sẽ được in 
cỡ chữ nhỏ dành cho sinh viên đọc thêm. 
 Chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong 
muốn nhận được và rất biết ơn các ý kiến quí báu đóng góp của đồng nghiệp cũng 
như bạn đọc để giáo trình này có thể hoàn thiện hơn nữa về mặt nội dung cũng 
như hình thức trong lần tái bản sau. 
 Đà lạt, 04/2008 
 Tác giả 
MỤC LỤC 
Chương I. GIỚI THIỆU CẤU TRÚC DỮ LIỆU, 
PHÂN TÍCH GIẢI THUẬT 
 Trang 
I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 
I.1.1. Biểu diễn dữ liệu I.1 
I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu 
 I.1 
I.1.3. Các bước chính để giải một bài toán trên máy tính I.2 
I.2. Thiết kế và phân tích giải thuật I.4 
I.2.1. Thiết kế giải thuật theo phương pháp Top-Down I.4 
I.2.2. Các chiến lược khác để thiết kế giải thuật I.5 
I.2.3. Phân tích giải thuật và độ phức tạp của giải thuật I.5 
I.2.4. Qui ước về ngôn ngữ mã giả I.9 
Chương II. TÌM KIẾM VÀ SẮP XẾP TRONG 
II.1. Giới thiệu về sắp xếp và tìm kiếm II.1 
 II.1.1. Sắp xếp II.1 
a. Định nghĩa sắp xếp II.1 
 b. Phân loại phương pháp sắp xếp II.1 
 c. Vài qui uớc về kiểu dữ liệu khi xét các giải thuật sắp xếp II.1 
 II.1.2. Tìm kiếm II.3 
 a. Định nghĩa phép tìm kiếm II.3 
 b. Phân loại các phương pháp tìm kiếm II.3 
II.2. Phương pháp tìm kiếm trong II.3 
II.2.1. Phương pháp tìm kiếm tuyến tính II.3 
a. Dãy chưa được sắp II.3 
b. Dãy đã được sắp II.5 
II.2.2. Phương pháp tìm kiếm nhị phân II.6 
II.3. Phương pháp sắp xếp trong 
 II.7 
II.3.1. Phương pháp sắp xếp chọn đơn giản II.8 
 II.3.2. Phương pháp sắp xếp chèn đơn giản II.9 
 II.3.3. Phương pháp sắp xếp đổi chỗ đơn giản II.10 
II.3.4. Phương pháp sắp xếp đổi chỗ cải tiến (Shake Sort) II.12 
II.3.5. Phương pháp sắp xếp chèn cải tiến (Shell Sort) II.14 
 II.3.6. Phương pháp sắp xếp phân hoạch (Quick Sort) II.16 
 II.3.7. Phương pháp sắp xếp trên cây có thứ tự (HeapSort) II.19 
 II.3.8. Phương pháp sắp xếp trộn (Merge Sort) II.25 
 II.3.9. Phương pháp sắp xếp dựa trên cơ số (Radix Sort) II.28 
 II.3.10. So sánh các phương pháp sắp xếp trong II.31 
 Trang 
Chương III. CẤU TRÚC DANH SÁCH LIÊN KẾT 
III.1. Giới thiệu đối tượng dữ liệu con trỏ III.1 
III.1.1. So sánh cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động III.1 
III.1.2. Kiểu dữ liệu con trỏ III.1 
a. Định nghĩa III.1 
b. Khai báo III.2 
c. Các thao tác trên kiểu dữ liệu con trỏ III.3 
III.1.3. Biến động III.4 
a. Đặc trưng của biến động III.4 
b. Truy xuất biến động III.4 
c. Hai thao tác cơ bản trên biến động III.5 
III.2. Danh sách liên kết (DSLK) III.7 
 III.2.1. Định nghĩa danh sách III.7 
III.2.2. Các cách tổ chức danh sách III.7 
III.3. DSLK đơn III.8 
III.3.1. Tổ chức DSLK đơn, các thao tác cơ bản, tìm kiếm và sắp xếp 
trên kiểu DSLK đơn III.8 
a. Tổ chức DSLK đơn (không có nút câm) III.8 
b. Các thao tác cơ bản trên kiểu DSLK đơn III.9 
c. Sắp xếp trên kiểu DSLK đơn: sắp xếp chèn, QuickSort, 
MergeSort, RadixSort III.17 
 III.3.2. Vài ứng dụng của DSLK đơn III.24 
III.3.2.1. Ngăn xếp: định nghĩa, cài đặt, các phép toán cơ bản 
 và ứng dụng của ngăn xếp III.24 
III.3.2.2. Hàng đợi: định nghĩa, cài đặt, các phép toán cơ bản 
 và ứng dụng của hàng đợi III.31 
III.4. Một số kiểu DSLK khác III.34 
 III.4.1. DSLK đơn có nút câm III.34 
III.4.2. DSLK vòng III.37 
III.4.3. DSLK đối xứng III.38 
a. Cấu trúc dữ liệu biểu diễn DSLK đối xứng III.39 
b. Các thao tác cơ bản trên kiểu DSLK đối xứng III.39 
c. Ứng dụng của DSLK đối xứng: hàng đợi hai đầu III.47 
 III.4.4. DS đa liên kết III.48 
 III.4.5. Một số ứng dụng khác của DSLK III.51 
 a. DS có thứ tự và DS tổ chức lại III.51 
 b. Biểu diễn tập hợp bằng DSLK III.53 
 c. Biểu diễn đa thức rời rạc bằng DSLK III.54 
 d. Biểu diễn ma trận thưa nhờ DSLK III.56 
 e. Sắp xếp tôpô III.57 
 Trang 
Chương IV. CẤU TRÚC CÂY 
IV.1. Định nghĩa và các khái niệm cơ bản IV.1 
 IV.1.1. Định nghĩa cây IV.1 
 IV.1.2. Các khái niệm khác IV.1 
IV.2. Cây nhị phân IV.3 
IV.2.1. Định nghĩa IV.3 
IV.2.2. Vài tính chất của cây nhị phân IV.3 
IV.2.3. Biểu diễn cây nhị phân IV.3 
IV.2.4. Duyệt cây nhị phân IV.4 
IV.2.5. Một cách biểu diễn khác của cây nhị phân IV.7 
IV.2.6. Biểu diễn cây n - phân bằng cây nhị phân IV.8 
IV.2.7. Xây dựng cây nhị phân cân bằng hoàn toàn IV.8 
IV.3. Cây nhị phân tìm kiếm IV.9 
IV.3.1. Định nghĩa cây nhị phân tìm kiếm IV.9 
 IV.3.2. Tìm kiếm một phần tử trên cây BST IV.10 
 IV.3.3. Chèn một phần tử vào cây BST, xây dựng cây BST IV.11 
IV.3.4. Phương pháp sắp xếp bằng cây BST IV.13 
IV.3.5. Xóa một phần tử khỏi cây BST, hủy cây nhị phân IV.13 
IV.4. Cây nhị phân tìm kiếm cân bằng IV.16 
IV.4.1. Định nghĩa IV.17 
IV.4.2. Chiều cao của cây cân bằng IV.17 
IV.4.3. Chỉ số cân bằng và việc cân bằng lại cây AVL IV.18 
 IV.4.4. Chèn một phần tử vào cây AVL IV.24 
IV.4.5. Xóa một phần tử khỏi cây AVL IV.25 
Bài tập. BT.1 
 Bài tập chương I BT.1 
 Bài tập chương II BT.4 
 Bài tập chương III BT.6 
 Bài tập chương IV BT.11 
Tài liệu tham khảo 
 Chương I 
GIỚI THIỆU CẤU TRÚC DỮ LIỆU 
VÀ PHÂN TÍCH GIẢI THUẬT 
I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu 
I.1.1. Biểu diễn dữ liệu 
Một mục tiêu quan trọng của tin học là nhằm giải quyết tự động những bài 
toán trong thế giới thực bằng máy tính điện tử. Các thông tin về bài toán cần giải 
quyết trên máy tính luôn được mã hoá dưới dạng nhị phân. Các thông tin này gồm 
dữ liệu và các thao tác trên các dữ liệu đó. 
Việc biểu diễn dữ liệu ở dạng nhị phân rất bất tiện cho con người trong khi 
xử lý các bài toán, đặc biệt là các bài toán lớn và phức tạp. Chính vì lý do đó, các 
ngôn ngữ lập trình bậc cao đã cung cấp sẵn các cách biểu diễn dữ liệu trừu tượng 
đơn giản và có cấu trúc, nhằm giúp người lập trình không phải mất nhiều thời 
gian và công sức thực hiện thường xuyên lặp lại các thao tác sơ cấp nặng nề trên 
các kiểu dữ liệu nhị phân ở mức thấp. Tính trừu tượng của dữ liệu thể hiện ở chỗ 
nó không quá chú trọng đến những đặc điểm và ý nghĩa riêng của từng đối tượng 
cụ thể mà chỉ rút ra và phản ánh những tính chất chung nhất mà các đối tượng 
thuộc cùng một lớp có được. 
I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu 
Dựa vào bản chất chung của từng nhóm dữ liệu, các đối tượng dữ liệu được 
phân thành các lớp. Mỗi lớp dữ liệu được thể hiện qua một kiểu dữ liệu. Một kiểu 
dữ liệu T là một tập hợp nào đó, mỗi phần tử của tập được gọi là một thể hiện của 
kiểu. 
Ta đã biết giải thuật (hay giải thuật) là một dãy câu lệnh rõ ràng, xác định 
một trình tự các thao tác trên một số đối tượng nào đó (input) sao cho sau một số 
hữu hạn bước thực hiện (chú ý đến tính khả thi về thời gian), ta đạt được kết quả 
(output) mong muốn. Giải thuật phản ánh các phép xử lý, còn đối tượng để xử lý 
bởi giải thuật chính là dữ liệu: dữ liệu (input) đưa vào, dữ liệu trung gian và kết 
qủa (output) cuối cùng. 
Đối với bất kỳ một lớp dữ liệu nào, nếu để ý kỹ, ta thấy trên đó luôn tồn tại 
những thao tác cơ bản mật thiết gắn liền với các đối tượng dữ liệu cùng kiểu đó. 
Khi cách biểu diễn dữ liệu thay đổi thì các thao tác gắn liền với chúng cũng thay 
đổi theo. Vì nếu không thì trong nhiều trường hợp việc xử lý sẽ gượng ép, thiếu tự 
 Giôùi thieäu caáu truùc döõ lieäu vaø phaân tích giaûi thuaät I.2 
nhiên, khó hiểu, phức tạp không cần thiết và chương trình kém hiệu quả, lãng phí 
tài nguyên trên máy tính (CPU và bộ nhớ). 
Chẳng hạn, đối với một chuỗi ký tự, ta có ít nhất hai cách biểu diễn chúng 
như được thể hiện trong ngôn ngữ lập trình Pascal và C. Với mỗi cách biểu diễn, 
ta sẽ có những cách xây dựng các thao tác tương ứng trên chúng khác nhau. 
Một ví dụ khác, sẽ thấy rõ hơn trong các chương tiếp theo, đối với một dãy 
các phần tử dữ liệu cùng loại, ta có thể lưu trữ chúng ít nhất bằng hai cách: lưu 
bằng mảng (tĩnh, động) hay lưu trữ bằng danh sách liên kết động. Khi đó, các 
thao tác cơ bản trên chúng như chèn, xóa, sắp xếp sẽ thực hiện theo những cách 
thức khác nhau và do đó có hiệu quả khác nhau. 
Do đó, khi nói đến một kiểu dữ liệu T, ta thường chú ý đến hai đặc trưng 
quan trọng và liên hệ mật thiết với nhau: 
- tập V các giá trị thuộc kiểu, đó là tập các giá trị hợp lệ mà đối tượng kiểu 
T có thể nhận và lưu trữ; 
- tập O các phép toán (hay thao tác xử lý) xác định có thể thực hiện trên các 
đối tượng dữ liệu kiểu đó. 
Người ta thường viết: T = . 
Trong một ngôn ngữ lập trình cấp cao cụ thể, người ta thường xây dựng sẵn 
một số kiểu dữ liệu đơn giản hay sơ cấp xác định, chẳng hạn với C++, ta có các 
kiểu dữ liệu: số (nguyên, thực), ký tự, lôgic. Với kiểu số nguyên, các phép toán 
thường gặp là: các phép toán số học +, -, *, / (chia nguyên), % (mod, lấy phần dư) 
và các phép toán so sánh như: ==, !=, ≥, ≤, >, <. Với kiểu số thực, các phép toán 
thường gặp là: các phép toán số học +, -, *, /, và các phép toán so sánh như: ==, 
!=, ≥, ≤, >, <. Với kiểu lôgic, các phép toán thường gặp là: ! (not), && (and), || 
(or). Với kiểu ký tự, các phép toán thường gặp là: phép toán ép kiểu và các phép 
toán so sánh như: ==, !=, ≥, ≤, >, <,  
Dựa trên các kiểu đơn giản đã có và các phương pháp xác định của ngôn 
ngữ lập trình qui định, ta có thể xây dựng nên các cấu trúc dữ liệu hay kiểu dữ 
liệu có cấu trúc phức tạp hơn nhằm phản ánh tốt hơn các loại dữ liệu phong phú 
và đa dạng trong thế giới thực. Chẳng hạn như: kiểu mảng, kiểu cấu trúc, kiểu 
hợp, kiểu file,  Một trong những phép toán cơ bản trên các kiểu dữ liệu đó là: 
truy cập đến từng phần tử hay từng thành phần của đối tượng dữ liệu. 
I.1.3. Các bước chính để giải một bài toán trên máy tính 
Để giải một bài toán trên máy tính, ta thường trải qua các giai đoạn chính 
sau đây: 
 Giôùi thieäu caáu truùc döõ lieäu vaø phaân tích giaûi thuaät I.3 
- Đặt bài toán, phân tích, đặc tả và mô hình hoá bài toán 
- Chọn cấu trúc dữ liệu để biểu diễn bài toán và phát triển giải thuật (chọn 
kiểu dữ liệu) 
- Mã hóa chương trình 
- Thử nghiệm chương trình 
- Bảo trì chương trình. 
Hai giai đoạn đầu rất quan trọng, nó góp phần quyết định tính đúng đắn và 
hiệu quả của chương trình nhằm giải bài toán. 
Vai trò của kiểu dữ liệu trong việc giải một bài toán trên máy tính 
Khi đề cập đến một thao tác, cần phải xác định nó tác động lên loại đối 
tượng hay trên cấu trúc dữ liệu hoặc trong kiểu dữ liệu nào? 
Với mỗi mô hình dữ liệu, có thể có nhiều cách cài đặt bởi các cấu trúc dữ 
liệu khác nhau. Trong mỗi cách cài đặt, có thể có một số phép toán được thực hiện 
thuận lợi, nhưng một số phép toán khác lại không thuận tiện. Khi đề cập đến một 
thao tác, cần phải xác định rõ nó tác động trên loại đối tượng hoặc kiểu dữ liệu 
nào? Khi cấu trúc dữ liệu thay đổi thì các giải thuật cơ bản tương ứng với nó cũng 
thay đổi theo. Vì vậy việc chọn cấu trúc dữ liệu nào để biểu diễn mô hình sẽ phụ 
thuộc vào từng ứng dụng cụ thể. 
Để việc chọn cấu trúc dữ liệu biểu diễn bài toán một cách phù hợp, cần 
chú ý đến những quan hệ giữa các đối tượng và thành phần dữ liệu với nhau; 
ngoài ra, ta còn cần phải lưu ý đến những phép toán cơ bản nào sẽ được thực hiện 
thường xuyên trên các đối tượng dữ liệu đó. Chẳng hạn, đối với một dãy các đối 
tượng dữ liệu cùng loại, nếu số lượng các đối tượng này không quá lớn (để có thể 
lưu ở bộ nhớ trong), biến động nhiều, hơn nữa các phép toán thêm và hủy các đối 
tượng xảy ra rất thường xuyên thì ta nên chọn kiểu dữ liệu là danh sách liên kết 
động hơn là kiểu mảng tĩnh để lưu trữ dãy đối tượng này. 
Khi xây dựng các giải thuật nhằm giải quyết một bài toán, ta phải dựa trên 
các yêu cầu cần xử lý để xem xét kỹ lưỡng, cũng như nên dựa trên các đặc trưng 
của bài toán và tài nguyên (tốc độ xử lý và khả năng lưu trữ của hệ thống máy 
tính) thực tế hiện có. 
Tóm lại, khi xây dựng các kiểu dữ liệu nhằm giải quyết một bài toán cụ thể, 
ta nên để ý các tiêu chuẩn sau: 
- Phản ánh đúng thực tế: có dự trù đến khả năng biến đổi của dữ liệu trong 
chu trình sống của nó. Đây là tiêu chuẩn rất quan trọng nhằm quyết định tính đúng 
đắn của toàn bộ bài toán. 
- Cấu trúc dữ liệu được xây dựng cần phù hợp với các thao tác trên đó (đặc 
biệt là các thao tác được sử dụng nhiều nhất). Khi đó, việc phát triển các giải thuật 
sẽ đơn giản, tự nhiên hơn và đạt hiệu quả cao về mặt tốc độ và bộ nhớ. 
 Giôùi thieäu caáu truùc döõ lieäu vaø phaân tích giaûi thuaät I.4 
- Tiết kiệm tài nguyên (tốc độ xử lý và dung lượng bộ nhớ): Đối với các 
giải thuật không quá tầm thường, hai yêu cầu này thường mâu thuẫn nhau và khó 
đạt được tối ưu đồng thời. Tùy theo yêu cầu của bài toán và tài nguyên thực tế, ta 
nên chọn giải thuật cho phù hợp. 
I.2. Thiết kế và phân tích giải thuật 
I.2.1. Thiết kế giải thuật theo phương pháp Top-Down 
Các bài toán giải được trên máy tính ngày càng đa dạng và phức tạp. Việc 
xây dựng mô hình cùng với các giải thuật và cách cài đặt các chương trình giải 
chúng ngày càng có quy mô lớn và phức tạp, thường đòi hỏi công sức đồng thời 
của cả một tập thể các nhóm phân tích - thiết kế viên cũng như các thảo  ...  đếm số đường chạy (tự nhiên) của một dãy gồm n phần tử cho 
trước. 
9) Hãy cài đặt thêm thuật toán xuất bảng lương nhân viên (trong bài tập 1 - 
chương 1) theo thứ tự tiền lương tăng dần. 
10) (*) Hãy viết lại giải thuật QuickSort dưới dạng lặp. 
11) (*) Cải tiến hai thuật toán QuickSort viết dưới dạng đệ qui và lặp [gợi ý: ta nên 
thực hiện sắp xếp trước dãy con nào ngắn hơn]. 
12) (*) Xây dựng ví dụ để trường hợp xấu nhất của thuật toán QuickSort xảy ra. 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.6 
Bài tập chương III (Cấu trúc danh sách liên kết) 
1) Xét đoạn chương trình tạo một DSLK đơn có 4 nút (không quan tâm đến dữ 
liệu) sau đây: 
 NodePointer p, Dx = NULL; 
 p = Dx; Dx = new NodeType; 
 for (i = 0; i < 4; i++) 
 { p = p->Next; 
 p = new NodeType; 
 } 
 p->Next = NULL; 
 Đoạn chương trình này có thực hiện đúng như mục đích đã đưa ra không ? 
Tại sao ? Nếu không thì cần sửa lại như thế nào cho đúng ? 
2) Hãy thực hiện các yêu cầu sau đối với từng loại danh sách liên kết: 
 i) DSLK không có nút câm 
 ii) DSLK có nút câm 
 iii) DSLK vòng (không có nút câm) 
 iv) DSLK đối xứng 
 v) DSLK vòng đôi 
a. Tạo bản sao của một DSLK cho trước. 
b. Nối hai DSLK cho trước. 
c. Tính số lượng các nút dữ liệu. 
d. Tìm nút dữ liệu đầu tiên trong DSLK thỏa một tính chất nào đó, chẳng hạn: 
- nút thứ k, 
- hoặc có trường dữ liệu trùng với một giá trị cùng kiểu K cho trước. 
Nếu có thì trả về con trỏ chỉ đến nút đứng trước nút tìm thấy. 
e. Xóa một (hay mọi) nút dữ liệu trong DSLK thỏa một tính chất nào đó, ví 
dụ: 
- nút thứ k, 
- hoặc có trường dữ liệu trùng với một giá trị cùng kiểu K cho trước. 
f. Bổ sung một nút L vào sau một (hay mọi) nút dữ liệu trong DSLK thỏa 
một tính chất nào đó, chẳng hạn: 
- nút thứ k, 
- hoặc có trường dữ liệu trùng với một giá trị cùng kiểu K cho trước. 
g. Đảo ngược DSLK nói trên theo hai cách : tạo DSLK mới hay sửa lại chiều 
con trỏ trong DSLK ban đầu. 
h. Gọi M là con trỏ chỉ tới một nút đã có trong DSLK trên và P là con trỏ chỉ 
tới một DSLK khác cùng loại. Hãy chèn DSLK P này vào sau nút trỏ bởi 
M. 
i. Tách thành 2 DSLK mà DS sau được trỏ bởi M (giả thiết như câu h). 
j. So sánh 2 DSLK (có trường dữ liệu của các nút liên tiếp tương ứng bằng 
nhau hay không ?) 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.7 
3) Hãy viết chương trình nhằm thực hiện các yêu cầu của bài tập 1 – chương 1 
(biết rằng số lượng nhân viên biến động nhiều, không dự đoán được giới hạn của 
nó) bằng cách dùng DSLK để cài đặt. 
4) Hãy viết thuật toán và chương trình để trộn hai DSLK tăng A, B cho trước 
thành một DSLK C cũng tăng theo hai cách: 
 a. C là DSLK mới (cấp phát bộ nhớ mới cho mọi nút của C) và bảo toàn hai 
DSLK cũ A, B; 
 b. C là DSLK mới do A, B hợp thành (do đổi chỗ vị trí các con trỏ sẵn có 
trên A, B). Khi đó cấu trúc hai DSLK A, B có thể bị thay đổi. 
5) Một số giới hạn vé (MAX_VE) cho buổi hòa nhạc sẽ được bán vào ngày mai. 
Người nào đăng ký trước sẽ được mua trước. Hãy viết một chương trình: 
a. Đọc các tên, tuổi của những người đăng ký cùng với số vé họ mua và lưu 
vào một DSLK (chú ý kiểm tra không có người nào được đăng ký nhiều lần). 
b. Hiện ra màn hình DSLK trên. 
6) (Bài toán Josephus) Một nhóm binh sĩ bị kẻ thù bao vây và một binh sĩ được 
chọn để đi cầu cứu. Việc chọn được thực hiện theo cách sau đây. Một số nguyên n 
và một binh sĩ được chọn ngẫu nhiên. Các binh sĩ được sắp theo vòng tròn và họ 
đếm từ binh sĩ được chọn ngẫu nhiên. Khi đạt đến n, binh sĩ tương ứng được lấy ra 
khỏi vòng và việc đếm lại được bắt đầu từ binh sĩ tiếp theo. Quá trình này tiếp tục 
cho đến khi chỉ còn lại một binh sĩ là người gặp may (hoặc không may) được chọn 
để đi cầu cứu. Hãy viết một thuật toán cài đặt cách chọn này, dùng danh sách liên 
kết vòng để lưu trữ các tên của binh sĩ. 
(Ngăn xếp và hàng đợi) 
7) Cho X là ngăn xếp chứa các ký tự. Giả sử có hàm sau trong C++: 
void Out(StackType &S, ElementType &Item) 
{ Pop(S,Item); cout << Item<< endl; 
} 
Ta cần sử dụng luân phiên các phép toán Push(S, Item) và Out(S,Item) như 
thế nào (nếu có thể) từ bộ các ký tự : ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’ để thu được các 
anagram (hoán vị) sau đây của nó: 
 a) BDCFEA 
 b) BDACEF 
 c) ABCDEF 
 d) EBFCDA 
 e) FEDCBA 
8) Xét một cơ cấu đường tàu và kho sửa chữa như hình sau: 
 Giả sử ở đường vào có 4 đường tàu được đánh số 1, 2, 3, 4. Gọi V là phép 
đưa một đầu tàu vào kho sửa chữa, R là phép đưa một đầu tàu ra khỏi kho. 
 a. Nếu thực hiện dãy VVRVVRRR thì thứ tự các đầu tàu lúc ra là gì ? (Có 
thể xem đây là một cách hoán vị các số được không ?) 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.8 
 b. Xét trường hợp có 6 đầu tàu:1, 2, 3, 4, 5, 6 có thể thực hiện một dãy các 
phép V và R thế nào để đổi thứ tự đầu tàu ở đường ra là: 3, 2, 5, 6, 4, 1 ? và 1, 5, 
4, 6, 2, 3 ? 
Ra Vào 
 Kho sửa chữa 
9) Xét chuỗi: 
 EAS*Y**QUE***ST***I*ON 
Trong đó, mỗi chữ cái tượng trưng cho thao tác thêm nó vào một DSLK List, dấu 
* tượng trưng cho thao tác lấy nó ra khỏi List và xuất ra màn hình. 
Trong từng trường hợp sau, với List là: 
 a. ngăn xếp 
 b. hàng đợi 
hãy cho biết: 
 - Nội dung của List sau mỗi thao tác cơ bản trên ? 
 - Kết quả cuối cùng xuất ra trên màn hình ? 
 - Hãy kiểm tra lại các kết quả trên bằng một chương trình hoàn chỉnh. 
10) Viết các thao tác cơ bản trên ngăn xếp và thêm vào các thao tác sau đây: 
 a. ElementType XemPTửThứ_2CủaNX(StackType S) có tác dụng xem 
phần tử thứ 2 kể từ đỉnh ngăn xếp S mà không làm S thay đổi. 
 b. ElementType LấyPTửThứ_2CủaNX(StackType &S) có tác dụng trả về 
phần tử thứ 2 của ngăn xếp S và S bị mất đi 2 phần tử ở đỉnh của nó. 
 c. ElementType LấyĐáyNX(StackType &S) có tác dụng trả về phần tử ở 
đáy ngăn xếp S và làm S trở thành rỗng. 
 d. ElementType XemĐáyNX(StackType S) có tác dụng trả về phần tử ở đáy 
ngăn xếp S và S không thay đổi. 
11) Để có thể duyệt ngăn xếp hay hàng đợi theo cả hai chiều, ta có thể tổ chức 
chúng theo kiểu DSLK đối xứng như sau: 
 Top Bottom 
 S 
 A B C D 
 Hãy thực hiện các phép toán sau trên ngăn xếp: 
 a. Thực hiện phép duyệt qua DSLK từ dưới lên. 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.9 
 b. Thực hiện phép duyệt qua DSLK từ trên xuống. 
 c. Thực hiện phép bổ sung một phần tử vào (đầu và đuôi) DSLK. 
 d. Thực hiện phép loại bỏ một phần tử (ở đầu và đuôi) khỏi DSLK. 
12) a. Cho Q là hàng đợi rỗng. Cho biết kết quả của Q sau một dãy các phép toán 
thêm vào và lấy ra các ký tự sau đây: 
EnQueue(Q, ’A’), EnQueue(Q, ’B’), EnQueue(Q, ’C’), DeQueue(Q, Item), 
EnQueue(Q, ’D’), EnQueue(Q, ’E’), DeQueue(Q, Item), DeQueue(Q, Item), 
EnQueue(Q, ’F’), DeQueue(Q, Item). 
 b. Viết các thao tác cơ bản trên hàng đợi và thêm vào các thao tác sau đây: 
duyệt hàng đợi từ đầu đến đuôi của nó và ngược lại. 
13) Dùng các phép toán cơ bản trên ngăn xếp và hàng đợi để đảo ngược thứ tự 
các phần tử trên hàng đợi. 
14) Phân tích một số thành tích các thừa số nguyên tố theo thứ tự giảm dần. Ví 
dụ: phân tích: 60 = 5*3*2*2. 
15) Dùng ngăn xếp để kiểm tra một chuỗi ký tự S1 có phải là palyndrome của một 
chuỗi ký tự S2 hay không ? 
16) (*) Viết một chương trình đọc một xâu ký tự chứa các dấu ngoặc và xác định 
xâu đó có chứa các dấu ngoặc tương ứng hợp lệ hay không. Ví dụ: 
- các xâu sau là hợp lệ: a*(b+c), a(), b[d(e+f-)], d-{[a(b)d]} 
- các xâu sau là không hợp lệ: (, ], a*(b+c], a[), b[d(e+f-]), d-{[a((b)d]} 
(Các ứng dụng khác của DSLK) 
17) a. Chuyển các biểu thức trung tố sau đây sang dạng hậu tố: 
a/(b*c), a/b*c, a∧b∧c, (a∧b)∧c, a-b-c, a-(b-c), a5 + 4a3 - 3a2 + 7, (a+b)*(c-
d), Sa+b 
 b. Viết biểu thức sau đây dưới dạng hậu tố: (A * B)/(C + D). Minh họa thông 
qua hình ảnh Stack để tính giá trị biểu thức hậu tố này ứng với: A= 20, B = 4, C = 
9, D = 7. 
 c. (**) Cài đặt một chương trình để : 
 i) Chuyển một biểu thức từ dạng trung tố sang dạng hậu tố (có kiểm tra cú 
pháp của biểu thức). 
 ii) Tính giá trị của một biểu thức cho trước ở dạng hậu tố. 
 iii) Vẽ đồ thị của một hàm giải tích cho trước được đưa vào dưới dạng biểu 
thức chuỗi. 
 iv) Có thể viết lại chương trình trên khái quát hơn để có thể áp dụng cho 
các biểu thức lôgic mệnh đề hay không ? 
18) (**) Hãy viết một chương trình thực hiện các yêu cầu tương tự của bài tập 4 - 
chương 2 để cài đặt các thuật toán sắp xếp sau trên DSLK động (DSLK đơn, 
DSLK kép): 
 a. QuickSort 
 b. MergeSort 
 c. RadixSort 
 d. Các phương pháp sắp xếp trực tiếp: chèn, chọn, đổi chỗ 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.10 
19) (*) Hãy lập các giải thuật cộng, trừ, nhân hai đa thức và tính đạo hàm, nguyên 
hàm của một đa thức cho trước trong hai trường hợp: 
 a) Khi các hệ số của đa thức được lưu đầy đủ trong mảng. 
b) (*) Khi chỉ các hệ số khác không và các số mũ tương ứng được lưu trong 
một danh sách liên kết. 
20) (*) Hãy cài đặt tập hợp bằng DSLK và thực hiện các phép toán trên tập hợp 
(quan hệ một phần tử có thuộc vào một tập không; quan hệ bao hàm, bằng nhau 
giữa hai tập; phép toán giao, hiệu, hợp hai tập hợp, ...) 
21) (**) Viết các phép toán cơ bản trên ma trận thưa được cài đặt bằng DSLK tổng 
quát. 
22) a. Hãy cài đặt các thao tác cơ bản trên DSLK có thứ tự và tổ chức lại, hàng 
đợi ưu tiên. So sánh thời gian tìm kiếm của cách tổ chức này với các cách tổ chức 
bình thường. 
 b. Tìm một ứng dụng thực tế của hàng đợi ưu tiên. 
23) (*) Áp dụng thuật toán sắp xếp tôpô vào bài toán sắp lịch giảng dạy (tuyến 
tính) cho dãy các học phần thỏa điều kiện “học trước” đã biết. 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.11 
Bài tập chương IV (Cấu trúc cây) 
1) Xuất ra theo thứ tự : giữa, đầu, cuối các phần tử trên cây nhị phân sau: 
A 
 P R 
 Q E T 
 M N D B C 
2) a. Tìm cây nhị phân thỏa đồng thời hai điều kiện kết xuất sau: 
theo thứ tự đầu NLR của nó là dãy ký tự sau: 
 A, B, C, D, E, Z, U, T, Y 
và theo thứ tự giữa LNR của nó là dãy ký tự sau: 
 D, C, E, B, A, U, Z, T, Y 
 b. (*) Khi cho trước 2 trong 3 kết quả duyệt NLR, LNR, LRN thì có luôn xác 
định duy nhất cây nhị phân thỏa điều kiện nêu ra không ? Dùng chương trình để 
kiểm chứng ? 
3) a. Biểu diễn mỗi biểu thức số học dưới đây trên cây nhị phân, từ đó rút ra 
dạng biểu thức hậu tố của chúng: 
i. a/(b*c) 
 ii. a5 + 4a3 -3a2 + 7 
 iii. (a+b)*(c-d) 
iv. Sa+b 
 b. (*) Viết thuật toán và chương trình: 
- Chuyển một biểu thức số học ký hiệu lên cây nhị phân (có kiểm tra biểu 
thức đã cho có hợp cú pháp không ?). 
- Xuất ra biểu thức số học đó dưới dạng: trung tố, hậu tố, tiền tố. 
- Sau đó nhập trị cho các ký hiệu trong biểu thức, hãy đánh giá biểu thức hậu 
tố tương ứng. 
4) Xây dựng cây tìm kiếm nhị phân BST và cây AVL từ mỗi bộ mục dữ liệu đầu 
vào như sau: 
a. 1, 2, 3, 4, 5 
b. 5, 4, 3, 2, 1 
c. fe, cx, jk, ha, gc, ap, aa, by, my, da 
d. 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 10, 12, 17, 16, 18. 
Sau đó xóa lần lượt các nút sau: 2, 10, 19, 8, 20, 6, 1. 
5) Viết một chương trình có các tác dụng sau: 
a. Nhập từ bàn phím các số nguyên vào một cây nhị phân tìmkiếm (BST) mà 
nút gốc được trỏ bởi con trỏ Root. 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.12 
b. Xuất các phần tử trên cây BST trên theo thứ tự : đầu, giữa, cuối theo dòng 
và vẽ sơ đồ cây (*) (chỉ yêu cầu trường hợp khi số phần tử của cây nhị phân 
không quá lớn !). 
c. Tìm và xóa (nếu có thể) phần tử trên cây Root có dữ liệu trùng với một mục 
dữ liệu Item cho trước được nhập từ bàn phím. 
d. Sắp xếp n mục dữ liệu (được cài đặt bằng mảng hay DSLK) bằng phương 
pháp cây nhị phân tìm kiếm BSTSort. 
Yêu cầu: viết các thao tác trên bằng 2 phương pháp: đệ quy và lặp (*). 
(**) Riêng với duyệt cây, hãy viết dưới dạng lặp cả 3 phương pháp duyệt 
trong một hàm duy nhất có tính khái quát. 
e. Kiểm tra lại kết quả của bài tập 4) bằng chương trình vừa xây dựng. 
6) Tương tự bài tập 5, nhưng mỗi nút có thêm trường con trỏ Parent chỉ đến nút 
cha của nó. 
7) (*) Xây dựng các thao tác cơ bản trên cây n-phân được biểu diễn bởi cây nhị 
phân: chèn một nút, tạo cây n-phân, xóa một nút, hủy cây n-phân. 
8) Cho cây nhị phân T. Viết chương trình chứa các hàm có tác dụng xác định: 
a. Tổng số nút của cây. Số nút tối đa của cây nhị phân có chiều cao h là bao 
nhiêu? Chứng minh điều khẳng định bằng qui nạp và kiểm nghiệm lại bằng 
chương trình. 
b. (*) Số nút của cây ở mức k. Số nút tối đa ở mức k của cây nhị phân là bao 
nhiêu ? Chứng minh điều khẳng định bằng qui nạp và kiểm nghiệm lại bằng 
chương trình. 
c. Số nút lá. 
d. (*) Chiều cao của cây. 
e. Tổng giá trị trường dữ liệu (số !) trên các nút của cây. 
f. Kiểm tra xem nó có phải là một cây nhị phân chặt (là cây nhị phân mà mỗi 
nút khác nút lá đều có đúng 2 con) hay không ? 
g. Kiểm tra xem T có phải là cây cân bằng hoàn toàn hay không ? 
h. Số nút có đúng 2 con khác rỗng 
i. Số nút có đúng 1 con khác rỗng 
j. Số nút có khóa nhỏ hơn x trên cây nhị phân hoặc cây BST 
k. Số nút có khóa lớn hơn x trên cây nhị phân hoặc cây BST 
l. Số nút có khóa nhỏ hơn x và lớn hơn y (y ≤ x) trên cây nhị phân hoặc cây 
BST 
m. Duyệt cây theo chiều rộng 
n. Duyệt cây theo chiều sâu 
o. Độ lệch lớn nhất của các nút trên cây (độ lệch của một nút là trị tuyệt đối 
của hiệu số giữa chiều cao của cây con phải và cây con trái của nó) 
p. Đảo nhánh trái và phải của mọi nút trên một cây nhị phân 
Yêu cầu: viết các thao trên bằng 2 phương pháp: đệ quy và lặp (*). 
9) Viết chương trình xây dựng cây nhị phân tìm kiếm có chiều cao bé nhất từ một 
dãy có thứ tự tăng của các phần tử được lưu trữ trên một danh sách liên kết. 
10) a. Hãy vẽ cây AVL có chiều cao cực đại có 12 nút 
 Baøi taäp Caáu truùc döõ lieäu vaø Thuaät toùan 1 BT.13 
 b. Hãy tìm một ví dụ về một cây AVL có chiều cao là 6 và khi hủy một nút lá 
(chỉ ra cụ thể), việc cân bằng lại cây lan truyền lên tận gốc. 
c. (*) Viết chương trình thể hiện các thao tác cơ bản trên cây AVL: chèn một 
nút, xóa một nút, tạo cây AVL, hủy cây AVL. Kiểm tra lại bằng chương 
trình với dữ liệu của câu a. và b. trên đây. 
11) (*) Viết chương trình cho phép tạo, thêm, bớt, tra cứu, sửa chữa từ điển. 
 TÀI LIỆU THAM KHẢO 
[1] A.V. AHO , J.E. HOPCROFT , J.D. ULMANN: Data structures and 
algorithms. Addition Wesley - 1983. 
[2] DONALD KNUTH: The Art of Programming. (vol.1: Fundamental 
Algorithms, vol. 3: Sorting and Searching). Addition Wesley Puplishing 
Company - 1973. 
[3] ĐINH MẠNH TƯỜNG: Cấu trúc dữ liệu và giải thuật. NXB KHKT - 2001. 
[4] ĐỖ XUÂN LÔI: Cấu trúc dữ liệu và giải thuật. NXB KHKT - 1995. 
[5] LARRY N. HOFF, SANFORD LEESTMA: Lập trình nâng cao bằng Pascal 
với các cấu trúc dữ liệu. Bản dịch của Lê Minh Trung. Công ty Scitec - 1991. 
[6] NGUYỄN TRUNG TRỰC: Cấu trúc dữ liệu. Trung tâm điện toán, trường ĐH 
Bách khoa TP. HCM – 1992. 
[7] NIKLAUS WIRTH: Cấu trúc dữ liệu + Giải thuật = Chươngtrình (Nguyễn 
Quốc Cường dịch). NXB ĐH và THCN – 1991 
[8] TRẦN HẠNH NHI & DƯƠNG ANH ĐỨC: Nhập môn cấu trúc dữ liệu và 
giải thuật. Khoa Công nghệ thông tin, ĐH KHTN TP HCM – 2000.