tailieunhanh - Đề thi học kỳ năm 2011 môn Cấu trúc dữ liệu và giải thuật (Mã đề 02) - Đạ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 gồm 5 câu hỏi hệ thống lại kiến thức học phần và giúp các bạn sinh viên ôn tập kiến thức đã học, chuẩn bị cho kỳ thi sắp tới. Tài liệu hữu ích cho các các bạn sinh viên đang theo học và những ai quan tâm đến môn học này dùng làm tài liệu tham khảo. | Mã đề CD 2011 - 02 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 So sánh ưu nhược điểm khi lưu trữ cây nhị phân chiều cao ℎ dùng 1 mảng 2 cấu trúc liên kết 1 Điểm struct BNode DATA_TYPE data là kiểu dữ liệu lưu trữ tại nút struct BNode Lchild Rchild con trỏ tới cây con trái và con phải Theo các tiêu chí Bộ nhớ thời gian truy cập một nút bất kỳ tìm nút cha của một nút bất kỳ trên cây Biểu diễn cây nhị phân dùng mảng dùng mảng có số lượng phần tử bằng số lượng nút trên cây nhị phân đầy đủ chiều cao ℎ số lượng phần tử của mảng sẽ là 2ℎ 1 1 phần tử . 1 Với nút thứ 0 thì nút con của nó sẽ là 2 1 và 2 2 nút cha của nó sẽ là 2 Biểu diễn cây nhị phân dùng cấu trúc liên kết mỗi nút có thêm hai con trỏ là con trỏ tới cây con trái và con trỏ tới cây con phải. Tiêu chí Biểu diễn dùng mảng Biểu diễn dùng cấu trúc liên kết Bộ nhớ Biểu diễn 1 phần tử không cần sử dụng thêm Biểu diễn 1 phần tử Cần thêm bộ nhớ phụ lưu trữ bộ nhớ phụ con trỏ tới cây con trái và cây con phải Biểu diễn cho cả cây luôn cần bộ nhớ Biểu diễn cho cả cây Cây có bao nhiêu nút thì cấp 2ℎ 1 1 cho cây nhị pahan bất kỳ chiều cao phát động bấy nhiêu bộ nhớ. Tiết kiệm bộ nhớ ℎ nên sẽ rất lãng phí bộ nhớ nếu cây nhị phân hơn nếu dùng biểu diễn cho cây nhị phân bất kỳ đó không phải là cây gần hoàn chỉnh. Thời gian 1 ℎ truy cập 1 Vì mảng hỗ trợ truy cập ngẫu nhiên Cấu trúc liên kết không hỗ trợ truy cập ngẫu nhiên nút bất kỳ ta phải truy cập thông qua các nút tổ tiên của nút đó Tìm nút cha Thời gian là 1 Thời gian trung bình cỡ vì ta phải duyệt từ của một nút gốc để tìm tới nút cha của nút đó bất kỳ 1 Page https tailieudientucntt 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 fract fastPower x n 2 .