Bài tập CTDLGT cho SIE 20162

Bài tập cho SIE CTDLGT 20162

Đầu vào:
1 tập văn bản tiếng việt (có thể lấy từ các đoạn chat hoặc nhắn tin cá nhân)
1 từ điển tiếng việt ngắn

Yêu cầu

Lọc và thống kê các 1-gram, 2-gram từ tập văn bản tiếng Việt
(1 gram là 1 âm tiết, 2 gram là 2 âm tiết)

VD câu "BK Hà Nội"
thì 1-gram là BK, Hà, Nội
2-gram là BK Hà, Hà Nội

• Loại các gram có tần số xuất hiện <=3 mà không chứa toàn chữ cái viết hoa
• Thống kê các gram đó và sắp xếp theo thứ tự giảm đần về tần số

Xây dựng gợi ý theo cấp độ từ

•  Khi người dùng gõ vào xong 1 từ (nhập từ + dấu cách trống) thì sẽ duyệt các 1 giảm và 2 Gram có, và cả các từ trong từ điển. Trường hợp mà từ đó chưa có trong từ điển hoặc danh sách thì gợi ý các từ có thể tạo ra được hoặc từ chính xác (vì có thể người đó gõ sai).

VD. Người dùng gõ vào Bn thì đưa ra gợi ý là: BK, BK Hà

Xây dựng gợi ý theo cấp độ chữ cái

• Khi người dùng nhập vào >=2 chữ cái thì gợi ý tiếp các chữ cái và từ còn lại.

VD. Người dùng nhập vào Hà thì gợi ý là Hà Nội

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