Câu hỏi và bài tập môn cấu trúc dữ liệu và giải thuật - Trường ĐH Công nghệ Thông tin

Tập hợp các Câu hỏi và Bài tập các chương: Chương Bảng băm Chương Danh sách liên kết; B-Tree; Chương Stack – Queue và các bài tập thực hành khác Mời các bạn xem nội dung chi tiết để bạn hệ thống lại kiến thức và ôn tập hiệu quả.

Nội dung trích xuất từ tài liệu:
Câu hỏi và bài tập môn cấu trúc dữ liệu và giải thuật - Trường ĐH Công nghệ Thông tin BÀI THỰC HÀNHDùng danh sách liên kết đơn để quản lý một lớp học. Biết rằng mỗi sinh viên bao gồmcác thông tin sau: Tên (chuỗi ký tự), Mã số sinh viên (chuỗi ký tự), Điểm trung bình.Hãy viết hàm thực hiện các yêu cầu sau: a. In danh sách sinh viên ra màn hình b. Liệt kê 5 sinh viên có điểm trung bình cao nhất trong lớp học. c. Cho biết số tổng số sinh viên có điểm trung bình Câu hỏi & Bài tập Chương Bảng bămPhần câu hỏi ôn kiến thức:1.Hãy trình bày ưu điểm và hạn chế của cấu trúc bảng băm và cho ví dụ minh họa cụ thể ?Bài tập :1.Cho bảng A kích thước 11 ô và tập khóa K = {7, 20, 16, 24, 12, 40, 15}, ta cần nạp các giá trịkhóa K vào bảng A sử dụng hàm băm H(k) = k % 11. omHãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ trong bảng A, sử dụng kỹ .cthuật danh sách liên kết để xử lý xung đột. ng2. Cho bảng A kích thước 11 ô và tập khóa K = {30, 10, 56, 14, 22, 60, 15}, ta cần nạp các giá trị cokhóa K vào bảng A sử dụng hàm băm H(k) = k % 7.Hãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ vào bảng A, sử dụng kỹ anthuật dò tuyến tính để xử lý xung đột. th3. Cho bảng A kích thước 11 ô và tập khóa K = {23, 12, 65, 27, 8, 50, 58}, ta cần nạp các giá trị ngkhóa K vào bảng A sử dụng hàm băm H(k) = k % 10. oHãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ vào bảng A, sử dụng kỹ duthuật dò toàn phương để xử lý xung đột. u cu4.Cho bảng A kích thước 11 ô và tập khóa K = {7, 20, 16, 24, 12, 40, 15}, ta cần nạp các giá trịkhóa K vào bảng A sử dụng hàm băm H(k) = k % 11.Hãy vẽ bảng A sau khi tất cả các giá trị khóa trong tập K được lưu trữ vào bảng A, sử dụng kỹthuật băm kép để xử lý xung đột, với hàm băm kép thứ 2 tự định nghĩa.5.Viết chương trình minh hoạ bảng băm dùng phương pháp nối kết trong các trường hợp sau : a. Dữ liệu lưu trữ là số nguyên (khoá tìm kiếm là số nguyên). b. Dữ liệu lưu trữ là thông tin học sinh, bao gồm: họ tên học sinh, lớp, tên trường (khoá tìm kiếm là tên lớp). CuuDuongThanCong.com https://fb.com/tailieudientucntt6.Viết chương trình minh hoạ bảng băm dùng phương pháp dò tuyến tính trong các trường hợpsau: a. Dữ liệu lưu trữ là số nguyên (khoá tìm kiếm là số nguyên). b. Dữ liệu lưu trữ là thông tin học sinh, bao gồm: họ tên học sinh, lớp, tên trường (khoá tìm kiếm là tên lớp).3.Giả sử kích thước của bảng băm là SIZE = s và d1, d2, …, ds-1 là hoán vị ngẫu nhiên củacác số 1, 2, …, s-1. Dãy thăm dò ứng với khoá k được xác định như sau: om i = i = h(k) 0 .c i = (i + d ) % SIZE , 1 ≤m≤s –1 m i ngHãy cài đặt hàm thăm dò theo phương pháp trên. coBài tập áp dụng: an 1. Viết chương trình cho phép tạo, tra cứu từ điển Anh-Việt sử dụng cấu trúc bảng băm 2. Viết chương trình cho phép tạo, tra cứu sách trong thư viện sử dụng cấu trúc bảng băm th 3. Các bài tập khác do Giảng viên đề nghị o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucnttCâu hỏi & Bài tập B-TreePhần câu hỏi ôn kiến thức:1. Trình bày định nghĩa và các tính chất của cây B-Tree.2. Cài đặt tất cả các thao trên cây B-Tree.3. Cho B-tree bậc 5 gồm các khóa sau (chèn vào theo thứ tự): 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56 Thực hiện các yêu cầu sau: - Thêm các khóa: 2, 6,12 - Xóa khóa: 4, 5, 7, 3, 144. Khởi tạo B Tree bậc 7 với các thao tác Insert: 34, 12, 55, 21, 6, 84, 5, 33, 15, 74, 54, 28, 10, 19. Hãy thực hiện các chuỗi thao tác sau và cho biết kết quả qua từng thao tác: - Insert(11) - Delete(15) - Delete(6) - Insert(98) - Delete(34) - Delete(5)Bài tập : 1. Viết chương trình cài đặt các thao tác trên ...