TAILIEUCHUNG - ĐỀ THI SAU ĐẠI HỌC NĂM 2008
PHẦN A: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ( điểm) Câu 1 ( điểm). Thí sinh trả lời ngắn gọn 6 câu hỏi sau đây, mỗi câu điểm: Đề giải bài toán Tháp Hà Nội bằng một lời giải thuật đệ quy, người ta hay dùng chiến lược thiết kế giải thuật nào sau đây: a tham lam b quay lui c chia để trị d cả ba câu trên đều sai | TSSĐH-B02 ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA HỘI ĐỒNG TUYỂN SINH SĐH ------- oOo ------- ĐỀ THI SAU ĐẠI HỌC NĂM 2008 Tuyển sinh: CAO HỌC 9 NGHIÊN CỨU SINH Chuyên ngành: KHOA HỌC MÁY TÍNH Mơn Thi: CƠ BẢN CƠ SỞ 9 CHUYÊN NGÀNH Thời gian làm bài: 180 phút (Khơng được phép dùng tài liệu) Đề thi số: 01 Đề thi gồm 4 trang ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ PHẦN A: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ( điểm) Câu 1 ( điểm). Thí sinh trả lời ngắn gọn 6 câu hỏi sau đây, mỗi câu điểm: Để giải bài tốn Tháp Hà Nội bằng một giải thuật đệ quy, người ta hay dùng chiến lược thiết kế giải thuật nào sau đây: a. tham lam b. quay lui c. chia để trị d. cả ba câu trên đều sai Hãy nêu độ phức tạp của các thao tác làm việc trên cấu trúc heap. Cĩ hai cách diễn tả đồ thị: (1) ma trận kế cận và (2) tập danh sách kế cận. Hãy nêu trường hợp nào nên dùng cách 1 và trường hợp nào nên dùng cách 2). Hãy so sánh phương pháp tìm kiếm bằng kỹ thuật băm và tìm kiếm bằng cây tìm kiếm nhị phân, phương pháp nào tốt hơn. Tại sao? Tại sao đối với một mảng đã gần có thứ tự, ta không nên áp dụng Quicksort? Trong giải thuật Quicksort để sắp thứ tự một dãy, người ta hay chọn phần tử chốt (pivot) là: a. phần tử tận cùng trái của dãy b. phần tử tận cùng phải của dãy c. phần tử trung vị của 3 phần tử tận cùng phải, tận cùng trái và phần tử ở vị trí chính giữa dãy. d. một trong 3 cách trên đều đúng. Câu 2 ( điểm) Hãy vẽ từng bước quá trình xây dựng cây tìm kiếm nhị phân khi ta đưa vào cây (lúc đầu rỗng) những trị khố như sau: E, A, R, C, H, N, M, P, L. Và cây tìm kiếm nhị phân sẽ trở thành như thế nào khi ta xĩa trị khĩa E ra khỏi cây. Câu 3 ( điểm) Hãy chạy từng bước giải thuật sắp thứ tự bằng phương pháp trộn (merge sort) để sắp thứ tự dãy số 53, 59, 56, 52, 58, 51, 57, 54. PHẦN B: NGƠN NGỮ LẬP TRÌNH ( điểm) Câu 1 (1 điểm) a. () Giả sử kích thước của một đối tượng kiểu integer là .
đang nạp các trang xem trước
