Bài tập cấu trúc dữ liệu và giải thuật có đáp án

Bài 24. Gray Code to Binay & Binary to Gray (Microsoft, Amazon) [A]. Số nhị phân được xem là cách mặc định biểu diễn các số. Tuy nhiên, trong nhiều ứng dụng của điện tử và truyền thông lại dùng một biến thể của mã nhị phân đó là mã Gray. Mã Gray độ dài n có mã đầu tiên là n số 0, mã kế tiếp của nó là một xâu nhị phân độ dài n khác biệt với xâu trước đó một bít. Ví dụ với n=3 ta có 23 mã Gray như sau: 000, 001, 011, 010, 110, 111, 101, 100. Hãy viết chương trình chuyển đổi một xâu mã Gray X có độ dài n thành một xâu mã nhị phân.

Dữ liệu vào:

·       Dòng đầu tiên là số lượng test T (T≤100).

·       T dòng kế tiếp ghi lại mỗi dòng một test. Mỗi test là một xâu mã Gray độ dài n (n≤100).

Kết quả ra của mỗi test được đưa ra trên một dòng tương ứng với mã nhị phân của test tương ứng.

Input:	Output:
2 01101 01011	01001 01101

Tải về code C++
Bài 25.  Chia số trong xâu (Adopt)[C]. Cho một xâu ký tự bao gồm các chữ số. Hãy tìm tất cả các số có thể tạo ra bằng cách kết hợp các số trong xâu nhưng giữ nguyên vị trí. Ví dụ với xâu S[] =”123” ta sẽ có các cách tạo các số như sau:

1          2          3          23        12        123

Tải về code C++
Bài 26.  Cho số tự nhiên n và k. Hãy viết chương trình liệt kê tất cả các tổ hợp chập k của 1, 2, .., n. Ghi chú, mỗi tổ hợp chập k của 1, 2, .., n tương ứng với một tập con k phần tử của 1, 2, .., n. Ví dụ với n = 5, k =3 ta có 10 tập con ba phần tử của 1, 2, 3, 4, 5 như dưới đây:

N=5, k = 3
1   2   3 1   2   4 1   2   5 1   3   4 1   3   5 1   4   5 2   3   4 2   3   5 2     4   5

Tải về code C++
Bài 27.  Cho hình chữ nhật gồm n´m hình vuông đơn vị. Hãy đếm số đường đi từ đỉnh của ô vuông cuối cùng góc trái lên đến đỉnh của ô vuông trên cùng góc phải. Biết mỗi bước đi ta chỉ được phép dịch sang phải hoặc lên trên theo các cạnh của hình vuông đơn vị.

Dữ liệu vào cho bởi file data.in theo khuôn dạng:

·       Dòng đầu tiên ghi lại số T tương ứng với số lượng test.

·       T dòng kế tiếp, mỗi dòng ghi lại một test. Mỗi test là một bộ đôi n, m tương ứng với hình chữ nhật gồm n´m hình vuông đơn vị.

Kết quả ra ghi lại trong file ketqua.out theo từng dòng ứng với mỗi test. Ví dụ dưới đây sẽ minh họa cho file data.in và ketqua.out của bài toán.

Data.in	Ketqua.out
3 5 3 6 3 7 4	10 20 35

Tải về code C++
Bài 28. Hãy viết chương trình liệt kê tất cả các hoán vị của 1, 2, .., n. Ví dụ với n = 4 sẽ cho ta 4! Hoán vị như dưới đây:

N=4
1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1	3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 2   3 2 1

Tải về code C++
Bài 29. Hãy viết chương trình liệt kê tất cả các hoán vị của từ computer. Ví dụ từ computre là một hoán vị của từ compter.
Tải về code C++
Bài 30. Cho dãy số nguyên dương A[] = {a1, a2,.., an}. Hãy liệt kê tất cả các dãy số có thể tạo ra bằng cách tráo đổi các phần tử khác nhau của dãy số A[] sao cho tổng hai phần tử liên tiếp bất kỳ đều là một số nguyên tố. Dữ liệu vào cho bởi file data.in theo khuôn dạng:

·       Dòng đầu tiên ghi lại số tự nhiên n là số phần tử của dãy số A[].

·       Dòng kế tiếp ghi lại các phần tử của dãy số A[].

Các dãy số thỏa mã yêu cầu của bài toán ghi lại trong file ketqua.out, mỗi dãy số được ghi trên một dòng. Ví dụ dưới đây sẽ minh họa cho file data.in và ketqua.out của bài toán.

Data.in	Kequa.out
6 9 7 12 8 6 5	6       7        12        5          8          9   9       8        5          6          7          12   9       8        5          12        7          6   12     7        6          5          8          9

Tải về code C++
Bài 31.  Dãy sắp xếp tạo ra từ hai dãy sắp xếp (Microsoft). Cho hai dãy số đã được sắp xếp A[], B[]. Hãy in ra rất cả các dãy số đã được sắp xếp theo nguyên tắc: phần tử đầu tiên thuộc A[], phần tử tiếp theo thuộc B[]….

Ví dụ với dãy A[] = {10, 15, 25}, B[] = {1, 5, 20, 30 } ta sẽ có các dãy số được tạo ra theo nguyên tắc trên như sau:

            10        20

            10        20        25        30

            10        30

            15        20

            15        20        25        30

            15        30

            25    30

Tải về code C++
Bài 32.  Giải bài toán cái túi bằng thuật toán qui hoạch động. 
Tải về code C++
Bài 33.   Tìm số các cách chia số tự nhiên n thành tổng các số tự nhiên nhỏ hơn n. Các cách chia là hoán vị của nhau chỉ được tính là một cách.
Tải về code C++
Bài 34.   Thuật toán Brute-Force
Tải về code C++
Bài 35.   Ban đầu cho một queue rỗng. Bạn cần thực hiện các truy vấn sau: 1. Trả về kích thước của queue 2. Kiểm tra xem queue có rỗng không, nếu có in ra “YES”, nếu không in ra “NO”. 3. Cho một số nguyên và đẩy số nguyên này vào cuối queue. 4. Loại bỏ phần tử ở đầu queue nếu queue không rỗng, nếu rỗng không cần thực hiện. 5. Trả về phần tử ở đầu queue, nếu queue rỗng in ra -1. 6. Trả về phần tử ở cuối queue, nếu queue rỗng in ra -1. Dữ liệu vào Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu, mỗi bộ dữ theo dạng sau. Dòng đầu tiên chứa số nguyên n - lượng truy vấn (1 ≤ n ≤ 1000) N dòng tiếp theo, mỗi dòng sẽ ghi loại truy vấn như trên, với truy vấn loại 3 sẽ có thêm một số nguyên, không quá 106. Kết quả: In ra kết quả của các truy vấn.. Ví dụ: Input                       Output 1                              1 14                            3 3 1                           5 3 2                           2 3 3 5 6 4 4 4 4 4 3 5 3 6 5 1 Tải về code C++
Bài 36.   Yêu cầu bạn xây dựng một queue với các truy vấn sau đây: “PUSH x”: Thêm phần tử x vào cuối của queue (0 ≤ x ≤ 1000). “PRINTFRONT”: In ra phần tử đầu tiên của queue. Nếu queue rỗng, in ra “NONE”.

“POP”: Xóa phần tử ở đầu của queue. Nếu queue rỗng, không làm gì cả. 

Dữ liệu vào: Dòng đầu tiên là số lượng truy vấn Q (Q ≤ 100000). Mỗi truy vấn có dạng như trên. 

Kết quả:    Với mỗi truy vấn “PRINT”, hãy in ra phần tử đầu tiên của queue. Nếu queue rỗng, in ra “NONE”. Ví dụ:

Input:                              Output:

9                                      2 

PUSH 1                           2

PUSH 2                           NONE

POP 

PRINTFRONT 

PUSH 3 

PRINTFRONT  

POP 

POP 

PRINTFRONT

Tải về code C++
Bài 37.   Cho hai số nguyên tố khác nhau có bốn chữ số. Người ta cho rằng hoàn toàn có thể biến đổi từ số này thành số kia sau một số bước theo quy tắc: Tại mỗi bước ta chỉ thay đổi một chữ số trong số trước đó sao cho số tạo được trong mỗi bước đều là một số nguyên tố có bốn chữ số. Một cách biến đổi như vậy gọi là một “đường nguyên tố”. Bài toán đặt ra là với một cặp số nguyên tố đầu vào, hãy tính ra số bước của đường nguyên tố ngắn nhất. Giả sử đầu vào là hai số 1033 và 8179 thì đường nguyên tố ngắn nhất sẽ có độ dài là 6 với các bước chuyển là: 1033 1733 3733 3739 3779 8779 8179 Dữ liệu vào: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test viết trên một dòng bao gồm hai số nguyên tố có 4 chữ số.. Kết quả: Với mỗi bộ test, in ra màn hình trên một dòng số bước của đường nguyên tố ngắn nhất. Ví dụ: Input                        Output 3                               6 1033                         7 8179                         0 1373 8017 1033 1033 Tải về code C++
Bài 38.   Có một chiếc bảng hình chữ nhật với 6 miếng ghép, trên mỗi miếng ghép được điền một số nguyên trong khoảng từ 1 đến 6. Tại mỗi bước, chọn một hình vuông (bên trái hoặc bên phải), rồi quay theo chiều kim đồng hồ.

Yêu cầu: Cho một trạng thái của bảng, hãy tính số phép biến đổi ít nhất để đưa bảng đến trạng thái đích.

Dữ liệu vào: Dòng đầu tiên chứa 6 số là trạng thái bảng ban đầu (thứ tự từ trái qua phải, dòng 1 tới dòng 2).

Dòng thứ hai chứa 6 số là trạng thái bảng đích (thứ tự từ trái qua phải, dòng 1 tới dòng 2).

Kết quả:   In ra một số nguyên là đáp số của bài toán.

Ví dụ:

Input:                               Output:

1 2 3 4 5 6                       2

4 1 2 6 5 3

Tải về code C++
Bài 39.   Cho một bảng kích thước N x N, trong đó có các ô trống ‘.’ và vật cản ‘X’. Các hàng và các cột được đánh số từ 0. Mỗi bước di chuyển, bạn có thể đi từ ô (x, y) tới ô (u, v) nếu như 2 ô này nằm trên cùng một hàng hoặc một cột, và không có vật cản nào ở giữa. Cho điểm xuất phát và điểm đích. Bạn hãy tính số bước di chuyển ít nhất? Dữ liệu vào: Dòng đầu tiên là số nguyên dương N (1 ≤ N ≤ 100). N dòng tiếp theo, mỗi dòng gồm N kí tự mô tả bảng. Cuối cùng là 4 số nguyên a, b, c, d với (a, b) là tọa độ điểm xuất phát, (c, d) là tọa độ đích. Dữ liệu đảm bảo hai vị trí này không phải là ô cấm.  Kết quả:   In ra một số nguyên là đáp số của bài toán.

Tải về code C++
Bài 39.   Thành phố X có N thị trấn trên trục đường chính. Tọa độ của các thị trấn lần lượt là a[1], a[2], …, a[N], các tọa độ này là phân biệt, không có 2 tọa độ nào trùng nhau. Chính quyền thành phố muốn xây dựng một tuyến buýt nhanh BRT để kết nối 2 thị trấn gần nhau nhất với nhau. Bạn hãy tính thử xem chiều dài của tuyến buýt này bằng bao nhiêu? Và có bao nhiêu cặp thị trấn có tiềm năng giống nhau để xây dựng tuyến BRT này. Dữ liệu vào: Dòng đầu tiên là số lượng bộ test T (T ≤ 10). Mỗi test bắt đầu bằng số nguyên N (N ≤ 100 000). Dòng tiếp theo gồm N số nguyên A[i] (-109 ≤ A[i] ≤ 109). Kết quả:  Với mỗi test in ra 2 số nguyên C và D, lần lượt là khoảng cách ngắn nhất giữa 2 thị trấn, và số lượng cặp thị trấn có cùng khoảng cách ngắn nhất này.

Tải về code C++
Bài 40.    Xây dựng các thao tác cơ bản trên danh sách liên kết đơn(C++), bao gồm: • Khởi tạo danh sách liên kết đơn. • Chèn node vào đầu danh sách liên kết đơn. • Chèn node vào cuối danh sách liên kết đơn. • Chèn node vào vị trí xác định trong danh sách liên kết đơn. • Loại node tại vị trí Pos trong danh sách liên kết đơn. • Sửa đổi nội dung node trong danh sách liên kết đơn. • Sắp xếp các node của danh sách liên kết đơn. • Đảo ngược các node trong danh sách liên kết đơn. • Tìm kiếm vị trí của node trong danh sách liên kết đơn. • Hiển thị nội dung trong danh sách liên kết đơn. Tải về code C++
Bài 41.   Thuật toán chuyển đổi biểu thức trung tố P thành biểu thức hậu tố?(Sử dụng ngăn xếp) VD:

Infix	Postfix
A / B – C * D	A B / C D * +
A / ( B – C * D)	A B C D * - /
A / (B – C) * D	A B C - / D *

Tải về code C++