�ݺ�ߣ

CÁC BÀI THỰC HÀNH
BÀI THỰC TẬP SỐ 1
Bài Thực Tập Số 1 : CÀI ÐẶT DANH SÁCH BẰNG MẢNG
TOP
• Viết chương trình quản lý dòng văn bản.
Yêu cầu chi tiết:
1. Viết phần khai báo để cài đặt một dòng văn bản (nội dung của văn bản là các ký tự,
chiều dài tối đa của 1 dòng là 80 ký tự).
2. Viết thủ tục khởi tạo dòng rỗng
3. Thiết kế hàm kiểm tra dòng rỗng.
4. Thiết kế hàm kiểm tra dòng đầy.
5. Viết thủ tục nhập một dòng văn bản.
6. Viết thủ tục hiển thị dòng văn bản ra màn hình.
7. Viết thủ tục xen một ký tự x vào vị trí thứ p nào đó trong dòng văn bản D.
8. Viết thủ tục xóa một ký tự tại vị trí thứ p nào đó ra khỏi dòng văn bản D.
9. Thiết kế hàm copy một dòng văn bản để có một dòng văn bản mới. Copy k ký tự từ
dòng D sang dòng D1 bắt đầu từ vị trí p trong dòng D (Không sử dụng hàm chuẩn của
Pascal).
10. Viết hàm tìm vị trí của phần tử đầu tiên trong dòng văn bản có nội dung là x.
11. Viết thủ tục thay thế tất cả các ký tự c trong dòng văn bản D bằng ký tự c1.
12. Thiết kế hàm hoặc thủ tục lấy nội dung của phần tử thứ p trong dòng.

13. Viết thủ tục xóa tất cả các ký tự c trong dòng văn bản D.
14. Viết thủ tục cắt các khoảng trắng dư (các khoảng trắng không cần thiết) giữa 2 ký tự
trong một dòng.
15. Thiết kế hàm kiểm tra dòng văn bản D1 có phải là dòng con của dòng văn bản D hay
không.
• Viết chương trình nhập một dòng văn bản từ bàn phím, cắt tất cả các khoảng
trống không cần thiết trong dòng này. Thay thế ký tự đầu dòng bằng ký tự hoa.
Chép dòng văn bản này sang dòng mới để khi thao tác thì dòng văn bản cũ không
bị mất đi.
• Trên dòng văn bản mới ta thực hiện các thao tác sau đây:
Xen một ký tự mới vào dòng.
Xóa một ký tự ra khỏi dòng.
Thay thế tất cả các ký tự nào đó trong dòng bằng ký tự mới.
Xóa tất cả các ký tự c trong dòng (c được nhập từ bàn phím).
Nhập một dòng văn bản mới và kiểm tra xem dòng văn bản này có phải là dòng
con của dòng văn bản đang lưu trữ hay không?
Bài Thực tập số 2: CÀI ÐẶT DANH SÁCH LIÊN KẾT BẰNG CON TRỎ
TOP
A. DANH SÁCH LIÊN KẾT ÐƠN
Viết chương trình lưu trữ đa thức có dạng:
1. Viết các khai báo cần thiết để cài đặt một đa thức như trên.
2. Viết thủ tục khởi tạo một đa thức rỗng.
3. Viết hàm kiểm tra đa thức rỗng.
4. Xen một phần tử mới x vào đa thức D sau vị trí p.

5. Xóa một phần tử x sau vị trí p ra khỏi đa thức D.
6. Viết thủ tục nhập một đa thức.
7. Thiết kế hàm kiểm tra tính chuẩn hóa của đa thức (ứng với mỗi cấp số mũ thì chỉ có
duy nhất một hệ số a tương ứng với nó).
Ví dụ : 2x3 + 3x3 Sai. Ta phải viết thành: 5x3
8. Thiết lập một hàm chuyển đa thức về dạng chuẩn hóa.
9. Viết thủ tục hiển thị đa thức ra màn hình.
10. Viết thủ tục sắp xếp đa thức theo thứ tự giảm dần của số mũ.
11. Viết thủ tục cộng 2 đa thức D1 và D2 thành đa thức D3
12. Viết thủ tục trừ 2 đa thức D1 và D2 thành đa thức D3
13. Viết thủ tục nhân 2 đa thức D1 và D2 thành đa thức D3
14. Viết hàm tính giá trị của đa thức với giá trị đã cho của x được nhập từ bàn phím.
Viết chương trình nhập vào một đa thức rồi thực hiện các yêu cầu sau:
Hiển thị đa thức đã nhập.
Xen một phần tử mới vào đa thức.
Xóa một phần tử khỏi đa thức.
Chuẩn hóa đa thức, hiển thị đa thức sau khi đã chuẩn hóa (nếu đa thức là
đa thức chưa chuẩn hóa).
Sắp xếp đa thức theo số mũ giảm dần, hiển thị đa thức sau khi đã sắp xếp.
Nhập vào 2 đa thức D1, D2 và thực hiện các phép toán cộng, trừ, nhân
trên hai đa thức này. Hiển thị kết quả của mỗi phép toán để kiểm tra.
Nhập giá trị cho biến x và tính giá trị của đa thức.
B. DANH SÁCH LIÊN KẾT KÉP
Viết chương trình lưu trữ một danh sách các số nguyên, sắp xếp danh sách theo
thứ tự (tăng hoặc giảm), trộn 2 danh sách có thứ tự để được một danh sách mới có thứ tự.

1. Viết các khai báo cần thiết để cài đặt một danh sách các số nguyên.
2. Viết thủ tục khởi tạo một danh sách rỗng.
3. Viết hàm kiểm tra danh sách rỗng.
4. Viết thủ tục nhập một danh sách.
5. Viết thủ tục hiển thị danh sách ra màn hình.
6. Viết thủ tục sắp xếp danh sách theo thứ tự (tăng hoặc giảm).
7. Xen một phần tử mới x vào danh sách sau cho danh sách mới vẫn bảo đảm thứ tự.
8. Xóa một phần tử x ra khỏi danh sách sao cho danh sách mới vẫn bảo đảm thứ tự.
9. viết thủ tục trộn 2 danh sách đã có thứ tự thành một danh sách mới sao cho danh sách
mới vẫn bảo đảm thứ tự.
Viết chương trình nhập vào một danh sách các số nguyên và thực hiện các yêu cầu
sau:
Hiển thị danh sách vừa nhập.
Sắp xếp danh sách theo thứ tự. Hiển thị danh sách sau khi sắp xếp.
Xen một phần tử mới vào danh sách. Hiển thị danh sách mới sau khi xen.
Xóa một phần tử khỏi danh sách. Hiển thị danh sách mới sau khi xóa.
Nhập 2 danh sách, sắp xếp 2 danh sách theo thứ tự, sau đó trộn 2 danh
sách này để được một danh sách mới cũng có thứ tự. Hiển thị danh sách mới ra màn hình
để kiểm tra.
Bài Thực Tập Số 3 : CẤU TRÚC NGĂN XẾP (STACK) & HÀNG (QUEUE)
TOP
Ứng dụng ngăn xếp (Stack) và hàng Queue để viết chương trình biến đổi
biểu thức trung tố thành tiền tố và hậu tố.
Viết chương trình tính giá trị của biểu thức tiền tố và hậu tố.
1. Viết các khai báo cần thiết để cài đặt một Stack, một Queue.
2. Viết thủ tục khởi tạo một Stack rỗng.

3. Viết hàm kiểm tra Stack rỗng.
4. Viết thủ tục thêm một phần tử vào Stack.
5. Viết thủ tục xóa một phần tử khỏi Stack.
6. Viết chương trình con lấy nội dung của phần tử tại đỉnh của Stack.
7. Viết thủ tục khởi tạo một Queue rỗng.
8. Viết hàm kiểm tra Queue rỗng.
9. Viết thủ tục thêm một phần tử vào Queue.
10. Viết thủ tục xóa một phần tử khỏi Queue.
11. Viết chương trình con lấy nội dung của phần tử tại đỉnh của Queue.
12. Viết chương trình con đổi biểu thức từ dạng trung tố sang dạng tiền tố.
13. Viết chương trình con đổi biểu thức từ dạng trung tố sang dạng hậu tố.
14. Viết chương trình con tính giá trị của biểu thức tiền tố.
15. Viết chương trình con tính giá trị của biểu thức hậu tố.
• Giải thuật chuyển đổi biểu thức từ dạng trung tố sang dạng hậu tố
Procedure HAUTO ( BT: Biểu thức trung tố ; Var HT: Hàng chứa biểu thức hậu tố sau
khi đổi }
Begin
MakeNullS(S); { Tạo một Stack rỗng }
MakeNullQ(S); { Tạo một Queue rỗng }
x = Phần tử đầu tiên trong biểu thức trung tố
While chưa xét hết biểu thức trung tố do
Begin
If x = '(' then Push (x,S) { thêm x vào Stack }
If x = ')' then

Begin
While (Not Empty(S)) and (Top(S)<> '(') do
Begin
Y:= Top (S); EnQueue(y,Q); {Thêm Y vào hàng}
Pop(S); {xóa phần tử tại đỉnh Stack}
End;
If EmptyS(S) then báo lỗi Stack rỗng
Else Pop(S) { xóa phần tử tại đỉnh Stack }
End; { If }
If < x là một toán tử > then
If EmptyS(S) then Push (x,S) {thêm x vào Stack}
Else
Begin
While (Uutien(Top(S))<=Uutien(x))and (Top(S)<>'(') do
Begin
Y:= Top(S);
Enqueue(Y,Q);
Pop(S);
End;
Push(x,S);
End;
If < x là một toán hạng > then
EnQueue(x,Q);
X = phần tử kế tiếp trong biểu thức trung tố

End; { While }
While Not EmptyS(S) do
Begin
Y:= Top(S);
Enqueue(Y,Q);
Pop(S);
End;
End; { Thủ tục }
• Trong đó hàm Uutien trả về thứ tự ưu tiên của các toán tử như sau:
Toán tử ( , ) * , / + , -
Thứ tự ưu tiên 1 2 3
Bài Thực Tập Số 4 : CẤU TRÚC CÂY
TOP
( Cây Nhị Phân - Cây Biểu Thức - Cây Tìm Kiếm Nhị Phân )
A. CÂY BIỂU THỨC
Viết chương trình cài đặt một cây biểu thức, tính trị của cây biểu thức này.
1. Viết phần khai báo để cài đặt một cây biểu thức.
2. Viết thủ tục khởi tạo cây rỗng.
3. Viết hàm kiểm tra cây rỗng.
4. Thiết kế hàm tạo cây từ cây con trái L, cây con phải R và nhản của nút n, bằng cách
xem đây là có nút gốc là n và 2 cây con tương ứng là L (con trái) và R (con phải).
5. Viết các thủ tục duyệt cây:
Duyệt tiền tự, trung tự, hậu tự .
Duyệt theo mức.

6. Viết hàm xác định số nút trong cây.
7. Thiết kế hàm xác định chiều cao của cây.
8. Viết hàm tính giá trị của cây biểu thức.
9. Viết hàm xác định mức của một nút trong cây.
B. CÂY TÌM KIẾM NHỊ PHÂN
Viết chương trình cài đặt một cây tìm kiếm nhị phân (nhãn của mỗi nút được nhập
từ bàn phím) .
1. Viết phần khai báo để cài đặt một cây tìm kiếm nhị phân.
4. Viết thủ tục xen một nút vào cây tìm kiếm nhị phân.
5. Viết thủ tục xóa một nút trong cây tìm kiếm nhị phân.
6. Viết thủ tục nhập một cây tìm kiếm nhị phân với nhản của các nút của cây được nhập
vào từ bàn phím.
Duyệt tiền tự, trung tự, hậu tự .
Duyệt theo mức.
10. Viết hàm xác định mức của một nút trong cây.
Bài Thực Tập Số 5 : CẤU TRÚC CÂY ( Cây Tổng Quát)
TOP
( Viết chương trình cài đặt một cây tổng quát ( dùng mảng hay con trỏ ).

1. Viết phần khai báo để cài đặt một cây.
4. Viết thủ tục nhập một cây với nhản của các nút của cây được nhập từ bàn phím.
Duyệt tiền tự.
Duyệt trung tự.
Duyệt hậu tự.
Duyệt theo mức.
8. Viết hàm xác định mức của một nút trong cây (nút đầu tiên có nhản cần xác định).
9. Thiết lập một hàm kiểm tra sự hiện hữu của một nút nào đó trong cây.
10. Thiết lập hàm xác định nhản của nút con trái nhất của một nút với nhản của nút được
nhập từ bàn phím.
11. Thiết lập hàm xác định nhản của nút anh ruột phải của một nút với nhản của nút
được nhập từ bàn phím.
12. Thiết lập hàm xác định nhản của nút cha của một nút với nhản của nút với nhản của
nút được nhập từ bàn phím.
Bài Thực Tập Số 6: CẤU TRÚC TẬP HỢP- TỰ ÐIỂN - BẢNG BĂM
TOP
A. CÀI ÐẶT TỰ ÐIỂN ANH - VIỆT
( Viết chương trình cài đặt một tự điển Anh - Việt đơn giản. ( có thể dùng bảng
băm đóng hay mở để giải quyết đụng độ).
1. Viết phần khai báo để cài đặt một tự điển Anh Việt.

2. Viết thủ tục khởi tạo tự điển rỗng.
3. Viết hàm kiểm tra tự điển rỗng.
4. Viết thủ tục nhập nội dung cho tự điển.
5. Thiết lập thủ tục thêm một từ mới vào tự điển.
6. Thiết lập thủ tục xóa một từ ra khỏi tự điển.
7. Viết hàm xác định sự tồn tại của một từ trong tự điển.
8. Tra cứu tự điển. Nhập từ cần tìm bằng tiếng Việt từ màn hình, hiển thị ý nghĩa bằng
tiếng Anh của từ đó ra màn hình.
B. CÀI ÐẶT TẬP HỢP
Viết chương trình cài đặt tập hợp các ký tự (độ dài tối đa 8 ký tự). Nhập vào 2 tập
hợp, tìm tập hợp giao, hợp, hiệu của 2 tập hợp đã cho và hiển thị kết quả ra màn hình để
kiểm tra.
1. Viết phần khai báo để cài đặt một tập hợp.
2. Viết thủ tục khởi tạo tập hợp rỗng.
3. Viết hàm kiểm tra tập hợp rỗng.
4. Viết thủ tục nhập nội dung cho tập hợp.
5. Thiết kế hàm kiểm tra thành viên của tập hợp.
6. Thiết kế thủ tục xen một phần tử mới vào tập hợp.
7. Viết thủ tục hiển thị nội dung của tập hợp ra màn hình.
8. Thiết kế thủ tục tìm hợp của 2 tập hợp.
9. Thiết kế thủ tục tìm giao của 2 tập hợp.
10. Thiết kế thủ tục tìm hiệu của 2 tập hợp.
<BACK NEXT>

�ݺ�ߣ

Bài tập CTDL và GT 11

More Related Content

Bài tập CTDL và GT 11