Đề ôn thi học sinh giỏi Tin học lớp 8 số 4 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 8 – ĐỀ SỐ 4
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 10 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 8×9, 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.