Bài tập cấu trúc dữ liệu
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (129.07 KB, 2 trang )
Cấu Trúc Dữ Liệu Bài Tập Chương 2 – Phần 1
1
BAØI TAÄP CHÖÔNG 2 (1)
(Danh sách đặc và liên kết đơn)
1. Viết chương trình cài đặt và thực hiện các phép toán như thêm, xóa, tìm kiếm, …
các phần tử trên danh sách đặc.
2. Viết chương trình tạo một DSLK đơn với các phần tử là các số nguyên dương. Sau
đó thực hiện các yêu cầu sau:
a) In nội dung các phần tử trong danh sách. Tính trung bình cộng các phần tử
trong danh sách.
b) Tìm kiếm giá trị một phần tử trong DSLK. Nếu tìm thấy thì thêm ngay sau
phần tử đó một phần tử mới có giá trị được nhập từ bàn phím.
c) Hoán đổi vị trí của phần tử đã tìm thấy và phần tử mới trong câu b).
d) In nội dung các phần tử trong danh sách đã thực hiện ở câu c). Sau khi in
xong, các phần tử trong danh sách bị xóa.
3. Viết chương trình tạo một DSLK đơn với các phần tử có giá trị nguyên dương, sau
đó in nội dung các phần tử này theo thứ tự như lúc nhập.
4. Viết chương trình tạo một DSLK đơn với các phần tử có giá trị nguyên dương.
Sau đó, nhập vị trí
k
của phần tử cần tìm trong danh sách (giả sử vị trí tính từ 0),
xoá phần tử đứng trước phần tử
k
, in danh sách sau khi xóa.
5. Viết chương trình tạo một DSLK đơn với các phần tử có giá trị nguyên dương.
Sau đó, nhập giá trị của phần tử cần tìm. Nếu tìm thấy thì tách danh sách này
thành hai danh sách con (danh sách con thứ hai bắt đầu từ phần tử vừa tìm được),
in hai danh sách kết quả. Ngược lại, nếu không tìm thấy thì thông báo không tìm
thấy phần tử có giá trị đã nhập.
6. Viết chương trình tạo một DSLK, sau đó xét xem danh sách này có tính tăng dần,
giảm dần hay không có thứ tự.
7. Viết chương trình tạo một DSLK đơn với các phần tử là các số nguyên dương theo
thứ tự tăng dần. Sau đó, thực hiện các yêu cầu sau:
a) In nội dung các phần tử trong danh sách.
b) Đổi thành một danh sách có thứ tự giảm dần (không tạo thêm danh sách mới).
c) In nội dung các phần tử trong danh sách đã đổi. Sau khi in, xoá các phần tử
trong danh sách.
8. Viết chương trình tạo hai DSLK đơn là
L1
và
L2
với các phần tử nguyên dương.
Sau đó, ghép hai danh sách này lại (
L1
trước
L2
sau) thành danh sách chung là
L3
.
Giả sử rằng
L1
và
L2
tất cả đều có thể rỗng. In nội dung của danh sách đã ghép.
9. Viết chương trình tạo hai DSLK đơn là
L1
và
L2
với các phần tử nguyên dương có
giá trị tăng dần. Sau đó, tạo danh sách liên kết thứ ba
L3
là kết quả trộn các phần
tử của hai danh sách trên (cũng có thứ tự tăng dần). In nội dung của danh sách thứ
ba này.
Cấu Trúc Dữ Liệu Bài Tập Chương 2 – Phần 1
2
10. Viết chương trình tạo hai DSLK đơn là
L1
và
L2
với các phần tử nguyên dương.
Sau đó, in kết quả của phép giao, hội và hiệu của hai danh sách này. Lưu ý rằng
hai danh sách ban đầu không bị thay đổi.
11. Giả sử chúng ta muốn thao tác trên đa thức có dạng
Trong đó,
e
1
>
e
2
>
...
>
e
n
≥
0
. Đa thức trên có thể được biểu diễn bởi danh
sách liên kết với mỗi phần tử gồm ba trường: Hệ số
c
i
, số mũ
e
i
, và một con trỏ
để trỏ đến phần tử kế tiếp. Viết chương trình để cộng và nhân hai đa thức.
