Đề ôn thi học sinh giỏi Tin học lớp 7 số 2 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 7 – ĐỀ SỐ 2
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 Ngõ nhỏ đánh giá, Cho dãy 8 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ố 2, hãy trình bày ít nhất một bước kiểm tra kết quả. Hãy chỉ ra điều kiện hoặc dữ kiện nào quyết định cách giải.
- Bài 2 (4 điểm). Trong tình huống Ngõ nhỏ đánh giá, 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ố 2, hãy trình bày ít nhất một bước kiểm tra kết quả. 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 3 (4 điểm). Trong tình huống Ngõ nhỏ đánh giá, Trên lưới 6×7, 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ố 2, hãy trình bày ít nhất một bước kiểm tra kết quả. 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 4 (4 điểm). Trong tình huống Ngõ nhỏ đánh giá, 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ố 2, hãy trình bày ít nhất một bước kiểm tra kết quả. 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.
- Bài 5 (4 điểm). Trong tình huống Ngõ nhỏ đánh giá, 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ố 2, hãy trình bày ít nhất một bước kiểm tra kết quả. 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.
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. 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 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. 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 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). 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 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. 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 đó.
- 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. 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ố.
Nhận xét
Đề theo bối cảnh Ngõ nhỏ đánh giá đã 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.