Đề thi học kì 2 môn Cấu trúc dữ liệu và giải thuật năm 2018-2019 - Trường Đại học Bách Khoa được chia sẻ dưới đây hi vọng sẽ là tài liệu luyện thi hiệu quả dành cho các bạn sinh viên. Cùng tham khảo và tải về đề thi để ôn tập kiến thức, rèn luyện nâng cao khả năng giải đề thi để chuẩn bị thật tốt cho kì thi sắp tới nhé. Chúc các bạn thi tốt! | TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM CẤU TRÚC DỮ LIỆU amp GIẢI THUẬT CO2003 ĐỀ KIỂM TRA CUỐI KỲ 2 2018-2019 MÔN THI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT THỜI GIAN 120 PHÚT NGÀY THI 30 05 2019 HƯỚNG DẪN Sinh viên điền Họ tên và MSSV vào đề thi. Sinh viên viết trực tiếp câu trả lời lên đề thi và nộp lại đề thi. Được sử dụng tài liệu trên giấy. Không sử dụng laptop điện thoại hoặc các thiết bị tương tự Tổng điểm 110 NGUYỄN XUÂN TRỰC Họ và tên _ 1513804 MSSV _ PHẦN ĐIỂM Phần A 15 điểm Phần B 15 điểm Phần C 20 điểm Phần D 20 điểm Phần E 15 điểm Phần F 10 điểm Phần G 15 điểm TỔNG ĐIỂM Ngày ra đề 28 05 2019 TRƯỞNG KHOA BỘ MÔN GIẢNG VIÊN TS. Nguyễn Hồ Mẫn Rạng 1 TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM CẤU TRÚC DỮ LIỆU amp GIẢI THUẬT CO2003 PHẦN A PHÂN TÍCH ĐỘ PHỨC TẠP 15 điểm A1 . Điền vào các ô trống độ phức tạp trong trường hợp trung bình average case của các hàm thêm xóa và tìm kiếm phần tử trong các cấu trúc dữ liệu sau 5 điểm Trả lời Mảng được sắp xếp Cây AVL Bảng Hash Sorted ArrayList AVL Tree Hash Table Thêm Insertion Xóa Deletion Tìm kiếm Retrieval A2 . Giả sử bạn thu thập được thông tin dữ liệu thời gian chạy của một chương trình theo kích thước số lượng phần tử N của dữ liệu đầu vào như sau N Time 1 000 s 8 000 s 64 000 1 s 512 000 32 s Ước lượng thời gian chạy f N theo kích thước N. 5 điểm Trả lời A3 . Cho biết độ phức tạp của thuật toán bên dưới 5 điểm for int i 0 i lt n i for int j i j lt n - i j count Trả lời 2 TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM CẤU TRÚC DỮ LIỆU amp GIẢI THUẬT CO2003 PHẦN B DANH SÁCH 20 điểm Sử dụng cấu trúc dữ liệu danh sách liên kết đôi như bên dưới để trả lời các câu B1-B2 class Node class DoubleLinkedList public Node head tail int data int count Node next prev B1 . Biết rằng kiểu int có kích thước là 4 bytes và kiểu con trỏ pointer có kích thước là 8 bytes. Hỏi kích thước của một đối tượng kiểu DoubleLinkedList chứa 10 phần tử là bao nhiêu bytes 5 điểm Trả lời B2 . Cho biết độ phức tạp trong
