ĐỀ KIỂM
TRA
MÔN CẤU
TRÚC DỮ LIỆU VÀ GIẢI THUẬT
SỐ 02
Câu 1:
Trình bày khái niệm giải thuật,
ngôn ngữ diễn đạt giải thuật. Trình bày về thiết kế giải thuật và cách đánh giá
giải thuật. Trình bày khái niệm đệ quy,
giải thuật đệ quy và chương trình đệ quy
Câu 2:
a. Mô tả giải thuật bài toán
tính ước số chung lớn nhất (giải thuật Euclide) của 2 số p và q (p>q). Lập bảng
ghi nhận các giá trị của q, p, r trong quá trình thực hiện tính ước số chung lớn
nhất của 2 số: 1260 và 198.
b. Viết một giải thuật đệ quy
và một giải thuật không đệ quy (dùng phép lặp) để tính ước số chung lớn nhất của
p, q.
Câu 3:
a. Mô
tả ý tưởng, giải thuật cài đặt thuật toán sắp xếp bằng phương pháp chèn
(Insertion sort).
b. Cho dãy số: 5, 6, 2, 2, 10, 12, 9, 10, 9,
3. Minh họa việc sắp xếp dãy số theo chiều tăng
dần bằng phương pháp sắp chèn (Insertion sort).
Câu 4:
a. Mô
tả ý tưởng, giải thuật cài đặt thuật toán sắp xếp bằng phương pháp sắp xếp
nhanh (Quick sort).
b. Cho dãy số: 5, 6, 2, 2, 10, 12, 9, 10, 9,
3. Minh họa việc sắp xếp dãy số theo chiều tăng
dần bằng phương pháp sắp xếp nhanh (Quick sort).
Câu 5. Mô tả ý tưởng, giải thuật cài đặt thuật toán phương pháp tìm kiếm tuyến
tính và tìm kiếm nhị phân