TRƯỜNG ĐH SƯ PHẠM TP.HCM
KHOA/TỔ: CNTT/KHMT
Đề chính thức
Đề số 01
(Đề thi gồm có 02 trang)
ĐỀ THI KẾT THÚC HỌC PHẦN
Tên HP: CẤU TRÚC DỮ LIỆU
Mã HP: COMP1016 Số tín chỉ: 03
Học kỳ: 03 Năm học: 2023 - 2024
Ngày thi: ……………………………………………
Thời gian làm bài: 90 phút (không kể thời gian phát đề)
Câu 1 (3 điểm).
a) (0.5 điểm) Hãy cho biết đoạn chương trình bên
phải cài đặt thuật toán sắp xếp nào?
b) (2 điểm) Trình bày từng bước sắp xếp dãy số sau
theo thuật toán đã cài đặt ở trên: 18, 90, 91, 85, 10, 92,
71, 4.
c) (0.5 điểm) Nếu muốn sắp xếp theo thứ tự ngược
lại, ta chỉnh sửa đoạn chương trình bên như thế nào?
1
2
3
4
5
6
7
8
9
10
j=1;
while (j<n){
i=j-1; t=a[j];
while (i>=0 && t<a[i]){
a[i+1]=a[i];
i--;
}
a[i+1]=t;
j++;
}
Câu 2 (3 điểm).
a) (1 điểm) Hãy vẽ cây nhị phân tìm kiếm, sao cho nếu duyệt cây theo thứ tự LRN, anh/chị sẽ thu
được dãy số như sau: 1, 2, 4, 3, 7, 9, 8, 12, 11, 6. Sau khi vẽ, hãy xác định cây có cân bằng hay
không? Vì sao?
b) (1 điểm) Sử dụng cây nhị phân cân bằng (AVL) ở câu a, lần lượt thêm các giá trị 5 và 10 vào cây.
Vẽ lại cây sau mỗi thao tác thêm.
c) (1 điểm) Sử dụng cây nhị phân cân bằng (AVL) ở câu b, lần lượt xóa các giá trị 9 và 7 khỏi cây.
Vẽ lại cây sau mỗi thao tác xóa.
Câu 3: (4 điểm)
Phòng đào tạo cần xây dựng chương trình đăng ký môn học trong 1 học kỳ của sinh viên. Thông tin
cơ bản của môn học được tổ chức theo cấu trúc sau:
class MonHoc
{ string _strMaMH; //mã môn học
string _strTenMH; //tên môn học
int _iSoTC; //số tín chỉ
string _strGioHoc; //giờ học
int _iNgayHoc; //ngày học trong tuần là thông tin cho biết môn học sẽ được học vào thứ
mấy, có giá trị từ 1 (Chủ nhật) đến 7 (thứ Bảy)
MonHoc* _pNext; //con trỏ lưu địa chỉ của môn học tiếp theo
};
class ListMonHoc{
MonHoc* _pHead;
MonHoc* _pTail;
};
Mau KT.ĐT.01
Thông tin về Sinh viên gồm các thuộc tính: mã sinh viên, họ tên, giới tính, ngày sinh, danh sách các
môn học đã đăng ký. Mỗi sinh viên sẽ được phép đăng ký nhiều môn học, nhưng sẽ bị giới hạn bởi số
tín chỉ tối đa và tối thiểu trong 1 học kỳ. Yêu cầu anh/chị hãy:
a) (1 điểm) Xây dựng class SinhVien để lưu trữ thông tin của sinh viên.
b) (1 điểm) Viết hàm đăng ký môn học cho 1 sinh viên là hàm thành phần của class SinhVien. Biết
rằng, số tín chỉ sinh viên được phép đăng ký trong 1 học kỳ là từ 15 đến 28 tín chỉ. Hàm sẽ trả về true
nếu đăng ký thành công, trả về false nếu thất bại. Hàm được mô tả như sau:
bool SinhVien::dangKyMonHoc(MonHoc monHoc);
Trong đó: monHoc là môn học được đăng ký.
c) (1 điểm) Viết hàm tính học phí cho 1 sinh viên là hàm thành phần của class SinhVien. Biết rằng
học phí sẽ được tính theo công thức:
𝐻ọ𝑐 𝑝ℎí = ∑𝑆ố 𝑡í𝑛 𝑐ℎỉ ∗ Đơ𝑛 𝑔𝑖á
với ∑𝑆ố 𝑡í𝑛 𝑐ℎỉ là tổng số tín chỉ sinh viên đã đăng ký trong 1 học kỳ.
Hàm được mô tả như sau:
long SinhVien::tinhHocPhi(int donGia);
Trong đó: donGia là đơn giá của 1 tín chỉ;
d) (1 điểm) Để quản lý lịch học, sinh viên cần phải sắp xếp các môn học đã đăng ký theo thứ tự ngày
giờ học trong tuần. Ví dụ: môn A học lúc 15g thứ Hai, phải đứng trước môn E học lúc 7g thứ Ba. Viết
hàm xếp lịch học là hàm thành phần của lớp SinhVien. Hàm được mô tả như sau:
void SinhVien::xepLichhoc();
Ghi chú: sinh viên có thể bổ sung các hàm hỗ trợ khác cho class MonHoc, ListMH, SinhVien
trong quá trình thực hiện các yêu cầu trên. ----- HẾT -----
Lưu ý:
- Sinh viên chỉ được sử dụng “Giáo trình CTDL – NXB Đại học Sư phạm TPHCM” khi làm bài.
- Cán bộ coi thi không giải thích gì thêm.
- Sinh viên chỉ được sử dụng ngôn ngữ C/C++ khi làm bài.
Không in phần này khi sao in đề thi