Đề ôn thi học sinh giỏi Tin học lớp 12 số 1 là đề tự biên soạn để luyện tập nâng cao; không phải đề thi chính thức của một địa phương hay kỳ thi cụ thể.
ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC LỚP 12 – ĐỀ SỐ 1
Thời gian làm bài gợi ý: 150 phút | Tổng điểm tham khảo: 20 điểm
- Bài 1 (4 điểm). Trong tình huống Vườn cam quan sát, Cho dãy 7 số nguyên. Hãy thiết kế thuật toán tìm phần tử lớn thứ hai phân biệt với phần tử lớn nhất trong một lần duyệt, nêu độ phức tạp; trong đề số 1, hãy trình bày ít nhất một bước kiểm tra kết quả.
Yêu cầu bổ sung cho Tin học lớp 12, đề số 1: nêu thêm một bước kiểm tra, ví dụ hoặc căn cứ phù hợp trước khi kết luận. Ngoài kết quả, hãy nêu một cách kiểm tra độc lập để phát hiện sai sót. - Bài 2 (4 điểm). Trong tình huống Vườn cam quan sát, Cho một xâu kí tự chỉ gồm chữ cái thường. Hãy đếm số kí tự xuất hiện đúng một lần mà không sắp xếp xâu; trong đề số 1, hãy trình bày ít nhất một bước kiểm tra kết quả.
Yêu cầu bổ sung cho Tin học lớp 12, đề số 1: nêu thêm một bước kiểm tra, ví dụ hoặc căn cứ phù hợp trước khi kết luận. Hãy chỉ ra điều kiện hoặc dữ kiện nào quyết định cách giải. - Bài 3 (4 điểm). Trong tình huống Vườn cam quan sát, Trên lưới 5×6, robot chỉ đi sang phải hoặc xuống dưới. Hãy nêu công thức quy hoạch động đếm số đường từ góc trên trái tới góc dưới phải khi có một số ô cấm; trong đề số 1, hãy trình bày ít nhất một bước kiểm tra kết quả.
Yêu cầu bổ sung cho Tin học lớp 12, đề số 1: nêu thêm một bước kiểm tra, ví dụ hoặc căn cứ phù hợp trước khi kết luận. Sau khi trả lời, hãy giải thích vì sao một phương án khác dễ dẫn tới kết luận sai. - Bài 4 (4 điểm). Trong tình huống Vườn cam quan sát, Giải thích vì sao thuật toán tìm kiếm nhị phân cần dữ liệu có thứ tự và chứng minh độ phức tạp O(log n); trong đề số 1, hãy trình bày ít nhất một bước kiểm tra kết quả.
Yêu cầu bổ sung cho Tin học lớp 12, đề số 1: nêu thêm một bước kiểm tra, ví dụ hoặc căn cứ phù hợp trước khi kết luận. Hãy nêu một bước đối chiếu giúp xác nhận kết quả là hợp lí. - Bài 5 (4 điểm). Trong tình huống Vườn cam quan sát, Một chương trình cho kết quả đúng với dữ liệu nhỏ nhưng chậm ở n lớn. Hãy nêu quy trình xác định nút thắt và ba hướng tối ưu có thể thử; trong đề số 1, hãy trình bày ít nhất một bước kiểm tra kết quả.
Yêu cầu bổ sung cho Tin học lớp 12, đề số 1: nêu thêm một bước kiểm tra, ví dụ hoặc căn cứ phù hợp trước khi kết luận. Nếu dữ kiện thay đổi, hãy cho biết yếu tố nào trong cách giải phải được xem lại trước.
LỜI GIẢI CHI TIẾT
- Bài 1. Duy trì max1 và max2. Với mỗi x: nếu x>max1 thì max2=max1,max1=x; ngược lại nếu max1>x>max2 thì cập nhật max2=x. Một lần duyệt nên O(n), bộ nhớ O(1). Cần xử lí trường hợp không có hai giá trị phân biệt. Phần kiểm tra nên đối chiếu lại điều kiện, dữ kiện và kết quả cuối thay vì chỉ nhìn đáp số.
- Bài 2. Dùng mảng tần suất 26 phần tử: duyệt xâu tăng đếm; sau đó đếm bao nhiêu vị trí có tần suất 1. Thời gian O(n), bộ nhớ O(1) theo bảng chữ cái cố định. Cần nêu rõ căn cứ quyết định cách làm, sau đó kiểm tra kết luận bằng phép tính ngược, nguồn khác hoặc trường hợp biên phù hợp.
- Bài 3. Đặt dp[i][j]=0 nếu ô cấm; nếu không dp[i][j]=dp[i-1][j]+dp[i][j-1], với dp[1][1]=1 khi không bị cấm. Tính theo thứ tự tăng i,j. Độ phức tạp O(mn). Một lời giải tốt phải chỉ ra vì sao phương án được chọn phù hợp hơn phương án dễ nhầm.
- Bài 4. Mỗi bước phải so sánh với phần tử giữa và loại bỏ một nửa không gian tìm kiếm; điều này chỉ đúng khi dữ liệu đã sắp. Sau k bước còn n/2^k phần tử, nên k≈log2 n. Nên tự kiểm tra bằng một bước độc lập để bảo đảm không bỏ sót điều kiện hoặc đọc sai dữ kiện.
- Bài 5. Đo thời gian từng khối hoặc dùng profiler; xác định phần chiếm thời gian lớn. Có thể thay thuật toán bậc cao bằng thuật toán tốt hơn, dùng cấu trúc dữ liệu phù hợp, tránh tính lặp/lưu kết quả trung gian và giảm thao tác I/O. Khi dữ kiện thay đổi, cần xem lại giả định và bước suy luận phụ thuộc trực tiếp vào dữ kiện đó.
Nhận xét
Đề theo bối cảnh Vườn cam quan sát đã bổ sung yêu cầu kiểm chứng hoặc đối chiếu ngay trong từng nhiệm vụ, tránh kiểu chỉ thay số mà giữ nguyên cách suy luận.