Đề thi GVG môn Tin

Trường THPT Thuận Thành số ĐỀ THI GIÁO VIÊN GIỎI CẤP TRƯỜNG VÒNG THI LÝ THUYẾT Môn: Tin học Thời gian làm bài: 120 phút Câu 1(2điểm). Viết thuật toán tính tổng sau bằng cả cách liệt kê và sơ đồ khối 20140!1)(nnne Câu 2(2điểm): Theo anh (chị) nhập dữ liệu là tạo lập hồ sơ hay cập nhật hồ sơ? Tại sao? Câu 3(2điểm): Tại sao phải tạo nhiều bảng sau đó liên kết lại? Có thể đưa tất cả các thông tin cần thiết vào một bảng được hay không? Câu 4(2điểm): Một chương trình có chứa câu lệnh While Do, trong đó điều kiện viết sau While luôn đúng (Ví dụ While x*x>=0 Do ...). Có thể khẳng định được ngay là chương trình này sai hay không? Tại sao? Câu 5(2điểm): Anh (chị) hãy nêu tưởng giải quyết bài toán theo phương pháp qui hoạch động, cho ví dụ. ..................................Hết........................................... Hướng dẫn chấm Câu 1: Bước 1: E1; Ttg1.0/1; n1; Bước 2: Nếu n>2014 thì thông báo và kết thúc Bước 3. 3.1: TgTg/n; 3.2: EE+Tg; Bước 4. nn+1, quay lại bước Sơ đồ khối các lệnh tương tự Câu 2: Thao tác nhập dữ liệu cần thiết phải thực hiện trong cả khâu tạo lập hồ sơ và cập nhật hồ sơ vì trong cả khâu đó điều cần phải đưa dữ liệu vào hệ thống để lưu trữ ra bộ nhớ ngoài. khâu tạo lập thông thường người ta nhập đầy đủ thông tin về mỗi hồ sơ, khâu cập nhật có thể nhập đầy đủ hồ sơ (bổ sung thêm hồ sơ mới) hoặc một phần của hồ sơ (sửa đổi hồ sơ) Câu 3: Làm rõ: Có thể tồn tại những CSDL chỉ có một bảng duy nhất (ví dụ hệ thống CDS ISIS của UNESCO phục vụ cho độc giả tra cứa sách của tất cả các thư việc Quốc gia trên thế giới). Tuy vậy bên trong mỗi hệ thống vẫn có nhiều bảng phụ hỗ trợ Về nguyên tắc, ta có thể tập trung hết thông tin vào một bảng duy nhất, nhưng như vậy bảng đó phải có rất nhiều cột để thể hiện hết tất cả các thuộc tính cần thiết và phải ghi lại nhiều lần một giá trị thông tin nhiều thuộc tính khác nhau và nhiều bản ghi khác nhau. VD:.... vì vậy để đảm bảo tính không dư thừa, …. Người ta tạo nhiều bảng ….Hãy tưởng tượng, điều gì xảy ra nếu tổ chức quản lí thư viện chỉ bằng một bảng duy nhất. Câu 4: Không thể khẳng định ngay là chương trình sai. Có những chương trình cần lặp vô hạn lần hoặc có thể kết chương trình hay thoát ra khỏi vòng lặp bằng việc kiểm tra điều kiện và sử dụng công cụ do ngôn ngữ lập trình cung cấp. (Ví dụ lệnh Break) Câu 5: Quy hoạch động giống như phương pháp chia để trị giải quyết các bài toán bằng cách kết hợp các giải pháp của các bài toán con. Điểm khác biệt là một thuật toán quy hoạch động giải quyết tất cả các bài toán con đúng một lần và sau đó ghi kết quả của chúng trong một bảng, như vậy tránh được việc phải tính lại các kết quả khi bài toán con được gặp lại. 1. Nguyên lý tối ưu Bellman Quy hoạch động là quá trình điểu khiển tối ưu với trạng thái bắt đầu. Mọi trạng thái bất kỳ thuộc quá trình này cũng tối ưu. Tư tưởng chính: Thực hiện các bài toán con trước, sử dụng các kết quả này để giải bài toán lớn Hướng tiếp cận: Giải bài toán theo công thức truy hồi Giải các bài toán con trước Dựa vào bài toán con để giải bài toán lớn hơn cho đến khi gặp bài toán cần giải Tổng quát: Giải bài toán qua bước Giải bài toán sao cho tổng chi phí -> N-1 và từ N-1 -> là tối ưu2. Thuật toán quy hoạch động Bước 1: Xây dựng công thức truy hồi Giả sử: Chia bài toán thành giai đoạn 1->N Xác định F(1) cơ sở quy nạp Gọi (i) là hàm số xác định giá trị tối ưu, tính đến giá trị thứ -> F(n) là nghiệm của bài toán Đối với bài toán Tìm Min: F(N) Min{F(i), F(j)} 1, N-1 N-1, Tìm Max: F(N) Max{F(i), F(j)} 1, N-1 N-1, Bước 2: Tìm cơ sở quy hoạch động Để chia bài toán lớn thành các bài toán con có cùng một cách giải thì phải yêu cầu phải biến đổi một số bài toán con trường hợp cơ sở quy nạp bằng cách thêm biến phụ, chính là cơ sở quy hoạch động Bước 3: Lấp đầy bảng phương án, dựa vào cơ sở quy hoạch động, công thức quy hoạch động Giải bài toán Bước 4: Truy vết Tìm nghiệm của bài toán 3. Ví dụ Bài toán: Dãy con không giảm dài nhất Phân tích:- Gọi là độ dài lớn nhất của dãy con không giảm từ x[i] -> x[n] -> L[1] là nghiệm của bài toán Để đưa các trường hợp này về cùng một cách giải, ta thêm phần tử a[0] -œ a[n+1] +œ Thuật toán: Bước 1: Xây dựng công thức truy hồi Xét tại phần tử thứ i: L[i] nếu a[i] ... a[n] L[i] L[jmin] với jmin min{j a[i] a[j]} Tổng quát: L[i] max {L[j] với i+1, và a[i] a[j]} Bước 2: Cơ sở quy hoạch động L[n+1] Bước 3: Tính bảng phương án void QHD() int i, j; int jmax, temp; a[0] -32766; a[n+1] 32767; L[n+1] 1; for(i=n;i>=0; i--) jmax n+1; temp L[n+1]; for(j=i+1; j<=n; j++) if(a[i] a[j] && L[j] temp) {temp L[j]; jmax j; L[i] L[jmax]+1; T[i] jmax; Bước 4: Truy vết Theo các vết sử dụng mảng T[i] mà ta đã đánh dấu Bắt đầu từ T[0] ta lần lượt lưu lại T[i] cho tới khi T[i] n+1Trên đây chỉ là phần trích dẫn 10 trang đầu của tài liệu và có thế hiển thị lỗi font, bạn muốn xem đầyđủ tài liệu gốc thì ấn vào nút Tải về phía dưới.