Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005 BảngB ngày 2

Chia sẻ: Lý Hoàng Duy | Ngày: | Loại File: DOC | Số trang:4

Thêm vào BST

Báo xấu

286
lượt xem 58
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo chuyên môn công nghệ thông tin - Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005 BảngB ngày 2

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005 BảngB ngày 2

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT QUẢNG NGÃI Năm học 2004-2005 Môn: Tin học - Bảng B ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề) Ngày thi: 05/12/2004 TỔNG QUAN BÀI THI NGÀY THỨ HAI - BẢNG B Tên bài Tên chương trình Dữ liệu vào Kết quả BÀI 4 Dòng dài MAXSTR.PAS MAXSTR.INP Màn hình BÀI 5 Liên thông GRAPH.PAS GRAPH.INP Màn hình Bài 4: Xâu dài nhất Tên chương trình: MAXSTR.PAS Viết chương trình xác định dòng có nhiều ký tự nhất trong một tập tin văn bản. Dữ liệu: Ghi vào tập tin maxstr.inp - Gồm các dòng kí tự, số dòng không quá 100 dòng Kết quả: Xuất ra màn hình - Nội dung dòng dài nhất. - Số kí tự của dòng dài nhất. Ví dụ: maxstr.inp Màn hình hom nay la thu hai Xau dai nhat: Toi di thi hoc sinh gioi mon Tin hoc Toi di thi hoc sinh gioi mon Tin hoc tai truong Tran Quoc Tuan Do dai dong: 36 Bài 5: Đồ thị liên thông Tên chương trình: GRAPH.PAS Định nghĩa 1 (Ma trận kề): Xét đơn đồ thị vô hướng G=(V,E), với tập đỉnh V={1,2,...,n}, tập cạnh E={e1, e2,...,en}. Ta gọi ma trận kề của đồ thị G là ma trận A = {aij ; i,j =1,2,...,n}, với các phần tử được xác định theo quy tắc sau: 1 (i, j ) ∈ E , ∀i, j = 1..n aij =  0 (i, j ) ∉ E , ∀i, j = 1..n Định nghĩa 2 (Liên thông): Đồ thị G=(V,E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. Ví dụ: Ma trận kề của đồ thị G Đồ thị G Ma trận kề của đồ thị G 1 5 001000 1 001000 110000 3 4 000011 000100 2 6 000100 1/2
Bài toán: Cho đồ thị vô hướng G=(V,E). Hãy cho biết đồ thị có bao nhiêu thành phần liên thông và từng thành phần liên thông của nó gồm những đỉnh nào. Dữ liệu : Vào từ tập tin văn bản graph.inp có qui cách như sau: - Dòng đầu tiên ghi số N (số đỉnh của đồ thị), N ≤ 20. - N dòng tiếp theo, ghi ma trận kề của đồ thị, mỗi số được viết phân cách cách nhau bởi dấu cách. Kết quả: In ra màn hình - Ma trận kề của đồ thị. - Số thành phần liên thông của đồ thị - Các đỉnh thuộc mỗi thành phần liên thông. Ví dụ: graph.inp In ra màn hình 6 Ma tran ke 001000 0 0 1 0 0 0 001000 0 0 1 0 0 0 110000 1 1 0 0 0 0 000011 0 0 0 0 1 1 000100 0 0 0 1 0 0 0 0 0 1 0 0 000100 So thanh phan lien thong: 2 Thanh phan lien thong gom cac dinh 1 2 3 Thanh phan lien thong gom cac dinh 4 5 6 Ghi chú: - Thí sinh không được sử dụng tài liệu - Giám thị không giải thích gì thêm. 2/2
SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT QUẢNG NGÃI Năm học 2004-2005 HƯỚNG DẪN CHẤM ĐỀ CHÍNH THỨC Môn: Tin học - Bảng B Ngày thi: 05/12/2004 Bài 4: 10 điểm Test 1: 5 điểm maxstr.inp Màn hình hom nay la thu hai Xau dai nhat: Toi di thi hoc sinh gioi mon Tin hoc Toi di thi hoc sinh gioi mon Tin hoc tai truong Tran Quoc Tuan Do dai dong: 36 Test 2: 5 điểm maxstr.inp Màn hình Hoang hon chim bo cat min Xau dai nhat: Song khep mi roi Tuoi tho lan ngup voi nhung con phu du chi biet song Giau hoang mang duoi day vuc sau Do dai dong: 52 Nuoc dua nhung phan lenh denh vao mong Am ap sao xanh Tuoi tho lan ngup voi nhung con phu du chi biet song Tim la lam thuyen tha roi theo dong nuoc Ngo chan troi that gan Sau cho uon mem mai kia Bài 2: 10 điểm Test 1: 3 điểm graph.inp In ra màn hình 6 Ma trận kề 001000 0 0 1 0 0 0 101000 1 0 1 0 0 0 110000 1 1 0 0 0 0 000011 0 0 0 0 1 1 000100 0 0 0 1 0 0 0 0 0 1 0 0 000100 So thanh phan lien thong: 2 Thanh phan lien thong gom cac dinh 1 2 3 Thanh phan lien thong gom cac dinh 4 5 6 Tổ chấm xây dựng thêm hai test Test 2: Đồ thị liên thông (4 điểm) Test 3: Đồ thị có nhiều hơn 5 thành phần liên thông (4 điểm) 3/2
4/2