KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN CÔNG NGHỆ PHẦN MỀM
Đề số: 02
ĐỀ KIỂM TRA LẬP TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 2 (POHE)
(Thời gian làm bài: 75 phút)
Bài 1 (4 điểm): ctdlgt2-kt-de02bai1.cpp
Viết chương trình C/C++ cài đặt giải thuật sắp xếp nhanh. Áp dụng giải thuật này để sắp xếp tăng dần dãy khóa có n phần tử là các số nguyên, dãy khóa đọc vào từ tệp văn bản.
Bài 2 (6 điểm): ctdlgt2-kt-de02bai2.cpp
Cho đồ thị vô hướng, không trọng số có n đỉnh là các số nguyên từ 1 đến n. Cài đặt cấu trúc lưu trữ phân tán và phép toán duyệt đồ thị theo chiều sâu. Nhập vào tệp văn bản 'dothi-kt.txt' đồ thị có n=5 đỉnh dưới đây. Đọc đồ thị từ tệp và đưa ra màn hình. Áp dụng để đưa ra thứ tự các đỉnh được thăm khi duyệt đồ thị theo chiều sâu bắt đầu từ đỉnh 1.
1: 4, 5 2: 3, 5 3: 2, 4, 5 4: 1, 3, 5 5: 1, 2, 3, 4
--- Hết --- Ghi chú: + Sinh viên không được sử dụng tài liệu.
+ Cán bộ coi thi không giải thích gì thêm.