Đề cương ôn tập thi học kỳ I môn Tin học Lớp 11 - Năm học 2018-2019 - Trường THPT Chu Văn An

TRƯỜNG THPT CHU VĂN AN ĐỀ CƯƠNG ÔN TẬP HỌC KỲ I LỚP 11 CHUYÊN TIN NĂM HỌC 2018 - 2019 I. BÀI TẬP MẢNG MỘT CHIỀU Bài 1. Dãy con liên tiếp dài nhất Cho dãy số A gồm n số nguyên a1, a2, ..., an (n<=10000), các phần tử có giá trị không vượt quá 109. Yêu cầu: Tìm dãy con liên tiếp dài nhất mà các số hạng là các số dương trong dãy trên? Dữ liệu vào file 'DAYCONDN.INP': - Dòng đầu là số n; - Dòng tiếp theo là các giá trị của dãy A, mỗi số cách nhau một dấu cách. Kết quả ra file 'DAYCONDN.OUT': - Dòng đầu ghi ra số lượng phần tử dãy con đã tìm được; - Dòng thứ hai ghi các giá trị của dãy con đã tìm được. Nếu có nhiều dãy con đáp ứng yêu cầu trên thì chỉ cần ghi ra dãy con đầu tiên tìm được. Bài 2. Đổi hệ đếm nhị phân Cho số nguyên dương n trong hệ thập phân (n<=1018). Yêu cầu: Đổi số nguyên dương n từ dạng biểu diễn thập phân sang dạng biểu diễn nhị phân? Dữ liệu vào file 'DOINP.INP': Một dòng duy nhất chứa số n. Kết quả ra file 'DOINP.OUT': Một dòng duy nhất chứa số nhị phân đã đổi được. Bài 3. Đổi hệ đếm thập lục phân Cho số nguyên dương n trong hệ thập phân (n<=1018). Yêu cầu: Đổi số nguyên dương n từ dạng biểu diễn thập phân sang dạng biểu diễn thập lục phân (hệ đếm cơ số 16 gồm các kí tự biểu diễn: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F)? Dữ liệu vào file 'DOITLP.INP': Một dòng duy nhất chứa số n. Kết quả ra file 'DOITLP.OUT': Một dòng duy nhất chứa số thập lục phân đã đổi được. Bài 4. Số xuất hiện một lần Cho dãy số A gồm n số nguyên a1, a2, ..., an (n<=10000), các phần tử có giá trị không vượt quá 105. Yêu cầu: Hãy đếm và in ra những phần tử có giá trị chỉ xuất hiện trong dãy trên đúng một lần? Dữ liệu vào file 'XUATHIEN1LAN.INP': - Dòng đầu là số n; - Dòng tiếp theo là các giá trị của dãy A, mỗi số cách nhau một dấu cách. Kết quả ra file 'XUATHIEN1LAN.OUT': - Dòng đầu là số lượng các số xuất hiện 1 lần; - Dòng thứ hai ghi ra các giá trị xuất hiện một lần trên một dòng theo thứ tự tăng dần, mỗi số cách nhau một dấu cách. Nếu không có số nào ghi số 0. 1 Bài 5. Tổng bằng M Cho dãy số A gồm n số nguyên a1, a2, ..., an (n<=1000), các phần tử có giá trị không vượt quá 109 và số M có giá trị tuyệt đối không vượt quá 1018. Yêu cầu: Hãy tìm tất cả các bộ 3 số ai, aj, ak thoả mãn: ai + aj + ak = M ( 1<= i < j < k<=n)? Dữ liệu vào file 'TONGBANGM.INP': - Dòng đầu là 2 số n và M; - Dòng tiếp theo là các giá trị của dãy A, mỗi số cách nhau một dấu cách. Kết quả ra file 'TONGBANGM.OUT': Mỗi dòng ghi một bộ 3 số ai, aj, ak cách nhau một dấu cách. Nếu không có bộ số nào ghi số 0. Bài 6. Tìm số gần M nhất Cho dãy số A gồm n số nguyên a1, a2, ..., an (n<=10000), các phần tử có giá trị không vượt quá 109 và số M có giá trị tuyệt đối không vượt quá 1018. Yêu cầu: Tìm phần tử có giá trị gần với M nhất? Dữ liệu vào file 'GANMNHAT.INP': - Dòng đầu là 2 số n và M; - Dòng tiếp theo là các giá trị của dãy A, mỗi số cách nhau một dấu cách. Kết quả ra file 'GANMNHAT.OUT': Ghi ra giá trị gần M nhất, nếu có hai giá trị thì in ra giá trị <= M. Bài 7: Tìm ước chung lớn nhất, bội chung nhỏ nhất 2 Cho N số nguyên dương a1, a2, . . . , aN (N<=10, ai<10 ). Yêu cầu: Tìm ước số chung lớn nhất và bội số chung nhỏ nhất của N số trên? Dữ liệu vào file 'UCBC.INP': Dòng đầu là số N; dòng tiếp UCBC.INP UCBC.OUT theo là các giá trị của dãy số. 5 2 Kết quả ra file 'UCBC.OUT': Dòng đầu ghi ước số chung 2 4 6 8 10 120 lớn nhất; dòng thứ hai ghi bội số chung nhỏ nhất. Bài 8: Dãy số FIBONACI Cho số nguyên dương n (n<=100). Yêu cầu: Hãy in ra dãy số Fibonaci từ 1 tới n, biết F 1=1; F2=1; Fi=Fi-1 + Fi-2, với i>=3 và đếm xem có bao nhiêu số lớn hơn trung bình cộng của cả dãy? Dữ liệu vào file 'FIBONACI.INP': Một dòng duy nhất chứa số n. Kết quả ra file ' FIBONACI.OUT': - Dòng thứ nhất ghi các số trong dãy Fibonaci đã được tạo ra, mỗi số cách nhau một dấu cách. - Dòng thứ hai ghi số lượng số lớn hơn trung bình cộng của cả dãy. 2 Bài 9: Tam giác Pascal 1 Cho số nguyên dương n (n<=100). 1 1 Yêu cầu: In ra hệ số của biểu thức (a+b) n được gọi là tam giác 1 2 1 Pascal. 1 3 3 1 Ví dụ n=5: 1 4 6 4 1 Dữ liệu vào file 'PASCAL.INP': Một dòng duy nhất chứa số n. 1 5 10 10 5 1 Kết quả ra file 'PASCAL.OUT': Gồm n+1 dòng, mỗi dòng ghi các hệ số của biểu thức (a+b)i, với i = 0 . . n, mỗi số cách nhau một dấu cách. II. BÀI TẬP BẢNG HAI CHIỀU Bài 1. Cho ma trận vuông A, có kích thước n x n (2 <= n <= 1000), các phần tử có giá trị tuyệt đối không vượt quá 105. a. Tính tổng các phần tử nằm trên đường chéo chính? b. Tính tổng các phần tử nằm trên đường chéo phụ? c. Tính tổng các phần tử nằm sát trên, sát dưới đường chéo chính? d. Tính tổng các phần tử nằm sát trên, sát dưới đường chéo phụ? e. Tính tổng các phần tử nằm phía trên đường chéo chính? f. Tính tổng các phần tử nằm phía dưới đường chéo phụ? Dữ liệu vào file 'MATRANVUONG.INP': Dòng đầu là số n; n dòng tiếp theo biểu diễn ma trận A. Kết quả ra file 'MATRANVUONG.OUT': Ghi kết quả mỗi yêu cầu trên một dòng theo thứ tự từ trên xuống. Bài 2. Bảng kết quả của một giải vô địch bóng đá thi đấu 1 lượt trận được cho bởi ma trận vuông cấp n (1 < n < 100) , trong đó tất cả các phần tử thuộc đường chéo chính bằng 0, các phần tử khác bằng 3, 1 hoặc 0 (đó là số điểm của trận đấu: 3 - thắng, 1 - hoà, 0 - thua). Dòng thứ i là kết quả thi đấu của đội thứ i. a. In ra các đội có tổng điểm lớn nhất với các thông tin số thứ tự đội, tổng số điểm, số trận thắng, số trận hoà và số trận thua? b. In ra thứ tự các đội có số trận thắng nhiều hơn số trận thua? Nếu không có in ra số 0. c. In ra thứ tự các đội không thua trận nào? Nếu không có in ra số 0. Dữ liệu vào file 'KQBONGDA.INP': Dòng đầu là số n; n dòng tiếp theo là bảng kết quả bóng đá. Kết quả ra file 'KQBONGDA.OUT': Mỗi kết quả ghi trên một dòng theo thứ tự các phần đã cho. Bài 3. Cho bảng A kích thước m x n (1 < m, n <= 1000), các phần tử là số nguyên có giá trị tuyệt đối không vượt quá 10 5. Trong các cột của bảng, mỗi cột có một giá trị lớn nhất, hãy tìm các cột mà giá trị lớn nhất là nhỏ nhất. Dữ liệu vào file 'MAXMIN.INP': Dòng đầu là hai số m, n; m dòng tiếp theo là bảng A. Kết quả ra file 'MAXMIN.OUT': Thứ tự các cột theo yêu cầu trên, mỗi số cách nhau một dấu cách. Bài 4. Cho bảng A kích thước m x n (với 1< n, m <=1000), các phần tử là số nguyên có giá trị tuyệt đối không vượt quá 105: 3 a. In ra bảng B=(bi) trong đó b[i] là tổng của dòng i trong bảng A? b. In ra bảng C=(ci) trong đó c[i] là giá trị lớn nhất của dòng i trong bảng A? Dữ liệu vào file 'TONGMAX.INP': Dòng đầu là hai số m, n; m dòng tiếp theo là bảng A. Kết quả ra file 'TONGMAX.OUT': Gồm hai dòng: dòng đầu là câu trả lời của phần a; dòng thứ hai là câu trả lời của phần b. Bài 5. Trên ma trận A[mxn] (1 < m, n <= 1000), các phần tử là số nguyên có giá trị tuyệt đối không vượt quá 105. Người ta gọi "điểm yên ngựa" trên ma trận A là điểm a[i,j] thoả mãn, - Trên dòng i thì a[i,j] là giá trị lớn nhất. - Trên cột j thì a[i,j] là giá trị nhỏ nhất. Hãy tìm xem trên ma trận A[mxn] có điểm yên ngựa hay không, nếu có hãy thông báo ra vị trí dòng, cột của nó? Dữ liệu vào file 'YENNGUA.INP': Dòng đầu là hai số m, n; m dòng tiếp theo là ma trận A. Kết quả ra file 'YENNGUA.OUT': Chỉ ra các vị trí dòng, cột nếu có điểm yên ngựa, còn ngược lại ghi số 0. Bài 6. Cho số tự nhiên n (1<n<100). Hãy tạo ra ma trận xoáy ốc gồm các số từ 1..n2 có dạng: Ví dụ: n = 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 Dữ liệu vào file 'MATRANXOAY.INP': Chứa duy nhất số tự nhiện n. Kết quả ra file 'MATRANXOAY.OUT': Gồm n dòng biểu diễn ma trận xoáy đã tạo ra, mỗi số định dạng 5 chỗ trống để in ra. Bài 7. Cho bảng A gồm m dòng, n cột (1 < m, n <= 100), các phần tử là số nguyên có giá trị tuyệt đối không vượt quá 10 5. Cho hai số nguyên m1, n1 (1 < m1 < m, 1 < n1 < n), hãy tìm ma trận con cấp m1 x n1 có tổng lớn nhất? Dữ liệu vào file 'MATRANMAX.INP': Dòng đầu là bốn số m, n, m1, n1; m dòng tiếp theo là ma trận A. Kết quả ra file 'MATRANMAX.OUT': Gồm hai dòng: dòng đầu là giá trị lớn nhất của ma trận con; dòng thứ hai là chỉ số dòng, chỉ số cột của ma trận con có tổng đạt giá trị lớn nhất, nếu có nhiều ma trận con thỏa mãn yêu cầu thì chỉ ra ma trận con có chỉ số dòng, cột nhỏ nhất. III. BÀI TẬP XÂU KÝ TỰ Bài 1: Đếm từ Cho xâu S tối đa 255 ký tự gồm các chữ cái, chữ số và dấu cách. Hãy đếm xem xâu S có bao nhiêu từ (một từ là một hoặc nhiều kí tự viết liền nhau). Dữ liệu vào file DEMTU.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file DEMTU.OUT: Một dòng duy nhất chứa số từ đếm được. 4 Bài 2: Tính tổng Cho xâu S tối đa 255 ký tự gồm các chữ cái, chữ số và dấu cách. Hãy tính tổng các số trong xâu S (một số được tạo bởi một hoặc nhiều kí tự số viết liền nhau). Dữ liệu vào file TINHTONG.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file TINHTONG.OUT: Một dòng duy nhất chứa tổng đã tính được. Bài 3: Đổi hệ đếm thập lục phân sang hệ đếm thập phân Cho xâu S tối đa 15 kí tự biểu diễn một số trong hệ đếm cơ số 16. Hãy đổi S từ hệ đếm cơ số 16 sang hệ đếm thập phân. Dữ liệu vào file TLPTP.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file TLPTP.OUT: Một dòng duy nhất chứa số trong hệ thập phân đã đổi được. Bài 4: Chuẩn hóa xâu Cho xâu S là họ và tên người việt tối đa 50 kí tự chữ cái và dấu cách. Hãy chuẩn hóa xâu họ và tên trên: Xóa dấu cách thừa nếu có; kí tự đầu mỗi từ viết in hoa, các kí tự còn lại viết in thường. Dữ liệu vào file CHUANHOA.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file CHUANHOA: Một dòng duy nhất chứa xâu S đã chuẩn hóa. Bài 5: Tách họ, đệm, tên Cho xâu S là họ và tên người việt tối đa 50 kí tự chữ cái và dấu cách đã được chuẩn hóa. Hãy viết họ, đệm và tên mỗi loại trên một dòng. Dữ liệu vào file TACHHDT.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file TACHHDT.OUT: Gồm 3 dòng: dòng thứ nhất chứa họ, dòng thứ hai chứa đệm và dòng thứ ba chứa tên. Bài 6: Đổi từ hệ đếm nhị phân sang hệ đếm bát phân Cho xâu S tối đa 200 kí tự biểu diễn một số trong hệ đếm nhị phân. Hãy đổi S từ hệ đếm nhị phân sang hệ đếm cơ số 8. Dữ liệu vào file NPBP.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file NPBP.OUT: Một dòng duy nhất chứa số trong hệ đếm cơ số 8 đã đổi được. Bài 7: Đếm ký tự khác nhau Cho xâu S tối đa 255 ký tự gồm các chữ cái, chữ số và dấu cách. Hãy đếm xem xâu S có bao kí tự chữ cái, chữ số khác nhau (chữ cái in thường, in hoa là một). Dữ liệu vào file KITUKN.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file KITUKN.OUT: Số lượng chữ cái, chữ số khác nhau trong S. 5 Bài 8: Xâu đối xứng Cho xâu S tối đa 255 ký tự gồm các chữ cái, chữ số và dấu cách. Hãy kiểm tra xâu S có là xâu đối xứng hay không? Dữ liệu vào file DOIXUNG.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file DOIXUNG.OUT: Nếu xâu S đối xứng ghi số 1, còn ngược lại ghi số 0. Bài 9: Đổi từ hệ đếm mười sáu sang hệ đếm nhị phân Cho xâu S tối đa 50 kí tự biểu diễn một số trong hệ đếm cơ số 16. Hãy đổi S từ hệ đếm cơ số 16 sang hệ đếm nhị phân. Dữ liệu vào file MSNP.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file MSNP.OUT: Một dòng duy nhất chứa số trong hệ nhị phân đã đổi được. Bài 10: Đếm xâu Cho hai xâu S1 và S2 tối đa 255 kí tự chữ cái. Hãy đếm số lần S1 có trong S2 và chỉ ra các vị trí nếu có. Dữ liệu vào file DEMXAU.INP: Dòng thứ nhất chứa xâu S1, dòng thứ hai chứa xâu S2. Kết quả ra file DEMXAU.OUT: Nếu có S1 trong S2 thì dòng thứ nhất chứa số lần S1 có trong S2; dòng thứ hai là các vị trí bắt đầu của S1 có trong S2. Nếu không có S1 có trong S2 ghi số 0; Bài 11: Xâu ghép Cho xâu S tối đa 255 ký tự gồm các chữ cái, chữ số và dấu cách. Hãy kiểm tra S xem có là ghép của một số lần xâu X nào đó không, nếu là ghép của một số lần xâu X thì đưa ra xâu X dài nhất có thể. Dữ liệu vào file XAUGHEP.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file XAUGHEP.OUT: Một dòng duy nhất chứa xâu X dài nhất ghép thành xâu S, nếu không có xâu X ghi số 0. Bài 12: Đổi từ hệ nhị phân sang hệ thập lục phân Cho xâu S độ dài tối đa 200 kí tự biểu diễn một số trong hệ đếm nhị phân. Hãy đổi S từ hệ đếm nhị phân sang hệ đếm cơ số 16. Dữ liệu vào file NPMS.INP: Một dòng duy nhất chứa xâu S. Kết quả ra file NPMS.OUT: Một dòng duy nhất chứa số trong hệ đếm cơ số 16 đã đổi được. ------------------------------------------------------ 6