Đề thi olympic 10-3 lần thứ 3 môn Tin học Lớp 11 - Trường THPT Trường Chinh (Có đáp án)

Nội dung text: Đề thi olympic 10-3 lần thứ 3 môn Tin học Lớp 11 - Trường THPT Trường Chinh (Có đáp án)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐẮK LẮK TRƯỜNG THPT TRƯỜNG CHINH KÌ THI OLYMPIC 10-3 LẦN III ĐỀ THI ĐỀ NGHỊ MÔN: TIN HỌC– LỚP 11
2. SỞ GD&ĐT ĐẮK LẮK ĐỀ THI OLYMPIC 10 – 3 LẦN THỨ III NĂM 2018 Đề thi Đề Nghị Môn thi: TIN HỌC– LỚP 11 (Đề thi có 02 trang) Thời gian làm bài: 180 phút, không kể thời gian phát đề TỔNG QUAN ĐỀ THI Tên bài Tên chương Dữ liệu vào Dữ liệu ra Điểm trình Bài 1 Số chính SO_CP.* SO_CP.INP SO_CP.OUT 6đ phương Bài 2 Chuổi đối CHUOI_LT.* CHUOI_LT.INP CHUOI_LT.OUT 7đ xứng liên tiếp Bài 3 Đi siêu thị SIEU_THI.* SIEU_THI.INP SIEU_THIOUT 7đ Kí tự ‘*’ được thay bằng ‘PAS’ nếu thí sinh sử dụng ngôn ngữ Pascal, hoặc được thay bằng ‘CPP’ nếu sử dụng ngôn ngữ C/C++ Bài 1: Số chính phương (6,0 điểm) Số chính phương là một số mà tự nó là căn bậc hai của một số tự nhiên khác, hay nói rõ hơn thì số chính phương là bình phương của một số tự nhiên. Một dãy số gồm N số nguyên bất kỳ. Hãy kiểm tra trong dãy số đó có bao nhiêu số chính phương. Dữ liệu vào: Đọc từ tệp văn bản: SO_CP.INP có cấu trúc - Dòng đầu chứa số nguyên N. - Dòng thứ hai chứa các phần tử a1 -> aN. Dữ liệu ra: Ghi ra tệp văn bản SO_CP.OUT một số nguyên duy nhất là kết quả tìm được. Ví dụ: SO_CP.INP SO_CP.OUT 5 4 4 7 9 16 25 Bài 2: Chuổi đối xứng liên tiếp (7,0 điểm)
3. Một chuổi S được gọi là chuổi đối xứng liên tiếp nếu S[i]=S[length(S)-i] với mọi i thỏa 1 ≤ i ≤ length(s). Cho một chuổi S dài không quá 255 kí tự. Hãy cho biết độ dài chuổi con đối xứng liên tiếp dài nhất trong chuổi S. Dữ liệu vào: Đọc từ tệp văn bản: CHUOI_LT.INP có cấu trúc - Gồm một dòng ghi chuổi kí tự S. Dữ liệu ra: Ghi ra tệp văn bản CHUOI_LT.OUT một số nguyên duy nhất chỉ chiều dài lớn nhất của chuổi con đối xứng dài nhất trong S. Ví dụ: CHUOI_LT.INP CHUOI_LT.OUT abccbghjkaaaaaaaaaakfwg 12 Bài 3: Đi siêu thị (7,0 điểm) Trong siêu thi Copmart có n món hàng (N ≤ 50). Món thứ i có khối lượng là W[i]≤ 50 Có giá trị V[i] ≤ 50. Em là người giúp mẹ đi siêu thị mua hàng, mang theo một cái túi có thể mang được tối đa khối lượng là M(M≤50) Em cần chọn những món hàng nào để bỏ vào cái túi sao tổng giá trị của các món hàng đã chọn là lớn nhất nhưng không vượt quá khối lượng M. Mỗi món chỉ chọn 1 hoặc không chọn. Dữ liệu vào: Đọc từ tệp văn bản: SIEU_THI.INP có cấu trúc - Dòng đầu chứa số nguyên N, M. - Dòng thứ hai chứa khối lượng các phần tử W1 -> WN. - Dòng thứ hai chứa giá trị các phần tử V1 -> VN Dữ liệu ra: Ghi ra tệp văn bản SIEU_THI.OUT. - Dòng đầu chứa giá trị lớn nhất bỏ vào túi. - Dòng thứ hai chứa các món hàng được chọn. Ví dụ: CHUOI_LT.INP CHUOI_LT.OUT 5 13 16 3 4 5 2 1 1 2 3 5 4 5 6 3 1 Hết Thí sinh không được sử dụng tài liệu. Giám thị không giải thích gì thêm. Họ và tên thí sinh: Số báo danh: Chữ kí của giám thị 1: Chữ kí của giám thị 2:
4. ĐÁP ÁN, BIỂU ĐIỂM VÀ HƯỚNG DẪN CHẤM MÔN TIN HỌC - LỚP 11 (Đáp án, biểu điểm và hướng dẫn chấm gồm tất cả 05 trang) HƯỚNG DẪN CHẤM I. HƯỚNG DẪN CHUNG: Sử dụng phần mềm chấm thi Themis (Version 1.9.0 build 1486) của thầy Lê Minh Hoàng-Đỗ Đức Đông, thông qua các bộ Test mẫu của giám khảo để chấm thi tự động. II. GỢI Ý THUẬT TOÁN: Bài 1: (6,0 điểm) - Số chính phương - Đọc dữ liệu vào mảng một chiều, kiểm tra số chính phương từng phần tử. Bài 2: (7,0 điểm) - Chuổi đối xứng liên tiếp - Sử dụng thuật toán duyệt toàn bộ và xử lý xâu??? Bài 3: (7,0 điểm) - Đi siêu thị Sử dụng phương pháp Quy hoạch động để giải. - Gọi F[i,j] là tổng khối lượng các món hàng được chọn vào túi. Cơ sở: F[0,j]=0; - Công thức quy hoạch động: F[i,j]:=F[i-1,j] III. Chương trình nguồn: Bài 1: (6,0 điểm) - Số chính phương Program So_CP; Uses Crt; Const tep_vao='SO_CP.INP'; tep_ra='SO_CP.OUT'; N_Max=100; Type Mang1c=array[1 N_Max] of Integer; Var a: Mang1c; f_vao, f_ra:text; i, N: Integer; Procedure nhap; Begin Assign(f_vao, tep_vao); Reset(f_vao); Readln(f_vao,N); Writeln(N); For i:=1 to N do Begin Read(f_vao, a[i]); Writeln(a[i]); End; Close(f_vao);
5. End; Procedure Kt_So_CP; Var x, dem:Integer; Begin dem:=0; For i:=1 to n do Begin x:=trunc(Sqrt(a[i])); if (sqr(x)=a[i]) then Begin dem:=dem+1; Writeln(a[i]); End; End; Writeln('Tong so chinh phuong la ',dem); Assign(f_ra,tep_ra); Rewrite(f_ra); Write(f_ra,dem); Close(f_ra); End; Begin {Chuong trinh chinh} Clrscr; nhap; Kt_So_CP; Readln; End. Bài 2: (7,0 điểm) - Chuổi đối xứng liên tiếp Program Chuoi_DX_LT_Dai_Nhat; Uses Crt; Const tep_vao='Chuoi_LT.INP'; tep_ra='Chuoi_LT.OUT'; Var S: String; f_vao, f_ra:text; max: Integer; Procedure nhap; Begin Assign(f_vao, tep_vao); Reset(f_vao); Read(f_vao, S); Writeln(S);
6. Close(f_vao); End; Procedure Xu_Ly; Var i, j, k:Integer; ok: Boolean; Begin max:=1; For i:=1 to length(S) do Begin For j:=length(S) downto i+1 do if (S[i]=S[j]) then Begin ok:=true; for k:=0 to (j-i) div 2 do If(S[i+k] max then max:=j-i+1; End; End; End; Procedure Xuat; Begin Assign(f_ra,tep_ra); Rewrite(f_ra); Writeln(max); Write(f_ra,max); Close(f_ra); End; Begin {Chuong trinh chinh} Clrscr; nhap; Xu_ly; Xuat; Readln; End. Bài 3: (7,0 điểm) - Đi siêu thị Program Di_Sieu_Thi;
7. Uses Crt; Const tep_vao='SIEU_THI.INP'; tep_ra='SIEU_THI.OUT'; N_max=100; Type Mang1c=Array[1 N_max] of Integer; Var w, v: Mang1c; f:Array[0 N_max,0 N_max] of Integer; f_vao, f_ra:text; N, M, i, j: Integer; Procedure nhap; Begin Assign(f_vao, tep_vao); Reset(f_vao); Readln(f_vao,N, M); Writeln(N,' ',M); For i:=1 to N do Begin Read(f_vao,w[i]); Writeln(w[i]); End; For i:=1 to N do Begin Read(f_vao,v[i]); Writeln(v[i]); End; Close(f_vao); End; Procedure Xu_Ly; Begin Assign(f_ra,tep_ra); Rewrite(f_ra); for i:=1 to n do for j:=0 to m do Begin f[i,j]:=f[i-1,j]; if(j>=w[i]) and (f[i,j]<f[i-1,j-w[i]]+v[i])then f[i,j]:=f[i-1,j-w[i]]+v[i]; End; Writeln(f[n,m]); Writeln(f_ra,f[n,m]); i:=0; j:=m; While i<=n do
8. Begin if f[i,j]<> f[i-1,j] then Begin Write(i,' '); Write(f_ra,i,' '); j:=j-w[i]; End; i:=i+1; End; Close(f_ra); End; Begin {Chuong trinh chinh} Clrscr; nhap; Xu_ly; Readln; End.