tailieunhanh - Đề thi học kỳ năm 2011 môn Cấu trúc dữ liệu và giải thuật (Mã đề 01) - Đại học Bách khoa Hà Nội

Đề thi học kỳ năm 2011 môn Cấu trúc dữ liệu và giải thuật giúp các bạn sinh viên có thêm tài liệu để củng cố các kiến thức, ôn tập kiểm tra, thi cuối kỳ. Đây là tài liệu bổ ích để các em ôn luyện và kiểm tra kiến thức tốt, chuẩn bị cho kì thi học kì. Mời các em và các quý thầy cô giáo bộ môn tham khảo. | Mã đề CD 2011 - 01 TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG BỘ MÔN KHOA HỌC MÁY TÍNH ĐỀ THI MÔN CẤU TRÚC DỮ LIỆU Hà nội . . . . Họ tên VÀ GIẢI THUẬT Trưởng bộ môn Ngày thi . . . Lớp Thời gian 90 SHSV . Sinh viên được sử dụng tài liệu Bài 1. a Phân biệt giữa mảng cấp phát động và mảng cấp phát tĩnh. Khi nào nên dùng mảng cấp phát động hoặc mảng cấp phát tĩnh Cho ví dụ minh họa. 1 Điểm Mảng cấp phát tĩnh Mảng cấp phát động Bộ nhớ Bộ nhớ lấy từ phần DATA Bộ nhớ lấy từ HEAP Kích thước Bộ nhớ giới hạn chỉ có thể cấp phát cho các Dung lượng bộ nhớ lớn có thể cấp phát được cho biến có kích thước nhỏ các biến kích thước lớn Thời điểm cấp Bộ nhớ được cấp phát tại thời điểm biên dịch Bộ nhớ được cấp phát tại thời điểm chạy phát chương trình Thu hồi bộ Hệ điều hành sẽ tự thu hồi bộ nhớ khi không Người lập trình phải tự thu hồi bộ nhớ xin cấp nhớ dùng đến phát Cấp phát tĩnh cho các biến kích thước nhỏ các biến đơn float a b Ar 100 Cấp phát động Dùng cho các biến kích thước lớn các mảng lớn double A A double malloc 10000 sizeof double b Đánh giá thời gian thực hiện tồi nhất của hàm sau theo O-lớn 1 Điểm double fastPower double x int n double fract if n 0 return 1 if n 2 0 return fastPower x n 2 fastPower x n 2 else return fastPower x n 2 fastPower x n 2 x 1 Page https tailieudientucntt Hàm trên được cài đặt đệ quy lời gọi đệ quy là fract fastPower x n 2 Được gọi 2 lần trong hàm ứng với if hoặc else ta có công thức đệ quy tổng quát là 1 ế 0 2 1 ế gt 0 2 Ta có thể viết gọn lại là 2 1 2 Áp dụng định lý thợ với 2 2 và 1 log log2 2 trường hợp 1 của định lý thợ Vậy kết luận c So sánh ưu nhược điểm của phương pháp tổ chức tìm kiếm dùng mảng và áp dụng thuật toán tìm kiếm nhị phân cây nhị phân tìm kiếm và dùng bảng băm theo các tiêu chí sau 1 Điểm Tiêu chí Tìm kiếm nhị phân Cây nhị phân tìm kiếm Bảng băm Bộ nhớ dùng lưu Số lượng ô nhớ xác định trước là trữ các phần tử Tỉ lệ với số phần tử tuy nhiên Tỉ lệ với số phần tử tuy .