138
CHƯƠNG TRÌNH MÔN HỌC
Tên môn học: Cấu trúc dữ liệu và giải thuật
Mã môn học: MH 16
Thời gian thực hiện môn học: 45 giờ; (Lý thuyết: 30 giờ; Thực hành, thảo
luận, thí nghiệm, bài tập: 13 giờ; Kiểm tra: 02 giờ).
I. Vị trí, tính chất của môn học
- Vị trí: Môn học được bố trí sau khi học xong các môn học, mô đun: Tin học,
Lập trình căn bản. Được bố trí giảng dạy cho học sinh cuối năm thứ nhất hoặc đầu
năm thứ hai.
- Tính chất: Là môn học cơ sở.
II. Mục tiêu môn học
- Về kiến thức:
+ Phát biểu được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc
xây dựng chương trình.
+ Trình bày được ý nghĩa, cấu trúc, cách khai báo, các thao tác của các loại cấu
trúc dữ liệu (mảng, danh sách liên kết, cây) và các giải thuật cơ bản xử lý các cấu trúc
dữ liệu đó.
+ Trình bày được các giải thuật sắp xếp.
- Về kỹ năng:
+ Xây dựng được cấu trúc dữ liệu cho một số bài toán ứng dụng cụ thể (Tạo,
hiển thị, tính toán, sắp xếp, tìm kiếm …)
+ Thực hiện cài đặt được một số giải thuật bằng ngôn ngữ lập trình Pascal
hoặc C.
- Về năng lực tự chủ và trách nhiệm
+ Nghiêm túc và tích cực trong việc học lý thuyết và làm bài tập, chủ động
tìm kiếm các nguồn tài liệu liên quan đến môn học.
III. Nội dung môn học:
1. Nội dung tổng quát và phân bổ thời gian:
Thời gian (giờ)
Stt

1

Tên chương, mục

Chương 1: Tổng quan về cấu trúc dữ liệu
và giải thuật. Các biện pháp nhằm bảo vệ
môi trường cơ sở học tập, sản xuất.

Thực
hành, Kiểm
Lý
Tổng
thảo
số thuyết
tra
luận,
bài tập
8

6

2

139

3

4

5

6

1. Tổng quan về cấu trúc dữ liệu và giải
thuật

2

2

2. Phân tích giải thuật

2

1

3. Pháp luật và quy định áp dụng trong lĩnh
vực máy tính và bảo vệ môi trường.

2

2

4. Ý thức và thái độ bảo vệ môi trường khi
làm việc trong xưởng và với máy tính

2

1

1

Chương 2: Các kiểu dữ liệu cơ sở.

4

3

1

1. Các kiểu dữ liệu cơ bản

1

1

2. Kiểu dữ liệu có cấu trúc

3

2

1

Chương 3: Mảng, danh sách và các kiểu
dữ liệu trừu tượng

8

5

3

1. Mảng

4

3

1

2. Danh sách liên kết

2

1

1

3. Các kiểu dữ liệu trừu tượng

2

1

1

Chương 4: Cấu trúc cây

12

8

3

1. Cây và một số phép toán trên cây

4

3

1

2. Phép toán trên cây

4

3

1

3. Cây nhị phân

3

2

1

4. Kiểm tra định kỳ

1

Chương 5: Thuật toán sắp xếp

13

8

1. Sắp xếp đổi chỗ trực tiếp

2

2

2. Sắp xếp chọn

2

2

3. Sắp xếp chèn

2

1

1

4. Sắp xếp nổi bọt

2

1

1

5. Sắp xếp phân đoạn

2

1

1

6. Sắp xếp hòa nhập

2

1

1

7. Kiểm tra định kỳ

1

Tổng cộng

45

1

1

1
4

1

1
30

13

2

* Ghi chú: Số giờ kiểm tra được tính vào giờ thực hành.
2. Nội dung chi tiết:
Chương 1: Tổng quan về cấu trúc dữ liệu và giải thuật. Các biện pháp
nhằm bảo vệ môi trường cơ sở học tập, sản xuất
Thời gian: 08 giờ

140
1. Mục tiêu
- Trình bày được mối quan hệ giữa cấu trúc dữ liệu và giải thuật.
- Trình bày được cách tư duy về tiến trình phân tích và thiết kế thuật toán.
- Đánh giá được độ phức tạp thuật toán.
- Trình bày được các quy định của pháp luật nhà nước về bảo vệ môi trường
đối với người lao động, chủ sử dụng lao động và các cơ quan quản lý liên quan;
- Thực hiện tốt các quy định bảo vệ môi trường tại cơ sở học tập, sản xuất và
kinh doanh;
- Rèn luyện ý thức tự giác trong việc bảo vệ môi trường.
- Có thái độ tích cực, nghiêm túc, cẩn thận trong học tập.
2. Nội dung
2.1. Tổng quan về cấu trúc dữ liệu và giải thuật
2.2. Phân tích giải thuật
2.3. Pháp luật và quy định áp dụng trong lĩnh vực máy tính và bảo vệ môi
trường.
2.4. Ý thức và thái độ bảo vệ môi trường khi làm việc trong xưởng và với
máy tính. Các yếu tố an toàn trong phòng học, nhà xưởng.
Chương 2: Các kiểu dữ liệu cơ sở

Thời gian: 04 giờ

1. Mục tiêu
- Trình bày được khái niệm, phạm vi lưu trữ dữ liệu, các phép xử lý của các
kiểu dữ liệu cơ bản như: kiểu số, chuỗi, logic, tập hợp,...
- Sử dụng được các kiểu dữ liệu bản trong việc mô tả các đối tượng trong các
ngôn ngữ lập trình bậc cao như C, Pascal.
- Nghiêm túc, tỉ mỉ, sáng tạo trong việc học và vận dụng vào làm bài tập.
2. Nội dung
2.1. Các kiểu dữ liệu cơ bản
2.2. Kiểu dữ liệu có cấu trúc
Chương 3: Mảng, danh sách và các kiểu dữ liệu trừu tượng
Thời gian: 08 giờ
1. Mục tiêu
- Trình bày được khái niệm, cấu trúc lưu trữ của dữ liệu kiểu mảng, kiểu danh sách.
- Mô tả được một số phép toán xử lý trên các phần tử của danh sách liên kết.
- Trình bày được cấu trúc, các phép xử lý, khả năng áp dụng của ngăn xếp,
hàng đợi.

141
- Viết được một số giải thuật xử lý các yêu cầu cụ thể trên các kiểu dữ liệu trên.
- Cài đặt được một số thao tác xử lý danh sách liên kết, ngăn xếp, hàng đợi
trên ngôn ngữ C, Pascal.
- Nghiêm túc, tỉ mỉ, sáng tạo trong việc học và vận dụng vào làm bài tập.
2. Nội dung
2.1. Mảng
2.2. Danh sách liên kết
2.3. Các kiểu dữ liệu trừu tượng
Chương 4: Cấu trúc cây

Thời gian: 12 giờ (1 giờ kiểm tra)

1. Mục tiêu
- Trình bày được các khái niệm, cấu trúc lưu trữ, phân loại, cách duyệt cây.
- Mô tả được một số bài toán thực tế có thể vận dụng cấu trúc dữ liệu kiểu cây.
Cài đặt và thực hiện các thao tác trên cây nhị phân.
Nghiêm túc, tỉ mỉ, sáng tạo trong việc học và vận dụng vào làm bài tập.
2. Nội dung
2.1. Cây và một số phép toán trên cây
2.2. Cây và một số phép toán trên cây
2.3. Cây nhị phân
Chương 5: Thuật toán sắp xếp

Thời gian: 13 giờ (1 giờ kiểm tra)

1. Mục tiêu
- Trình bày được tính chất của việc sắp xếp dữ liệu.
- Mô tả được ý tưởng, thuật toán chi tiết của một số phương pháp sắp xếp.
- Áp dụng được một số thuật toán sắp xếp vào thực hiện việc sắp xếp các dãy
khóa cụ thể.
- Cài đặt được các thuật toán sắp xếp trong ngôn ngữ lập trình bậc cao.
- Nghiêm túc, tỉ mỉ, sáng tạo trong việc học và vận dụng vào làm bài tập
2. Nội dung
2.1. Sắp xếp đổi chỗ trực tiếp
2.2. Sắp xếp chọn
2.3. Sắp xếp chèn
2.4. Sắp xếp nổi bọt
2.5. Sắp xếp phân đoạn
2.5. Sắp xếp hòa nhập

142
2.7. Kiểm tra
IV. Điều kiện thực hiện môn học
1. Phòng học chuyên môn hóa, nhà xưởng
1.1. Phòng học chuyên môn Phòng học lý thuyết: trang bị đầy đủ trang thiết
bị cần thiết phục vụ cho giờ học lý thuyết của 35 học sinh.
1.2. Yêu cầu: Sạch sẽ, gọn gàng. 100%. Đảm bảo an toàn cho người học và
thiết bị.
2 . Trang thiết bị máy móc
2.1. Máy chiếu + Phông chiếu
2.2. Yêu cầu: Hoạt động ổn định
3 . Học liệu, dụng cụ, nguyên vật liệu
3.1. Tài liệu môn học Cấu trúc dữ liệu và giải thuật
3.2. Yêu cầu: Giấy A4 1 gram
4 . Các điều kiện khác
4.1. Hệ thống mạng LAN có kết nối Internet
4.2. Yêu cầu: Kết nối tốt
V. Nội dung và phương pháp đánh giá
1. Nội dung
- Kiến thức:
+ Mối quan hệ giữa cấu trúc dữ liệu và giải thuật.
+ Phân tích và thiết kế thuật toán. Đánh giá được độ phức tạp thuật toán.
+ Trình bày được khái niệm, phạm vi lưu trữ dữ liệu, các phép xử lý của các
kiểu dữ liệu cơ bản như: kiểu số, chuỗi, logic, tập hợp,...
+ Cấu trúc lưu trữ của dữ liệu kiểu mảng, kiểu danh sách.
+ Cây và một số phép toán trên cây. Cây nhị phân
+ Sắp xếp đổi chỗ trực tiếp, chọn, chèn, nổi bọt, phân đoạn, hoà nhập
- Kỹ năng:
+ Thực hiện được cấu trúc, các phép xử lý, khả năng áp dụng của ngăn xếp,
hàng đợi.
+ Sử dụng được các kiểu dữ liệu cơ bản trong việc mô tả các đối tượng trong
các ngôn ngữ lập trình bậc cao như C, Pascal.
- Năng lực và tự chủ trách nhiệm:
+ Tuân thủ các quy định về an toàn, môi trường và phòng cháy, chữa cháy
+ Không nói chuyện và thảo luận trong quá trình thi

143
+ Tuân thủ các yêu cầu/hướng dẫn của đề thi
+ Tuân thủ theo những yêu cầu và hướng dẫn của giảng viên.
2. Phương pháp: Việc đánh giá kết quả học tập của người học được thực hiện
thông qua các bài kiểm tra thường xuyên, bài kiểm tra định kỳ, thi kết thúc môn
học.
2.1. Kiểm tra thường xuyên: 02 bài.
Hình thức kiểm tra: Thực hành.
2.2. Kiểm tra định kỳ: 02 bài.
Hình thức kiểm tra: Thực hành
2.3. Thi kết thúc môn học: 01 bài
Hình thức thi: Thực hành
VI. Hướng dẫn thực hiện môn học
1. Phạm vi áp dụng môn học: môn học được sử dụng để giảng dạy cho trình
độ trung cấp.
2. Hướng dẫn về phương pháp giảng dạy, học tập môn học:
- Đối với giảng viên:
+ Giới thiệu cấu trúc lưu trữ của dữ liệu kiểu mảng, kiểu danh sách, khả năng
áp dụng của ngăn xếp, hàng đợi.
+ Hướng dẫn cài đặt và thực hiện các thao tác trên cây nhị phân.
+ Hướng dẫn viết một số giải thuật đơn giản. Nhận xét, đánh giá.
- Đối với người học:
+ Học sinh cần đọc trước tài liệu lý thuyết trước khi lên lớp. Trong quá trình
học tập cần chủ động lắng nghe, mạnh dạn phát biểu.
+ Tiếp nhận khái niệm, phạm vi lưu trữ dữ liệu, các phép xử lý của các kiểu
dữ liệu cơ bản
+ Thực hành sử dụng các kiểu dữ liệu theo nhóm được phân công
+ Trong quá trình học cần rèn luyện thái độ chủ động, năng lực tự chủ, tự chịu
trách nhiệm khi thực hiện nhiệm vụ hoc tập.
+ Phát biểu được các khái niệm, cấu trúc, phân loại và cách duyệt cây.
+ Cài đặt và duyệt cây theo yêu cầu. Tích cực tự đọc các tài liệu liên quan.
3. Những trọng tâm cần chú ý
+ Các kiểu dữ liệu cơ sở
+ Mảng, danh sách
+ Cấu trúc cây nhị phân

144
+ Mô tả và áp dụng được các thuật toán
+ Tuân thủ quy tắc sức khỏe, an toàn và bảo vệ môi trường trong suốt bài thi.
+ Giảng viên cho dừng bài thi ngay nếu sinh viên không tuân thủ toàn bộ quy
tắc an toàn. Khi đó sinh viên sẽ bị đánh giá không đạt.
4. Tài liệu tham khảo
[1]. Cấu trúc dữ liệu và thuật toán, Hoàng Nghĩa Tý, NXB Xây dựng, 2000.
[2]. Cấu trúc dữ liệu và thuật toán, Đỗ Xuân Lôi, NXB ĐH Quốc gia Hà Nội,
2002.
[3]. Cấu trúc dữ liệu và giải thuật, An Văn Minh, Trần Hùng Cường,
KH&KT, 2013.
5. Ghi chú và giải thích (nếu có): Số lượng bài kiểm tra thường xuyên ở mục
2 của phần V được quy định theo quy chế tổ chức đào tạo trình độ trung cấp, trình
độ cao đẳng theo niên chế trong hoạt động giáo dục nghề nghiệp được ban hành
kèm theo Quyết định số 208/QĐ-CĐCĐ ngày 13/7/2022 của Hiệu trưởng Trường
Cao đẳng Cộng đồng Lai Châu. Khi Quy chế đào tạo điều chỉnh thì số lượng bài
kiểm tra thường xuyên sẽ áp dụng theo quy chế mới.