SỞ GIÁO DỤC VÀ ĐÀO TẠO TP. CẦN
THƠ
TRƯỜNG THPT CHUYÊN LÝ TỰ TRỌNG
|
ĐỀ KIỂM TRA CHUYÊN LẦN 1
HỌC KỲ I, NĂM HỌC 2015-2016
MÔN: TIN HỌC - KHỐI 11
THỜI GIAN LÀM BÀI: 120 PHÚT
|
ĐỀ
CHÍNH THỨC
|
TỔNG QUAN ĐỀ KIỂM TRA
(Đề thi gồm 4 bài nằm trên 4 trang)
(Đề thi gồm 4 bài nằm trên 4 trang)
Bài
|
Tên bài
|
File chương trình
|
File dữ liệu
|
File kết quả
|
Điểm
|
1
|
Xếp tháp
|
towers.*
|
towers.inp
|
towers.out
|
3.0
|
2
|
Trò chơi 2048
|
game2048.*
|
game2048.inp
|
game2048.out
|
2.0
|
3
|
Biểu diễn đồ thị
|
graph.*
|
graph.inp
|
graph.out
|
3.0
|
4
|
Kế hoạch ôn tập
|
todolist.*
|
todolist.inp
|
todolist.out
|
2.0
|
Lưu ý: Phần mở rộng * có thể là
pas hoặc cpp (tùy vào ngôn ngữ sử dụng là Pascal hay C++)
|
|||||
NỘI DUNG ĐỀ KIỂM TRA
Bài 1:
Xếp tháp
Tính vừa
nhận được một hộp quà chứa n thanh gỗ, thanh gỗ thứ i có độ dài li.
Bây giờ Tính muốn xếp lại các thanh gỗ theo quy tắc: “các thanh gỗ cùng độ
dài sẽ chung một nhóm”.
Yêu cầu:
Với chiều dài các thanh gỗ biết trước, hãy giúp Tính xác định xem nhóm có nhiều
thanh gỗ nhất là bao nhiêu thanh và có tổng cộng có bao nhiêu nhóm thanh gỗ.
Dữ liệu
vào: Cho trong file văn bản towers.inp có cấu trúc
như sau:
Ø Dòng
đầu ghi số nguyên dương n £ 1000.
Ø
Dòng thứ hai ghi n số
nguyên dương, mỗi số cách nhau một dấu cách và có giá trị không vượt quá 1000 lần
lượt cho biết độ dài các thanh gỗ.
Kết quả:
Ghi ra file văn bản towers.out gồm 2 số, số đầu cho biết số
lượng thanh gỗ ở nhóm có nhiều thanh gỗ nhất, số thứ hai cho biết số lượng nhóm
mà Tính có thể có.
Ví dụ
towers.inp
|
towers.out
|
4
1 2 3 4
|
1 4
|
5
1 2 3 2 5
|
2 4
|
Bài 2:
Trò chơi 2048
Yêu cầu:
cho biết một trạng thái hiện tại của trò chơi và phím được bấm,
hãy xác định trạng thái tiếp theo của trò chơi.
Dữ liệu
vào: cho trong file văn bản game2048.inp có cấu trúc
như sau:
Ø 4
dòng đầu, mỗi dòng ghi 4 số nguyên cho biết trạng thái hiện tại của trò chơi.
Giá trị của các số thuộc tập {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024}, số
0 cho biết ô đó không có giá trị (ô trống).
Ø
Dòng thứ 5 ghi 1 số nguyên có
giá trị là 0, 1, 2 hoặc 3 cho biết các phím được bấm tương ứng là qua trái, lên
trên, qua phải và xuống dưới.
Kết quả:
ghi ra file văn bản game2048.out gồm 4 dòng, mỗi dòng ghi 4
số nguyên cho biết trạng thái mới của trò chơi, số 0 cho biết ô trống. Ở đây,
chúng ta không quan tâm đến sự xuất hiện ngẫu nhiên các số mới như trong trò
chơi thật.
Lưu ý:
Các số trên cùng một dòng cách nhau một dấu cách, các quy tắc di chuyển được mô
tả chi tiết trong các ví dụ.
Ví dụ
game2048.inp
|
game2048.out
|
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
0
|
4 0 0 0
4 16 8 2
2 64 32 4
2048 64 0 0
|
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
1
|
2 16 8 4
4 64 32 4
2 1024 64 0
1024 0 0 0
|
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
2
|
0 0 0 4
4 16 8 2
2 64 32 4
0 0 2048 64
|
2 0 0 2
4 16 8 2
2 64 32 4
1024 1024 64 0
3
|
2 0 0 0
4 16 8 0
2 64 32 4
1024 1024 64 4
|
2 2 4 8
4 0 4 4
16 16 16 16
32 16 16 32
0
|
4 4 8 0
8 4 0 0
32 32 0 0
32 32 32 0
|
2 2 4 8
4 0 4 4
16 16 16 16
32 16 16 32
2
|
0 4 4 8
0 0 4 8
0 0 32 32
0 32 32 32
|
Bài 3:
Biểu diễn đồ thị
Cho một
đồ thị vô hướng gồm n đỉnh được đánh số từ 1 đến n và m cạnh
được biểu diễn bằng ma trận kề, hãy biểu diễn đồ thị đã cho ở dạng danh sách kề.
Dữ liệu
vào: cho trong file văn bản graph.inp có cấu trúc như
sau:
Ø
Dòng đầu ghi 1 số nguyên dương n
£
1000 cho biết kích thước ma trận kề của đồ thị.
Ø
n dòng
tiếp theo, mỗi dòng ghi n số có giá trị là 0 hoặc 1 mô tả ma trận kề của
đồ thị.
Kết quả:
ghi ra file văn bản graph.out có cấu trúc như sau:
Ø Dòng
đầu tiên ghi 2 số nguyên dương n và m lần lượt cho biết số đỉnh
và số cạnh của đồ thị.
Ø Dòng
thứ i trong n dòng tiếp theo, mỗi dòng ghi theo cấu trúc
sau:
·
Số đầu tiên ghi i, số thứ
hai ghi k cho biết có k đỉnh kề với đỉnh thứ i.
·
k số tiếp
theo ghi các đỉnh kề với đỉnh i, k số này ghi theo thứ tự từ bé đến
lớn.
Ví dụ:
graph.inp
|
graph.out
|
4
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
|
4 4
1 2 2 3
2 2 1 3
3 3 1 2 4
4 1 3
|
Bài 4: Kế hoạch ôn tập
Tân
vừa đặt ra một kế hoạch ôn tập để có thể vào được đội tuyển dự thi học sinh giỏi
cấp quốc gia môn Tin học năm học 2015-2016. Hiện giờ Tân đang có n bài tập
cần phải giải quyết hết trước ngày thi chọn đội tuyển sắp tới. Thời gian từ đây
đến ngày thi còn khá lâu nên Tân hoàn toàn tự tin mình sẽ có đủ thời gian để giải
quyết hết số bài tập này. Tuy nhiên, vấn đề đặt ra là: không phải Tân muốn giải
bài nào là có thể bắt tay vào làm ngay bài đó, đôi khi có những bài cần kiến thức
của các bài khác, do đó Tân cần phải sắp xếp một thứ tự hợp lý để giải n
bài tập này, và đây là vấn đề gây rất nhiều khó khăn cho bạn ấy. Các bạn trong
lớp mình hãy tìm cách giúp Tân nhé!
Yêu cầu: Cho biết số lượng bài tập Tân
cần giải và các ràng buộc giữa các bài tập (mỗi ràng buộc là thứ tự phải làm của
2 bài tập trong số n bài của Tân).
Dữ liệu vào: cho trong file văn bản
todolist.inp có cấu trúc như sau:
Ø Dòng đầu ghi 2 số nguyên dương n và m (n £
1000, m £ 10000) lần lượt cho biết số lượng bài tập
và số ràng buộc.
Ø
Dòng thứ hai ghi n tên
bài tập, mỗi tên bài tập là một xâu chỉ chứa các chữ cái in thường, chữ số và có
không quá 10 ký tự, các tên bài tập cách nhau 1 dấu cách.
Ø
m dòng
tiếp theo, mỗi dòng ghi 2 tên bài x và y cho biết ràng buộc bài x
phải được làm trước bài y.
Dữ liệu cho
đảm bảo luôn tìm được kết quả.
Kết quả: ghi ra file văn bản
todolist.out gồm n dòng, mỗi dòng là tên một bài tập cho biết thứ tự cần
phải làm của Tân (nếu có nhiều kết quả, ghi ra một trong số chúng).
Ví dụ:
todolist.inp
|
todolist.out
|
4 3
uva100 uva10027 uva10046 uva458
uva100 uva10027
uva100 uva10046
uva458 uva100
|
uva458
uva100
uva10027
uva10046
|
-----HẾT-----
(Giám thị coi thi không giải thích gì thêm)
No comments:
Post a Comment