Bài thi giữa kì môn Cấu trúc dữ liệu - Giải thuật | Học viện Công Nghệ Bưu Chính Viễn Thông

lOMoAR cPSD| 58457166
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA KỸ THUẬT ĐIỆN TỬ I
BÀI THI GIỮA KÌ MÔN
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NHÓM MÔN HỌC: 17
Giảng viên: TS. Phạm Hoàng Anh Họ và tên: Hoàng Trung Kiên MSV: B22DCDT156 Hà Nội, 2025 lOMoAR cPSD| 58457166 LỜI CẢM ƠN
Em xin trân trọng gửi lời cảm ơn đến thầy TS. Phạm Hoàng Anh, giảng viên môn
Cấu trúc Dữ liệu và Giải thuật, người đã tận tâm giảng dạy và hướng dẫn chúng em trong suốt học kỳ vừa qua.
Nhờ sự chỉ dẫn rõ ràng, dễ hiểu và sát với thực tế từ thầy, em đã có thể tiếp cận môn
học một cách hệ thống, nắm vững các kiến thức nền tảng cũng như vận dụng linh hoạt các
thuật toán vào bài kiểm tra giữa kỳ này.
Bài làm là kết quả của quá trình học tập và cố gắng áp dụng kiến thức đã học. Tuy
nhiên, chắc chắn vẫn còn nhiều thiếu sót, chúng em rất mong nhận được sự góp ý quý báu
từ thầy để hoàn thiện hơn trong các bài làm sau.
Một lần nữa, em xin chân thành cảm ơn thầy! lOMoAR cPSD| 58457166 LỜI MỞ ĐẦU
Cấu trúc dữ liệu và giải thuật là một trong những nền tảng cốt lõi của khoa học máy
tính và kỹ thuật phần mềm. Môn học này không chỉ giúp sinh viên hiểu rõ cách tổ chức
và xử lý dữ liệu hiệu quả, mà còn rèn luyện tư duy logic, phân tích thuật toán và tối ưu hóa chương trình.
Bài kiểm tra giữa kỳ này gồm hai phần chính. Phần đầu tiên yêu cầu xây dựng
chương trình xử lý thông tin sinh viên trong nhóm, kết hợp giữa thao tác chuỗi, mảng và
tìm kiếm dữ liệu – những kiến thức cơ bản nhưng quan trọng trong thực hành lập trình.
Phần thứ hai là ứng dụng thuật toán chuyển biểu thức từ dạng trung tố sang hậu tố bằng
cấu trúc dữ liệu stack, giúp sinh viên hiểu sâu hơn về cách biểu diễn và xử lý biểu thức trong máy tính.
Thông qua bài kiểm tra này, em mong muốn thể hiện sự hiểu biết và khả năng vận
dụng kiến thức đã học vào thực tiễn, đồng thời củng cố nền tảng tư duy giải thuật để phục
vụ cho các môn học chuyên ngành tiếp theo. lOMoAR cPSD| 58457166 MỤC LỤC
LỜI CẢM ƠN...........................................................................................................2
LỜI MỞ ĐẦU...........................................................................................................3
PHÂN CÔNG CÔNG VIỆC.....................................................................................5
1 CÂU 1.....................................................................................................................6
1.1 Ý TƯỞNG BÀI TOÁN....................................................................................6
1.2 LƯU ĐỒ THUẬT TOÁN................................................................................8
1.3 CODE...............................................................................................................9
1.4 MÀN HÌNH KẾT QUẢ CHẠY CODE.........................................................14
2 CÂU 2...................................................................................................................16
2.1 Ý TƯỞNG BÀI TOÁN..................................................................................16
2.2 LƯU ĐỒ THUẬT TOÁN..............................................................................18
2.3 CODE.............................................................................................................18
2.4 MÀN HÌNH KẾT QUẢ CHẠY CODE.........................................................21 lOMoAR cPSD| 58457166 1 CÂU 1
Viết chương trình thực hiện các chức năng sau:
Cho một dãy N viên bi gồm 3 màu xanh, trắng, đỏ xếp lẫn lộn. Bằng cách đổi chỗ từng
cặp viên bi cho nhau có thể xếp lại dãy bi trên sao cho các viên bi xanh đứng trước, sau
đó đến các viên bi trắng và cuối cùng là các viên bi đỏ. Tìm số lượng ít nhất các phép đổi chỗ cần thực hiện Input •
Dòng đầu tiên ghi N (N≤100) •
Dòng thứ hai ghi xâu ký tự mô tả dãy bi (T-trắng, X-xanh, D-đỏ). Output
Một dòng duy nhất ghi số phép đổi chỗ tối thiểu cần thực hiện
Viết lại lưu đồ chương trình thực hiện các chức năng trên để làm báo cáo. 1.1 Ý TƯỞNG BÀI TOÁN
Nhập thông tin ban đầu
Đếm số viên bi màu xanh, màu trắng, màu đỏ.
Số viên bi màu xanh là dx, số viên bi màu trắng là dt, số viên bi màu đỏ là dd.
Ta cần xếp các bi xanh ở đoạn 0 đến dx-1, các bi trắng ở đoạn dx đến dx + dt, các bi đỏ ở đoạn dx +
dt – 1 đến n-1.
Sắp xếp các viên bi màu xanh:
- Duyệt lần lượt các viên bi theo thứ tự từ 0 đến dx-1;
- Nếu thấy viên bi màu trắng thì tìm và đổi chỗ với viên bi màu xanh trong khoảng từ dx đến dx + dt-1;
- Nếu thấy viên bi màu đỏ thì tìm và đổi chỗ với viên bi màu xanh trong khoảng từ dx + dt đến n- 1;
Sắp xếp các viên bi màu trắng:
- Duyệt lần lượt các viên bi theo thứ tự từ dx đến dx + dt - 1;
- Nếu thấy viên bi màu đỏ thì tìm và đổi chỗ với viên bi màu trắng trong khoảng từ dx + dt đến n- 1;
Thực hiện in ra số lần đổi vị trí và xâu mới đã sắp xếp.
(Trong báo cáo e in ra xâu nhận được để quan sát)
1.2 LƯU ĐỒ THUẬT TOÁN lOMoAR cPSD| 58457166 lOMoAR cPSD| 58457166 1.3 CODE #include #define endl "\n" using namespace std; int n, ok, ans = 0; string s;
void Try(int l, int pos, char c) {
for (int i = l; i < n; i++) { if (s[i] == c) { ok = 1; swap(s[pos], s[i]); ans++; return; } lOMoAR cPSD| 58457166 } } int main() { ios_base::sync_with_stdio(0);
cin.tie(0); cin >> n >> s; int dx = 0, dt = 0, dd = 0; for (int i=0; i { if (s[i] == 'X') dx++; else if (s[i] == 'T') dt++; else dd++; }
for (int i = 0; i < dx; ++i) { if (s[i] == 'T') Try(dx, i, 'X'); else if (s[i] == 'D') { ok = 0; Try(dx + dt, i, 'X'); if (ok == 0) Try(dx, i, 'X'); } }
for (int i = dx; i < dt + dx; i++) if (s[i] == 'D') Try(dx + dt, i, 'T'); cout << ans; }
1.4 MÀN HÌNH KẾT QUẢ CHẠY CODE
1.5 MÀN HÌNH KẾT QUẢ NỘP CODE (không in xâu nhận được) lOMoAR cPSD| 58457166 2 CÂU 2
Cho dãy số nguyên A có n phần tử.
Hãy đếm xem có bao nhiêu cặp (i,j) thỏa mãn: • i < j •
A[i] > A[j] và đều là số chẵn •
Tồn tại chỉ số k với i < k < j sao cho A[k] là số lẻ Input
Dòng đầu tiên ghi số n (1 ≤ n ≤ 105). Output
Dòng thứ 2 ghi n số của dãy A, các giá trị A[i] không vượt quá 106.
2.1 Ý TƯỞNG BÀI TOÁN
Bài toán yêu cầu chuyển đổi biểu thức trung tố (infix) sang hậu tố (postfix). Biểu
thức trung tố là biểu thức dạng thông thường (ví dụ: 3 + 4 * 2), còn biểu thức hậu tố là
dạng mà các toán tử nằm sau toán hạng (ví dụ: 3 4 2 * +).
Để giải bài toán này, chúng em áp dụng thuật toán chuyển đổi trung tố sang hậu tố sử
dụng ngăn xếp (stack), cụ thể như sau: Các bước chính của thuật toán
Một nhập số lượng biểu thức cần xử lý và lặp qua từng biểu thức một.
Hai duyệt từng ký tự trong chuỗi biểu thức:
Nếu ký tự là số (có thể nhiều chữ số), đọc hết cả cụm số và đưa trực tiếp vào kết quả hậu tố.
Nếu ký tự là chữ cái (biến), thêm trực tiếp vào biểu thức hậu tố. Nếu gặp toán tử (+, -, *, /, ^):
So sánh độ ưu tiên của toán tử đang xét với toán tử đang nằm trên đỉnh ngăn xếp.
Nếu toán tử trong ngăn xếp có độ ưu tiên cao hơn hoặc bằng, thì đưa nó ra khỏi ngăn xếp vào kết quả.
Sau đó, đẩy toán tử mới vào ngăn xếp.
Nếu gặp dấu ngoặc mở ‘(’, đưa vào ngăn xếp. lOMoAR cPSD| 58457166
Nếu gặp dấu ngoặc đóng ‘)’, lấy các phần tử trong ngăn xếp ra cho đến khi gặp dấu ‘(’.
Ba sau khi duyệt hết chuỗi, nếu ngăn xếp vẫn còn phần tử, đưa tất cả ra ngoài để hoàn
thành biểu thức hậu tố.
Cuối cùng, hiển thị kết quả là biểu thức hậu tố.
Thuật toán sử dụng cấu trúc ngăn xếp để đảm bảo thứ tự đúng của các toán tử và dấu ngoặc.
Có thể xử lý biểu thức chứa nhiều chữ số và biến, không giới hạn độ dài. Kết quả thu được
đúng chuẩn hậu tố, dễ áp dụng tiếp cho việc tính toán giá trị biểu thức sau này.
Thuật toán chuyển đổi biểu thức trung tố sang hậu tố sử dụng ngăn xếp giúp đảm bảo
đúng thứ tự toán tử và xử lý chính xác cả biểu thức có ngoặc và độ ưu tiên khác nhau.
Đây là thuật toán cơ bản nhưng rất hiệu quả trong các bài toán xử lý biểu thức và đóng
vai trò nền tảng cho việc xây dựng trình biên dịch, máy tính biểu thức hoặc các hệ
thống tính toán tự động. Việc tách riêng số nhiều chữ số, ký tự và xử lý toán tử một
cách linh hoạt giúp chương trình có tính tổng quát và dễ mở rộng.
2.2 LƯU ĐỒ THUẬT TOÁN
Hình 7. Lưu đồ thuật toán câu 2 lOMoAR cPSD| 58457166 2.3 CODE #include #define endl "\n" using namespace std; int bit[1000001]; void update(int i) {
for (; i < 1000001; i += i & -i) bit[i]++; } int get(int i) { int s = 0; for (; i; i -= i & -i) s += bit[i]; return s; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, ans = 0; cin >> n; int a[n + 1]; stack st;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = n; i > 0; i--) { if (a[i] % 2 == 0) { ans += get(a[i] - 1); st.push(a[i]); } else { while (!st.empty()) { update(st.top()); st.pop(); } } } cout << ans; } lOMoAR cPSD| 58457166
2.4MÀN HÌNH KẾT QUẢ CHẠY CODE
2.5 MÀN HÌNH KẾT QUẢ NỘP CODE
Hình 7. Kết quả chạy câu 2 3 CÂU 3
Cho biểu thức đúng P chỉ bao gồm các phép toán +, -, các toán hạng cùng với các ký tự ‘(’, ‘)’. Hãy bỏ
tất cả các ký tự ‘(’, ‘)’ trong P để nhận được biểu thức tương đương. Ví dụ với P = a – (b + c) ta có kết quả P = a – b – c . Input: •
Dòng đầu tiên đưa vào số lượng bộ test T; •
Những dòng tiếp theo mỗi dòng đưa vào một bộ test. Mỗi bộ test là một biểu thức P được viết trên một dòng. Output: •
Đưa ra kết quả mỗi test theo từng dòng. Ràng buộc: •
T, P thỏa mãn ràng buộc: 1≤T≤100; 1≤length(P)≤103.
3.1 Ý TƯỞNG BÀI TOÁN Nhập thông tin ban đầu
Duyệt từng ký tự trong biểu thức: lOMoAR cPSD| 58457166
- Nếu là dấu ‘(’: Ghi nhớ dấu ngay trước nó (‘+’ hoặc ‘-’) để sau này xử lý biểu thức bên trong ngoặc.
- Nếu là dấu ‘)’:
o Bắt đầu lấy các ký tự trong stack ra cho đến khi gặp ‘(’.
o Nếu dấu trước ‘(’ là ‘-’, thì đảo tất cả dấu ‘+’ thành ‘-’ và ngược lại. o Sau đó, đẩy
phần đã xử lý lại vào stack.
Nếu là chữ cái hoặc toán tử: đẩy vào stack.
Cuối cùng, nối các phần tử trong stack thành chuỗi kết quả.
3.2LƯU ĐỒ THUẬT TOÁN lOMoAR cPSD| 58457166 3.3 CODE #include #define endl "\n" using namespace std; int main() { ios_base::sync_with_stdio(0);
cin.tie(0); int t; cin >> t; while (t--) { string s, k, ans = ""; cin >> s; char c, d; stack st, ld;
for (int i = 0; i < s.size(); i++) { if (s[i] == '(') { st.push(s[i]); ld.push(s[i - 1]); } else if (s[i] == ')') { k = ""; while (st.size()) { c = st.top(); st.pop(); d = st.top(); st.pop(); if (ld.top() == '-') { k = c + k; if (d == '-') k = '+' + k; else k = '-' + k; } else { lOMoAR cPSD| 58457166 k = c + k; k = d + k; } if (d == '(') {
for (int j = 1; j < k.size(); j++) st.push(k[j]); break; } } ld.pop(); } else st.push(s[i]); } while (st.size()) { ans = st.top() + ans; st.pop(); }
cout << ans << endl; } }
3.4 MÀN HÌNH KẾT QUẢ CHẠY CODE
3.5 MÀN HÌNH KẾT QUẢ NỘP CODE HẾT.