Giáo trình môn học Cấu trúc dữ liệu và giải thuật

MỤC LỤC 
 Mục Trang 
 CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & GT ...........3 
 1.1. Tầm quan trọng của CTDL & GT trong một đề án tin học ........................ 3 
 1.1.1. Xây dựng cấu trúc dữ liệu ......................................................................... 3 
 1.1.2. Xây dựng giải thuật ................................................................................... 3 
 1.1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật ....................................... 3 
 1.2. Đánh giá Cấu trúc dữ liệu & Giải thuật ....................................................... 3 
 1.2.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu ................................................. 3 
 1.2.2. Đánh giá độ phức tạp của thuật toán ........................................................ 4 
 1.3. Kiểu dữ liệu ..................................................................................................... 4 
 1.3.1. Khái niệm về kiểu dữ liệu .......................................................................... 4 
 1.3.2. Các kiểu dữ liệu cơ sở ............................................................................... 4 
 1.3.3. Các kiểu dữ liệu có cấu trúc...................................................................... 5 
 1.3.4. Kiểu dữ liệu con trỏ ................................................................................... 5 
 1.3.5. Kiểu dữ liệu tập tin .................................................................................... 5 
 Câu hỏi và bài tập ................................................................................................. 6 
 CHƯƠNG 2: KỸ THUẬT TÌM KIẾM (Searching) .............................8 
 2.1. Khái quát về tìm kiếm.................................................................................... 8 
 2.2. Các giải thuật tìm kiếm nội ........................................................................... 8 
 2.2.1. Đặt vấn đề ................................................................................................. 8 
 2.2.2. Tìm tuyến tính ............................................................................................ 8 
 2.2.3. Tìm nhị phân ............................................................................................ 10 
 2.3. Các giải thuật tìm kiếm ngoại ..................................................................... 14 
 2.3.1. Đặt vấn đề ............................................................................................... 14 
 2.3.2. Tìm tuyến tính .......................................................................................... 14 
 2.3.3. Tìm kiếm theo chỉ mục ............................................................................. 16 
 Câu hỏi và bài tập ............................................................................................... 17 
 CHƯƠNG 3: KỸ THUẬT SẮP XẾP (SORTING) .............................19 
 3.1. Khái quát về sắp xếp .................................................................................... 19 
 3.2. Các giải thuật sắp xếp nội............................................................................ 19 
 3.2.1 Sắp xếp bằng phương pháp đổi chỗ .......................................................... 20 
 3.2.2. Sắp xếp bằng phương pháp chọn ............................................................. 28 
 3.2.3. Sắp xếp bằng phương pháp chèn ............................................................. 33 
 3.2.4. Sắp xếp bằng phương pháp trộn .............................................................. 40 
 3.3. Các giải thuật sắp xếp ngoại........................................................................ 60 
 3.3.1. Sắp xếp bằng phương pháp trộn .............................................................. 60 
 3.3.2. Sắp xếp theo chỉ mục ............................................................................... 79 
 Câu hỏi và bài tập ............................................................................................... 82 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 2 
 CHƯƠNG 4: DANH SÁCH (LIST) .....................................................84 
 4.1. Khái niệm về danh sách ............................................................................... 84 
 4.2. Các phép toán trên danh sách ..................................................................... 84 
 4.3. Danh sách đặc ............................................................................................... 85 
 4.3.1. Định nghĩa ............................................................................................... 85 
 4.3.2. Biểu diễn danh sách đặc .......................................................................... 85 
 4.3.3. Các thao tác trên danh sách đặc ............................................................. 85 
 4.3.4. Ưu nhược điểm và Ứng dụng ................................................................... 91 
 4.4. Danh sách liên kết ........................................................................................ 92 
 4.4.1. Định nghĩa ............................................................................................... 92 
 4.4.2. Danh sách liên kết đơn ............................................................................ 92 
 4.4.3. Danh sách liên kết kép .......................................................................... 111 
 4.4.4. Ưu nhược điểm của danh sách liên kết .................................................. 135 
 4.5. Danh sách hạn chế ...................................................................................... 135 
 4.5.1. Hàng đợi ................................................................................................ 135 
 4.5.2. Ngăn xếp ............................................................................................... 142 
 4.5.3. Ứng dụng của danh sách hạn chế .......................................................... 147 
 Câu hỏi và bài tập ............................................................................................. 147 
 CHƯƠNG 5: CÂY (TREE) ...............................................................149 
 5.1. Khái niệm – Biểu diễn cây......................................................................... 149 
 5.1.1. Định nghĩa cây ...................................................................................... 149 
 5.1.2. Một số khái niệm liên quan ................................................................... 149 
 5.1.3. Biểu diễn cây ......................................................................................... 151 
 5.2. Cây nhị phân ............................................................................................... 152 
 5.2.1. Định nghĩa ............................................................................................. 152 
 5.2.2. Biểu diễn và Các thao tác ..................................................................... 152 
 5.2.3. Cây nhị phân tìm kiếm ........................................................................... 163 
 5.3. Cây cân bằng............................................................................................... 188 
 5.3.1. Định nghĩa – Cấu trúc dữ liệu ............................................................... 188 
 5.3.2. Các thao tác .......................................................................................... 189 
 Câu hỏi và bài tập ............................................................................................. 227 
 ÔN TẬP (REVIEW) ..........................................................................224 
 Hệ thống lại các Cấu trúc dữ liệu và các Giải thuật đã học.......................... 224 
 Câu hỏi và Bài tập ôn tập tổng hợp ................................................................. 227 
 TÀI LIỆU THAM KHẢO .................................................................229 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 3 
Chương 1: TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 
1.1. Tầm quan trọng của cấu trúc dữ liệu và giải thuật trong một 
 đề án tin học 
1.1.1. Xây dựng cấu trúc dữ liệu 
Có thể nói rằng không có một chương trình máy tính nào mà không có dữ liệu để xử lý. 
Dữ liệu có thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra 
(output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình có ý 
nghĩa rất quan trọng trong toàn bộ hệ thống chương trình. Việc xây dựng cấu trúc dữ 
liệu quyết định rất lớn đến chất lượng cũng như công sức của người lập trình trong việc 
thiết kế, cài đặt chương trình. 
1.1.2. Xây dựng giải thuật 
Khái niệm giải thuật hay thuật giải mà nhiều khi còn được gọi là thuật toán dùng để chỉ 
phương pháp hay cách thức (method) để giải quyết vần đề. Giải thuật có thể được minh 
họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã 
giả (pseudo code). Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng 
mã giả tựa trên một hay một số ngôn ngữ lập trình nào đó (thường là ngôn ngữ mà 
người lập trình chọn để cài đặt thuật toán), chẳng hạn như C, Pascal,  
Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến hành 
xây dựng thuật giải tương ứng theo yêu cầu của bài toán đặt ra trên cơ sở của cấu trúc 
dữ liệu đã được chọn. Để giải quyết một vấn đề có thể có nhiều phương pháp, do vậy 
sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải cân nhắc và tính 
toán. Sự lựa chọn này cũng có thể góp phần đáng kể trong việc giảm bớt công việc 
của người lập trình trong phần cài đặt thuật toán trên một ngôn ngữ cụ thể. 
1.1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật 
Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật có thể minh họa bằng đẳng thức: 
Cấu trúc dữ liệu + Giải thuật = Chương trình 
Như vậy, khi đã có cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện 
chương trình bằng một ngôn ngữ cụ thể chỉ là vấn đề thời gian. Khi có cấu trúc dữ liệu 
mà chưa tìm ra thuật giải thì không thể có chương trình và ngược lại không thể có 
Thuật giải khi chưa có cấu trúc dữ liệu. Một chương trình máy tính chỉ có thể được hoàn 
thiện khi có đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật xử lý dữ liệu 
theo yêu cầu của bài toán đặt ra. 
1.2. Đánh giá cấu trúc dữ liệu và giải thuật 
1.2.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu 
Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau: 
- Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong), 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 4 
- Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán, 
- Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu. 
1.2.2. Đánh giá độ phức tạp của thuật toán 
Việc đánh giá độ phức tạp của một thuật t oán quả không dễ dàng chút nào. Ở dây, 
chúng ta chỉ muốn ước lượng thời gian thực hiện thuận toán T(n) để có thể có sự so 
sánh tương đối giữa các thuật toán với nhau. Trong thực tế, thời gian thực hiện một 
thuật toán còn phụ thuộc rất nhiều vào các điều kiện khác như cấu tạo của máy tính, 
dữ liệu đưa vào, , ở đây chúng ta chỉ xem xét trên mức độ của lượng dữ liệu đưa vào 
ban đầu cho thuật toán thực hiện. 
Để ước lượng thời gian thực hiện thuật toán chúng ta có thể xem xét thời gian thực hiện 
thuật toán trong hai trường hợp: 
- Trong trường hợp tốt nhất: Tmin 
- Trong trường hợp xấu nhất: Tmax 
Từ đó chúng ta có thể ước lượng thời gian thực hiện trung bình của thuật toán: Tavg 
1.3. Kiểu dữ liệu 
1.3.1. Khái niệm về kiểu dữ liệu 
Kiểu dữ liệu T có thể xem như là sự kết hợp của 2 thành phần: 
- Miền giá trị mà kiểu dữ liệu T có thể lưu trữ: V, 
- Tập hợp các phép toán để thao tác dữ liệu: O. 
T = 
Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần tử dữ liệu có 
kiểu T sẽ có giá trị trong miền V và có thể được thực hiện các phép toán thuộc tập hợp 
các phép toán trong O. 
Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ nhớ, số 
byte(s) này gọi là kích thước của kiểu dữ liệu. 
1.3.2. Các kiểu dữ liệu cơ sở 
Hầu hết các ngôn ngữ lập trình đều có cung cấp các kiểu dữ liệu cơ sở. Tùy vào mỗi 
ngôn ngữ mà các kiểu dữ liệu cơ sở có thể có các tên gọi khác nhau song chung quy 
lại có những loại kiểu dữ liệu cơ sở như sau: 
- Kiểu số nguyên: Có thể có dấu hoặc không có dấu và thường có các kích thước sau: 
+ Kiểu số nguyên 1 byte 
+ Kiểu số nguyên 2 bytes 
+ Kiểu số nguyên 4 bytes 
Kiểu số nguyên thường được thực hiện với các phép toán: O = {+, -, *, /, DIV, MOD, <, 
>, =, =, } 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 5 
- Kiểu số thực: Thường có các kích thước sau: 
+ Kiểu số thực 4 bytes 
+ Kiểu số thực 6 bytes 
+ Kiểu số thực 8 bytes 
+ Kiểu số thực 10 bytes 
Kiểu số thực thường được thực hiện với các phép toán: O = {+, -, *, /, , =, =, } 
- Kiểu ký tự: Có thể có các kích thước sau: 
+ Kiểu ký tự byte 
+ Kiểu ký tự 2 bytes 
Kiểu ký tự thường được thực hiện với các phép toán: O = {+, -, , =, =, ORD, 
CHR, } 
- Kiểu chuỗi ký tự: Có kích thước tùy thuộc vào từng ngôn ngữ lập trình 
Kiểu chuỗi ký tự thường được thực hiện với các phép toán: O = {+, &, , =, =, 
Length, Trunc, } 
- Kiểu luận lý: Thường có kích thước 1 byte 
Kiểu luận lý thường được thực hiện với các phép toán: O = {NOT, AND, OR, XOR, , 
=, =, } 
1.3.3. Các kiểu dữ liệu có cấu trúc 
Kiểu dữ liệu có cấu trúc là các kiểu dữ liệu được xây dựng trên cơ sở các kiểu dữ liệu 
đã có (có thể lại là một kiểu dữ liệu có cấu trúc khác). Tùy vào từng ngôn ngữ lập 
trình song thường có các loại sau: 
- Kiểu mảng hay còn gọi là dãy: kích thước bằng tổng kích thước của các phần tử 
- Kiểu bản ghi hay cấu trúc: kích thước bằng tổng kích thước các thành phần (Field) 
1.3.4. Kiểu dữ liệu con trỏ 
Các ngôn ngữ lập trình thường cung cấp cho chúng ta một kiểu dữ lie ... ơng pháp để chuyển từ cấu trúc dữ liệu của một cây N-phân nói 
chung thành một cây nhị phân? 
3. Trình bày thuật toán và cài đặt tất cả các thao tác trên cây nhị phân tìm kiếm, cây 
nhị phân tìm kiếm cân bằng? 
4. Trình bày thuật toán và cài đặt tất cả các thao tác trên cây nhị phân tìm kiếm, cây 
nhị phân tìm kiếm cân bằng trong trường hợp chấp nhận sự trùng khóa nhận diện 
của các nút trong cây? 
5. Trình bày tất cả các thuật toán và cài đặt tất cả các thuật toán để thực hiện việc hủy 
một nút trên cây nhị phân tìm kiếm nếu cây có 02 cây con? Theo bạn, thuật toán 
nào là đơn giản? Cho nhận xét về mỗi thuật toán? 
6. Trình bày và cài đặt tất cả các thuật toán để thực hiện các t hao tác trên cây nhị 
phân tìm kiếm, cây nhị phân tìm kiếm cân bằng trong hai trường hợp: Chấp nhận và 
Không chấp nhận sự trùng lắp về khóa của các nút bằng cách không sử dụng thuật 
toán đệ quy (Trừ các thao tác đã trình bày trong tài liệu)? 
7. Trình bày thuật toán và cài đặt chương trình thực hiện các công việc sau trên cây nhị 
phân: 
a) Tính số nút lá của cây. 
b) Tính số nút trung gian của cây. 
c) Tính chiều dài đường đi tới một nút có khóa là K trên cây. 
d) Cho biết cấp của một nút có khóa là K trên cây. 
8. Trình bày thuật toán và cài đặt chương trình thực hiện công việc tạo cây nhị phân 
tìm kiếm mà khóa của các nút là khóa của các nút trong một danh sách liên kết đôi 
sao cho tối ưu hóa bộ nhớ. Biết rằng, danh sách liên kết đôi ban đầu không cần thiết 
sau khi tạo xong cây nhị phân tìm kiếm và giả sử không cho phép sự trùng khóa 
giữa các nút trong cây. 
9. Với yêu cầu trong bài tập 8 ở trên, trong trường hợp nếu danh sách liên kết có nhiều 
nút có thành phần dữ liệu giống nhau, bạn hãy đề xuất phương án giải quyết để 
không bị mất dữ liệu sau khi tạo xong cây nhị phân tìm kiếm. 
10. Trình bày thuật toán và cài đặt chương trình thực hiện công việc chuyển cây nhị 
phân tìm kiếm thành danh sách liên kết đôi s ao cho tối ưu hóa bộ nhớ. Biết rằng, 
cây nhị phân tìm kiếm ban đầu không cần thiết sau khi tạo xong danh sách liên kết 
(ngược với yêu cầu trong bài tập 8). 
11. Trình bày thuật toán và cài đặt chương trình thực hiện công việc nhập hai cây nhị 
phân tìm kiếm thành một cây nhị phân tìm kiếm duy nhất sao cho tối ưu bộ nhớ. Biết 
rằng, hai cây nhị phân tìm kiếm ban đầu không cần thiết sau khi tạo xong cây mới. 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 224 
ÔN TẬP (REVIEW) 
Hệ thống lại các Cấu trúc dữ liệu và các Giải thuật đã học 
Chương 1: Tổng quan về Cấu Trúc Dữ Liệu và Giải Thuật 
1. Tầm quan trọng của Cấu trúc dữ liệu và Giải thuật trong một đề án tin học 
1.1. Xây dựng Cấu trúc dữ liệu 
1.2. Xây dựng Giải thuật 
1.3. Mối quan hệ giữa Cấu trúc dữ liệu và Giải thuật 
2. Đánh giá Cấu trúc dữ liệu và Giải thuật 
2.1. Các tiêu chuẩn đánh giá Cấu trúc dữ liệu 
- Thời gian thực hiện 
- Mức độ tiêu tốn bộ nhớ 
- Tính thực tế 
2.2. Đánh giá độ phức tạp của thuật toán 
3. Kiểu dữ liệu 
3.1. Khái niệm về Kiểu dữ liệu 
T = {V, O} 
3.2. Các kiểu dữ liệu cơ sở 
- Nguyên 
- Thực 
- Ký tự 
3.3. Các kiểu dữ liệu có cấu trúc 
- Mảng 
- Cấu trúc (struct) 
3.4. Kiểu dữ liệu con trỏ 
T * Pt; 
3.5. Kiểu dữ liệu tập tin 
FILE * Fp; 
int Fh; 
Chương 2: Kỹ thuật tìm kiếm (Searching) 
1. Khái quát về tìm kiếm 
2. Các giải thuật tìm kiếm nội (tìm kiếm trên dãy) 
2.1. Tìm tuyến tính (Linear Search) 
Duyệt từ đầu đến cuối mảng để tìm 
2.2. Tìm nhị phân (Binary Search) 
Duyệt từng nửa các phần tử, chỉ áp dụng cho mảng đã có thứ tự. 
3. Các giải thuật tìm kiếm ngoại (tìm kiếm trên tập tin) 
3.1. Tìm tuyến tính (Linear Search) 
Duyệt từ đầu đến cuối file để tìm 
3.2. Tìm kiếm theo chỉ mục (Index Search) 
Duyệt từ đầu đến tập tin chỉ mục để lấy dữ liệu trong tập tin dữ liệu. 
Chương 3: Kỹ thuật sắp xếp (Sorting) 
1. Khái quát về sắp xếp 
2. Các phương pháp sắp xếp nội (sắp xếp dãy) 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 225 
2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange) 
- Nổi bọt (Bubble Sort) 
- Phân hoạch (Quick Sort) 
2.3. Sắp xếp bằng phương pháp chọn (Selection) 
Chọn trực tiếp (Straight Selection Sort) 
2.4. Sắp xếp bằng phương pháp chèn (Insertion) 
- Chèn trực tiếp (Straight Insertion Sort) 
2.5. Sắp xếp bằng phương pháp trộn (Merge) 
- Trộn trực tiếp (Straight Merge Sort) 
- Trộn tự nhiên (Natural Merge Sort) 
3. Các phương pháp sắp xếp ngoại (sắp xếp tập tin) 
3.1. Sắp xếp bằng phương pháp trộn 
- Trộn trực tiếp (Straight Merge Sort) 
- Trộn tự nhiên (Natural Merge Sort) 
3.2. Sắp xếp theo chỉ mục 
Chương 4: Danh sách (List) 
1. Khái niệm về danh sách 
2. Các phép toán trên danh sách 
3. Danh sách đặc (Condensed List) 
3.1. Định nghĩa 
3.2. Biểu diễn và Các thao tác 
const int MaxLen = 10000; // hoặc: #define MaxLen 10000 
int Length; 
T CD_LIST[MaxLen]; // hoặc: T * CD_LIST = new T[MaxLen]; 
3.3. Ưu nhược điểm và Ứng dụng 
4. Danh sách liên kết (Linked List) 
4.1. Định nghĩa 
4.2. Danh sách liên kết đơn (Singly Linked List) 
typedef struct SLL_Node 
{ T Key; 
SLL_Node * NextNode; 
} SLL_OneNode; 
typedef SLL_OneNode * SLL_Type; 
4.3. Danh sách liên kết kép (Doubly Linked List) 
typedef struct DLL_Node 
{ T Key; 
DLL_Node * NextNode; 
DLL_Node * PreNode; 
} DLL_OneNode; 
typedef DLL_OneNode * DLL_Type; 
4.4. Ưu nhược điểm của danh sách liên kết 
5. Danh sách hạn chế 
5.1. Hàng đợi (Q ueue) 
typedef struct Q_C 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 226 
{ int Len; // Chiều dài hàng đợi 
int Front, Rear; 
T * List; // Nội dung hàng đợi 
} C_QUEUE; 
C_QUEUE CQ_List; 
5.2. Ngăn xếp (Stack) 
typedef struct S_C 
{ int Size; // Kích thước ngăn xếp 
int SP; 
T * List; // Nội dung ngăn xếp 
} C_STACK; 
C_STACK CS_List; 
Chương 5: Cây (Tree) 
1. Các khái niệm 
2. Cây nhị phân (Binary tree) 
2.1. Định nghĩa 
2.2. Biểu diễn và Các thao tác 
typedef struct BinT_Node 
{ T Key; 
BinT_Node * BinT_Left; 
BinT_Node * BinT_Right; 
} BinT_OneNode; 
typedef BinT_OneNode * BinT_Type; 
2.3. Cây nhị phân tìm kiếm (Binary Searching Tree) 
typedef struct BST_Node 
{ T Key; 
BST_Node * BST_Left; 
BST_Node * BST_Right; 
} BST_OneNode; 
typedef BST_OneNode * BST_Type; 
3. Cây cân bằng (Balanced tree) 
3.1. Định nghĩa 
typedef struct BAL_Node 
{ T Key; 
int Bal; 
BAL_Node * BAL_Left; 
BAL_Node * BAL_Right; 
} BAL_OneNode; 
typedef BAL_OneNode * BAL_Type; 
3.2. Các thao tác 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 227 
Câu hỏi và Bài tập ôn tập tổng hợp 
1. Phân biệt về cấu trúc dữ liệu, ý nghĩa và tác dụng giữa: danh sách liên kết đôi, danh 
sách đa liên kết có hai mối liên kết và cây nhị phân? 
2. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ các số nguyên có dấu có giá trị 
tuyệt đối quá lớn trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này, hãy 
trình bày thuật toán và cài đặt chương trình thực hiện việc cộng, trừ, nhân, chia 
nguyên, lấy dư, so sánh các số nguyên có giá trị lớn này. 
3. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ độ dài đường đi giữa các Thành 
phố với nhau trong một quốc gia vào trong bộ nhớ trong của máy tính. Với cấu trúc 
dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình thực hiện việc liệt kê tất 
cả các đường đi từ Thành phố A đến Thành phố B? Đường đi nào là đường đi ngắn 
nhất? 
4. Các văn bản được lưu trữ thành từng dòng trên các file văn bản, mỗi dòng có chiều 
dài không quá 127 ký tự. Hãy đề xuất cấu trúc dữ liệu thích hợp để lưu trữ trong bộ 
nhớ trong của máy tính tần suất xuất hiện của các từ trong tập tin văn bản này. Với 
cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình thực hiện việc 
thống kê xem các từ trong file văn bản xuất hiện với tần suất như thế nào? Cho biết 
văn bản có bao nhiêu t ừ, bao nhiêu tên từ? 
5. Các văn bản được lưu trữ thành từng dòng trên các file văn bản, mỗi dòng có chiều 
dài không quá 127 ký tự. Hãy đề xuất cấu trúc dữ liệu thích hợp để lưu trữ trong bộ 
nhớ trong của máy tính các dòng văn bản trong tập tin văn bản này (có thể bộ nhớ 
không đủ để lưu toàn bộ nội dung tập tin văn bản này vào trong bộ nhớ trong của 
máy tính). Với cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình 
thực hiện việc hiện nội tập tin văn bản này theo từng trang màn hình sao cho chúng 
ta có thể sử dụng các phím PgUp/PgDn để lật lên/xuống theo từng trang màn hình và 
sử dụng các phím Up-arrow/Down-arrow để cho trôi lên/xuống từng dòng văn bản 
trên màn hình? Cho biết văn bản có bao nhiêu dòng? 
6. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ các ma trận thưa (ma trận mà chủ 
yếu giá trị các phần tử bằng 0) trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu 
này, hãy trình bày thuật toán và cài đặt chương trình thực hiện việc cộng, trừ, nhân 
hai ma trận thưa với nhau, tạo ma trận thưa chuyển vị từ một ma trận thưa khác. 
7. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ Gia phả của một dòng họ nào đó 
trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này, hãy trình bày thuật toán 
và cài đặt chương trình thực hiện việc kiểm tra xem 02 người có tên là X và Y có 
phải là hai anh em ruột hay không? Nếu không phải thì ai có “vai vế” cao hơn? Giả 
sử rằng mỗi cặp vợ chồng có không quá 05 người con. 
8. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ một hệ thống Menu có nhiều mục 
chọn, nhiều cấp trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này, hãy trình 
bày thuật toán và cài đặt chương trình thực hiện việc cho menu xuất hiện trên màn 
hình và cho phép người sử dụng chọn một chức năng nào đó của menu. 
9. Kết hợp cấu trúc dữ liệu ở trong bài tập và 4, 5 và 8. Hãy trình bày thuật toán và cài 
đặt chương trình thực hiện các chức năng của một phần mềm soạn thảo văn bản 
đơn giản? 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 228 
10. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ các từ của một từ điển vào trong 
tập tin có tên DICT.DAT. Thông tin giải nghĩa về một từ bao gồm: Tên từ, Loại từ 
(Danh từ, động từ, tính từ, ), nghĩa tiếng Việt. 
a) Sử dụng tập tin chỉ mục để liệt kê các từ theo thứ tự Alphabet (A -> Z). 
b) Hãy đề xuất cấu trúc dữ liệu thích hợp để lưu trữ trong bộ nhớ trong của máy tính 
thông tin giải nghĩa của các từ trong tập tin DICT.DAT này (có thể bộ nhớ không 
đủ để lưu toàn bộ nội dung tập tin DICT.DAT này vào trong bộ nhớ trong của máy 
tính). Với cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình 
thực hiện việc tra nghĩa cho một từ. Ngoài ra, ta có thể sử dụng các phím 
PgUp/PgDn để lật lên/xuống theo từng trang (do mình quy định) màn hình và sử 
dụng các phím Up-arrow/Down-arrow để cho trôi lên/xuống từng từ trên màn 
hình? Sử dụng cấu trúc dữ liệu thích hợp để lưu trữ trong bộ nhớ trong các từ đã 
được tra nghĩa. 
11. Người ta lưu trữ các hệ số của một đa thức bậc n thành các dòng văn bản trong file 
DATHUC.DAT theo nguyên tắc: Mỗi dòng là hệ số và số mũ của 1 đa thức và các hệ 
số và số mũ này cách nhau ít nhất là một khoảng trắng. 
Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ một đa thức vào trong bộ nhớ 
trong của máy tính. Với cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt 
chương trình thực hiện các công việc sau: 
- Xuất các đa thức trong file DATHUC.DAT ra màn hình; 
- Tính đa thức tổng, đa thức hiệu của các đa t hức này; 
- Tính đa thức tích của các đa thức này. 
12. Một hình vuông có độ dài cạnh là a được tô 02 màu: trắng và đen. Người ta tiến 
hành chia hình vuông này thành 04 hình vuông con đều nhau và ghi nhận vị trí của 
chúng trong hình vuông lớn. Nếu trong mỗi hình vuông con chỉ gồm toàn màu trắng 
hoặc màu đen thì giữ nguyên, còn nếu trong hình vuông con còn có 02 màu thì tiếp 
tục chia hình vuông con này thành 04 hình vuông con nhỏ hơn và ghi nhận vị trí, , 
cứ như vậy sau một số hữu hạn phép chia sẽ kết thúc việc chia. Hãy sử dụng cấu 
trúc dữ liệu thích hợp để lưu trữ các hình vuông này vào trong bộ nhớ trong của máy 
tính. Với cấu trúc dữ liệu lựa chọn, hãy trình bày thuật toán và cài đặt chương trình 
thực hiện các công việc sau: 
- Tính tổng số hình vuông tạo thành qua các lần chia. 
- Tính tổng số hình vuông màu trắng, màu đen và tổng diện tích tương ứng của 
chúng. 
- Tái tạo lại hình vuông ban đầu. 
13. Định nghĩa cấu trúc dữ liệu thích hợp để lưu trữ các giá trị trong tam giác Pascal 
vào trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này hãy trình bày thuật 
toán và viết chương trình thực hiện các công việc sau: 
- In tam giác Pascal có N dòng ra màn hình. 
- In và tính giá trị biểu thức (a+b)N ra màn hình. 
14. Trình bày thuật toán và viết chương trình thực hiện công việc minh họa (Demo) quá 
trình thực hiện tất cả các thuật toán đã học. 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 229 
IV. HƯỚNG DẪN SỬ DỤNG TÀI LIỆU THAM KHẢO 
1. Cấu trúc dữ liệu 
Tác giả: Nguyễn Trung Trực 
Khoa CNTT, trường ĐHBK TP.HCM 
2. Giáo trình Cấu trúc dữ liệu 1 
Tác giả: Trần Hạnh Nhi – Dương Anh Đức 
Khoa CNTT, trường ĐHKHTN – ĐHQG TP.HCM 
3. Algorithms + Data Structures = Programs 
Tác giả: N.Wirth 
NXB: Prentice Hall, 1976 
4. Data Structures and Algorithms 
Tác giả: Alfred V.Aho - John E.Hopcroft – Jeffrey D.Ullman 
NXB: Addison-Wesley Publishing Company 
5. Algorithms (Second Edition) 
Tác giả: Robert Sedgewick 
NXB: Addison-Wesley Publishing Company 
6. Data Structures and Program Design (Third Edition) 
Tác giả: Robert L.Kruse 
NXB: Prentice Hall