Bài tập Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm nâng cao
Chương 6. Tìm kiếm nâng cao
Bài 1. Inverted table
Giả sử chúng ta cần quản lý các bản ghi là thông tin về các khách hàng của một nhà mạng. Để cho dễ
quản lý thì người phụ trách muốn tên các khách hàng này được sắp theo thứ tự ABC. Tuy nhiên để đánh
giá hiệu quả của một chiến dịch marketing, lúc này ta lại cần sắp xếp các khách hàng theo thứ tự thời
gian đăng ký (index). Bên phòng hậu mãi cũng muốn sắp xếp khách hàng theo thứ tự tăng dần số điện
thoại để tiện cho việc liên lạc với các khách hàng.
Chúng ta sẽ tổ chức các thông tin này như thế nào để cho tiện, và cũng để tiết kiệm bộ nhớ, chúng ta
không muốn phải lưu trữ lại các bản ghi này.
Index
Name
Address
Phone
Hill, Thomas M. High Towers #317 2829478
Baker, John S.
Roberts, L. B.
King, Barbara
17 King Street
53 Ash Street
2884285
4372296
High Towers #802 2863386
Hill, Thomas M. 39 King Street
2495723
4394231
Byers, Carolyn
Moody, C. L.
118 Maple Street
High Towers #210 2822214
Bài 2. Chứng minh rằng trong phương pháp khắc phục đụng độ bằng đánh địa chỉ mở dùng dò toàn phương
với hàm băm là ℎ = 푘%푚 trong đó 푚 là số nguyên tố thì chỉ có ½ phần tử trong bảng băm được dò.
Bài 3. Viết hàm thêm phần tử vào bảng băm khắc phục đụng độ bằng đánh địa chỉ mở dùng dò toàn phương
Bài 4. Viết hàm tìm kiếm phần tử trong bảng băm khắc phục đụng độ bằng đánh địa chỉ mở dùng dò toàn
phương
Bài 5. Trong trường hợp khóa là các giá trị nguyên, nếu chúng ta sử dụng hàm băm sau thì có vấn đề gì?
(
)
a. ℎ = 푖푛푡 sin(푘)
(
)
b. ℎ = 푖푛푡 exp(푘)
Bài 6. Cho các khóa là các xâu gồm 3 kí tự sau
PAL
LAP
PAM MAP PAT
PET
SET
SAT
TAT
BAT
Hãy xây dựng một hàm băm đơn giản để ánh xạ chúng vào một bảng băm kích thước 푛 trong các
trường hợp giá trị của 푛 là: 11, 13, 17, 19
Hãy xây dựng hàm băm sao cho số đụng độ ít nhất có thể.
Bài 7. Cho bảng băm kích thước 13, và các khóa là
10
100
32
45
58
126
3
29
200
400
0
a. Trong trường hợp dùng hàm băm ℎ = 푘%13 hãy xác định số lượng đụng độ với dãy khóa trên
b. Trước khi chia modulo cho 13 ta cộng giá trị các chữ số của khóa lại thì số lượng đụng độ là bao
(
)
nhiêu? Ví dụ với khóa có 3 chữu số abc thì hàm băm là ℎ = 푎 + 푏 + 푐 %13
c. Tìm một hàm băm hoàn hảo cho dãy khóa trên. Hàm băm hoàn hảo là hàm băm mà không xảy ra
đụng độ trên dãy khóa.
d. Hãy tìm một hàm băm hoàn hảo trong trường hợp kích thước bảng băm là 11
Bài 8. Một phương pháp khác phục đụng độ khác là dùng một bảng phụ để chứa các khóa mà bị đụng độ.
Các khóa trong bảng phụ có thể được lưu trữ theo kiểu 1 bảng băm phụ, hoặc đơn giản là lưu trữ tuần
tự. Hãy mô tả ưu nhược điểm của phương pháp này.
Bài 9. Hãy cài đặt các hàm thêm, xóa, và tìm kiếm phần tử trong trường hợp bảng băm đánh địa chỉ đóng
dùng xích ngăn cách.
Bài 10.Viết hàm xóa trong trường hợp bảng băm đánh địa chỉ mở dùng dò tuyến tính. Ta phải dùng một dấu
hiệu đặc biệt để đánh dấu phần tử đã bị xóa (phương pháp xóa trễ - lazy deletion).
Bài 11.Trong trường hợp hợp bảng băm đánh địa chỉ mở dùng dò tuyến tính, có cách nào khác để xóa phần
tử mà không phải dùng một giá trị đặc biệt để đánh dấu phần tử đó bị xóa hay không? Nếu trong trường
hợp xây dựng được thì hàm thêm và tìm kiếm phần tử có phải sửa đổi gì không?
2 trang
14980
Free
Bạn đang xem tài liệu "Bài tập Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm nâng cao", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_cau_truc_du_lieu_va_thuat_toan_chuong_6_tim_kiem_nan.pdf
