Đề cương chi tiết học phần Cấu trúc dữ liệu và giải thuật (Data structures and algorithms)

1 
TRƯỜNG ĐH NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM 
Độc lập – Tự do – Hạnh Phúc 
ĐỀ CƯƠNG CHI TIẾT HỌC PHẦN 
1. Thông tin chung về học phần 
 Tên học phần: Cấu trúc dữ liệu và giải thuật (Data structures and algorithms) 
 Mã học phần: 4021014 
 Số tín chỉ: 4 (3+1) tín chỉ 
 Thuộc chương trình đào tạo của bậc, ngành: Cao đẳng, ngành Công nghệ thông tin 
 Số tiết học phần: 
 Nghe giảng lý thuyết : 30 tiết 
 Làm bài tập trên lớp : 10 tiết 
 Thảo luận : 0 tiết 
 Thực hành, thực tập : 30 tiết 
 Hoạt động theo nhóm : 5 tiết 
 Thực tế : 0 tiết 
 Tự học : 120 tiết 
 Đơn vị phụ trách: Bộ môn Khoa học máy tính, Khoa Công nghệ thông tin 
2. Học phần trước: Nhập môn lập trình. 
3. Mục tiêu của học phần 
 Hiểu được tầm quan trọng của giải thuật và cách tổ chức dữ liệu. 
 Khai thác được các cấu trúc dữ liệu phức tạp. 
4. Chuẩn đầu ra của học phần 
Nội dung 
Đáp ứng 
CĐR 
CTĐT 
Kiến thức 4.1.1. Trình bày được tầm quan trọng của giải thuật và cách tổ 
chức dữ liệu – hai thành phần quan trọng nhất của một chương 
trình lập cho máy tính.
K1 
BM01.QT02/ĐNT-ĐT 
2 
4.1.2. Thiết kế các thuật toán cơ bản trong lập trình (ý tưởng, 
cài đặt, đánh giá thuật toán, đặc biệt là các thuật toán sắp xếp và 
tìm kiếm, các thuật toán trên cây).
K2 
4.1.3. Áp dụng các thuật toán cơ bản trong lập trình (ý tưởng, 
cài đặt, đánh giá thuật toán, đặc biệt là các thuật toán sắp xếp và 
tìm kiếm, các thuật toán trên cây) để giải quyết một số bài toán 
cho máy tính. 
Phân tích bài toán thực tế, chọn CTDL và giải thuật để giải 
quyết. 
Phân tích và đánh giá độ phức tạp của CTDL và giải thuật được 
chọn cho bài toán cụ thể. 
K3 
Kỹ năng 4.2.1. Có khả năng tư duy logic về cách tổ chức, áp dụng các 
cấu trúc dữ liệu thích hợp vào các bài toán lập trình cụ thể. 
S1 
4.2.2. Có khả năng sử dụng ngôn ngữ lập trình C/C++ để cài đặt 
các cấu trúc dữ liệu cụ thể. 
S2 
4.2.3. Có khả năng xây dựng một chương trình thực hiện một 
CTDL cụ thể cùng với thuật toán tương ứng để giải quyết một 
bài toán cụ thể. 
S3 
Thái độ 4.3.1. Có thái độ làm việc khoa học, trung thực, rõ ràng. A1 
4.3.2. Chuẩn bị bài trước khi đến lớp. Đi học đầy đủ. Tham gia 
tích cực trong giờ học.
A2,A3 
4.3.3. Làm tất cả các bài tập lý thuyết và thực hành. A3 
5. Mô tả tóm tắt nội dung học phần 
 Vai trò của cấu trúc dữ liệu và giải thuật trong cuộc sống và phương thức đánh giá 
các cấu trúc và giải thuật. 
 Tìm hiểu, phân tích và đánh giá các giải thuật tìm kiếm và sắp xếp nội. 
 Tìm hiểu, phân tích và đánh giá các kiểu danh sách lưu trữ nhiều phần tử, các kiểu 
danh sách đặc biệt và các bài toán ứng dụng. 
 Tìm hiểu, phân tích, đánh giá và xây dựng các cấu trúc cây lý thuyết như cây nhị 
phân tìm kiếm, cây cân bằng AVL. 
3 
6. Nội dung và lịch trình giảng dạy 
6.1. Lý thuyết 
Buổi/ 
Tiết Nội dung 
Hoạt động của 
giảng viên 
Hoạt động của 
sinh viên 
Giáo trình 
chính 
Tài liệu tham 
khảo 
Ghi chú 
1 Chương 1: Tổng quan về CTDL 
1.1. Vai trò của CTDL 
1.2. Mối quan hệ giữa CTDL và giải 
thuật 
1.3. Các tiêu chuẩn để đánh giá CTDL 
1.4. Một số kiểu dữ liệu cơ bản 
1.5. Kiểu dữ liệu trừu tượng 
- Giới thiệu môn 
học 
- Tổ chức lớp 
- Hướng dẫn học 
tập học phần 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Làm bài tập 
[1]: Chương Mở 
đầu 
[2]: Chương 1 
[3]: Chương 2 
4.1.1, 4.3.1, 
4.3.2, 4.3.3 
2 Chương 1: Tổng quan về CTDL 
1.6. Đánh giá độ phức tạp của giải thuật - Thuyết giảng - Hướng dẫn bài 
tập 
- Nghe giảng, 
- Làm bài tập 
[1]: Chương Mở 
đầu 
[2]: Chương 1 
4.1.1, 4.3.1, 
4.3.2, 4.3.3 
3 Chương 2: Tìm kiếm và sắp xếp 
2.1. Vai trò của tìm kiếm và sắp xếp dữ 
liệu trong hệ thống thông tin 
2.2. Các giải thuật tìm kiếm nội 
2.2.1 Tìm kiếm tuyến tính 
2.2.2 Tìm kiếm nhị phân 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 7 
4.1.1, 4.1.2, 
4.2.1 
4 Chương 2: Tìm kiếm và sắp xếp 
2.3. Các giải thuật sắp xếp nội 
2.3.1 Định nghĩa bài toán sắp xếp 
2.3.2 Các phương pháp sắp xếp 
thông dụng: đổi chỗ trực tiếp, nổi bọt, 
Shaker sort, Quick Sort 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
[1]: Chương 7 [2]: Chương 2 
4.1.1, 4.1.2, 
4.2.1 
4 
nhân 
5 Chương 2: Tìm kiếm và sắp xếp 
2.3. Các giải thuật sắp xếp nội 
2.3.2 Các phương pháp sắp xếp 
thông dụng: chọn trực tiếp, Heap Sort 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 7 [2]: Chương 2 
4.1.1, 4.1.2, 
4.2.1 
6 Chương 2: Tìm kiếm và sắp xếp 
2.3. Các giải thuật sắp xếp nội 
2.3.2 Các phương pháp sắp xếp 
thông dụng: chèn trực tiếp, Shell Sort 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 7 [2]: Chương 2 
4.1.1, 4.1.2, 
4.2.1 
7 Chương 2: Tìm kiếm và sắp xếp 
2.3. Các giải thuật sắp xếp nội 
2.3.2 Các phương pháp sắp xếp 
thông dụng: Merge Sort, Radix Sort 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 7 [2]: Chương 2 
4.1.1, 4.1.2, 
4.2.1 
8 Chương 3: Danh sách 
3.1 Định nghĩa 
3.2 Phân loại 
3.3 Danh sách đặc 
3.4 Danh sách liên kết 
3.4.1 Định nghĩa 
3.4.2 Danh sách liên kết đơn 
3.4.3 Danh sách liên kết kép 
3.4.4 Danh sách liên kết có thứ tự 
3.4.5 Danh sách vòng 
3.4.6 Danh sách có nhiều mối liên kết 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 4, 
Chương 5 
[2]: Chương 3 
4.1.1, 4.1.2, 
4.2.1 
5 
9 Chương 3: Danh sách 
3.5 Các cấu trúc đặc biệt của danh sách 
3.5.1 Stack 
3.5.1 Queue 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 2, 
Chương 3 
[2]: Chương 3 
4.1.1, 4.1.2, 
4.2.1 
10 Chương 3: Danh sách 
3.5 Các cấu trúc đặc biệt của danh sách 
3.5.3 Các ứng dụng: tính biểu thức, 
khử đệ quy 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 1, 
Chương 2 
[2]: Chương 3 4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.2.3, 
4.3.2 
11 Chương 4: Cấu trúc cây 
4.1 Các khái niệm cơ bản 
4.2 Cách biểu diễn cây 
4.3 Cây nhị phân 
4.3.1 Một số tính chất của cây nhị 
phân 
4.3.2 Duyệt cây nhị phân 
4.4 Cây nhị phân tìm kiếm 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 6 [2]: Chương 4 4.1.1, 4.1.2, 
4.2.1 
12 Chương 4: Cấu trúc cây 
4.5 Cây AVL 
4.5.1 Cấu trúc 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 6 [2]: Chương 4 4.1.1, 4.1.2, 
4.2.1 
13 Chương 4: Cấu trúc cây 
4.5 Cây AVL 
4.5.2 Xây dựng 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
[1]: Chương 6 [2]: Chương 4 4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.2.3, 
6 
nhóm 
- Làm bài tập cá 
nhân 
4.3.2 
14 Chương 4: Cấu trúc cây 
4.5 Cây AVL 
4.5.2 Xây dựng 
- Thuyết giảng 
- Hướng dẫn bài 
tập 
- Nghe giảng, 
- Thảo luận, 
- Làm bài tập 
nhóm 
- Làm bài tập cá 
nhân 
[1]: Chương 6 [2]: Chương 4 4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.2.3, 
4.3.2 
15 Ôn tập - Thuyết giảng - Nghe giảng 4.3.1 
6.2. Thực hành 
Buổi/ 
Tiết Nội dung Hoạt động của giảng viên 
Hoạt động của sinh 
viên 
Giáo trình 
chính 
Tài liệu tham 
khảo 
Ghi chú 
1 Bài 1-4: Tìm kiếm tuyến tính - Hướng dẫn làm bài tập 
- Hướng dẫn cách nộp bài 
- Sửa lỗi lập trình cho SV 
- Thực hành viết các 
chương trình theo yêu 
cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.3.1, 
4.3.3 
2 Bài 5-9: Tìm kiếm nhị phân, 
Bubblesort - Hướng dẫn làm bài tập - Hướng dẫn cách nộp bài 
- Sửa lỗi lập trình cho SV 
- Thực hành viết các 
chương trình theo yêu 
cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.3.1, 
4.3.3 
3 Bài 11-13: Quicksort - Sửa lỗi lập trình cho SV - Viết các chương trình 
theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.3, 
4.2.1, 4.2.2, 
4.3.1, 4.3.3 
7 
4 Bài 14,15: selection sort, heap 
sort, insertion sort - Sửa lỗi lập trình cho SV - Viết các chương trình theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.3, 
4.2.1, 4.2.2, 
4.3.1, 4.3.3 
5 Bài 16,17: shell sort, merge sort - Sửa lỗi lập trình cho SV - Viết các chương trình 
theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.3, 
4.2.1, 4.2.2, 
4.3.1, 4.3.3 
6 Bài 18,19: Danh sách kề - Sửa lỗi lập trình cho SV - Viết các chương trình 
theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.3.1, 
4.3.3 
7 Bài 20-22: Danh sách liên kết - Sửa lỗi lập trình cho SV - Viết các chương trình 
theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.1, 4.1.2, 
4.1.3, 4.2.1, 
4.2.2, 4.3.1, 
4.3.3 
9 Bài 23,24: Stack và bài toán biểu 
thức - Sửa lỗi lập trình cho SV - Viết các chương trình theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.2, 4.1.3, 
4.2.1, 4.2.2, 
4.3.1, 4.3.3 
10 Bài 25: Cây AVL - Sửa lỗi lập trình cho SV - Viết các chương trình 
theo yêu cầu bài tập 
 [2] Danh sách 
bài tập 
4.1.2, 4.1.3, 
4.2.1, 4.2.2, 
4.3.1, 4.3.3 
8 
7. Nhiệm vụ của sinh viên 
 Yêu cầu chung 
 Về kiến thức nền tảng: sinh viên nắm vững các nguyên lý cơ sở lập trình để có nền 
tảng để tiếp tục nghiên cứu học phần này. 
 Về nghiên cứu tài liệu: sinh viên đọc các tài liệu liên quan đến môn học theo sự 
hướng dẫn của giảng viên. 
 Về thực hành: sinh viên tham gia đầy đủ các buổi thực hành và thực hiện hoàn thành 
các bài toán được giao. 
 Về nghiên cứu xử lý tình huống, làm bài tập: sinh viên phải hoàn thành đầy đủ các 
bài tập cá nhân và bài tập nhóm. 
 Về thái độ học tập, sự chuyên cần: sinh viên tham gia đầy đủ và đúng giờ các hoạt 
động của lớp. 
 Về việc tự học: sinh viên phải thực hiện việc tự học theo kế hoạch của giảng viên. 
 Quy định về hành vi trong lớp học 
 Khóa học được thực hiện trên nguyên tắc tôn trọng người học và người dạy. Mọi 
hành vi làm ảnh hưởng đến quá trình dạy và học đều bị nghiêm cấm. 
 Sinh viên phải đi học đúng giờ quy định. Sinh viên đi trễ quá 5 phút sau khi giờ học 
bắt đầu sẽ không được điểm danh tham dự buổi học. 
 Tuyệt đối không làm ồn, gây ảnh hưởng đến người khác trong quá trình học. 
 Tuyệt đối không được ăn, uống, nhai kẹo cao su, sử dụng các thiết bị như điện thoại, 
máy nghe nhạc trong giờ học. 
 Máy tính xách tay, máy tính bảng chỉ được thực hiện vào mục đích ghi chép bài 
giảng, tính toán phục vụ bài giảng, bài tập, tuyệt đối không dùng vào việc khác. 
 Sinh viên vi phạm các nguyên tắc trên sẽ bị mời ra khỏi lớp và bị coi là vắng buổi 
học đó. 
8. Đánh giá kết quả học tập của sinh viên 
8.1. Cách đánh giá 
TT Điểm thành phần Quy định Trọng số Mục tiêu 
1 Điểm thi giữa kỳ - Tham gia học lý thuyết 
- Tham gia học thực hành 
- Nộp bài tập thực hành 
- Làm bài tập nhóm 
- Làm bài tập cá nhân
5% 
5% 
10% 
5% 
5% 
4.1.2, 4.1.3, 
4.2.1, 4.2.2, 
4.2.3, 4.3.1, 
4.3.2, 4.3.3 
2 Điểm thi kết thúc 
học phần 
Thi viết 90 phút 70% 4.1.1, 4.1.2, 
4.2.1, 4.2.2, 
4.3.1 
9 
8.2. Cách tính điểm 
 Điểm đánh giá thành phần và điểm thi kết thúc học phần được chấm theo thang điểm 
10 (từ 0 đến 10), làm tròn đến 0.5. 
 Điểm học phần là tổng điểm của tất cả các điểm đánh giá thành phần của học phần 
nhân với trọng số tương ứng. Điểm học phần theo thang điểm 10 làm tròn đến một 
chữ số thập phân. 
9. Tài liệu học tập 
9.1. Giáo trình chính 
[1] Nguyễn Hồng Chương, “Cấu trúc dữ liệu - Ứng dụng và cài đặt bằng C”, NXB TPHCM, 
2003 
9.2. Tài liệu tham khảo 
 [2] Trần Hạnh Nhi, Dương Anh Đức, “Nhập môn cấu trúc dữ liệu và thuật toán”, ĐH Quốc 
gia TPHCM, 2003. 
 [3] Kurt Mehlhorn and Peter Sanders, “Algorithms and Data Structures – The Basic 
Toolbox”, Springer, 2007. Free Ebook - 
data-structures-the-basic-toolbox-t871.html 
10. Hướng dẫn sinh viên tự học 
10.1. Lý thuyết 
Theo nội dung phần 6. Nội dung và lịch trình giảng dạy, thực hiện theo thời gian những 
việc sau: 
 Đọc tài liệu phần nội dung tương ứng trong tài liệu chính và tài liệu tham khảo. 
 Ghi chú lại mục đích, ý tưởng, tính chất, độ phức tạp của các cấu trúc và giải thuật 
tương ứng. 
 Sau khi học trên lớp, thực hiện nhiều lần giải thuật bằng tay với nhiều ví dụ và so 
sánh kết quả làm bằng tay với giải thuật đã cài đặt để nắm rõ hoạt động của giải 
thuật. 
 Tìm kiếm thêm tài liệu khác trên internet với từ khóa là tên của giải thuật, tên của 
cấu trúc để hiểu sâu hơn về cấu trúc/giải thuật. 
10.2. Thực hành 
 Làm trước ít nhất 2/3 các yêu cầu về bài tập thực hành ở nhà. Tạm ghi chú các điểm 
bị lỗi, các điểm chưa hiểu lại để xử lý sau. 
10 
 Hoàn thiện bài thực hành ở trên lớp thực hành thông qua hỏi đáp với giảng viên 
hướng dẫn. 
 Nộp bài thực hành đã hoàn thiện cho giảng viên hướng dẫn. 
Ngày  tháng  năm 2015 
Trưởng khoa 
(Ký và ghi rõ họ tên) 
Ngày  tháng  năm 2015 
Tổ trưởng Bộ môn 
(Ký và ghi rõ họ tên)
Ngày  tháng  năm 2015 
Người biên soạn 
(Ký và ghi rõ họ tên)
Đinh Hùng 
ThS. Phạm Minh Dũng 
 Ngày  tháng  năm 2015 
Ban giám hiệu