Đề ôn thi học sinh giỏi Tin học lớp 10 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 10 – ĐỀ 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). 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.
- Bài 2 (4 điểm). 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.
- Bài 3 (4 điểm). 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.
- Bài 4 (4 điểm). 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).
- Bài 5 (4 điểm). 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ử.
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.
- 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.
- 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).
- 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.
- 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.