homework 2_cài đặt lời giải sắp xếp selection sort, heap sort để bố trí một mảng số nguyên theo_thứ từ tăng dần.pdf
Giới thiệu, ngôn từ môn học tập |
| Môn học nhằm cung ứng cho sinh viên tài năng sử dụng các cấu tạo dữ liệu nền tảng. Môn học tập cũng trả lời sinh viên hiểu, so sánh và đánh giá được những giải thuật làm việc với các kết cấu dữ liệu đó.Ôn lại về lập trình, những kiểu dữ liệu trong C/C++, đặc biệt quan trọng là cấu tạo và nhỏ trỏ.Giới thiệu về độ phức tạp giám sát và đo lường và đệ qui.Các kết cấu dữ liệu cùng sự phân tích chúng: danh sách; ông chồng và hàng; cây, cây nhị phân, cây nhị phân tra cứu kiếm, AVL cùng đa phân; heap; giải thuật sắp xếp; bảng băm; và đồ thị. Bạn đang xem: Sách cấu trúc dữ liệu và giải thuật |
công dụng cần có được |
| Phân tích lời giải L.O.1.1 – Định nghĩa được các khái niệm độ phức tạp và độ phức hợp trong các trường vừa lòng “tốt nhất”, “xấu nhất”, cùng “trung bình”.L.O.1.2 – phân tích được những giải thuật và thực hiện được ký hiệu “Big O” nhằm ghi ra độ tinh vi của lời giải cấu thành tự các cấu trúc điều khiển: tuần tự, rẽ nhánh và lặp.L.O.1.3 – Liệt kê được, mang lại được lấy một ví dụ và so sánh được các lớp độ phức tạp, như, hằng số, log, con đường tính, etc.L.O.1.4 – nhấn thức được sự thăng bằng giữa bộ lưu trữ và thời hạn trong giải thuật.L.O.1.5 – bộc lộ được các chiến lược thiết kế giải thuật và giải quyết bài toán.Sử dụng cấu tạo dữ liệu danh sách, ông chồng và hàngL.O.2.1 – vạc họa được bởi hình hình ảnh cho: (a) list hiện thực bởi mảng cùng bằng link (con trỏ); (b) cho chồng; với (c) cho hàng chờ và hàng hóng vòng (mức logic).L.O.2.2 – Viết được bởi mã giả mô tả cấu trúc lưu trữ cho: (a) danh sách hiện thực bởi mảng và bằng liên kết; (b) cho chồng; cùng (c) mang lại hàng hóng và hàng chờ vòng (mức logic).L.O.2.3 – Liệt kê được những phương thức cần thiết cho từng cấu trúc như danh sách, chồng và hàng đợi; cũng tương tự mô tả được chúng bởi mã đưa (mức logic).L.O.2.4 – lúc này được các kết cấu danh sách, chồng và mặt hàng đợi bởi C/C++ (mức physics)L.O.2.5 – sử dụng được danh sách, chồng, và hàng để giải quyết và xử lý bài toán thực, cũng như quan tâm đến chọn lựa giao diện hiện thực tối ưu.L.O.2.6 – phân tích được và làm cho thí nghiệm đánh giá các thủ tục đã hổ trợ mang lại các cấu trúc danh sánh, chồng, với hàng.Sử dụng kết cấu câyL.O.3.1 – phân phát họa được bởi hình hình ảnh cho các cây tiêu biểu, như, cây nhị phân, cây nhị phân đầy đủ, cây nhị phân cân nặng bằng, cây AVL, cây đa phân, v.v. (mức logic).L.O.3.2 – Viết được bởi mã mang mô tả cấu tạo lưu trữ cho các loại cây (mức logic)L.O.3.3 – Liệt kê được các phương thức quan trọng cho cho các cấu trúc cây; cũng giống như mô tả được chúng bởi mã đưa (mức logic).L.O.3.4 – chỉ ra rằng được và mang đến ví dụ minh họa về tầm quan trọng đặc biệt của tính cân bằng trong cây.L.O.3.5 – chỉ ra rằng được cùng vẽ hình minh họa về tất cả các ngôi trường mất cân bằng trong cây AVL và cây B, cũng tương tự thực hiện mỗi bước để tái thăng bằng chúng trên mẫu vẽ (mức logic).L.O.3.6 – hiện tại được các kết cấu cây nhị phân với cây AVL bằng C/C++L.O.3.7 – áp dụng được cây nhị phân và cây AVL để giải quyết bài toán thực, nhất là liên quan mang lại tìm kiếm.L.O.3.8 – phân tích được và có tác dụng thực nghiệm reviews được các phương thức đang hổ trợ cho các cấu tạo cây nhị phân với cây AVL.Sử dụng HeapL.O.4.1 – chỉ ra được những áp dụng cần mang đến HeapL.O.4.2 – phác họa được bằng hình ảnh cho cấu tạo Heap và nêu ra sự liên quan đến tàng trữ ở dạng mảng.L.O.4.3 – Liệt kê được những phương thức cần thiết cho cho kết cấu heap; tương tự như mô tả được chúng bởi mã giả (mức logic).L.O.4.4 – demo được bởi hình ảnh các cách làm để bảo đảm an toàn tính chất của cấu tạo Heap khi đưa vào hay rước ra bộ phận trong heap (mức logic).L.O.4.5 – hiện thực được cấu tạo heap bằng C/C++.L.O.4.6 – so với được và làm cho thực nghiệm nhận xét được những phương thức sẽ hổ trợ cho kết cấu Heap.Sử dụng bảng băm L.O.5.1 – Vẽ được hình minh họa một bảng băm thuộc với khái niệm về khóa, chạm độ và xử lý đụng độ.L.O.5.2 – thể hiện được bởi mã đưa và mang lại ví dụ minh họa cho những hàm băm cơ bản.L.O.5.3 – diễn đạt được bằng mã trả và mang lại ví dụ minh họa cho các phương thức giải quyết đụng độ.L.O.5.4 – thực tại được cấu tạo bảng băm bởi C/C++.L.O.5.5 – phân tích được và có tác dụng thực nghiệm reviews được những phương thức đã hổ trợ cho kết cấu bảng băm.Phát triển các giải thuật sắp xếpL.O.6.1 – Minh họa được bởi hình vẽ từng bước hoạt động vui chơi của các giải mã sắp xếp.L.O.6.2 – trình bày được bởi mã giả cho những giải thuật sắp xếp. L.O.6.3 – hiện thực được những giải thuật thu xếp bằng C/C++ .L.O.6.4 – so sánh được và làm thực nghiệm reviews các lời giải sắp xếp.L.O.6.5 – áp dụng được giải thuật sắp xếp trong việc thực.Hiểu biết cơ phiên bản về đồ gia dụng thịL.O.7.1 – vạc họa được bằng hình ảnh cho các khái niệm như vật dụng thị liên thông và không liên thông, thiết bị thị được bố trí theo hướng và ko hướng, chu trình, v.v.L.O.7.2 – Vẽ được hình minh họa cùng mô tả cấu tạo lưu trữ đến đồ thị ở các dạng ma trận kề và list kề bằng mã đưa (mức logic).L.O.7.3 – Liệt kê được các phương thức quan trọng cho mang đến các cấu trúc đồ thị; cũng tương tự mô tả được chúng bởi mã trả (mức logic).L.O.7.4 – Minh họa được bằng hình ảnh các cách thức duyệt đồ thị cơ bản (depth first and bread-first).L.O.7.5 – hiện thực được kết cấu lưu trữ thiết bị thì bằng C/C++.L.O.7.6 – lúc này được các phương pháp duyệt nói trên bởi C/C++ và thực hiện chúng xử lý bài toán thực.L.O.7.7 – Minh họa bởi hình vẽ từng bước hoạt động vui chơi của các lời giải tìm mặt đường ngắn nhất bằng Dijktra và giải thuật tìm cây phủ về tối tiểu bằng giải thuật Prim.Sử dụng đệ quyL.O.8.1 – biểu hiện được những thành phần cơ bản của một lời giải đệ quy.L.O.8.2 – Vẽ được cây mô tả các lần hotline hàm cùng giá trị của các tham số được truyền vào những hàm đó.L.O.8.3 – cho được lấy một ví dụ về một hàm gọi đệ quy viết bởi C/C++.L.O.8.4 – trở nên tân tiến được giải mã đệ quy cho các phương thức cần thiết của các cấu trúc: danh sách, cây, heap, kiếm tìm kiếm trên cây và tìm kiếm nhị phân, và đồ thị.L.O.8.5 – làm cho được thí nghiệm để so sánh cách tiếp cận đệ quy và bí quyết lặp.L.O.8.6 – đến được lấy một ví dụ minh họa sự tương quan giữa Backtracking với đệ quy. |
Tài liệu tham khảo |
| Sách, Giáo trình chính:<1>. “Data Structures: a Pseudocode Approach with C++”, R.F.Gilberg and B.A. Forouzan, Thomson Learning Inc., 2001.Sách tham khảo:<1> “Data Structures and Algorithms in C++”, A. Drozdek, Thomson Learning Inc., 2005. Xem thêm: Hướng Dẫn Cách Sử Dụng Loa Bluetooth Mini Đơn Giản Hiệu Quả Nhanh Nhất <2> “C/C++: How lớn Program”, 7th Ed. – Paul Deitel và Harvey Deitel, Prentice Hall, 2012.<3> Internet.<4> Minh họa kết cấu dữ liệu cùng giải thuật |
