Đề thi chọn học sinh giỏi môn Tin học Lớp 11 - Năm học 2015-2016 - Trường THPT Tam Dương II

Nội dung text: Đề thi chọn học sinh giỏi môn Tin học Lớp 11 - Năm học 2015-2016 - Trường THPT Tam Dương II

1. TRƯỜNG THPT TAM DƯƠNG II ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 11 MÔN: TIN HỌC Năm học: 2015 - 2016 Thời gian làm bài: 180 phút không kể thời gian phát đề Chú ý: Các file chương trình đặt tên lần lượt là: BL1.PAS; BL2.PAS; BL3.PAS Đề thi có: 02 trang Câu 1: (3,0 điểm) Xâu ngoặc Cho xâu S độ dài không quá 250 chỉ gồm các kí tự ‘(‘,’)’. Hãy xác định số cặp chỉ số (p,q) sao cho p<q và Sp=Sp+1= ‘(‘ ; Sq=Sq+1= ‘)‘. Chẳng hạn, với xâu S =’)((()())())’, ta có 4 cặp chỉ số (p,q) là (2,7), (2,10); (3,7) và (3,10) Dữ liệu (xaungoac.inp) - Một dòng duy nhất ghi xâu ngoặc độ dài không vượt quá 250 Kết quả (xaungoac.out) - Một dòng ghi một số nguyên là số cặp (p,q) thỏa mãn yêu cầu bài toán Ví dụ: xaungoac.inp xaungoac.out )((()())()) 4 Câu 2: (3,5 điểm) Số thân thiện Đang tìm hiểu các thuật toán về số tự nhiên, Nguyên phát hiện ra số tự nhiên có rất nhiều tính chất thú vị. Ví dụ số hoàn hảo có tính chất: tổng các ước bằng 2 lần số đó, như số 6, số 24 Nhiều số tự nhiên khi tìm ước chung lớn nhất với số đảo ngược của nó bằng 1, những số như thế được gọi là số thân thiện. Chẳng hạn số 23, số đảo ngược của nó là 32, hai số này có ước chung lớn nhất là 1 nên số 23 là số thân thiện và 32 cũng là số thân thiện. Yêu cầu: Cho 2 số tự nhiên a, b (10 ≤ a ≤ b ≤ 104). Hãy đếm xem trong đoạn từ a đến b có bao nhiêu số thân thiện. Dữ liệu (thanthien.inp) - Một dòng duy nhất ghi 2 số tự nhiên a, b Kết quả (thanthien.out) - Một dòng ghi một số nguyên là số lượng số thân thiện Ví dụ: thanthien.inp thanthien.out Giải thích 19 29 4 Đó là các số: 19, 23, 25, 29 Câu 3: (3,5 điểm) Đếm kí tự Cho xâu S chỉ chứa các kí tự in thường ‘a z’ và các kí tự số từ ‘0 9’. Hãy đếm và đưa ra màn hình số lượng kí tự khác nhau trong xâu S. 1
2. Dữ liệu ( demkt.inp) gồm một dòng duy nhất chứa xâu S Kết quả ( demkt.out) một số nguyên là số lượng số kí tự khác nhau trong xâu Ví dụ: DEMKT.INP DEMKT.OUT Abcabcaab 3 HẾT Giám thị coi thi không giải thích gì thêm 2
3. TRƯỜNG THPT TAM DƯƠNG II ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 11 MÔN: TIN Năm học: 2015 - 2016 HƯỚNG DẪN CHẤM I. Phương pháp: - Giám khảo tạo bộ dữ liệu vào, tính toán kết quả. Thực hiện chương trình của học sinh và so sánh kết quả. - Giám khảo có thể sử dụng chương trình gợi ý dưới đây để tính toán kết quả của dữ liệu vào. - Chương trình học sinh đúng một bộ test, giám khảo cho 0,5 điểm. Như vậy, nếu một câu có 3 điểm thì giám khảo phải tạo 6 bộ test. - Với mỗi câu, giám khảo phải tạo được ít nhất một bộ test có không gian dữ liệu lớn. II. Chương trình gợi ý: Câu 1: (3,0 điểm) var f1,f2:text; s:string; d,i,j,n:integer; procedure nhap; begin assign(f1,'xaungoac.inp'); reset(f1); readln(f1,s); close(f1); end; procedure kq; begin assign(f2,'xaungoac.out'); rewrite(f2); n:=length(s); d:=0; for i:=1 to n-2 do for j:=i+2 to n do if (s[i]='(') and (s[i+1]='(') and (s[j]=')') and (s[j+1]=')') then d:=d+1; write(f2,d); close(f2); end; begin nhap; kq; end. Câu 2: (3,5 điểm) var f1,f2:text; 3
4. a,b,i,t:longint; function UCLN(x,y:longint):longint; var r:longint; begin while y>0 do begin r:=x mod y; x:=y; y:=r; end; ucln:=x; end; function sodao(x:longint):longint; var y:longint; begin y:=0; while x<>0 do begin y:=y*10+(x mod 10); x:=x div 10; end; sodao:=y; end; procedure nhap; begin assign(f1,'thanthien.inp'); reset(f1); readln(f1,a,b); close(f1); end; procedure kq; begin assign(f2,'thanthien.out'); rewrite(f2); t:=0; for i:=a to b do if ucln(i,sodao(i))=1 then t:=t+1; write(f2,t); close(f2); end; begin nhap; kq; end. Câu 3: (3,5 điểm) var f1,f2:text; s:string; i,j,k,n:integer; procedure nhap; begin assign(f1,'demkt.inp'); reset(f1); 4
5. read(f1,s); close(f1); end; procedure kq; begin assign(f2,'demkt.out'); rewrite(f2); i:=1; n:=length(s); while (i<=n) do begin for k:=i+1 to n do if (s[i]=s[k]) then delete(s,k,1); i:=i+1; end; n:=length(s); write(f2,n); close(f2); end; begin nhap; kq; end. 5