Đề thi Cấu trúc dữ liệu và giải thuật | 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 | 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!

48 24 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
ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CNTT
CỘNG HÒA XÃ H I CHỘ Ủ NGHĨA VIỆT NAM
Độ ậ ự ạc l p -T do - H nh phúc
ĐỀ Ấ Ả Ậ THI MÔN C U TRÚC DỮ LIỆU & GI I THU T
THỜI GIAN: 90 PHÚT - c s d ng tài li u Sinh viên không đượ ử ụ ệ
Câu 1 (4 : điểm) Giả s i ta có nhu c u dùng danh sách liên k các s ử ngườ ầ ết để lưu trữ ố nguyên dương.
Anh / ch hãy th c hi n : ị ự ệ
a. Định nghĩa cấ ệu để lưu trữ như yêu cầu (1 điểu trúc dữ li có thể m)
b. Viết hàm nhập các số nguyên vào danh sách, việc nhập kết thúc khi nhập giá tr - ị 1 (1 điểm)
c. Viết hàm void TinhToan(ptr Head) in ra giá tr l n nhị ớ ất, giá tr nh nhị ỏ ất và giá tr trung bình ị
của danh sách. c: nQui ướ ếu danh sách là rỗng thì các giá tr u là 0. ị này đề (1 điểm)
d. Viết hàm sắp xếp danh sách theo giá tr c a ph n tị ủ ầ ử trong danh sách m dgiả ần và in ra màn
hình (1 điểm)
Câu 2 :(2 điểm) Hãy phát bi cây nh phân tìm ki m. V cây nh ph n tìm ki v ểu định nghĩa ị ế ẽ ị ầ ếm (chỉ ẽ
cây k t qu ) t dãy s nguyên khi xây d ng cây theo th t t trái qua ph i c a dãy s 72; 67; 73; 58; ế ả ừ ố ự ứ ự ừ ả ủ ố:
5; 4; 27; 53; 61; 32.
Câu 3 (3 điểm) : Cho cây nh phân tìm ki m T ị ế
như hình bên. Anh /chị hãy thực hiện :
a. Viế ạ ứt hàm in ra các nút trên cây t i m c
thứ ủ ụ ậ ứ k c a cây. Ví d : nh p k = 0 (m c
gốc) thì in ra 33. (1 điểm)
b. Hãy v lẽ ại cây khi xóa l t nút 33 ; ần lượ
35 ; 12 ; 5. N u khi xóa nút, cây b mế ị ất
cân b ng, hãy cân b ng l i cây và cho ằ ằ ạ
biết loại mất cân bằng (nếu có) (2 điểm)
Câu 4 (1 điểm) : Giả sử ho bảng c băm A kích thước 7 ô và tập khóa K = {76, 93, 40, 47, 10,55}, ta cần
nạp các giá trị khóa K vào bảng A sử dụng hàm băm H1(k) = k % 7. Hãy vẽ bảng băm kết quả, trong
trường hợp xảy ra đụng độ, hãy sử dụng phương pháp băm kép để xử lý, với hàm băm thứ 2 do anh / chị tự
đề nghị.
- H - ết
| 1/1
| | Tải xuống

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

Preview text:

ĐẠI HỌC QUỐC GIA TP.HCM
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG ĐẠI HỌC CNTT
Độc lập -Tự do - Hạnh phúc
ĐỀ THI MÔN CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
THỜI GIAN: 90 PHÚT - Sinh viên không được sử dụng tài liệu
Câu 1 (4 điểm :
) Giả sử người ta có nhu cầu dùng danh sách liên kết để lưu trữ các s ố nguyên dương. Anh / chị hãy th c ự hiện :
a. Định nghĩa cấu trúc dữ liệu để có thể lưu trữ như yêu cầu (1 điểm)
b. Viết hàm nhập các số nguyên vào danh sách, việc nhập kết thúc khi nhập giá trị -1 (1 điểm)
c. Viết hàm void TinhToan(ptr Head) in ra giá trị lớn nhất, giá trị nhỏ nhất và giá trị trung bình
của danh sách. Qui ước: nếu danh sách là rỗng thì các giá trị này đều là 0. (1 điểm)
d. Viết hàm sắp xếp danh sách theo giá trị của phần tử trong danh sách giảm dần và in ra màn hình (1 điểm) Câu 2 (2 điểm
) : Hãy phát biểu định nghĩa cây nhị phân tìm kiếm. Vẽ cây nhị phần tìm kiếm (chỉ vẽ
cây kết quả) từ dãy s ngu ố
yên khi xây dựng cây theo th t ứ t ự t ừ rái qua phải c a
ủ dãy số: 72; 67; 73; 58; 5; 4; 27; 53; 61; 32.
Câu 3 (3 điểm) : Cho cây nhị phân tìm kiếm T
như hình bên. Anh /chị hãy thực hiện :
a. Viết hàm in ra các nút trên cây tại mức
thứ k của cây. Ví dụ : ậ nh p k = 0 (mức
gốc) thì in ra 33. (1 điểm)
b. Hãy vẽ lại cây khi xóa lần lượt nút 33 ;
35 ; 12 ; 5. Nếu khi xóa nút, cây bị mất
cân bằng, hãy cân bằng lại cây và cho
biết loại mất cân bằng (nếu có) (2 điểm)
Câu 4 (1 điểm) : Giả sử cho bảng băm A kích thước 7 ô và tập khóa K = {76, 93, 40, 47, 10,55}, ta cần
nạp các giá trị khóa K vào bảng A sử dụng hàm băm H1(k) = k % 7. Hãy vẽ bảng băm kết quả, trong
trường hợp xảy ra đụng độ, hãy sử dụng phương pháp băm kép để xử lý, với hàm băm thứ 2 do anh / chị tự đề nghị. - Hết -