Hội đồng tuyển dụng công chức năm 2015 Tài liệu ôn tập Trang 0

HỘI ĐỒNG TUYỂN DỤNG CÔNG CHỨC NĂM 2015 TÀI LIỆU ÔN TẬP NGHIỆP VỤ CHUYÊN NGÀNH TIN HỌC

(Dành cho thí sinh dự tuyển vào vị trí việc làm yêu cầu trình độ
chuyên môn là Tin học, bao gồm các vị trí:
vị trí số 02, Sở Công Thương;
vị trí số 03, Sở Khoa học và Công nghệ;
vị trí số 01, Sở Thông tin và Truyền thông;
vị trí số 04 và số 14, Sở Nội vụ;

điều 6,7,8,9,12,21,50,66)
- Phần cấu trúc dữ liệu và giải thuật (30 điểm) tập trung vào các phần
+ Các thuật toán về danh sách liên kết đơn: duyệt danh sách xuôi, ngược;
sắp xếp theo thứ tự giảm dần, tăng dần; tìm kiếm trong danh sách; xóa phần tử
ra khỏi danh sách thỏa mãn điều kiện; đếm số phần tử trong danh sách thỏa mã
điều kiện; sao chép danh sách sang danh sách khác; chèn phần tử vào danh sách.
+ Trình vày ý tưởng của phương pháp sắp xếp nhanh(Quick Sort), phương
pháp sắp xếp hòa trộn (Merge Sort); lập trình các bài toán ứng dụng sử dụng các
phương pháp sắp xếp vừa nêu.
+ Trình bày ý tưởng của phương pháp tìm kiếm nhị phân; lập trình các bài
toán ứng dụng sử phương pháp tìm kiếm nhị phân.
+ Các bài toán trên cây nhị phân, cây nhị phân tìm kiếm: xác định chiều
cao của cây, xóa các nút thỏa mãn điều kiện ra khỏi cây, thêm phần tử vào cây,
đếm số phần tử trên cây thỏa mã điều kiện, đếm số nút lá; các thuật toán duyệt
cây: Node-Left-Right, Left-Node-Right, Left-Right-Node.
+ Các thuật toán về đồ thị; đồ thị được biểu diễn dưới dạng mảng viết thuật
toán: duyệt đồ thì theo phương pháp duyệt sâu, rộng, thuật toán đếm số miền liên
thông.
Hội đồng tuyển dụng công chức năm 2015 Tài liệu ôn tập Trang 2
(Đề sử dụng ngôn ngữ lập trình pascal để định nghĩa, thí sinh cần hiểu
biết về cách thức định nghĩa và khai báo bằng ngôn ngữ lập trình pascal)
- Phần cơ sở dữ liệu (30 điểm ) tập trung vào các phần
+ Cho một bài toán về một hệ thống trong thực tế được phát biểu bằng lời;
yêu cầu xây dựng lược đồ cơ sở dữ liệu của hệ thống trên. Trong mỗi một lược
đồ của lược đồ cơ sở dữ liệu cần xác định rõ: thuộc tính khóa chính, khóa ngoại,
thuộc tính không khóa.
+ Từ lược đồ cơ sở dữ liệu đã được xây dựng hãy vễ mô hình quan hệ dữ

thông tin điện tử hoặc cổng thông tin
điện tử của cơ quan nhà nước;
- Phần cấu trúc dữ liệu và giải thuật (10 câu ) tập trung vào các phần
+ Thế nào là giải thuật tốt, xác định thời gian thực để thực hiện một
chương trình dựa vào yếu tố nào?
+ Độ phức tạp thuật toán: Xác định độ phức tạp thuật toán; các quy tắc:
cộng, nhân, tổng quát.
+ Các thuật toán tìm kiếm: Tuần tự, nhị phân
+ Các thuật toán sắp xếp: Sắp xếp lựa chọn (Selection Sort), sắp xếp chèn
(Insertion Sort), Sắp xếp nổi bọt (Bubble Sort), Sắp xếp nhanh (Quick Sort)
+ Danh sách liên kết đơn và kép: Định nghĩa, cách thức tổ chức lưu trữ, duyệt
danh sách, tìm kiếm phần tử trong danh sách, loại bỏ phần tử khỏi danh sách.
Hội đồng tuyển dụng công chức năm 2015 Tài liệu ôn tập Trang 3
+ Ưu và nhược điểm của dữ liệu kiểu mảng
+ Các biểu thức biểu diễn ở các dạng: tiền tố, trung tố, hậu tố và cách tính
giá trị một biểu thức biểu diễn ở 3 dạng vừa nêu; cách chuyển biểu thức qua lại
giữa các dạng
+ Định nghĩa về cây (cây tổng quát, nhị phân, nhị phân tìm kiếm); các
phương thức duyệt cây (Left-Node-Right, Node-Left-Right, Left-Right-node);
các thuật toán:tìm kiếm phần tử trên cây nhị phân tìm kiếm, xóa phần tử ra khỏi
cây nhị phân tìm kiếm, thêm phần tử vào cây nhị phân tìm kiếm, xác định chiều
cao của một cây, bậc của cây, nút lá, nút trung gian, nút gốc…
+ Nguyên tắc làm việc của ngăn xếp, hàng đợi.
+ Định nghĩa về đệ quy, áp dụng đệ quy giải một số bài toán đơn giản
(Đề sử dụng ngôn ngữ lập trình pascal, thí sinh cần hiểu biết về cách
thức khai báo danh sách liên kết, cây, bằng ngôn ngữ lập trình pascal)
- Phần cơ sở dữ liệu (15 câu) tập trung vào các phần