Đề thi CTDL cũ

========================================== ==========================================

Một số đề kiểm tra giữa kỳ cũ môn CTDLGT

Đề cũ hơn xem tại

http://tinhocdaicuong4newbies.blogspot.com/2014/07/e-thi-cu-ctdl-2013.html

Bài tập giữa kỳ cho lớp INPG 13 và LTU 13A kỳ 20152

Bài 1. Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận. 10×10 dùng backtracking.

Chỉ có thể đi ở các ô có giá trị 1 và theo hướng lên, xuống, trái và qua phải

1100000000000001111
1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010000
0010000110101010000
1111000110101010000
1000000110101011111
1111110110101010001
1111010110101010001
1111010010100000001
1111011101111010001
1111110110101110000
0001000111101111111
1111000110101010001
1110000110101010101
1111000110101010111

Bài 2. Xây dựng các phương án tô màu cho đồ thị với các quốc gia được mô tả bằng ma trận. Các màu có thể chọn là 1,2,3,4

Liệu có thể dùng 3 màu tô cho bản đồ trên được không?

Bài 3. Xây dựng thuật toán quay lui giải sodoku 3x3 như dưới.
Có bao nhiêu phương án giải?

Cheat sheet cho Linux, Emacs và GCC

Cheat sheet cho Linux, Emacs và GCC

• Linux:
• Emacs
• Gcc

Links:

https://drive.google.com/folderview?id=0B5nb3v94xY_WT3YtTHJwVWxWcDg&usp=sharing

Bài tập giữa kỳ môn CTDL GT 20152

Bài tập giữa kỳ

Bài 1. Hoàn thiện hàm tìm dãy tăng dài nhất cài đặt dùng đệ quy

VD. dãy 1, 3, 2, 5, 6, 4, 7, 8, 9, 4, 5, 2, 1, 3, 4

Thì dãy tăng dài nhất là 4, 7, 8, 9 với độ dài 4.

Yêu cầu:

• in ra độ dài và giá trị các phần tử trong dãy tăng
• trong trường hợp có 2 dãy tăng cùng độ dài thì in ra cả 2.

Bài 2. Cho một mảng số nguyên A và một số s. Hãy xây dựng chương trình tìm hai số a,b không trùng nhau trong A sao cho có tổng đúng bằng s.

VD. A[]={1, 3, 5, 7, 6, 4, 2} và s=10 thì chương trình trả về 3 ,7 hoặc 6, 4

Yêu cầu:

• Loại bỏ các cặp số bị trùng

Bài 3. Xâu palindrome là xâu đối xứng
VD adbda hoặc abccba

Cho một xâu bất kỳ, hãy tìm và đưa ra xâu con palindrome dài nhất một cách nhanh nhất

VD. abcdcbbcdbccadbca thì xâu con là palindrome dài nhất là dcbbcd

Yêu cầu:

• Trường hợp có nhiều thì cần in ra tất cả các xâu con palindrome có độ dài dài nhất
• Thực hiện với thời gian O(n)

Bài 4. Chỉ dùng các phép toán -1 (trừ đi 1) và * 2 (nhân với 2), hãy xây dựng thuật toán biến đổi 1 số nguyên n thành 1 số nguyên m một cách nhanh nhất (dùng ít thao tác nhất)

VD. 4 thành 6 cần 2 thao tác là

(4-1)*2

Bài 5. Biểu diễn đa thức bậc n dùng danh sách liên kết đơn

Hãy viết các hàm cộng, trừ, nhân và chia hai đa thức

Bài 6. Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận 20×20 dùng backtracking.

Đầu vào là ô (1,1) và đầu ra là ô (20,20)
Chỉ có thể đi ở các ô có giá trị 1 và theo hướng lên, xuống, trái và qua phải

1100000000000001111
1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010000
0010000110101010000
1111000110101010000
1000000110101011111
1111110110101010001
1111010110101010001
1111010010100000001
1111011101111010001
1111110110101110000
0001000111101111111
1111000110101010001
1110000110101010101
1111000110101010111

Bài 7. Cho một dãy số nguyên A với số lượng phần tử là n
A[]={5,3,4,7,8,9,2,4,5}
Hãy in các dãy con tăng/giảm với độ dài dãy từ 3 đến n
VD. Với mang A trên thì

Dãy tăng độ dài 3 là: 3,4,7 và 7,8,9 và 2,4,5
Dãy tăng độ dài 4 là: 3,4,7,8 và 4,7,8,9
Dãy tăng độ dài 5 là: 3,4,7,8,9

Bài 8. Cho đầu vào là một danh sách các từ (gồm chữ cái và chữ số, có phân biệt chữ hoa và thường). Hãy viết chương trình nhập và giá trị nguyên n và in ra màn hình các từ chỉ khác nhau đúng n ký tự. Các từ ngắn hơn thì được coi là có dấu cách trống phía sau.

VD từ abc và abcde khác nhau 2 ký tự
abD và abcD khác nhau 2 ký tự

Danh sách các từ này được nhập vào từ file input.txt

Bài 9. Cho ma trận chỉ gồm 1 và 0 được nhập vào từ file.
Hãy in ra màn hình diện tích vùng chứa các số 0 lớn nhất

1111111110111110000
0001000110101010000
1111000110101010000
1111000010101010111
0010000111101010000
1111001110101010000
1000001110111111111
1111110110101010001
1111010110101010001
1111010010101010001

Ví dụ với hình trên thì diện tích lớn nhất là 21

Bài 10. Cho hai danh sách các khoảng liên tục. Hãy viết chương trình trộn hai danh sách này để được một danh sách các khoảng liên tục

Đầu vào:
Arr1 = [3-11, 17-25, 58-73];
Arr2 = [6-18, 40-47];

Đầu ra:
Arr3 = [3-25, 40-47, 58-73];

Chú ý: Các khoảng này đã được sắp theo thứ tự tăng dần cho trước

Bài 11. Cho một mảng chứa toàn số 0 và 1 và một giá trị nguyên k. Tìm đoạn con liên tục chứa nhiều số 1 nhất sau khi lật k bit 0 thành 1.

Ví dụ mảng đầu vào là {1,1,0,0,1,1,1,0,1,1}
k = 1 (chỉ được lật 1 bit 0 thành 1)

Độ dài đoạn lớn nhất là 6 (Nếu ta lật bit 0 tại vị trí chỉ số 7, ta sẽ có đoạn con chứa các bit 1 dài nhất là 6)

Bài 12. Xây dựng hàm kiểm tra xem có thể xáo trộn các ký tự trong 1 xâu ký tự đầu vào sao cho hai ký tự liên tiếp không được giống nhau

Ví dụ

apple >> alpep, so valid
b>> b, valid
bb>> bb, invalid/impossible
aab >> aba, valid
aaaabbcc >> acabacab, valid
etc.

Bài 13. Cho đầu vào là 2 xâu ký tự.

• Xâu target chỉ chứa các ký tự chữ cái và số
• xâu pattern chứa các mẫu bao gồm kyws tự chữ cái, chữ số và dâu ? và *

Xây dựng hàm kiểm tra xem xâu target có tuân theo mẫu mô tả bởi xâu pattern hay không.

Dấu ? thay cho 1 ký tự hoặc 1 chữ số
Dấu * thay cho 1 chuỗi ký tự hoặc số (có thể rỗng)

Ví dụ với các trường hợp sau thì hàm trả về giá trị TRUE.

isMatching("abab", "abab")
isMatching("abab", "a**b")
isMatching("ababab", "ab*b")
isMatching("", "*")
isMatching("aaaaaab", "*?*b") 

Điểm giữa kỳ THDC lớp sáng thứ 5 kỳ 20151

Điểm chưa cộng

Điểm cuối kỳ CTDLGT SIE (chưa cộng cho những bạn chưa đủ 10)

Hạn cuối bảo vệ là sáng thứ 2 tuần tới lúc 11h00 tại 602 nhà B1