Đề thi Cấu trúc dữ liệu và giải thuật - Đề 2 | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Đề thi Cấu trúc dữ liệu và giải thuật - Đề 2 | Trường Đại học CNTT Thành Phố Hồ Chí Minh được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

37 19 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (IT003)

Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

1 trang 5 tháng trước

Tác giả:

Profile Mai Nguyệt
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỀ THI MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Thời gian: 90 phút
(Không s d ng tài li ử ụ ệu)
Câu 1: (5 m) điể
Giả sử cho một danh sách liên kết đơn mà mỗi phần tử chứa thông tin về một sinh
viên bao gồm các trường: mã số sinh viên (chuỗi ký tự), họ và tên sinh viên(chuỗi ký
tự), điểm trung bình tích lũy (số thực), loại tốt nghiệp (ký tự). Hai con trỏ Head và
Tail trỏ vào phần tử đầu và cuối trong danh sách.
Hãy xây dựng các hàm sau:
a) Hàm n hập danh sách sinh viên bằng thao tác thêm sinh viên vào đầu danh sách
b) Hàm xếp loại tốt nghiệp cho sinh viên. Trong đó xếp loại X(Xuất sắc) nếu có
điểm trung bình tích lũy ĐTB>=9.0; Loại nếu 8<=ĐTB <9.0; Loại G(Giỏi)
K(Khá) nếu 7<= ĐTB< 8; Loại T(Trung bình) nếu có điểm trung bình tích lũy
5<= ĐTB <7; Loại Y (Yếu) nếu ĐTB < 5.
c) Hàm xóa các sinh viên xếp loại Y (Yếu) ra khỏi danh sách
d) Sắp xếp danh sách sinh viên theo điểm trung bình tích lũy
Câu 2 3 m) : ( điể
Cho một cây nhị phân tìm kiếm T, mỗi nút là một số nguyên.
a) Hãy vẽ cây nhị phân tìm kiếm biết rằng khi duyệt cây theo thứ tự Left –T
Right – Node thì được dãy như sau:
5, 3, 7, 9, 8, 11, 6 20, 19, 37, 25, 21, 15, 12. ,
b) Viết hàm đếm xem trong cây có bao nhiêu số chẵn, bao nhiêu số lẻ
Câu 3: (2 m) điể
Cho bốn cây nhị phân tìm kiếm bị mất cân bằng như sau. Hãy cho biết đây là
loại mất cân bằng gì và cân bằng lại cây.
a) 30
20
10 2 5
b) 40
20 50
4 55 5
60
c) 4
3 6
1 5 7
2
d) 10
9 17
15 18
16
----------------- Hết -----------------
| 1/1
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐỀ THI MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Thời gian: 90 phút
(Không sử dụng tài liệu )
Câu 1: (5 điểm)
Giả sử cho một danh sách liên kết đơn mà mỗi phần tử chứa thông tin về một sinh
viên bao gồm các trường: mã số sinh viên (chuỗi ký tự), họ và tên sinh viên(chuỗi ký
tự), điểm trung bình tích lũy (số thực), loại tốt nghiệp (ký tự). Hai con trỏ Head và
Tail trỏ vào phần tử đầu và cuối trong danh sách.
Hãy xây dựng các hàm sau:
a) Hàm nhập danh sách sinh viên bằng thao tác thêm sinh viên vào đầu danh sách
b) Hàm xếp loại tốt nghiệp cho sinh viên. Trong đó xếp loại X(Xuất sắc) nếu có
điểm trung bình tích lũy ĐTB>=9.0; Loại G(Giỏi) nếu 8<=ĐTB <9.0; Loại
K(Khá) nếu 7<= ĐTB< 8; Loại T(Trung bình) nếu có điểm trung bình tích lũy
5<= ĐTB <7; Loại Y (Yếu) nếu ĐTB < 5.
c) Hàm xóa các sinh viên xếp loại Y (Yếu) ra khỏi danh sách
d) Sắp xếp danh sách sinh viên theo điểm trung bình tích lũy
Câu 2: (3 điểm)
Cho một cây nhị phân tìm kiếm T, mỗi nút là một số nguyên.
a) Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây theo thứ tự Left –
Right – Node thì được dãy như sau:
5, 3, 7, 9, 8, 11, 6, 20, 19, 37, 25, 21, 15, 12.
b) Viết hàm đếm xem trong cây có bao nhiêu số chẵn, bao nhiêu số lẻ
Câu 3: (2 điểm)
Cho bốn cây nhị phân tìm kiếm bị mất cân bằng như sau. Hãy cho biết đây là
loại mất cân bằng gì và cân bằng lại cây. a) 30 b) 40 20 20 50 10 25 45 55 60 c) 4 d) 10 3 6 9 17 1 5 7 15 18 2 16
----------------- Hết -----------------