Đề cương môn công nghệ phần mềm- Trường Đại học bách khoa - Đại học đà nẵng.

TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
Thời gian làm bài: 90 phút, không kể thời gian phát đề
KHOA CÔNG NGHỆ THÔNG TIN ĐỀ SỐ 1 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 42, 27, 15, 29, 21, 68, 34, 18
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh
sách được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau: a. Tạo nút cho danh sách
b. Bổ sung một nút mới vào giữa danh sách.
c. Tìm phần tử X trong danh sách.
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau 6 11 5 10 15 20 2 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia
hết cho số k = 3 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa. TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
Thời gian làm bài: 90 phút, không kể thời gian phát đề
KHOA CÔNG NGHỆ THÔNG TIN ĐỀ SỐ 2 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Selection Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 30, 47, 35, 49, 41, 31, 24, 28
Câu 2 (3 điểm) Cho một danh sách nối đơn lưu trữ các số nguyên, giả sử đầu của danh
sách được trỏ bởi con trỏ p. Hãy viết thủ tục thực hiện các công việc sau: a. Tạo nút cho danh sách
b. Bổ sung một nút mới vào đầu danh sách.
c. Xóa nút cuối của danh sách.
Câu 3 (3 điểm) Cho một dãy A gồm các số nguyên như sau 2 3 5 7 9 6 12 7
Hãy tìm một dãy con (không nhất thiết phải liên tiếp nhau) dài nhất có tổng các số chia
hết cho số k = 5 (k nguyên dương).
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau. TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
Thời gian làm bài: 90 phút, không kể thời gian phát đề
KHOA CÔNG NGHỆ THÔNG TIN ĐỀ SỐ 3 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Insertion Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 30, 47, 35, 49, 21, 22, 24, 15
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các số nguyên.
a. Cài đặt danh sách trên.
b. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
c. Hiển thị danh sách sau khi thêm nút X.
Câu 3 (3 điểm) Cho một balo khối lượng W=9. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {3, 5, 6, 4, 1}; khối lượng A[i] = {3, 4, 5, 2, 1}. Hãy chọn các đồ vật để cho vào
ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi đồ vật có thể được chọn nhiều lần.
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự sau. TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
Thời gian làm bài: 90 phút, không kể thời gian phát đề
KHOA CÔNG NGHỆ THÔNG TIN ĐỀ SỐ 4 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Bubble Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 20, 37, 25, 39, 11, 5, 14, 15
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các số nguyên.
a. Cài đặt danh sách trên.
b. Hãy bổ sung một nút mới với thông tin X vào cuối danh sách.
c. Xóa nút đầu danh sách.
Câu 3 (3 điểm) Cho một balo khối lượng W=15. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {4, 2, 1, 2, 10}; khối lượng A[i] = {12, 2, 1, 1, 4}. Hãy chọn các đồ vật để cho
vào ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi vật chỉ được chọn một lần
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa. TRƯỜNG ĐẠI HỌC
ĐỀ THI KẾT THÚC HỌC PHẦN
KINH TẾ - KỸ THUẬT CÔNG NGHIỆP
CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
Hệ đào tạo: ĐẠI HỌC
Thời gian làm bài: 90 phút, không kể thời gian phát đề
KHOA CÔNG NGHỆ THÔNG TIN ĐỀ SỐ 5 Câu 1 (3 điểm)
a. Viết giải thuật sắp xếp Heap Sort để sắp xếp một dãy số nguyên theo thứ tự tăng dần.
b. Minh họa giải thuật trên với dãy số đã cho sau: 40 30 50 22 60 55 77 65
Câu 2 (3 điểm) Cho một danh sách nối vòng có nút cuối được trỏ bởi pList lưu trữ các số nguyên.
a. Cài đặt danh sách trên.
b. Hãy bổ sung một nút mới với thông tin X vào đầu danh sách.
c. Xóa nút ở vị trí giữa của danh sách.
Câu 3 (3 điểm) Cho một balo khối lượng W=13. Có 5 đồ vật lần lượt như sau: Giá trị
C[i] = {4, 5, 6, 3, 1}; khối lượng A[i] = {3, 4, 5, 2, 1}. Hãy chọn các đồ vật để cho vào
ba lô sao cho các đồ vật được chọn có giá trị lớn nhất và khối lượng không vượt quá
khối lượng balo. Mỗi vật chỉ được chọn một lần
a. Hãy dùng phương pháp quy hoạch động để giải quyết bài toán trên (Tạo bảng phương án, Truy vết).
b. Viết giải thuật truy vết của bài toán trên.
Câu 4 (1 điểm) Viết dãy duyệt cây dưới đây theo thứ tự trước và thứ tự giữa.