Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết)

Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn

DeThi.edu.vn

ĐỀ SỐ 1

SỞ GIÁO DỤC VÀ ĐÀO TẠO

THÀNH PHỐ HỒ CHÍ MINH

(Đề thi gồm 3 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ NĂM HỌC 2024 – 2025

MÔN: TIN HỌC Thời gian: 120 phút (không tính thời gian phát đề)

Tổng quan bài thi Tên bài Tập tin chương trình Tập tin dữ liệu Tập tin kết quả SẮP XẾP SAPXEP.* SAPXEP.INP SAPXEP.OUT KHU VỰC KHUVUC.* KHUVUC.INP KHUVUC.OUT GIẢI ĐẤU GIAIDAU.* GIAIDAU.INP GIAIDAU.OUT

Dấu * được thay thế bởi PAS hoặc CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++ hoặc PYTHON. Các tập tin chương trình lưu trong cùng một thư mục với tên thư mục là TIN<số báo danh>. Ví dụ: thí sinh có số báo danh là 1234 thì tên thư mục là TIN1234. Hãy lập trình và giải 3 bài toán sau:

Bài 1. Sắp xếp (7 điểm) Sắp xếp nổi bọt (Bubble Sort) là một trong những thuật toán đơn giản và dễ hiểu. Thuật toán sắp xếp nổi bọt thực hiện sắp xếp dãy phần tử bằng cách liên tục lập lại việc so sánh hai phần tử liền kề và hoán đổi vị trí của chúng nếu chung không theo thứ tự mong muốn. Quá trình này được lặp lại cho đến khi toàn bộ dãy đã được sắp xếp hoàn chỉnh. Yêu cầu: Cho một dãy gồm n phần tử hãy viết chương trình đêm số lần hoán đổi vị trí các phần tử theo thuật toán sắp xếp nổi bọt để sắp xếp dãy tăng dần. Dữ liệu: Đọc từ file SAPXEP.INP gồm: - Dòng thứ nhất chứa số nguyên dương (1 ≤ ai ≤ 2.105) - Dòng thứ hai chứa số nguyên dương cách nhau bằng khoảng trắng ai,... ,an (1 ≤ ai ≤ 109) Kết quả: Ghi ra file SAPXEP.OUT một số nguyên duy nhất cho biết số lần hoán đổi vị trí các phần tử theo thuật toán sắp xếp trên. Ràng buộc: - 80% số điểm bài thi: 1 ≤ n ≤ 103

- 100% số điểm bài thi: 1 ≤ n ≤ 2.105

DeThi.edu.vn

Tuyển tập 15 Đề thi HSG môn Tin học 9 tại TP.HCM (Có đáp án chi tiết) - DeThi.edu.vn

DeThi.edu.vn

Ví dụ:

SAPXEP.INP SAPXEP.OUT Giải thích 4 3 2 1 4

3 Theo thuật toán sắp xếp nổi bọt có 3 lần hoán đổi vị trí các phần tử gồm: - Hoán đổi vị trí hai phần tử (3, 2), dãy phần tử 2 3 1 4 - Hoán đổi vị trí hai phần tử (3, 1), dãy phần tử 2 1 3 4 - Hoán đổi vị trí hai phần tử (2, 1), dãy phần tử 1 2 3 4

Bài 2. Khu vực (6,5 điểm) Vùng đất thần tiên AlphaLand rộng lớn được chia thành nhiều khu vực khác nhau. Các khu vực được đánh số 1, 2, 3... Việc phân chia khu vực sinh sống, lao động,vui chơi cho người dân cũng khá kì lạ. Mỗi người dân được cấp một cái thẻ chứa một con số và họ chỉ được phép ra vào khu vực có số thứ tự là ước số của số thẻ. Các số trên thẻ của người dân được phép trùng nhau. Mỗi dịp lễ hội thường niên, trưởng lão sẽ tập trung tât cả người dân về một khu vực để tổ chức tiệc mừng. Năm nay, ông quyết định mở tiệc tại khu vực mà tất cả người dân được phép ra vào khu vực đó có số thứ tự lớn nhất. Nhận thấy rằng có một số thẻ đã cấp cho người dân làm ảnh hưởng đến việc chọn khu vực như trên, ông quyết định đổi cho một trong số họ cái thẻ mới để chọn được khu vực tổ chức tiệc có số thứ tự lớn hơn. Yêu cầu: Cho danh sách n thẻ với các số tương ứng. Hãy viết chương trình tìm khu vực mà tất cả người dân được phép ra vào và khu vực đó có số thứ tự lớn nhất. Lưu ý, việc xác định khu vực thực hiện sau khi người dân được đổi thẻ. Dữ liệu: Đọc từ file KHUVUC.INP gồm: - Dòng thứ nhất chứa số nguyên dương n (1 ≤ n ≤ 105) - Dòng thứ hai chứa số nguyên dương cách nhau bằng khoảng trắng ai,…,a1,...,an (1 < ai < 109) Kết quả: Ghi file KHUCVUC.OUT một số nguyên duy nhất cho biết số thứ tự của khu vực tìm được theo yêu cầu trên Ràng buộc: - 40% số điểm bài thi: 1 ≤ n ≤ 100, 1 ≤ ai ≤ 100 - 80% số điểm bài thi: 1 ≤ n ≤ 103

- 100% số điểm bài thi: 1 ≤ n ≤ 105

Ví dụ:

DeThi.edu.vn