SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH CẤP TỈNH
TỈNH HẬU GIANG LỚP 12 NĂM HỌC 2009-2010
Khóa ngày 26 tháng 11 năm 2009

ĐỀ CHÍNH THỨC

MÔN: TIN HỌC
Thời gian: 180 phút, không kể phát đề


Câu 1: (6 điểm)
Hãy tìm tất cả các số X (M≤X≤N; M,N là hai số nguyên dương) thỏa mãn:
X là số nguyên tố
X là số Fibonacci
Số Fibonacci được định nghĩa như sau


Dữ liệu vào: được cho trong tập tin văn bản NGTOFIB.INP. Gồm hai số nguyên dương M, N (M≤N≤65535)
Kêt quả: ghi vào tập tin văn bản NGTOFIB.OUT.
Dòng đầu là số nguyên dương T (T là số các số X tìm được; Nếu không tìm được số X thì T=0)
T dòng tiếp theo mỗi dòng là một số X tìm được.
Ví dụ :
NGTOFIB.INP NGTOFIB.OUT
1 10 3
2
3
5
Câu 2 : (7 điểm)
Có M trường học. Biết rằng đường đi giữa 2 trường bất kì (nếu có) đều là đường đi 2 chiều. Sơ đồ mạng lưới giao thông của M trường học này cho bới ma trận A[i,j] trong đó
A[i,j] là độ dài đường đi từ trường i đến trường j
A[i,j] = 0 nếu không có đường đi từ trường i đến trường j
A[i,j] = A[j,i]
A[i,j] nguyên, không âm
Hãy xác định đường đi ngắn nhất giữa 2 trường học O và P (O, P là thứ tự trường đi và trường đến) hay thông báo không tồn tại lời giải
Dữ liệu vào: cho tập tin văn bản TRUONG.INP. Gồm M+2 dòng
Dòng đầu chứa số M (M nguyên dương, M≤50)
Dòng i+1 (1≤i≤M) ghi M số A[i,1], A[i,2],… A[i,M]
Dòng M+2 ghi hai số O và P.
Các số ghi cùng một dòng cách nhau ít nhất một dấu cách

Kết quả: ghi vào tập tin văn bản TRUONG.OUT
Ví dụ:
TRUONG.INP TRUONG.OUT
6 Duong di ngan nhat tu 1 den 5 là 18
0 5 0 0 0 9 1 --> 6 --> 5
5 0 6 0 0 0
0 6 0 7 0 0
0 0 7 0 8 0
0 0 0 8 0 9
9 0 0 0 9 0
1 5
Câu 3: (7 điểm)
Quan hệ vòng
Lớp học có N (0
Dữ liệu vào: tập tin văn bản HOCSINH.INP có các dòng ghi theo dạng: đầu tiên là tên học sinh sau đó là tên các học sinh mà học sinh đó biết nhà (Ví dụ : Tay Nam Bac : nghĩa là bạn Tay biết nhà 2 bạn Nam và bạn Bac). Các tên ghi cách nhau dấu cách.
Kết quả: ghi vào tập tin văn bản HOCSINH.OUT:
Nếu có: dòng 1 ghi tổng số học sinh, dòng 2 ghi tên những học sinh trong vòng quay lớn nhất.
Nếu không có thì ghi là không có quan hệ quay vòng.
Ví dụ:
HOCSINH.INP HOCSINH.OUT
tay nam bac 3
dong nam tay dong nam
tay dong
nam tay

--------Hết----------
Đề thi này gồm 2 trang