ÔN TẬP MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
I. Phần bài tập 1. Cho cây nhị phân, viết thứ tự các nút được thăm theo các thứ tự:
trước, giữa, sau. Ví dụ: A C B G F E D I H
2. Biết thứ tự duyệt cây nhị phân theo thứ tự trước và giữa, hãy dựng lại cây
nhị phân. Ví dụ thứ tự trước là: A B D E H C F I G, thứ tự giữa là: D B H E A F I C G.
3. Biết thứ tự duyệt cây nhị phân theo thứ tự giữa và sau, hãy dựng lại cây nhị
phân. Ví dụ thứ tự giữa là: D H B E A F C I G, thứ tự sau là: H D E B F I G C A.
4. Minh hoạ diễn biến từng bước khi áp dụng giải thuật sắp xếp nhanh
(QuickSort) với một dãy số, chọn chốt là phần tử đầu của mỗi phân đoạn. Ví dụ với
dãy số: 10, 7, 31, 12, 9, 30, 14.
5. Minh hoạ diễn biến từng bước khi 65
áp dụng giải thuật sắp xếp vun đống
(Heap Sort) đối với đống là cây nhị phân 45 35
như hình vẽ, với thứ tự các nút được tính
từ trên xuống dưới, từ trái qua phải. Ví dụ 20 25 12 với cây như hình vẽ:
6. Minh hoạ diễn biến từng bước khi áp dụng giải thuật sắp xếp hoà nhập
(Merge Sort) với một dãy số. Ví dụ với dãy số: 20, 12, 62, 9, 52, 17, 64, 68, 43, 81, 16.
7. Dựng cây nhi phân tìm kiếm với một dãy số nhập vào. Ví dụ với dãy số: 30,
17, 18, 15, 5, 15, 58, 6, 42, 23. 1
II. Phần giải thuật
1. Trình bày (bằng ngôn ngữ tựa C) giải thuật bổ sung một nút mới có chứa dữ
liệu X vào trước nút trỏ bởi Q trong danh sách móc nối hai chiều với: Pdau trỏ vào
phần tử đầu, Pcuoi trỏ vào phần tử cuối, mỗi nút có cấu trúc như sau: P_L Trỏ tới nút bên trái DATA Chứa dữ liệu P_R Trỏ tới nút bên phải
2. Trình bày (bằng ngôn ngữ tựa C) giải thuật loại bỏ một nút trỏ bởi Q trong
danh sách móc nối hai chiều với: Pdau trỏ vào phần tử đầu, Pcuoi trỏ vào phần tử
cuối, mỗi nút có cấu trúc như sau: P_L Trỏ tới nút bên trái DATA Chứa dữ liệu P_R Trỏ tới nút bên phải
3. Trình bày (bằng ngôn ngữ tựa C) giải thuật cộng 2 đa thức: C = A + B. Các
phần tử trong mỗi đa thức có cấu trúc như sau: HSO Ghi hệ số MU Ghi số mũ
NEXT Ghi địa chỉ đến phần tử tiếp theo
4. Trình bày (bằng ngôn ngữ tựa C) giải thuật định giá biểu thức hậu tố bằng
cách dùng STACK. Minh hoạ diễn biến của quá trình đọc biểu thức và sự thay đổi
trong STACK với biểu thức: 8 4 - 6 3 / + theo dạng:
Diễn biến đọc biểu thức Diễn biến STACK Thực hiện phép toán
5. Trình bày (bằng ngôn ngữ tựa C) giải thuật duyệt cây theo thứ tự trước bằng
giải thuật không đệ qui có sử dụng STACK. Mỗi nút trên cây có cấu trúc như sau: P_L Trỏ tới cây con trái DATA Chứa dữ liệu P_R Trỏ tới cây con phải
6. Trình bày (bằng ngôn ngữ tựa C) giải thuật duyệt cây theo thứ tự giữa bằng
giải thuật không đệ qui có sử dụng STACK. Mỗi nút trên cây có cấu trúc như sau: P_L Trỏ tới cây con trái DATA Chứa dữ liệu P_R Trỏ tới cây con phải
7. Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm nhị phân. Đánh giá thời
gian thực hiện giải thuật với dãy có n phần tử. 2
8. Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm có bổ sung trên cây nhị
phân tìm kiếm. Mỗi nút trên cây có cấu trúc như sau: P_L Trỏ tới cây con trái KEY Chứa giá trị khoá P_R Trỏ tới cây con phải
9. Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật đệ qui quay
lui tìm tất cả các cách đặt 8 quân hậu vào bàn cờ vua sao cho không quân nào ăn
quân nào. Khi trình bày giải thuật bằng ngôn ngữ tựa C có mô tả cách tổ chức dữ liệu trong giải thuật.
10. Trình bày (bằng ngôn ngữ tựa C) giải thuật cài đặt hàm đệ qui có dùng
STACK cho bài toán tính n!. Minh hoạ diễn biến của STACK, trong quá trình thực
hiện giải thuật ứng với n = 3, theo dạng: Số mức Các bước thực hiện Nội dung của STACK
11.Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật chuyển
đổi biểu thức dạng trung tố sang dạng hậu tố.
12. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp nhanh (Quick Sort).
Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử trong trường hợp tốt nhất.
13. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp vun đống (Heap Sort).
Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử.
14. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp hoà nhập (Merge Sort).
Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử.
15. Trình bày (bằng ngôn ngữ tựa C) giải thuật loại bỏ một nút có giá trị X trên
cây nhị phân tìm kiếm. Chi phí thời gian trung bình của giải thuật này có lớn hơn
giải thuật tìm kiếm rồi bổ sung hay không, vì sao? Mỗi nút trên cây có cấu trúc như sau: P_L Trỏ tới cây con trái KEY Chứa giá trị khoá P_R Trỏ tới cây con phải
16. Trình bày (bằng ngôn ngữ tự nhiên và ngôn ngữ tựa C) giải thuật Kiểm tra
cây nhị phân T có phải là "cây nhị phân tìm kiếm" hay không? Mỗi nút trên cây có cấu trúc như sau: P_L Trỏ tới cây con trái KEY Chứa giá trị khoá P_R Trỏ tới cây con phải 3 4
Document Outline

• ÔN TẬP MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
• II.Phần giải thuật