BÀI THỰC HÀNH
Dù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ồm
cá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 <=5. Nếu không có thì thông
báo không có.
d. Tìm một sinh viên có tên X trong lớp học (X nhập từ bàn phím)
e. Xoá một sinh viên có mã số cho trước trong lớp học. Nếu không có thì thông
báo không có.
f. Sắp xếp danh sách sinh viên tăng theo điểm trung bình bằng thuật toán sắp xếp
mà các bạn đã học (Selection Sort, Interchange Sort, Binary Sort)
g. Chèn một sinh viên vào lớp học, biết ràng sau khi chèn danh sách sinh viên vẫn
tăng dần theo điểm trung bình.
CuuDuongThanCong.com https://fb.com/tailieudientucntt
Câu hỏi & Bài tập Chương Bảng băm
Phầ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.
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ữ trong bảng A, sử dụng kỹ
thuật danh sách liên kết để xử lý xung đột.
2. 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ị
khó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ỹ
thuật dò tuyến tính để xử lý xung đột.
3. 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ị
khóa K vào bảng A sử dụng hàm băm H(k) = k % 10.
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 dò toàn phương để xử lý xung đột.
4.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/tailieudientucntt
cuu duong than cong . com
6.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ợ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).
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ủa
các số 1, 2, …, s-1. Dãy thăm dò ứng với khoá k được xác định như sau:
i
0
= i = h(k)
i
m
= (i + d
i
) % SIZE , 1 ≤m≤s –1
Hãy cài đặt hàm thăm dò theo phương pháp trên.
Bài tập áp dụng:
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
3. Các bài tập khác do Giảng viên đề nghị
CuuDuongThanCong.com https://fb.com/tailieudientucntt
cuu duong than cong . com
Câu hỏi & Bài tập B-Tree
Phầ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, 14
4. 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 B tree.
2. Các bài tập khác do Giảng viên đề nghị
Câu hỏi & Bài tập Chương Danh sách liên kết
Phần câu hỏi ôn kiến thức:
1. Trình bày từng bước các thao tác trên danh sách liên kết đơn
2. Trình bày từng bước các thao tác trên danh sách liên kết đôi
3.Giả sử cho một danh sách liên kết đơn có thành phần dữ liệu là các số nguyên dương, người ta
muốn tách danh sách đã cho thành hai danh sách riêng biệt, trong đó một danh sách lưu số chẵn,
một danh sách lưu số lẻ. Hãy trình bày giải thuật để tách danh sách đã cho sao cho hiệu quả nhất về
thời gian xử lý và bộ nhớ sử dụng, đặc biệt xét cả trong trường hợp danh sách đã cho bao gồm tất cả
là số chẵn hoặc số lẻ.
4.Hãy trình bày giải thuật trộn hai danh sách liên kết đơn đã có thứ tự (tăng hoặc giảm dần) thành
một danh sách có thứ tự sao cho tối ưu bộ nhớ nhất có thể.
5.Cho danh sách liên kết được mô tả bởi cấu trúc dữ liệu trên C như sau:
struct Node
{ int info;
struct Node *next;
};
Hãy viết thuật giải nhận đầu vào là danh sách liên kết với phân tử đầu tiên được trỏ bởi list,
thực hiện sắp xếp lại các phần tử của danh sách đã cho, sao cho các nút chẵn đứng trước các
nút lẻ và trong trường hợp ngược lại, thứ tự tương đối ban đầu của các nút là không thay đổi.
Một nút được gọi là nút chẵn hay lẻ nếu nó đứng ở vị trí chẵn hay lẻ trong danh sách (vị trí của
các nút trong danh sách được đánh số từ phần tử đầu tiên đến phần tử cuối cùng bắt đầu từ 0).