tailieunhanh - Đề thi học sinh giỏi lớp 12 môn Tin cấp quốc gia

Kì thi học sinh giỏi là kì thi quan trọng đối với mỗi học sinh. Dưới đây là đề thi học sinh giỏi lớp 12 môn Tin học cấp quốc gia giúp các em kiểm tra lại đánh giá kiến thức của mình và có thêm thời gian chuẩn bị ôn tập cho kì thi sắp tới được tốt hơn. | BỘ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA LỚP 12 ThPT năm 2011 HƯỚNG DẪN CHẤM ĐỀ THI CHÍNH THỨC Môn TIN HỌC Ngày thi thứ hai 12 01 2011 Gồm 01 trang TỔNG QUAN NGÀY THI THỨ HAI Tên bài File chương trình File dữ liệu vào File kết quả Bài 4 Nối điểm đen trắng BWPOINTS. Bài 5 Trò chơi chẵn lẻ PARIGAME. Bài 6 Nâng cấp mạng UPGRANET. Bài 4. Nối điểm đen trắng 6 điểm Có 50 số tests ứng với 50 số điểm của bài có 1 n 100. Thuật toán tham lam trực tiếp với thời gian tính O n2 có thể đạt 50 số điểm. Thuật toán tham lam với tổ chức dữ liệu tốt với thời gian tính O n log n có thể đạt 100 số điểm. Giới hạn thời gian 1 giây. Bài 5. Trò chơi chẵn lẻ 7 điểm Có 50 số tests ứng với 50 số điểm của bài có 1 n 50. Thuật toán qui hoạch động trực tiếp với thời gian tính O n3 có thể đạt 50 số điểm. Thuật toán phát triển dựa trên qui hoạch động với tiền xử lý dữ liệu với thời gian tính O n2 có thể đạt 100 số điểm. Giới hạn thời gian 1 giây. Bài 6. Nâng cấp mạng 7 điểm Có 50 số tests ứng với 50 số điểm của bài có n 100. Thuật toán phát triển dựa trên thụât toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh với thời gian tính O V 3 E có thể đạt 50 số điểm. Thuật toán phát triển dựa trên thuật toán Dijkstra với hàng đợi có ưu tiên để tìm đường đi ngắn nhất giữa mọi cặp đỉnh với thời gian tính O V V E log V E có thể đạt 60 số điểm. Thuật toán phát triển dựa trên xây dựng cây khung thông lượng lớn nhất nhờ thuật toán Kruskal cài đặt với cấu trúc dữ liệu các tập không giao nhau kết hợp với tổ chức dữ liệu tìm kiếm trên cây với thời gian tính O E log V có thể đạt 100 số điểm. Giới hạn thời gian 1 giây. ----------------------Hết---------------------- Trang 1 1 BỘ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA ĐỀ THI CHÍNH THỨC LỚP 12 THPT NĂM 2011 Môn TIN HỌC Thời gian 180 phút không kể thời gian giao đề Ngày thi thứ hai 12 01 2011 Đề thi có 03 trang gồm 03 bài TỔNG QUAN NGÀY THI THỨ HAI Tên bài .