Title Cuối kì 2009.pdf ✅

Đề thi cuối kì cấu trúc dữ liệu và giải thuật Học kì I, 2009-2010 Lớp k52ca, cb, cc Thời gian : 90’ Lưu ý : các thí sinh không được phép trao đổi bài Câu 1 (1 điểm) Hãy cho biết các phát biểu sau đúng hay sai : a. Các phần tử trong cấu trúc dữ liệu hàng đợi ưu tiên được thực hiện theo nguyên tắc vào trước ra trước. b. Độ phức tạp của hai thuật toán merge-sort và heap-sort là như nhau. c. Một đồ thị vô hướng là liên thông nếu có số cạnh nhiều hơn hoặc bằng hai lần số đỉnh của đồ thị. d. Giữa hai đỉnh bất kì trong cây chỉ tồn tại một đường đi duy nhât. e. Tư tưởng của thuật toán duyệt là giải quyết bài toán lớn dựa vào kết quả của các bài toán nhỏ. Câu 2 (2 điểm) Cho một mảng có n số nguyên đã được sắp xếp theo thứ tự không giảm. hãy mô tả thuật toán dưới dạng mã giả để đếm số lần xuất hiện của số nguyên k trong mảng đó với độ phức tạp tốt nhất có thể được. tính độ phức tạp của thuật toán. Câu 3 (2 điểm) Hãy mô tả một thuật toán đệ quy dưới dạng mã giả để tìm số phần tử bằng giá trị x cho trước trong một dãy danh sách liên kết đơn. Câu 4 (1 điểm) a. Độ cao nhỏ nhất của cây nhị phân có 7 đỉnh là bao nhiêu ? Vẽ hình minh họa. b. Hãy mô tả thuật toán duyệt Postorder cho một câu nhị phân dưới dạng mã giả. Câu 5 (1 điểm) Cho dãy số : 9, 1, 2, 8, 5. a. Hãy vẽ một cấu trúc dữ liệu heap chứa dãy số trên. b. Hãy vẽ một câu trúc dữ liệu cây nhị phân tìm kiếm chứa dãy trên. Câu 6 (1 điểm) Hãy viết mã giả mô tả thuật toán kiểm tra một đồ thị vô hướng G có liên thông hay không. Hãy cho biết độ phức tạp của thuật toán dưới dạng O() ? Câu 7 (2 điểm) Cho một mảng A = {a1, a2, ...., an} chứa n số nguyên dương. Một cách chọn một số phần tử trong A (mỗi phần tử được chọn không quá một lần) có tổng bằng một giá trị k cho trước được gọi là thỏa mãn điều kiện k. Hãy mô tả thuật toán dưới dạng mã giả điếm số cách chọn thỏa mãn điều kiện k. cho biết độ phức tạp của thuật toán đó. Câu 8 (1 điểm)