//
you're reading...
Các chuyên đề bồi dưỡng học sinh giỏi, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10

Chuyên đề 3. CÁC CẤU TRÚC DỮ LIỆU NÂNG CAO

Số tiết: 10
Mục đích:
• Hiểu khái niệm kiểu dữ liệu trừu tượng cây;
• Nắm được các ứng dụng của cây;
• Biết cách tổ chức dữ liệu dạng cây;
• Nắm được một số cấu trúc dữ liệu và thuật toán xử lý;
• Nắm được một số ứng dụng của các cấu trúc dữ liệu vào việc cài đặt hiệu quả một số thuật toán điển hình.

TT Nội dung Mức độ cần đạt Ghi chú
1. Mô hình cây trong tổ chức dữ liệu Kiến thức:
– Hiểu khái niệm kiểu dữ liệu trừu tượng cây và một số khái niệm trong mô hình cây (chiều cao, gốc, nút lá, bậc của nút, bậc của cây);
– Biết một số ứng dụng của cách tổ chức dữ liệu theo mô hình cây (cây thư mục; biểu diễn không gian lời giải bài toán trong lý thuyết trò chơi; cây phân tích cú pháp của các văn phạm như biểu thức, các câu lệnh trong một chương trình; ứng dụng trong tổ chức dữ liệu ở bộ nhớ trong và bộ nhớ ngoài cho các bài toán tìm kiếm;…). Thông qua ví dụ để minh họa lí thuyết.
2. Cây nhị phân và ứng dụng
Kiến thức:
– Hiểu khái niệm cấu trúc dữ liệu cây nhị phân;
– Hiểu khái niệm cây nhị phân tìm kiếm và các ứng dụng của nó;
– Hiểu khái niệm cây biểu thức và ứng dụng.
Kĩ năng:
Cài đặt được các thuật toán và thử nghiệm chương trình với các bộ dữ liệu khác nhau. – Yêu cầu HS hiểu thấu đáo các khái niệm, các cấu trúc dữ liệu và các phép toán với chúng.
– GV nên hướng dẫn cho HS phân tích so sánh các cách cài đặt khác nhau.
3. Mã Huffman

Kiến thức:
– Biết khái niệm mã hoá và ứng dụng;
– Nắm được khái niệm mã Huffman và thuật toán xây dựng.
Kĩ năng:
Cài đặt được chương trình mã hoá và giải mã theo mã Huffman và thử nghiệm chương trình với các bộ dữ liệu khác nhau.
– Yêu cầu HS hiểu thấu đáo nội dung bài toán mã hoá và cách tổ chức dữ liệu cây để xây dựng mã và giải mã.
– GV nên hướng dẫn cho HS phân tích so sánh các cách cài đặt khác nhau .
4. Cấu trúc dữ liệu đống và ứng dụng
Kiến thức:
– Biết cấu trúc dữ liệu đống và các phép toán với cấu trúc dữ liệu đống;
– Hiểu được ứng dụng của cấu trúc dữ liệu đống vào xây dựng thuật toán sắp xếp vun đống (Heap Sort);
– Hiểu được ứng dụng của cấu trúc dữ liệu đống trong việc tổ chức hàng đợi có ưu tiên;
– Hiểu được ứng dụng hàng đợi ưu tiên vào việc cài đặt các thuật toán Prim, Dijkstra.
Kĩ năng:
Cài đặt được chương trình thực hiện các thuật toán và thử nghiệm chương trình với các bộ dữ liệu khác nhau. – Yêu cầu HS hiểu thấu đáo các khái niệm, các cách tổ chức dữ liệu bằng việc sử dụng nhiều minh họa, mô phỏng trước khi trình bày thuật toán cài đặt chương trình.
– GV nên hướng dẫn cho HS phân tích so sánh các cách cài đặt khác nhau

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

lost

Lookkk deeeply into my eyes....

Cimitero San Michele

More Photos

Thống kê

  • 115,518 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: