Bài tập thực hành cấu trúc dữ liệu và giải thuật

 tìm là Khuong, hiển thị toàn bộ sinh viên chứa tên Khuong) 
• Hiển thị danh sách sinh viên yếu (có ñiểm trung bình <=4) 
• Hiển thị danh sách sinh viên giỏi (có ñiểm trung bình >=8 và không có môn học nào 
<=6) 
• Sắp xếp danh sách tăng dần theo mã sinh viên 
• Sắp xếp danh sách tăng dần theo ñiểm trung bình 
• Sắp xếp danh sách tăng dần theo từng lớp, trong mỗi lớp tăng dần theo ñiểm trung bình 
• Sắp xếp danh sách tăng dần theo từng lớp, trong mỗi lớp giảm dần theo ñiểm trung bình 
• Sắp xếp danh sách tăng dần theo ñiểm toán, rồi ñến ñiểm lý, rồi ñến ñiểm hóa. 
• Nhập một lớp. Hủy toàn bộ các sinh viên thuộc về lớp ñó. 
• Hủy tất cả sinh viên có học lực kém (ñiểm trung bình <=3). 
• Sắp xếp danh sách tăng dần theo mã sinh viên. Sau ñó, khi thêm một sinh viên mới vào, 
chèn sinh viên này vào ñúng vị trí sao cho danh sách sinh viên vẫn thỏa ñiều kiện tăng 
dần theo mã. 
• Hủy tòan bộ danh sách 
• Lưu trữ danh sách sinh viên này vào file text 
• Nạp danh sách sinh viên từ file text. 
Faculty of Information Technology
Bài Tập Thực Hành CTDL> 
Trang 8/12 
Module 7 
Bài 1 
Sử dụng danh sách liên kết ñơn tạo stack. Mỗi thành phần của stack gồm 2 thông tin: Tên Lớp, sĩ số học 
sinh. Hệ thống menu gồm các mục 
 +Lưu stack hiện tại vào file 
+Push phần tử mới (lớp mới) vào stack 
+Pop phần tử vào stack 
+HIển thị danh sách của stack 
+Nạp stack từ file 
Lưu ý: 
+Mỗi khi Push một lớp vào stack, nếu tên lớp ñó chưa có, chương trình phải tạo phần tử mới. 
+Nếu lớp ñó ñã tồn tại thì không thêm lớp mới, mà chỉ cập nhật thêm sĩ số sinh viên (cộng dồn 
số lượng sinh viên mới vào sĩ số hiện tại). 
Bài 2 
Sử dụng danh sách liên kết ñôi ñể quản lý khách hàng cho một nhà ga.. Mỗi thành phần thông tin lưu trữ 
cho khách hàng gồm: số CMND khác hàng (10 ký tự), Tên khách hàng, Ga ñến, giá tiền. 
Hệ thống menu gồm các mục: 
 +Nạp danh sách từ file 
+Thêm một khách hàng mới vào hàng ñợi mua vé. 
+Bán một vé cho khách hàng. Chỉ bán cho người ñăng ký trước. 
+Hiển thị danh sách khách hàng. 
+Hủy một khách hàng ra khỏi danh sách. (khách hàng không mua vé nữa). 
+Thống kê tình hình bán vé 
+Lưu danh sách vào file 
+Hiển thị danh sách các ga ñang chờ mua vé. 
+Hiển thị danh sách các ga ñang chờ mua vé và số vé tương ứng cho ga. 
Lưu ý: 
+Số khách hàng trong danh sách hiện tại là số khách ñang chờ, nhưng chưa có vé. Khi một 
khách hàng ñã mua vé, thì loại khách hàng này ra khỏi danh sách chờ mua vé. 
+Việc mua vé phải có thứ tự: ai vào trước thì mua vé trước (FIFO). 
+Mỗi khi khách hàng mua ñược vé phải lưu lại khách hàng này ñể dùng cho việc thống kê. 
+Mỗi khi thêm một khác hàng mới, nếu Số CMND khách hàng ñã có thì không tạo phần tử mới 
mà chỉ cập nhật lại ga và giá tiền ñến cho khác hàng ñó. 
+Mục thống kê tình hình: cho biết còn bao nhiêu khách hàng chờ nhận vé, bao nhiêu khách hàng 
ñã nhận vé, tổng số tiền ñã thu về là bao nhiêu. 
+Việc lưu danh sách: chỉ lưu các khách hàng chờ mua vé. Các khách hàng ñã nhận vé xem như 
kết sổ trong ngày không cần lưu lại. 
+Khi chương trình vừa ñược chạy, lập tức tự ñộng nạp toàn bộ danh sách khách hàng từ file 
(cách khách hàng chưa có vé). 
+Khi hiển thị danh sách các ga ñến ñang chờ mua vé, chỉ hiển thị tên ga ñó một lần. (Ví dụ: giả 
sử 10 khách hàng nhưng ñăng ký ñi ñến 2 ga, thì chỉ hiển thị 2 hàng). 
Faculty of Information Technology
 Bài Tập Thực Hành CTDL> 
Trang 9/12 
Module 8 
Bài 1 
Viết chương trình xây dựng và quản lý cây nhị phân tìm kiếm (Binary Search Tree). Hiển thị menu thực 
hiện các chức năng sau (mỗi chức năng thực hiện bằng hàm). Thành phần dữ liệu trong mỗi Node là giá 
trị kiểu integer. 
• Thêm một node vào cây (giá trị nhập vào). Nếu node này ñã có giá trị thì thông báo 
không thêm vào node ñã có. 
• Tìm giá trị trung bình của danh sách 
• Xuất danh sách. Khi menu này ñược chọn, hiển thị menu con cho phép chọn lựa 
o Xuất danh sách theo thứ tự preorder 
o Xuất danh sách theo thứ tự inorder 
o Xuất danh sách theo thứ tự postorder 
Bài 2 
Sử dụng bài tập ở câu trên tiếp tục phát triển rộng các menu như sau. 
• Lưu tòan bộ cây xuống file 
• Nạp cây từ file 
• Tính số lượng node của tree 
• Tính chiều cao của cây 
• Tìm giá trị nhỏ nhất 
• Tìm giá trị lớn nhất 
• Tìm một node theo giá trị nhập vào 
• Hiển thị giá trị tăng dần toàn bộ cây 
• Thống kê số lượng node: là số chẵn, là số lẻm là số nguyên tố 
Chú ý: Khi người sử dụng thêm 1 node, chương trình phải tự ñộng lưu xuống file ngay lập tức 
Khi chương trình vừa khởi ñộng, lập tức nạp hiển thị tree ra màn hình 
Bài 3 
Viết chương trình xây dựng và quản lý danh sách sinh viên dựa trên cây nhị phân tìm kiếm (Binary 
Search Tree). Mỗi sinh viên chứa các thông tin: mã sv (char), tên sv (char), ñiểm tóan, ñiểm lý, ñiểm hóa. 
Hiển thị menu thực hiện các chức năng sau (mỗi chức năng thực hiện bằng hàm). Lập chỉ mục Index cho 
cơ sở dữ liệu theo mã sinh viên. Không có 2 sinh viên nào trùng mã với nhau. 
• Thêm một SV mới 
• Xuất danh sách SV tăng dần theo mã SV 
• Tìm 1 SV theo mã. Nếu tìm ra hiển thị menu con chứa các mục 
o Hiển thị thông tin sinh viên: tên, các ñiểm và ñiểm trung bình 
o Cập nhật (sửa) thông tin SV (tên, ñiểm tóan, ñiểm lý) 
• Lưu danh sách sinh viên xuống file 
• ðọc danh sách sinh viên từ file 
• Xuất danh sách sinh viên tăng dần theo tên SV. 
Faculty of Information Technology
Bài Tập Thực Hành CTDL> 
Trang 10/12 
Module 9 
Bài 1 
Viết chương trình xây dựng và quản lý cây nhị phân tìm kiếm (Binary Search Tree). Hiển thị menu thực 
hiện các chức năng sau (mỗi chức năng thực hiện bằng hàm). Thành phần dữ liệu trong mỗi Node là giá 
trị kiểu integer. 
• Thêm một node vào cây (giá trị nhập vào). 
• Lưu cây vào file 
• ðọc cây từ file 
• Xuất danh sách 
o Inorder 
o Preorder 
• Tìm một node trên cây 
• Hủy một node trên cây. (chọn node trái cùng nhánh bên phải) 
• Hủy một node trên cây. (chọn node phải cùng nhánh bên phải) 
Lưu ý: sinh viên vẽ trên giấy cây nhị phân, ñồng thời với việc thực thi chương trình cho các thao tác xóa-
thêm node và kiểm tra ñối chiếu kết quả chương trình với trên giấy. 
Bài 2 
Sử dụng bài tập ở câu trên tiếp tục phát triển rộng các menu như sau. (Chú ý: các chức năng thực hiện 
bằng hàm, không sử dụng biến tòan cục. Sử dụng kỹ thuật ñệ quy): 
• ðếm số node của cây. 
• ðếm số lnode lá của cây 
• ðếm số node có ñầy ñủ 2 con 
• ðếm số node chỉ có 1 con 
• ðếm số node có giá trị chẵn 
• ðếm số node có giá trị lẽ 
• Tính tổng giá trị các node 
• Tìm giá trị trung bình của danh sách 
• Tìm chiều cao của cây 
• Tính giá trị trung bình của các node 
• Tìm giá trị nhỏ nhất 
• Tìm giá trị lớn nhất 
• Tìm một node theo giá trị nhập vào 
• Tìm cấp (level) của một node theo giá trị nhập vào 
• Hủy tòan bộ cây. 
• (*) Xuất ra ñường ñi từ root ñến 1 node bất kỳ (giá trị nhập vào) 
• (*) Tìm ñường ñi giữa 2 node bất kỳ (với 2 giá trị nhập vào) 
• (*) Kiểm tra 2 node bất kỳ có quan hệ tổ tiên hay không? (với 2 giá trị nhập vào) 
• (*) Xuất ra ñường ñi giữa 2 node bất kỳ (với 2 giá trị nhập vào) 
Faculty of Information Technology
Bài Tập Thực Hành CTDL> 
Trang 11/12 
Module 10 
Bài 1 
Viết chương trình quản lý danh sách lớp. Mỗi sinh viên gồm các thành phần: 
+Mã SV: char[10]; 
+Mã Lớp : int 
+Tên SV: char[255]; 
+DiemToan 
+DiemLy 
+DiemHoa 
Mỗi lớp chứa gồm các thông tin: 
 +Mã Lớp: int 
 +Tên Lớp: char[10]; 
 +Khóa 
Thành phần khóa chính (và Index) của danh sách sinh viên chính là mã SV. Thành phần khóa chính (và 
Index) của danh sách lớp chính là mã lớp. 
Xây dựng và quản lý danh sách lớp sử dụng cây nhị phân tìm kiếm (Binary Search Tree). Hiển thị menu 
thực hiện các chức năng sau (mỗi chức năng thực hiện bằng hàm). Thành phần dữ liệu trong mỗi Node 
là giá trị kiểu integer. 
1. Thêm 1 lớp mới. 
2. Thêm một sinh viên 
a. Nếu mã SV ñã có thì hiển thị sinh viên ñó ra màn hình, cùng với thông báo không thể 
nhập sinh viên ñã có 
b. Mã lớp phải tồn tại trong danh sách lớp. Nếu chưa có, phải hiện thông báo lỗi. 
3. Tìm một sinh viên theo mã SV 
a. Khi tìm thấy, hiển thị mã, tên, ñiểm, mã lớp và tên lớp. 
4. Lưu danh sách sinh viên-lớp vào file 
5. ðọc danh sách sinh viện từ file. 
6. Hiển thị danh sách sinh viên 
a. Tăng dần theo mã SV 
b. Giảm dần theo mã SV 
c. Mỗi sinh viên hiển thị ñiểm toán, lý, hóa và ñiểm trung bình 
7. Tìm tất cả sinh viên theo tên nhập vào 
8. Hiển thị tất cả sinh viên theo mã lớp nhập vào 
9. Hiển thị tất cả sinh viên theo tên lớp nhập vào 
10. Xóa một sinh viên ra khỏi danh sách 
11. Xóa một lớp ra khỏi danh sách 
12. Tìm tất cả sinh viên có ñiểm trung bình lớn nhất 
13. Tìm tất cả sinh viên có ñiểm trung bình lớn nhất trong một lớp 
Chú ý: Sinh viên sử dụng 2 cây nhị phân, một cho danh sách lớp, một cho danh sách sinh viên. 
ðể ñơn giản, có thể lưu thành 2 file riêng cho danh sách lớp và danh sách sinh viên. 
Lưu ý: Mỗi một thao tác thêm sinh viên, xóa sinh viên: chương trình tự ñộng lưu vào file. Lần thực thi kế 
tiếp, chương trình tự ñộng nạp từ file vào bộ nhớ. 
Faculty of Information Technology
Bài Tập Thực Hành CTDL> 
Trang 12/12 
Module 11 
Bài 1 
Viết chương trình quản lý danh sách lớp. Mỗi sinh viên gồm các thành phần: 
+Mã SV, Tên SV: char[255], DiemTB 
Mỗi lớp gồm các thông tin: 
 +Mã Lớp: int 
 +Tên Lớp: char[10]; 
Mỗi lớp có nhiều Sinh viên. 
Sử dụng các cấu trúc dữ liệu sau. Mỗi trường hợp thực hiện 3 chức năng: thêm lớp, thêm sinh viên, tìm 
tất cả sinh viên của 1 lớp. 
Bài 2 
Viết chương trình quản lý danh sách mua vé máy bay – hành khách. Mỗi khách chỉ mua 1 vé. Mỗi vé 
máy bay gồm các thành phần: Vé máy bay (ID,giá) 
Mỗi hành khách gồm các thông tin: Khách(PassID, ten) 
Sử dụng các cấu trúc dữ liệu sau. Thực hiện menu với 3 chức năng: thêm vé máy bay, thêm hành khách, 
bán 1 vé máy bay (vé chưa bán) cho 1 hành khách (chưa mua vé). Khi bán vé, người sử dụng nhập ID 
của vé và PassID của hành khách. 
Faculty of Information Technology