ĐỀ KIỂM TRA MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT SỐ 02

ĐỀ 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

 

 

Bài giảng môn Cấu trúc dữ liệu và Giải thuật