TAILIEUCHUNG - Đề thi Cấu trúc dữ liệu và giải thuật (Mã đề 02) - Đại học Bách khoa Hà Nội

Mời các bạn cùng tham khảo đề thi Cấu trúc dữ liệu và giải thuật sau đây để biết được cấu trúc đề thi, cách thức làm bài thi cũng như những dạng bài chính được đưa ra trong đề thi. Từ đó, giúp các bạn sinh viên có kế hoạch học tập và ôn thi hiệu quả. | 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ụ mình họa. 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 if n 2 0 return fastPower x n 2 fastPower x n 2 else return fastPower x n 2 fastPower x n 2 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ó 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 Chuyển biểu thức dạng trung tố sau sang dạng hậu tố 3 2 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 1 Page https tailieudientucntt 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 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à 36. 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 DFS từ đỉnh D hãy đưa ra thứ tự các đỉnh được thăm. c Hãy đưa ra các loại cạnh thu được khi DFS tại đỉnh D BackEdge CrossEdge TreeEdge và ForwardEdge . Lưu ý Các đỉnh trên đồ thị được thăm theo thứ tự ABC Bài 5. Để biểu diễn các tập hợp số nguyên ta dùng danh .

• Cơ sở dữ liệu
• Đề thi học kỳ
• Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Đề thi Cấu trúc dữ liệu và giải thuật
• Khoa học máy tính
• Đề thi học kỳ 1 môn Lý
• Đề thi học kỳ 1 lớp 8
• Đề thi học kỳ 1
• Đề thi học kỳ Vật lý 8
• Đề thi học kỳ Vật lý
• Đề thi học kỳ lớp 8
• Đề thi học kỳ 2
• Đề kiểm tra học kỳ
• Đề kiểm tra học kỳ 2 lớp 7
• Đề thi học kỳ Mĩ thuật 7
• Đề thi học kỳ môn Mĩ thuật
• Đề thi học kỳ lớp 7
• Đề kiểm tra học kỳ 1 lớp 8
• Đề thi học kỳ Mĩ thuật 8
• Đề kiểm tra học kỳ 2 lớp 9
• Đề thi học kỳ Mĩ thuật 9
• Đề thi học kỳ lớp 9
• Đề kiểm tra học kỳ 1 lớp 7