TRƯỜNG ĐH SƯ PHẠM TP.HCM
KHOA/TỔ: CNTT/KHMT
Đề chính thức
Đề số 01
(Đề thi gồm có 03 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: 2022 - 2023
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) (1.5 đ) Hãy cho biết hàm bên cạnh
thực hiện chức năng gì?
Hãy cho biết thuật toán được sử
dụng trong hàm và trình bày ý tưởng
của thuật toán đó.
b) (1.5 đ) Cho dãy số a như sau:
30, 37, 91, 61, 56, 42, 42, 69, 15, 47
Hãy trình bày từng bước sắp xếp dãy
số a khi gọi hàm func(a,10,1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void func(int a[], int n, int f) {
int i = 0;
while (i < n - 1) {
int j = i + 1;
while (j < n) {
if (f == 0) {
if (a[j] < a[i])
swap(a[i], a[j]);
j++;
}
else {
if (a[j] > a[i])
swap(a[i], a[j]);
j++;
}
}
i++;
}
}
Câu 2 (3 điểm):
a) Hãy vẽ cây nhị phân tìm kiếm, sao cho nếu duyệt cây theo thứ tự LRN sẽ thu được dãy số như
sau: 4 9 6 14 17 32 27 19 12. Sau khi vẽ, hãy xác định cây có cân bằng hay không? Vì sao?
b) 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ị 13 và 15 vào cây. Vẽ lại
cây sau mỗi thao tác thêm.
c) 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ị 12 và 14 khỏi cây. Vẽ lại
cây sau mỗi thao tác xóa.
Câu 3: (4 điểm)
Khoa CNTT cần quản lý danh sách các học phần trong chương trình đào tạo nên xây dựng
thông tin cơ bản của một học phần theo cấu trúc sau:
class HocPhan
{
string _strMaHP; //mã học phần
string _strTenHP; //tên học phần
int _iSoTC; //số tín chỉ học phần
bool _bBatBuoc; //có giá trị true là bắt buộc, false là tự chọn
string _strMaHPTruoc;//mã học phần môn học trước, nếu không có thì có giá trị “Khong”
SV* _pNext; //con trỏ lưu địa chỉ của học phần tiếp theo
};
class List
{
HocPhan* _pHead;
HocPhan* _pTail;
};
Giả sử danh sách học phần được sắp xếp theo thứ tự tăng dần của mã học phần. Hãy thực hiện
các yêu cầu sau:
a) (1 đ) Hãy viết phương thức thêm một học phần vào danh sách sao cho vẫn đảm bảo tính
chất tăng dần theo mã học phần. Hàm được mô tả như sau:
void List::themHP(string maHP, string tenHP, int soTC, bool batBuoc, string maHPTruoc);
b) (1 đ) Với các học phần có điều kiện học phần trước, sinh viên chỉ có thể đăng ký học phần
này khi đã học các học phần học trước. Hãy viết phương thức liệt kê các học phần tự chọn
có học phần học trước là “COMP1314”:
void List::lietKeHP(string maHPTruoc);
c) (1 đ) Hãy viết phương thức xóa các học phần có mã học phần có đuôi là “13”.
void List::xoaHP();
d) (1 đ) Hai học phần được gọi là liên quan nhau nếu đăng ký học phần này thì phải học trước
học phần kia. Hãy viết phương thức xuất ra các cặp học phần liên quan nhau.
void List::xuatHPLienQuan();
----- 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
Ngày …..tháng…..năm…..
Trưởng bộ môn duyệt
(kí và ghi rõ họ tên)
Ngày …..tháng…..năm…..
Giảng viên ra đề
(kí và ghi rõ họ tên)