TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu và Giải Thuật
2022
1
Mục lục
Bài tập chương 1 .............................................................................................................. 3
Bài 1 – Dãy số nguyên ................................................................................................. 3
Bài 2 – Xây dựng số .................................................................................................... 3
Bài 3 – Mã hóa văn bản ............................................................................................... 3
Bài 4 – Mã hóa và giải mã ........................................................................................... 4
Bài 5 – Số siêu nguyên tố ............................................................................................ 4
Bài 6 – Tính A(m, n) ................................................................................................... 5
Bài 7 – Tìm ước chung lớn nhất .................................................................................. 5
Bài 8 – Đếm chữ số của số nguyên dương N .............................................................. 5
Bài tập chương 2 .............................................................................................................. 6
Bài 1 – Tạo ma trận số ................................................................................................. 6
Bài 2 – Chuỗi đối xứng................................................................................................ 6
Bài 3 – Đặt dấu * vào ma trận ..................................................................................... 6
Bài 4 – Quân mã đi tuần .............................................................................................. 7
Bài 5 – Tối ưu hóa lưu trữ ........................................................................................... 7
Bài 6 – Lưu trữ đa thức................................................................................................ 7
Bài 7 – Điều tra mức thu nhập trung bình ................................................................... 8
Bài 8 – Thống kê kết quả kinh doanh .......................................................................... 9
Bài 9 – Thống kê kết quả kinh doanh theo giá bán lẻ từng tháng ............................. 10
Bài tập chương 3 ............................................................................................................ 12
Bài 1 – Xử lý trên danh sách liên kết đơn ................................................................. 12
Bài 2 – Xử lý trên danh sách liên kết kép .................................................................. 12
Bài 3 – Tổ chức lưu trữ đa thức trên danh sách móc nối đơn ................................... 13
Bài 4 – Xử lý nâng cao trên danh sách móc nối đơn ................................................. 13
Bài 5 – Xử lý nâng cao trên danh sách móc nối kép ................................................. 13
Bài 6 – Tạo dãy số nguyên tố tăng dần ..................................................................... 14
Bài 7 – In giá trị các nút theo thứ tự ngược ............................................................... 14
Bài 8 – Quản lý học viên ........................................................................................... 14
Bài 9 – Lưu trữ văn bản ............................................................................................. 16
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu và Giải Thuật
2022
2
Bài tập chương 4 ............................................................................................................ 19
Bài 2 – Cây nhị phân biểu diễn biểu thức số học ...................................................... 19
Bài 3 – Tìm cây nhị phân giống nhau........................................................................ 20
Bài 4 – Khử đệ quy các phép duyệt cây nhị phân ..................................................... 20
Bài 5 – Tạo bản sao cây nhị phân .............................................................................. 20
Bài 6 – Đánh tráo con trái và con phải của cây nhị phân .......................................... 20
Bài 7 – Tính chiều cao cây nhị phân ......................................................................... 20
Bài 8 – Xác định mức của một nút ............................................................................ 21
Bài 9 – Tính số lượng nút trên cây ............................................................................ 21
Bài 10 – Duyệt cây nhị phân theo mức ..................................................................... 21
Bài 11 – Dựng cây nhị phân từ kết quả duyệt ........................................................... 21
Bài 12 – Chuyển đổi cơ chế lưu trữ cây nhị phân ..................................................... 21
Bài 13 – Xây dựng cây nhị phân tìm kiếm ................................................................ 22
Bài 14 – Dựng cây nhị phân ...................................................................................... 23
Bài tập chương 5 ............................................................................................................ 24
Bài 1 - Biểu diễn đồ thị trên máy tính ....................................................................... 24
Bài 2 – Duyệt đồ thị ................................................................................................... 24
Bài 3 – Duyệt đồ thị trên danh sách lân cận .............................................................. 24
Bài 4 – Đếm số miền liên thông của đồ thị ............................................................... 24
Bài 5 – Kiểm tra đường đi từ u tới v ......................................................................... 25
Bài 6 – Tìm đường đi ngắn nhất ................................................................................ 25
Bài tập chương 6 ............................................................................................................ 25
Bài 1 – Sắp xếp dãy khóa .......................................................................................... 25
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu và Giải Thuật
2022
3
Bài tập chương 1
Bài 1 – Dãy số nguyên
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314… (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
Anh chị hãy viết chương trình tính toán kết quả
Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên
màn hình kết quả là số nằm ở vị trí thứ K trong dãy (1) trên. Yêu cầu chương trình
chạy càng nhanh càng tốt.
Bài 2 – Xây dựng số
Cho các số sau: 1, 2, 3, 5, 7
Chỉ dùng phép toán cộng hãy dùng dãy trên để tạo ra số: 43, 52
Ví dụ để tạo ra số 130 có thể làm như sau: 123 + 7 = 130.
Bài 3 – Mã hóa văn bản
Bài toán sau mô tả một thuật toán mã hóa đơn giản (để tiện ta lấy ví dụ tiếng anh, các
anh chị có thể mở rộng cho tiếng việt):
Tập hợp các chữ cái tiếng Anh bao gồm 26 chữ cái được đánh số thứ tự từ 0 đến 25
như sau:
0
1
2
3
4
5
6
7
8
9
10
11
12
A
B
C
D
E
F
G
H
I
J
K
L
M
13
14
15
16
17
18
19
20
21
22
23
24
25
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
Quy tắc mã hóa một ký tự như sau (Lấy ví dụ ký tự X):
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu và Giải Thuật
2022
4
Tìm số thứ tự tương ứng của ký tự X ta được 23
Tăng giá trị số này lên 5 ta được 28
Tìm số dư trong phép chia số này cho 26 ta được 2
Tra ngược bảng chữ cái ta được C
a. Sử dụng quy tắc trên để mã hóa các dòng chữ sau:
PEACE
HEAL THE WORLD
I LOVE SPRING
b. Hãy tìm ra quy tắc giải mã các dòng chữ sau:
N FR F XYZIJSY
NSKTVRFYNHX
MFSTN SFYNTSFQ ZSNBJVXNYD
Bài 4 – Mã hóa và giải mã
Theo quy tắc mã hóa ở bài trên (bài 3), hãy viết chương trình cho phép:
Nhập một xây ký tự và in ra xấy ký tự đã được mã hóa
Nhập vào một xâu ký tự đã được mã hóa và in ra xâu ký tự đã được giải mã
Ví dụ:
Nhap xau ky tu:
PEACE
Xau ky tu tren duoc ma hoa la:
UJFHJ
Bài 5 – Số siêu nguyên tố
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tùy ý các chữ số bên phải của nó
thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ : 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên
tố.
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu và Giải Thuật
2022
5
Nhiệm vụ của các anh/chị là viết chương trình nhập dữ liệu vào là một số nguyên N (0
< N < 10) và đưa ra kết quả là số nguyên tố có N chữ số cùng số lượng của chúng.
Ví dụ khi chạy chương trình :
Nhap so N : 4
Cac so sieu nguyen to co 4 chu so la: 2333 2339 2393 2399 2939 3119 3137 3773
3739 3793 3797 5939 7193 7333 7393
Tat ca co 16 so
Bài 6 – Tính A(m, n)
Viết chương trình để tính giá trị của hàm A(m, n) được cho bởi định nghĩa đệ quy sau
đây:
n + 1
Nếu m = 0
A(m, n) =
A(m-1, 1)
Nếu n = 0
A(m-1, A(m, n-1)
Với các trường hợp khác
Bài 7 – Tìm ước chung lớn nhất
Giải thuật tìm ước chung lớn nhất của hai số nguyên dương p và q được mô tả như
sau:
Gọi r là số dư của phép chia p và q
Nếu r ≠ 0 thì gán cho p giá trị của q và gán cho q giá trị của r. Quay lại bước 1
Return(q)
Xây dựng một định nghĩa đệ quy cho hàm ULCN(p, q) và viết giải thuật tìm ước chung
lớn nhất của p và q theo định nghĩa này.
Bài 8 – Đếm chữ số của số nguyên dương N
Viết giải thuật để đếm số chữ số của số nguyên dương N cho trước, bằng hai cách:
dùng đệ quy và không dùng đệ quy.