Đề thi học kỳ năm 2011 môn Cấu trúc dữ liệu và giải thuật dưới đây nhằm giúp các em có thêm tư liệu để tham khảo cũng như củng cố kiến thức trước khi bước vào kì thi. Cùng tham khảo và giải đề thi để ôn tập kiến thức và làm quen với cấu trúc đề thi. | 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 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 b Đánh giá thời gian thực hiện tồi nhất của hàm sau theo O-lớn double fastPower double x int n double fract if n 0 return 1 fract fastPower x n 2 if n 2 0 return fract fract else return fract fract x 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 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 trữ các phần tử Thời gian tìm kiếm Thêm phần tử Xoá phần tử In ra danh sách các phần tử hiện có 1 Page https tailieudientucntt Bài 2. a Biểu thức dạng hậu tố là gì Ưu điểm của biểu thức dạng hậu tố b Định giá biểu thức dạng hậu tố sau trình bày rõ các trạng thái trung gian của STACK 10 2 3 2 4 12 8 c Vẽ cây biểu thức biểu diễn cho biểu thức ở phần b không cần phải trình bày các bước trung gian Bài 3. a Cho cây nhị phân tìm kiếm ban đầu như hình thêm lần lượt dãy khóa 33 43 12 36 78 29 16 9 65 27 32. Hãy vẽ cây nhị phân kết quả thu được cuối cùng không cần trình bày các bước trung gian . b Với cây nhị phân tìm kiếm thu được ở phần a thực hiện xóa lần lượt khóa 18 và 33. Hãy vẽ cây kết quả thu được sau mỗi lần xóa Chú ý chọn nút thay thế là nút phải nhất trên cây con trái Bài 4. Cho một đơn đồ thị vô hướng như sau a Hãy biểu diễn đồ thị trên dùng danh sách kề. b Thực hiện BFS từ đỉnh B hãy đưa ra thứ tự các đỉnh được thăm. c .
