Đề thi học sinh giỏi năm 2010

     SỞ GIÁO DỤC VÀ ĐÀO TẠO              KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH

                   KHÁNH HÒA                                                NĂM HỌC 2009-2010

                       ¾¾¾¾                                                      ¾¾¾¾¾¾¾¾¾

ĐỀ THI CHÍNH THỨC

                                                                               Môn thi : TIN HỌC – THCS (Bảng A)

                                                                                               Ngày thi : 06/4/2010

                                                                    (Thời gian : 150 phút – không kể thời gian phát đề)

                                                                                 ¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾

BÀI 1: (5 điểm)

Viết chương trình nhập số nguyên dương N, và dãy số thực A gồm có N số. Kiểm tra xem dãy vừa nhập đã được sắp xếp thành dãy tăng, hoặc giảm hoặc không tăng, không giảm? Thông báo kết quả trên màn hình.

Ví dụ 1:

Dữ liệu vào:   N =8, A = 1.2  3.5  4.0  5.3  6.0  7.7  8.1  9.0

Dữ liệu ra:      Day so da duoc sap xep thanh day tang.

Ví dụ 2:

Dữ liệu vào:   N= 7, A = 9.0  8.5  7.3  6.0  5.5  4.7  3.0

Dữ liệu ra:      Day so da duoc sap xep thanh day giam.

BÀI 2: (5 điểm)

Viết chương trình nhập các số nguyên dương N, K và dãy số thực A gồm có N số. Xét xem trong dãy số A có K số dương đứng cạnh nhau hay không?

Ví dụ 1:

            Dữ liệu vào:  

N = 8

A = 2 -2 5 7 3 0 2 -1

K = 4

            Dữ liệu ra: Trong day khong co 4 so duong dung canh nhau

Ví dụ 2:

            Dữ liệu vào:  

N = 9

A = 1 -2 3 7 9 1 2 -1 -7

K = 5

            Dữ liệu ra: Trong day co 5 so duong dung canh nhau

BÀI 3 : (5 điểm)

Mảng là kiểu dữ liệu có cấu trúc của ngôn ngữ lập trình Pascal, gồm một số hữu hạn các phần tử có cùng kiểu, có cùng một tên chung. Số phần tử của mảng được xác định khi mảng được định nghĩa, kiểu của các phần tử gọi là kiểu cơ bản của mảng. Ta có mảng một chiều, mảng hai chiều, ...

Để khai báo một mảng hai chiều (còn gọi ma trận) có n hàng, m cột, ta viết như sau :

CONST           n = .... ; m = ..... ;

TYPE  Tên_mảng = ARRAY[1..n,1..m] OF Kiểu_phần_tử;

VAR    Tên_biến_mảng : Tên_mảng;

Xem ví dụ sau :

CONST    n = 3 ; m = 4 ;

TYPE       Ma_tran = ARRAY[1..n,1..m] Of Integer;

VAR         X : Ma_tran;

Lúc đó biến X theo khai báo ở trên là một mảng (ma trận) gồm 3 hàng, 4 cột. Như vậy mảng này có tất cả 3*4 = 12 phần tử, mỗi phần tử là một số nguyên. Phần tử hàng i, cột j của mảng X được viết X[i,j]. Để nhập/xuất dữ liệu cho các phần tử của mảng X ta viết như sau :

Nhập dữ liệu :   For i :=  1 to n do

                                         For j := 1 to m do

                                         Begin

                                                     Write(‘Nhap gia tri X[‘,i,’,’,j,’] = ’);

                                                     Read(X[i,j]);

                                         End;

Xuất dữ liệu :    For i :=  1 to n do

                             Begin

For j := 1 to m do Write(X[i,j]);

Witeln;

                             End;

Ma trận vuông là ma trận có số hàng bằng số cột. Ma trận vuông cấp N là ma trận có số hàng bằng số cột đều bằng N.

Hãy viết chương trình điền các phần tử của ma trận vuông cấp N (0< N £ 200) gồm các số –1, 0, 1 sao cho tổng các số của mọi hình vuông cấp 2 đều bằng 0 và tổng các số của ma trận cấp N là lớn nhất.

BÀI 4 : (5 điểm)

Palindrome là xâu ký tự mà nếu đọc nó từ trái sang phải cũng như từ phải sang trái ta được cùng một xâu. Một xâu ký tự bất kỳ luôn có thể biểu diễn như là một dãy các palindrome nếu như ta coi xâu chỉ gồm một ký tự luôn là palindrome.

Ví dụ: Xâu ‘bobseesanna’ có thể biểu diễn dưới dạng dãy các palindrome theo nhiều cách, chẳng hạn

‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’

‘bobseesanna’ = ‘bob’ + ‘s’ + ‘ee’ + ’s’ + ‘anna’

‘bobseesanna’ = ‘b’ +’o’ + ‘b’ + ‘sees’ + ‘a’ + ‘n’ + ‘n’ + ‘a’

Yêu cầu: Cho xâu ký tự s, cần tìm cách biểu diễn xâu s dưới dạng một dãy gồm một số ít nhất các palindrome. 

Ví dụ: Cho s = ‘bobseesanna’, do ta có  ‘bobseesanna’ = ‘bob’ + ‘sees’ + ‘anna’ và không thể biểu diễn ‘bobseesanna’ bởi ít hơn là 3 palindrome nên biểu diễn này chính là biểu diễn cần tìm.

Dữ liệu: Vào từ file văn bản PALINDR.INP gồm một dòng chứa xâu ký tự s gồm không quá 255 ký tự.

Kết quả: Đưa ra màn hình đồng thời ghi vào file văn bản PALINDR.OUT:

- Dòng đầu tiên ghi k là số lượng ít nhất các palindrome trong biểu diễn tìm được;

- Dòng thứ i trong số k dòng tiếp theo ghi palindrome p_i (i = 1, 2, ..., k) sao cho :

s = p₁p₂...p_k.

Ví dụ

PALINDR.INP	PALINDR.OUT		PALINDR.INP	PALINDR.OUT
bobseesanna	3 bob sees anna		aabbaaaabb	2 aa bbaaaabb

¾¾¾¾¾¾¾¾¾¾ HẾT ¾¾¾¾¾¾¾¾¾¾

Ghi chú :

- Các tập tin bài làm phải đặt theo qui định BL1.PAS, BL2.PAS, BL3.PAS, BL4.PAS;

- Đề thi có 03 trang;

- Giám thị không giải thích gì thêm.