Đề kiểm tra năng lực chuyên môn môn: Tin học

UBND TỈNH BẮC NINH
SỞ GIÁO DỤC VÀ ĐÀO TẠO
ĐỀ CHÍNH THỨC
HỘI THI GVDG CẤP TỈNH NĂM HỌC 2015 - 2016
ĐỀ KIỂM TRA NĂNG LỰC CHUYÊN MÔN
MÔN: TIN HỌC – THPT, GDTX
Thời gian làm bài: 120 phút (không kể thời gian giao đề) 
Ngày thi: 09 tháng 12 năm 2015
===========
Bài 1 (3,0 điểm):
a) Nêu dưới dạng sơ đồ khối giải thuật tính tổng sau đây:
cho đến khi
với , được nhập từ bàn phím và ||<1.
b) Đánh giá độ phức tạp của thuật toán.
Bài 2 (2,0 điểm): 
Anh (chị) hãy phân biệt hai chế độ khác nhau của mẫu hỏi? Ngoài loại mẫu hỏi trong SGK lớp 12 (mẫu hỏi chọn – Select) thì Access còn có các loại mẫu hỏi nào, kể tên và nêu chức năng một số mẫu hỏi đó?
Bài 3 (2,0 điểm):
a) Tại sao thường 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 hay không?
b) Có thể thay đổi người quản trị CSDL được hay không? Nếu được cần phải cung cấp những gì cho người thay thế?
Bài 4 (3,0 điểm):
Tìm kiếm nhị phân là một thuật toán được ứng dụng nhiều trong thực tế cũng như lập trình có cấu trúc. Anh (chị) hãy:
Phát biểu bài toán.
Nêu ý tưởng của phương pháp.
Viết thủ tục.
Nhận xét độ phức tạp của thuật toán.
Minh họa thuật toán trên với hai bộ test sau:
Test1: Cho n=10; k=0
Dãy số: -100 -15 -5 0 10 20 21 30 55 100
Test2: Cho n=15; k=10
Dãy số: -5 0 7 9 15 17 20 21 30 40 45 55 70 87 90
----------- HẾT ----------
(Đề thi có 01 trang)
HƯỚNG DẪN CHẤM MÔN TIN HỌC THPT, GDTX
Bài
Hướng dẫn giải
Điểm
1a
Nhập x, ɛ
S¬1; T¬1; M¬1; N¬1
T¬T*x*(-1); M¬M*N;
N¬N+1;
S
Đ
Thông báo kết quả S, kết thúc
2,0
1b
Tùy thuộc vào giá trị của x và ɛ dãy trên có N số hạng và thuật toán trên tính tổng của n số hạng đó. Ta có thể coi kích thước của bài toán là N.
Với mỗi số hạng trong dãy ta phải thực hiện 1 phép so sánh và 5 phép tính. Vậy độ phức tạp của thuật toán là O(n)
1,0
2
Chỉ ra có 2 chế độ là chế độ thiết kế và chế độ trang dữ liệu 
0.5
Về chức năng: Chế độ thiết kế cho phép tạo mẫu hỏi, chỉnh sửa cấu trúc ... của mẫu hỏi, còn chế độ trang dữ liệu liệu dùng để xem kết quả mẫu hỏi đó (còn gọi đơn giản là thực thi mẫu hỏi) 
Về cấu trúc: Chế độ thiết kế: Cho phép đưa các trường vào trong mẫu hỏi, và đưa cả các trường không có mặt trong kết quả nhưng tham gia vào việc kết xuất các trường khác, còn chế độ hiển thị trang dữ liệu thì không chứa những trường này.
0.5
0.5
Ngoài ra còn có
Mẫu hỏi cập nhật Update: sử dụng để thay đổi dữ liệu trong bảng
Mẫu hỏi xóa: Dùng để xóa bản ghi 
Còn có mẫu hỏi tạo bảng, mẫu hỏi chéo ...
0.5
3a
Tồn tại những hệ CSDL chỉ có và làm việc với 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ứu sách của tất cả các thư viện Quốc gia trên thế giới).
0,25
Tuy vậy, bên trong mỗi hệ thống như vậy vẫn có nhiều bảng phụ hỗ trợ cho bảng chính trong hoạt động.
0,25
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 đó 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. Do đó, tính không dư thừa và tính nhất quán dữ liệu không được đảm bảo.
0,25
Vậy để đảm bảo dữ liệu không bị dư thừa và thiếu tính nhất quán, CSDL gồm nhiều bảng, các bảng có một số thông tin chung, muốn tổng hợp dữ liệu từ nhiều bảng cần phải liên kết các bảng lại với nhau.
0,25
3b
Có thể
0,5
Khi thay đổi người quản trị CSDL, cần cung cấp cho người mới tiếp quản quyền truy cập vào hệ CSDL với tư cách là người quản trị, các thông tin liên quan đến hệ thống bảo vệ, đảm bảo an toàn hệ thống, cấu trúc dữ liệu và hệ thống, các phần mềm ứng dụng đã được gắn vào, ... Nói một cách khác, toàn bộ thông tin về thực trạng hệ thống.
0,5
4a
Cho A là dãy tăng gồm N phần tử khác nhau A1, A2, ..., AN và một phần tử khóa k
Tìm ra chỉ số i mà Ai=k hoặc thông báo không có phần tử nào của dãy A bằng k
0,5
4b
Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sanh khóa k với phần tử được chọn. Để làm điều đó, ta chọn phần tử Agiữa ở “giữa dãy” để so sánh với k, trong đó giữa=
Khi đó, chỉ xảy ra một trong 3 trường hợp
- Nếu Agiữa=k thì giữa là chỉ số cần tìm. Việc tìm kiếm kết thúc
- Nếu Agiữa>k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy A1, A2, ..., Agiữa-1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó)
- Nếu Agiữa<k thì thực hiện tìm kiếm trên dãy Agiữa+1, Agiữa+2, ..., AN.
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khóa k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
0,5
4c
Mô phỏng thuật toán bằng ngôn ngữ tựa Pascal
Procedure timkiemnhiphan;
Var dau, cuoi:integer;
 Found:boolean;
Begin
 Dau:=1; cuoi:=N; found:=false;
 While (dau<=cuoi) and (not found) do
 Begin
 Giua:=(dau+cuoi) div 2;
 If A[giua]=k then found:=true
 Else
 If a[giua]>k then cuoi:=giua-1
 Else dau:=giua+1;
 End;
If found then writeln(‘chi so tim duoc la:’,giua)
Else writeln(‘khong tim thay’);
End;
0,5
4d
O(logn) vì nó phải dùng tới 2[logn]+2 phép toán so sánh.
0,5
4e
Test1: Cho n=10; k=0
Dãy số: -100 -15 -5 0 10 20 21 30 55 100
I
1
2
3
4
5
6
7
8
9
10
A
-100
-15
-5
0
10
20
21
30
55
100
Đầu
1
1
3
4
Cuối
10
4
4
4
Giữa
5
2
3
4
Agiữa
10
-15
-5
0
Lần duyệt
1
2
3
4
ở lần duyệt thứ 4 thì Agiữa=k. Vậy chỉ số cần tìm là i=giữa=4
0,5
Test2: Cho n=15; k=10
Dãy số: -5 0 7 9 15 17 20 21 30 40 45 55 70 87 90
I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
-5
0
7
9
15
17
20
21
30
40
45
55
70
87
90
Đầu
1
1
5
5
5
Cuối
15
7
7
5
4
Giữa
8
4
6
5
Agiữa
21
9
17
15
Lần duyệt
1
2
3
4
5
Tại lần duyệt thứ 5 đầu>cuối (phạm vi tìm kiếm bằng rỗng) nên kết luận trong dãy A không có số hạng nào bằng khóa k
0,5