Bài tập Cấu trúc dữ liệu và thuật toán
Tài liệu học tập môn Cấu trúc dữ liệu và thuật toán tại trường Đại học khoa học Huế giúp bạn học tập, ôn luyện và đạt điểm cao!
Môn: Cấu trúc dữ liệu và thuật toán
Trường: Trường Đại học Khoa học, Đại học Huế
Thông tin:
Tác giả:
Thông tin :
Môn:
Cấu trúc dữ liệu và thuật toán
Trường:
Trường Đại học Khoa học, Đại học Huế
Tác giả:
Preview text:
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 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 1
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
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 2
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 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): 3
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
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ố. 4
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
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. 5
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 Bài tập chương 2
Bài 1 – Tạo ma trận số
Cho trước số nguyên dương N bất kỳ. Hãy viết thuật toán và chương trình để tạo lập
bảng NxN phần tử nguyên dương theo quy luật được cho trong ví dụ sau: 1 2 3 4 5 6 2 4 6 8 10 12 3 6 9 12 2 4 4 8 12 2 4 6 5 10 2 4 6 8 6 12 4 6 8 10
Thực hiện chương trình với N = 12, đưa ra màn hình ma trận kết quả (như ví dụ).
Bài 2 – Chuỗi đối xứng
Một chuỗi ký tự St được gọi là đối xứng nếu từng cặp ký tự cách đều hay đầu mút đều
giống nhau. Ví dụ Các chuỗi “abcddcba” và “abcdedcba” là đối xứng, chuỗi
“abcdcda” là không đối xứng.
Hãy viết một giải thuật, bằng hai cách: dùng đệ quy và không dùng đệ quy, để kiểm tra
một chuỗi St cho trước có đối xứng hay không? Nếu có thì cho ra True, nếu không thì cho ra False.
Bài 3 – Đặt dấu * vào ma trận
Lập giải thuật để đặt các dấu * vào trong mảng hai chiều A[1..n, 1..n] sao cho trên mỗi
cột và trên mỗi dòng chỉ có đúng một dấu *.
Lập giải thuật để đặt các dấu * vào trong mảng hai chiều A[1..n, 1..n] sao cho trên mỗi
cột và trên mỗi dòng có đúng hai dấu * 6
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Bài 4 – Quân mã đi tuần
Cho quân mã đứng tại ô (u, v) trên bàn cờ vua. Hãy lập giải thuật để di chuyển quân
mã trên bàn cờ (di chuyển đúng luật cờ vua : đi chéo ô) sao cho quân mã đi hết tất cả
các ô trên bàn cờ, mỗi ô đi qua đúng một lần.
Bài 5 – Tối ưu hóa lưu trữ
Một ma trận vuông A, cấp n, các phần tử không nằm trên đường chéo chính và không
nằm trên hai đường chéo sát đường chéo chính đều bằng 0 (tức là A[i, j] = 0 nếu |i – j|
> 1. Ví dụ với n = 5 thì ma trận A có dạng a11 a12 0 0 0 a21 a22 a23 0 0 A = 0 a32 a33 a34 0 0 0 a43 a44 a45 0 0 0 a54 a55
Để tiết kiệm bộ nhớ người ta chỉ lưu trữ các phần tử trên đường chéo chính và hai
đường chéo sát đường chéo chính dưới dạng một Vector B theo thứ tự ưu tiên hàng như sau : B a11 a12 a21 a22 a23 a32 a33 a34 ……….. 1 2 3 4 5 6 7 8 ………..
Hãy lập giải thuật xác định giá trị của A[i, j] từ vector B.
Ví dụ: giá trị của A[2, 3] là B[5].
Bài 6 – Lưu trữ đa thức
Cho đa thức bậc n dạng p(x) = anxn + an-1xn-1 + … + a1x + a0. Để lưu trữ đa thwucs ta
dùng một vector có n + 2 phần tử biểu diễn đa thức theo dạng :
(n, an, an-1, an-2, …, a1, a0)
Cách lưu trữ trên có ưu, nhược điểm gì ? 7
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Ta thay đổi cách lưu trữ lại như sau : Dùng một vector để lưu trữ số đơn thức có
hệ số khác 0, mỗi đơn thức lưu trữ mũ và hệ số theo thứ tự lùi. Ví dụ đa thức x1000
– 4x10 + 5 thì vector biết diễn đa thức là: (3, 1000, 1, 10, -4, 0 ,5). Cách lưu trữ này
có ưu, nhược điểm gì ? Viết một giải thuật cộng hai đa thức được lưu trữ dưới dạng này.
Bài 7 – Điều tra mức thu nhập trung bình
Người ta dùng mảng hai chiều để lưu trữ kết quả một cuộc điều tra về mức thu nhập
trung bình/ người/ tháng của dân cư 61 tỉnh thành trong cả nước. Mức thu nhập được
phân loại theo nhóm từ 1 đến 10 triệu. Kết quả cho trong bảng sau đây: 1 Triệu 2 Triệu … 10 Triệu Hà Nội 2.000.000 1.000.000 … 4.000.000 Hải Phòng 3.000.000 2.000.000 … 6.000.000 Đà Nẵng 1.000.000 1.000.000 … 1.000.000 … … Hà Nam 1.000.000 500.000 … 50.000 ∑
Bảng 2.1: Điều tra mức thu nhập dân cư
Giá trị trong các ô của bảng là số người có mức thu nhập ở các mức tương ứng. Lập giải thuật:
Xác định địa phương có số người nhiều nhất trong mỗi mức thu nhập.
Xác định mức thu nhập có số người đông nhất của mỗi tỉnh.
Tính tỷ trọng của những người có mức thu nhập 1.000.000 so với tổng số người điều tra.
Viết chương trình minh họa với mức thu nhập bình quân đầu người từ 1 – 10 triệu
đồng trong 5 tỉnh bất kỳ. Sử dụng phương pháp nhập dữ liệu trực tiếp (hoặc gián tiếp). 8
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Bài 8 – Thống kê kết quả kinh doanh
Giả sử kết quả kinh doanh của một trung tâm thương mại trong 6 tháng đầu năm được
biểu diễn trong bảng thống kê sau : Tên CH Tiền hàng 1 Tiền hàng 2 … Tiền hàng 10 CH1 90.000.000 40.000.000 … 5.400.000 CH2 40.000.000 50.000.000 … 6.500.000 … … … CH5 60.000.000 50.000.000 … 9.700.000
Bảng 2.2. Thống kê kết quả kinh doanh 6 tháng đầu năm 1998 (Triệu đồng) Tên CH Tiền hàng 1 Tiền hàng 2 … Tiền hàng 10 CH1 80.000.000 30.000.000 … 1.000.000 CH2 30.000.000 30.000.000 … 2.000.000 … … … CH5 40.000.000 60.000.000 … 4.000.000
Bảng 2.3. Thống kê kết quả kinh doanh 6 tháng cuối năm 1998 (Triệu đồng).
Để tính toán kết quả kinh doanh trong cả năm 1998 của công ty thương mại theo đơn
vị của hàng ta lần lượt cộng từng giá trị tương ứng trong hai biểu trên đây. Kết quả thu
được ở bảng thống kê sau. Tên CH Tiền hàng 1 Tiền hàng 2 … Tiền hàng 10 CH1 170.000.000 40.000.000 … 5.400.000 CH2 70.000.000 50.000.000 … 6.500.000 … … … CH5 100.000.000 110.000.000 … 13.700.000
Bảng 2.4. Thống kê kết quả kinh doanh trong năm 1998 (Triệu đồng)
Hãy viết chương trình với các yêu cầu sau : 9
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Nhập dữ liệu cho biểu 1 và biểu 2 (dữ liệu tự thu thập)
Tiến hành thống kê thành biểu 3
Đưa kết quả ra màn hình máy tính
Bài 9 – Thống kê kết quả kinh doanh theo giá bán lẻ từng tháng
Xét bài toán lập bảng tổng hợp kinh doanh với điều kiện giá cả biến động trong từng
tháng. Giả sử rằng tring tâm thương mại đã bán ra 10 loại hàng được thống kê theo
từng tháng của 6 tháng đầu năm, cho biết số lượng mỗi loại hàng đã bán trong từng
tháng, đơn giá của mỗi loại hàng trong từng tháng. Trong trường hợp này, bảng số liệu
về số lượng các mặt hàng gồm 10 chủng loại đã bán trong 6 tháng là một mảng hai
chiều kích thước (6 * 10), còn đơn giá từng mặt hàng trong mỗi tháng là một mảng hai
chiều kích thước (10 * 6). Thực hiện nhân hai mảng hai chiều này với nhau chúng ta
thu được doanh số trong từng tháng của trung tâm thương mại.
Các bảng thống kê làm cơ sở để tính toán được biểu diễn như sau : Loại hàng 1 Loại hàng 2 … Loại hàng 10 Tháng 1 234 543 … 234 Tháng 2 657 897 … 345 … … … Tháng 6 675 678 … 678
Bảng 2.5. Thống kê số lượng các loại hàng hóa đã bán mỗi tháng Giá tháng 1 Giá tháng 2 … Giá thàng 6 Loại hàng 1 40.000 40.000 … 40.000 Loại hàng 2 20.000 21.000 … 21.000 … … … Loại hàng 10 40.000 40.000 … 40.000
Bảng 2.6. Thống kê giá cả các loại hàng trong mỗi tháng (Triệu đồng)
Kết quả tính toán là bảng tổng hợp kinh doanh sau đây : 10
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 Giá tháng 1 … Giá tháng 6 ∑ Doanh số tháng 1 … Doanh số tháng 2 … … … Doanh số tháng 6 … ∑
Bảng 2.7. Bảng tổng hợp kết quả kinh doanh theo giá bán lẻ từng tháng của 6 tháng đầu năm.
Xét bài toán dưới mô hình tổng quát. Cho mảng hai chiều :
A = (Aik) và B= (Bkj) i = 1, 2, …, n ; k = 1,2, …, q; j = 1, 2, …, m
Lập giải thuật nhân mảng hai chiều A và B. C = A * B
Trong trường hợp này mỗi thành phần của mảng kết quả Cij được xác định theo công thức sau đây:
Cij = ∑𝑞 𝑘=1 (Aik * Bkj)
Giải thuật nhân mảng hai chiều chính là giải thuật xác định kết quả kinh doanh 6 tháng
đầu năm của trung tâm thương mại.
Viết chương trình xác định kết quả kinh doanh 6 tháng đầu năm của trung tâm thương
mại. Dữ liệu nhập trực tiếp từ bàn phím (hoặc gián tiếp qua file). Đưa kết quả ra màn hình (hoặc qua file). 11
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 Bài tập chương 3
Bài 1 – Xử lý trên danh sách liên kết đơn
Cho một danh sách móc nối đơn có nút đầu tiên trỏ bởi L. Hãy viết giải thuật giải
quyết các công việc sau:
1) Tính số lượng các nút của danh sách
2) Lập bản sao của danh sách L thành danh sách L’
3) Tìm tới nút thứ k trong danh sách, nếu có thì cho ra địa chỉ của nút đó, nếu
không thì cho ra địa chỉ Null
4) Bổ sung nút mới chứa X và sau nút thứ k, nếu không có nút thứ k thì bổ sung vào sau cùng.
5) Loại bỏ nút đứng trước nút thứ k (nếu có nút thứ k)
6) Cho một danh sách móc nối đơn có nút đầu tiên trỏ bởi P. Hãy chèn danh sách
P vào sau nút trỏ bởi M trên danh sách L.
7) Tách danh sách L thành hai danh sách mà danh sách sau có nút đầu tiên trỏ bởi M cho trước.
8) Đảo ngược danh sách đã cho (khi duyệt danh sách đảo ngược ta được thứ tự các
nút được thăm theo chiều ngược lại của danh sách L).
Bài 2 – Xử lý trên danh sách liên kết kép
Cho một danh sách móc nối kép có nút đầu tiên và nút cuối cùng trỏ bởi First và Last.
Hãy viết giải thuật giải quyết các công việc sau:
1) Tính số lượng các nút của danh sách
2) Lập bản sao của danh sách First-Last thành danh sách First’-Last’
3) Tìm tới nút thứ k trong danh sách, nếu có thì cho ra địa chỉ của nút đó, nếu
không thì cho ra địa chỉ Null
4) Bổ sung nút mới chứa X và sau nút thứ k, nếu không có nút thứ k thì bổ sung vào sau cùng.
5) Loại bỏ nút đứng trước nút thứ k (nếu có nút thứ k)
6) Cho một danh sách móc nối kép có nút đầu tiên trỏ bởi F và nút cuối cùng trỏ
bởi L. Hãy chèn danh sách F-R vào sau nút trỏ bởi M trên danh sách First-Last. 12
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
7) Tách danh sách First-Last thành hai danh sách mà danh sách sau có nút đầu tiên trỏ bởi M cho trước.
8) Đảo ngược danh sách đã cho (khi duyệt danh sách đảo ngược ta được thứ tự các
nút được thăm theo chiều ngược lại của danh sách First-Last).
Bài 3 – Tổ chức lưu trữ đa thức trên danh sách móc nối đơn
Cho đa thức bậc n dạng p(x) = anXn + an-1Xn-1 + … + a1X + a0.
Hãy tổ chức lưu trữ đa thức dưới dạng một danh sách móc nối đơn sao cho tiết kiệm
bộ nhớ nhất. Lập giải thuật công hai đa thức được lưu trữ dưới dạng này.
Bài 4 – Xử lý nâng cao trên danh sách móc nối đơn
Cho danh sách móc nối đơn có nút đầu tiên trỏ bởi L, mỗi nút của danh sách chứa một
số nguyên dương. Hãy viết các giải thuật giải quyết các công việc sau đây:
1) Nếu trong danh sách vẫn còn có hai nút chứa số nguyên bằng nhau thì loại bỏ bớt một nút.
2) Trên cơ sở danh sách đã được xử lý ở câu 1) hãy hoán đổi giá trị trong các nút
để khi duyệt danh sách ta được dãy số tăng dần.
3) Trên cơ sở danh sách đã được xử lý ở câu 1) hãy hoán đổi mối nối trong các nút
để khi duyệt danh sách ta được dãy số tăng dần.
4) Trên cơ sở danh sách đã được xử lý ở câu 1), cho trước số nguyên X, nếu trong
danh sách chưa có nút nào chứa X thì hãy chèn thêm nút mới chứa X vào danh
sách sao cho khi duyệt danh sách ta được dãy số tăng dần.
Bài 5 – Xử lý nâng cao trên danh sách móc nối kép
Cho danh sách móc nối kép có nút đầu tiên và nút cuối cùng trỏ bởi First và Last, mỗi
nút của danh sách chứa một số nguyên dương. Hãy viết các giải thuật giải quyết các công việc sau:
1) Nếu trong danh sách vẫn còn có hai nút chứa số nguyên bằng nhau thì loại bỏ bớt một nút.
2) Trên cơ sở danh sách đã được xử lý ở câu 1) hãy hoán đổi giá trị trong các nút để
khi duyệt danh sách ta được dãy số tăng dần. 13
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
3) Trên cơ sở danh sách đã được xử lý ở câu 1) hãy hoán đổi mối nối trong các nút để
khi duyệt danh sách ta được dãy số tăng dần.
4) Trên cơ sở danh sách đã được xử lý ở câu 1), cho trước số nguyên X, nếu trong
danh sách chưa có nút nào chứa X thì hãy chèn thêm nút mới chứa X vào danh
sách sao cho khi duyệt danh sách ta được dãy số tăng dần.
Bài 6 – Tạo dãy số nguyên tố tăng dần
Cho danh sách móc nối đơn có nút đầu tiên trỏ bởi L, mỗi nút của danh sách chứa một
số nguyên dương. Hãy viết giải thuật giải quyết công việc sau:
Cắt các nút trong danh sách L chứa số nguyên là số nguyên tố và lắp ghép chúng thành
một danh sách móc nối đơn có nút đầu tiên trỏ bởi P sao cho khi duyệt danh sách P ta
được dãy số tăng dần (lưu ý là không thực hiện sắp xếp trên P).
Bài 7 – In giá trị các nút theo thứ tự ngược
Cho khai báo một danh sách móc nối đơn như sau: Class Node { Public Object Info; Public Node Link; } Node First;
Hãy viết thủ tục đệ quy: InNguoc(First) thực hiện việc in giá trị của các nút theo thứ tự
ngược lại (First được in cuối cùng trong danh sách in ra).
Bài 8 – Quản lý học viên
Một trung tâm đào tạo Tin học cần quản lý việc học của học viên theo chứng chỉ môn
học. Trong mỗi kỳ, trung tâm lưu giữ thông tin về kết quả học tập của các học viên
trong một danh sách liên kết với nút đầu được trỏ bởi con trỏ F (gọi là danh sách học viên F).
Mỗi nút của danh sách học viên là một đối tượng gồm 3 thuộc tính:
Thuộc tính Down: lưu địa chỉ của nút kế tiếp trong danh sách học viên 14
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Thuộc tính Hoten: lưu họ tên học viên (Trường khóa của danh sách)
Thuộc tính DsMon: lưu địa chỉ của nút đầu danh sách khác chứa các kết quả các
môn học mà học viên này đăng ký trong học kỳ đó (gọi là danh sách môn học)
Mỗi nút của danh sách môn học là một đối tượng gồm 3 thuộc tính:
Thuộc tính TenMH: tên của môn học (khóa)
Thuộc tính Diem: điểm thi kết thục môn học này của học viên
Thuộc tính Next: lưu địa chỉ nút tiếp theo của danh sách môn học
Lưu ý rằng chỉ có danh sách học viên được sắp xếp theo thứ tự tăng dần của Hoten.
Khai báo cấu trúc dữ liệu: Class MonHoc { Public String TenMH; Public byte Diem; Public MonHoc Next; } Class HocVien { Public String Hoten; Public HocVien Down; Public MonHoc DsMon; } HocVien F; String Name, Subject;
1) Hãy xây dựng phương thức Public HocVien TimHV(F, Name) trả về địa chỉ
của nút trong F có giá trị thuộc tính Hoten = Name, hoặc trả về giá trị null nếu
trong F không có học viên nào có họ tên là Name. 15
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
2) Hãy xây dựng phương thức Public MonHoc TimMH(P, Subject) trả về địa chỉ
của nút thuộc danh sách môn học P (nút đầu trỏ bởi P) có giá trị thuộc tính
TenMH = Subject, hoặc trả về giá trị null nếu trong danh sách P không có môn
học nào có tên Subject.
3) Hãy xây dựng phương thức Public void BoSung(F, Name, Subject) để bổ sung
một học viên có tên Name vào danh sách F nếu chưa có học viên đó và học viên
này có danh sách môn học đăng ký ban đầu gồm 1 môn học Subject. Nếu đã có
học viên này, thì bổ sung một môn học có tên Subject vào cuối danh sách môn
học của học viên đó, nếu môn học này chưa có trong danh sách; ngược lại, không làm gì cả.
4) Hãy xây dựng phương thức Public void CapNhat(F, Name, Subject, Mark) để
cập nhật điểm thi Mark của môn học Subject cho học viên Name. Nếu không
tìm thấy học viên Name thì thực hiện việc bổ sung học viên Name và môn học
Subject kèm điểm số Mark tương ứng. Nếu không thấy môn học Subject của
học viên Name thì thực hiện bổ sung môn học Subject kèm số điểm Mark.
5) Hãy xây dựng phương thức: Public void InDSHV(F) để thực hiện việc in danh
sách học viên và điểm của từng môn học đăng ký kèm điểm trung bình của mỗi
học viên, điểm trung bình bằng tổng tất cả các cột điểm chia cho số lượng môn
học đã đăng ký. In danh sách theo mẫu: DANH SACH HOC VIEN
1. Le Van A: Tin (9), Pascal (10) – DTB: 9.50
2. Le Van B: Word (5), Excel (8) – DTB: 6.50 …
Bài 9 – Lưu trữ văn bản
Trong một hệ soạn thảo, văn bản đang được soạn thảo được lưu trữ ở bộ nhớ trong
dưới dạng một danh sách nối kép như sau: 16
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Khai báo của danh sách này như sau: Class DongVB { Pubic DongVB Truoc; Public DongVB Sau; Public String Dong; }
DongVB Dau, Cuoi; //Đều bằng null khi văn bản rỗng
1) Hãy xây dựng phương thức Public void XenTruoc(d, p, line) cho phép xem
một dòng mới với nội dung cho bởi line và trước phần tử trỏ bởi p trong danh sách ban đầu d.
2) Gọi Block(db, cd) là một khối liền nhau các dòng kể từ dòng trỏ bởi db đến
dòng trỏ bởi cb. Hãy xây dựng phương thức dưới dạng: 17
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Public void chuyenBlock(d, c, db, cb, noiden);
Cho phép chuyển dời Block(db, cb) tới trước dòng trỏ bởi noiden trong
danhsach(d, c), giả sử nơi đến không ở trong Block(db, cb).
3) Xây dựng phương thức Public void chepBlock(d, db, cb, noiden) cho phép
chép (mà không hủy) một Block(db, cb) tới trước dòng trỏ bởi noiden trong
danh sách có đầu d. Giả sử noiden không ở trong Block(db, cb). 18
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 Bài tập chương 4
Bài 1 – Các câu hỏi cơ bản về cây nhị phân Cho cây nhị phân
Hãy trả lời các câu hỏi sau: 1) Các nút nào là nút lá? 2)
Các nút nào là nút nhánh? 3) Các nút con của nút C? 4) Nút cha của nút G? 5) Các nút anh em của H? 6) Mức của nút C và P? 7) Cấp của nút D, H, M? 8) Cấp của cây? 9) Chiều cao của cây?
10) Đường đi và độ dài đường đi từ A tới R
Bài 2 – Cây nhị phân biểu diễn biểu thức số học
Hãy biểu diễn các biểu thức sau dưới dạng cây nhị phân. 1) (a*b) + c/(d-e*f) 2) A/(B+C) + D*E – A*C 19
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Bài 3 – Tìm cây nhị phân giống nhau
Tìm tất cả các cây nhị phân mà các nút sẽ xuất hiện theo một dãy giống nhau khi duyệt:
1) Theo thứ tự trước và thứ tự giữa
2) Theo thứ tự trước và thứ tự sau
3) Theo thứ tự giữa và thứ tự sau
Bài 4 – Khử đệ quy các phép duyệt cây nhị phân
Hãy lập giải thuật không đệ quy để thực hiện duyệt cây nhị phân theo thứ tự trước, giữa và sau.
Bài 5 – Tạo bản sao cây nhị phân
Lập một giải thuật đệ quy để thực hiện lập bản sao của một cây nhị phân T thành cây nhị phân T’.
Bài 6 – Đánh tráo con trái và con phải của cây nhị phân
Lập một giải thuật đệ quy để thực hiện việc đánh tráo mọi nút con trái, phải của mọi
nút của một cây nhị phân cho trước.
Bài 7 – Tính chiều cao cây nhị phân
Hãy viết giải thuật tính chiều cao của một cây nhị phân T cho trước 20
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Bài 8 – Xác định mức của một nút
Hãy viết giải thuật xác định mức của một nút trỏ bởi M trong cây nhị phân T.
Bài 9 – Tính số lượng nút trên cây
Cho cây nhị phân T, viết các giải thuật sau:
1) Tính số lượng nút của cây
2) Tính số lượng nút lá của cây
Bài 10 – Duyệt cây nhị phân theo mức
Cho cây nhị phân T, hãy xây dựng giải thuật duyệt theo mức của cây, tại mỗi mức các
nút ưu tiên được duyệt từ trái sang phải
Bài 11 – Dựng cây nhị phân từ kết quả duyệt
Cho biết dãy các nút được thăm của một cây nhị phân khi duyệt theo thứ tự trước và
thứ tự giữa. Hãy lập giải thuật dựng lại cây nhị phân đó.
Điều này có thể thực hiện được không khi biết kết quả duyệt theo thứ tự trước và thứ
tự sau? Khi biết kết quả duyệt theo thư tự giữa và thứ tự sau?
Bài 12 – Chuyển đổi cơ chế lưu trữ cây nhị phân
1) Cho cây nhị phân được lưu trữ ở dạng móc nối, hãy lập giải thuật chuyển sang lưu trữ kế tiếp
2) Cho cây nhị phân được lưu trữ ở dạng kế tiếp, hãy lập giải thuật chuyển sang lưu trữ dạng móc nối
Bài 13 – Tính giá trị biểu thức
Người ta diễn tả một biểu thức số học infix bằng một cây nhị phân sau:
- Các nút trong cây chứa các toán tử (+, -, *, /, #, ↑). Trong đó # là phép toán một
ngôi và ↑ là phép lũy thừa.
- Các lá chứa toán hạng (số thực)
- Mỗi nút có các trường: Ctrai trỏ tới nút con trái, Cphai trỏ tới nút con phải, mộ
trường LoaiNut cho biết nút này ứng với +, -, *, /, #, ↑ hay toán hạng. Nếu loại 21
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
nút là # thì chỉ có con phải, còn nếu loại nút là toán hạng thì không có các cây
con trái, phải và nút có thêm một trường chứa giá trị (thực) của toán hạng.
Giả sử đã có một cây (xây dựng theo yêu cầu trên), trỏ bởi con trỏ T. Hãy viết một
phương thức cho phép tính giá trị của biểu thức tương ứng với cây đó.
Bài 13 – Xây dựng cây nhị phân tìm kiếm
Cho dãy khóa K[1..n]. Hãy viết giải thuật để:
1) Xây dựng câu nhị phân tìm kiếm được lưu trữ móc nối chứa dãy khóa
2) Xây dựng cây nhị phân tìm kiếm được lưu trữ móc nối, có chiều cao thấp nhất chứa dãy khóa.
Bài 14 – Xử lý trên cây nhị phân
Cho khai báo của một cây nhị phân như sau: Class Node { Public int Value; Public Node Left; Public Node Right; } Node Root;
Hãy xây dựng các phương thức thực hiện các công việc sau:
1) Phương thức Public bool CayTK(Root). Cho phép kiểm tra xem cây có gốc
được trỏ bởi Root có phải là cây nhị phân tìm kiếm hay không.
2) Trường hợp cây ban đầu không phải là cây nhị phân tìm kiếm, hãy xây dựng
phương thức: Public void SapLai(Root);
Cho phép tráo đổi nội dung của các nút trong cây, nhưng không thay đổi cấu
trúc cây, để nhận được cây nhị phân tìm kiếm.
Ví dụ: Với cây ở hình 1, sau khi tráo đổi ta nhận được cây nhị phân tìm kiếm ở hình 2. 22
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Bài 14 – Dựng cây nhị phân
Viết chương trình mô tả cây nhị phân dùng cấu trúc liên kết, mỗi nút chứa một số
nguyên, và viết các thủ tục duyệt trước, giữa, sau. 23
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022 Bài tập chương 5
Bài 1 - Biểu diễn đồ thị trên máy tính
Cho đồ thị có định hướng G Hãy lập:
1) Ma trận kề biểu diễn đồ thị G
2) Danh sách lân cận biểu diễn đồ thị G
Bài 2 – Duyệt đồ thị
Hãy duyệt đồ thị G đã cho ở câu 1 bằng phương pháp duyệt sâu và duyệt rộng. Đưa ra
thứ tự duyệt lần lượt của hai phương pháp.
Bài 3 – Duyệt đồ thị trên danh sách lân cận
Viết giải thuật duyệt đồ thị theo chiều sau và theo chiều rộng, với cấu trúc lưu trữ là
danh sách lân cận, các con trỏ quản lý danh sách laanc ận được lưu trử ở mảng con trỏ V[1..n].
Bài 4 – Đếm số miền liên thông của đồ thị
Cho đồ thị G = với tập đỉnh V = {1, 2, 3, .., n}. Hãy viết giải thuật để đếm số
miền liên thông của đồ thị. 24
TS. Hà Ngọc Long – Bài tập cấu trúc Dữ Liệu 2022
Bài 5 – Kiểm tra đường đi từ u tới v
Cho đồ thị G = với tập đỉnh V = {1, 2, 3, …, n}. Hãy viết giải thuật kiểm tra
xem có tồn tại đường đi từ đỉnh u tới đỉnh v cho trước hay không? Nếu có thì cho ra
giá trị True, còn không thì cho ra giá trị False.
Bài 6 – Tìm đường đi ngắn nhất
Cho đồ thị có trọng số G = với tập đỉnh V = {1, 2, 3, …, n}. Hãy tìm đường đi
ngắn nhất từ u tới v. Trả về giá trị đoạn đường ngắn nhất và liệt kê các đỉnh mà đoạn đường đó đi qua. Bài tập chương 6
Bài 1 – Sắp xếp dãy khóa
Cho dãy khóa: 50 08 34 06 98 17 83 25 66 42 21 59 62 71 85 76
Hãy minh họa kết quả từng bước trong quá trình sắp xếp dãy khóa theo các phương pháp sau:
- Ba phương pháp sắp xếp đơn giản - Quick Sort - Vun đống
- Hòa nhập hai đường trực tiếp 25