Bài tập về tập hợp

1. Viết các khai báo cấu trúc dữ liệu và các thủ tục/hàm cho các phép toán trên tập hợp để cài đặt tập hợp kí tự (256 kí tự ASCII) bằng vectơ bít.

2. Viết các khai báo cấu trúc dữ liệu và các thủ tục/hàm cho các phép toán trên tập hợp để cài đặt tập hợp các số nguyên bằng danh sách liên kết có thứ tự.

3. Giả sử bảng băm có 7 bucket, hàm băm là h(x)= x mod 7. Hãy vẽ hình biểu diễn bảng băm khi ta lần lượt đưa vào bảng băm rỗng các khoá 1,8, 27, 64, 125, 216, 343 trong các trường hợp:

- Dùng bảng băm mở.

- Bảng băm đóng với chiến lược giải quyết đụng độ là phép thử tuyến tính.

4. Cài đặt bảng băm đóng, với chiến lược băm lại là phép thử cầu phương. Tức là hàm băm lại lần thứ i có dạng h_i = (h(x)+i2) mod B.

5. Giả sử trong một tập tin văn bản ta có các kí tự đặc biệt sau:

BLANK=32 là mã ASCII của kí tự trống

CR = 13 là mã ASCII kí tự kết thúc dòng

LF = 10 là mã ASCII kí tự kết xuống dòng

EOF= 26 là mã ASCII kí tự kết thúc tập tin

Một từ (word) trong văn bản được định nghĩa là một chuỗi gồm các kí tự không chứa kí tự đặc biệt nào. Hơn nữa kí tự trước chuỗi trong văn bản hoặc không có hoặc là kí tự đặc biệt và kí tự sau chuỗi là kí tự đặc biệt.

Viết chương trình thành lập một từ điển gồm các từ trong văn bản bằng một bảng băm mở. Bằng cách đọc từng kí tự của một tập tin văn bản cho đến hết văn bản, khi đọc phải thiết lập từ để khi gặp kí tự đặc biệt (hết từ) thì đưa từ đó vào bảng băm đưa vào bảng băm nếu nó chưa có trong bảng. Hàm băm có thể chọn như hàm băm chuỗi 10 kí tự trong bài học.

6. Viết chương trình dùng cấu trúc bảng băm mở để cài đặt một từ điển tiếng Anh đơn giản. Giả sử mỗi mục từ trong từ điển chỉ gồm có từ tiếng Anh và phần giải nghĩa của từ này. Cấu trúc mỗi mục từ như sau:

Mẩu tin item gồm có 2 trường:

Word: kiểu chuỗi ký tự để lưu từ khóa cần tra;

Explanation: kiểu chuỗi ký tự giải thích cho từ khóa;

Tạo giao diện đơn giản để người dùng nhập các từ vào từ điển. Lưu trữ từ điển trong bảng băm và tạo một giao diện đơn giản cho người dùng có thể tra từ. Chương trình phải cạnh cấp cơ chế lưu các từ đã có trong từ điển lên đĩa và đọc lại từ đĩa một từ điển có sẵn.

7. Vẽ cây có thứ tự từng phần được thiết lập bằng cách lần lượt đưa vào cây rỗng các khoá 5,9,6,4,3,1,7

8. Ta thấy rằng nếu ta lần lượt thực hiện DELETEMIN trên cây có thứ tự từng phần thì ta sẽ có một dãy các khoá có thứ tự tăng. Hãy dùng ý tưởng này để sắp xếp 1 dãy các số nguyên.

9. Giả lập việc quản lí các tiến trình thời gian thực (real-time processes):

Giả sử hệ điều hành phải quản lí nhiều tiến trình khác nhau, mỗi tiến trình có một độ ưu tiên khác nhau được tính theo một cách nào đó. Để đơn giản ta giả sử rằng mỗi tiến trình được quản lí như là một record có hai trường:

Name: chuỗi ký tự;

Priority: số thực ghi nhận mức độ ưu tiên của tiến trình;

Hãy cài đặt một hàng ưu tiên để quản lí các tiến trình này. Độ ưu tiên của các tiến trình dựa trên giá trị trường priority.