Bài tập CTDLGT Giữa kỳ cho DH 20162 (học chiều thứ 5)

Bài 1. Cho 1 dãy gồm n số dương, hay xây dựng hàm chia day số này thành 2 nửa sao cho chênh lệch tổng giá trị các phần tử của 2 nửa là nhỏ nhất trong 2 trường hợp
a. Không được thay đổi vị trí các phần tử
b. Được thay đổi vị trí các phần tử

Bài 2. Cho 1 mảng có các phần tử bị trùng. Hãy xây dựng thuật toán sắp xếp mảng sao cho các phần tử bị trùng được đẩy về cuối dãy.

VD. 1,3,2,4,3,2,1,6 ==> 1,2,3,4,6,1,3,2

Bài 3. Cho 1 mảng gồm n số nguyên. Hãy tìm và in ra các bộ 3 có tổng bằng 0, hoặc thông báo không tồn tại bộ nào như vậy.

VD. 1,3,-2,4,-6,5,-4,2,-1
{1,3,-4}, {5,-4,1}

Thời gian thực hiện cần < O(n^3)

Bài 4. Viết hàm xóa các phần tử bị lặp trong DSLK đơn (không có thứ tự) với thời gian thực hiện O(n) mà không cần dùng thêm bộ nhớ phụ.
Không được sắp xếp danh sách !

Được khai báo thêm con trỏ và biến tạm

Bài 5. Cho danh sách liên kết đơn nối vòng, hay viết hàm trả về phần tử giữa danh sách chỉ với 1 lần duyệt

Bài 6. Viết hàm xóa phần tử hiện tại của DSLK đơn khi mà có biết 1 con trỏ tới phần tử cần xóa (không được duyệt để tìm phần tử ngay trước nó)

Bài 7. Đọc vào 1 file XML/HTML. Viết chương trình kiểm tra các thẻ Tag có hợp lệ hay không. Nếu không thì in ra vị trí thẻ bị lỗi đầu tiên.
Tag mở cần có 1 tag đóng tương ứng (bỏ qua tag <p> hoặc <br> nếu cần)

Bài 8. Xây dựng tiện ích Undo và reDo cho text editor với tính năng quay lui lại sửa đổi gần nhất dùng Stack. Nếu dùng trên console thì có thể chọn hot key Ctr-U và Ctrl-I và dùng hàm để bắt các hotkey này để xử lý.

Bài 9. Cho tập gồm n điểm trong không gian 2 chiều. Hãy xây dựng chương trình dựa trên chia để trị để tìm và trả về 2 cập điểm gần nhau nhất với thời gian <O(n^2)

Bài 10. Cho bảng gồm các ký tự và dấu cách trống được mã hóa
a : 1
b : 2
..
z : 26
' ' : 27

abc --> 123

Và 1 từ điển

Hãy xây dựng chương trình mã hóa và giải mã các từ trong 1 đoạn văn (các từ này phải có trong từ điển)

123 >> abc, aw, lc

Bài 11. Cho 1 tập các khoảng thời gian còn trống của máy
[-1,9],[1,10],[0,3],[9,10],[3,14],[2,9],[10,16]

và 1 khoảng thời gian cần sản xuất VD [2,15]

Hãy xây dựng chương trình tìm  cách bố trí số lượng máy ít nhất để có thể sản xuất, hoặc thông báo là không thể bố trí được máy

[2,15] = [-1,9], [9,10],[10,16] hoặc [1,10],[10,16]

Ở đây cách 2 dùng 2 máy sẽ được chọn

Bài 12. Cho ma trận nxn với m chướng ngại vật

0 0 0 0 0 0
0 1 0 0 1 0
0 1 1 0 0 0
1 0 0 0 0 0
0 0 1 0 0 0

Chướng ngại vật biểu diễn bằng số 1
1 robot do đường có thể đi theo các hướng
1: lên trên
2: sang phải
3: xuống dưới
4: sang trái
Nếu vào chướng ngại vật thì robot sẽ không di chuyển được

Robot bắt đầu từ ô đầu tiên bên trái (màu đỏ) và gửi về hành trình của mình là chuỗi di chuyển 2 2 2 3 2 3 2
Hãy tìm và trả về vị trí cuối cùng của robot
Như trong vd thì robot sẽ ở ô  bôi vàng