Bài tập thực hành: Giải thuật đệ quy trong Cấu trúc dữ liệu và Giải thuật (ĐHSPKT Hưng Yên)

Bài tập thực hành cấu trúc dữ liệu & giải thuật: Bài 9 hướng dẫn cài đặt giải thuật đệ quy. Nắm vững kiến thức & kỹ năng lập trình đệ quy hiệu quả.

• Trường học: Trường Đại Học Sư Phạm Kỹ Thuật Hưng Yên
• Chuyên ngành: Cấu trúc dữ liệu và giải thuật
• Đề tài: Đệ Quy: Bài Tập Cấu Trúc Dữ Liệu & Giải Thuật
• Loại tài liệu: Bài tập thực hành
• Năm xuất bản: 2021
• Địa điểm: Hưng Yên

Mục lục chi tiết

• MỤC LỤC
• 9. Bài 9: Thực hành cài đặt giải thuật đệ quy
• 10. Bài 10: Thực hành cài đặt danh sách bằng mảng
• 11. Bài 11: Thực hành cài đặt danh sách bằng danh sách liên kết đơn
• 12. Bài 12: Thực hành cài đặt danh sách Stack, Queue
• 13. Bài 13: Thực hành cài đặt cây nhị phân
• 14. Bài 14: Thực hành cài đặt các giải thuật sắp xếp - tìm kiếm

Tóm tắt

I. Đệ Quy Là Gì Tổng Quan Ứng Dụng Trong Cấu Trúc Dữ Liệu

Đệ quy, hay recursion, là một khái niệm nền tảng trong khoa học máy tính và lập trình. Nó cho phép một hàm tự gọi chính nó để giải quyết các bài toán phức tạp bằng cách chia nhỏ chúng thành các bài toán con nhỏ hơn, tương tự. Bản chất của đệ quy nằm ở việc định nghĩa một bài toán bằng chính nó, với một hoặc nhiều trường hợp cơ sở (base case) để ngăn chặn việc tự gọi vô hạn. Khi một hàm đệ quy được gọi, một bản sao mới của hàm được tạo ra trong bộ nhớ, và các tham số và biến cục bộ của bản sao này được lưu trữ trong một cấu trúc dữ liệu gọi là call stack. Khi một bản sao của hàm hoàn thành việc thực thi, nó trả về kết quả cho bản sao gọi nó, và bản sao đó được giải phóng khỏi bộ nhớ.

Ứng dụng của đệ quy rất rộng rãi, từ việc duyệt các cấu trúc dữ liệu như cây (tree traversal recursion), đồ thị (depth-first search recursion), đến việc giải các bài toán như tính giai thừa (factorial recursion), dãy Fibonacci (fibonacci recursion), hay các thuật toán sắp xếp như Merge Sort (merge sort recursion) và Quick Sort (quick sort recursion). Đệ quy cũng đóng vai trò quan trọng trong các kỹ thuật lập trình như divide and conquer, dynamic programming, và backtracking. Ưu điểm của đệ quy bao gồm tính ngắn gọn, dễ hiểu và khả năng giải quyết các bài toán phức tạp một cách tự nhiên. Tuy nhiên, đệ quy cũng có nhược điểm là có thể gây ra stack overflow nếu không được thiết kế cẩn thận, và có thể kém hiệu quả hơn so với các giải pháp lặp (iterative vs recursive solutions) trong một số trường hợp.

1.1. Khái niệm hàm đệ quy recursive function và vai trò

Hàm đệ quy là hàm tự gọi chính nó trong định nghĩa của nó. Điều này cho phép hàm giải quyết các bài toán phức tạp bằng cách chia nhỏ chúng thành các bài toán con tương tự. Vai trò của hàm đệ quy là tạo ra các giải pháp ngắn gọn, dễ hiểu và tự nhiên cho các bài toán có thể được định nghĩa bằng chính nó. Ví dụ, hàm tính giai thừa có thể được định nghĩa đệ quy như sau: factorial(n) = n * factorial(n-1) với trường hợp cơ sở factorial(0) = 1. Hàm đệ quy giúp đơn giản hóa việc lập trình và giảm thiểu mã lặp đi lặp lại.

1.2. Phân biệt Base Case trường hợp cơ sở và Recursive Step bước đệ quy

Một hàm đệ quy cần có hai thành phần chính: base case và recursive step. Base case là trường hợp đơn giản nhất của bài toán mà có thể giải quyết trực tiếp mà không cần gọi đệ quy. Nó đóng vai trò là điểm dừng cho quá trình đệ quy, ngăn chặn việc tự gọi vô hạn. Recursive step là phần của hàm mà gọi chính nó với một phiên bản nhỏ hơn của bài toán. Trong recursive step, bài toán được chia nhỏ thành các bài toán con tương tự, và hàm đệ quy được gọi để giải quyết các bài toán con này. Ví dụ, trong hàm tính giai thừa, base case là n = 0 và recursive step là n > 0 với factorial(n) = n * factorial(n-1).

1.3. Ưu điểm và nhược điểm của đệ quy advantages of recursion

Đệ quy có nhiều ưu điểm, bao gồm tính ngắn gọn, dễ hiểu, và khả năng giải quyết các bài toán phức tạp một cách tự nhiên. Nó cũng cho phép lập trình viên tập trung vào logic của bài toán hơn là các chi tiết triển khai. Tuy nhiên, đệ quy cũng có nhược điểm là có thể gây ra stack overflow nếu không được thiết kế cẩn thận, và có thể kém hiệu quả hơn so với các giải pháp lặp trong một số trường hợp. Việc sử dụng call stack để lưu trữ các bản sao của hàm đệ quy có thể tốn kém về mặt bộ nhớ, đặc biệt là đối với các bài toán có độ sâu đệ quy lớn. Trong một số trường hợp, việc sử dụng các kỹ thuật như tail recursion và memoization có thể giúp cải thiện hiệu suất của hàm đệ quy.

II. Vượt Qua Thách Thức Ngăn Chặn Stack Overflow Khi Dùng Đệ Quy

Một trong những thách thức lớn nhất khi sử dụng đệ quy là nguy cơ gây ra stack overflow. Điều này xảy ra khi độ sâu đệ quy quá lớn, dẫn đến việc call stack tràn bộ nhớ. Để ngăn chặn stack overflow, cần đảm bảo rằng hàm đệ quy có một base case rõ ràng và rằng mỗi lần gọi đệ quy đều tiến gần hơn đến base case. Cũng cần xem xét giới hạn độ sâu đệ quy của hệ thống và thiết kế thuật toán sao cho không vượt quá giới hạn này.

Một số kỹ thuật có thể giúp giảm thiểu nguy cơ stack overflow bao gồm tail recursion và memoization. Tail recursion là một hình thức đệ quy mà lời gọi đệ quy là thao tác cuối cùng được thực hiện trong hàm. Trong một số ngôn ngữ, trình biên dịch có thể tối ưu hóa tail recursion thành vòng lặp, giúp giảm thiểu việc sử dụng bộ nhớ. Memoization là một kỹ thuật lưu trữ kết quả của các lời gọi hàm đệ quy để tránh việc tính toán lại các giá trị đã biết. Kỹ thuật này có thể giúp cải thiện hiệu suất của hàm đệ quy, đặc biệt là đối với các bài toán có nhiều lời gọi đệ quy trùng lặp.

2.1. Tìm hiểu nguyên nhân gây ra lỗi Stack Overflow khi sử dụng đệ quy

Lỗi stack overflow xảy ra khi chương trình cố gắng sử dụng nhiều bộ nhớ hơn mức cho phép trên call stack. Khi một hàm đệ quy được gọi, một bản sao mới của hàm được tạo ra trên call stack, cùng với các tham số và biến cục bộ của bản sao đó. Nếu hàm đệ quy gọi chính nó quá nhiều lần mà không đạt đến base case, call stack sẽ tiếp tục tăng kích thước cho đến khi nó tràn bộ nhớ. Nguyên nhân chính gây ra lỗi stack overflow là do thiết kế hàm đệ quy không cẩn thận, dẫn đến việc tự gọi vô hạn hoặc độ sâu đệ quy quá lớn.

2.2. Kỹ thuật Tail Recursion đệ quy đuôi và cách tối ưu hóa

Tail recursion là một hình thức đệ quy mà lời gọi đệ quy là thao tác cuối cùng được thực hiện trong hàm. Điều này cho phép trình biên dịch tối ưu hóa hàm đệ quy thành vòng lặp, giúp giảm thiểu việc sử dụng bộ nhớ trên call stack. Để chuyển đổi một hàm đệ quy thông thường thành tail recursion, cần đảm bảo rằng lời gọi đệ quy là thao tác cuối cùng được thực hiện, và kết quả của lời gọi đệ quy được trả về trực tiếp mà không cần thực hiện thêm bất kỳ thao tác nào. Ví dụ, hàm tính giai thừa có thể được chuyển đổi thành tail recursion bằng cách sử dụng một tham số tích lũy để lưu trữ kết quả trung gian.

2.3. Memoization Lưu trữ kết quả để tránh tính toán lặp lại

Memoization là một kỹ thuật lưu trữ kết quả của các lời gọi hàm đệ quy để tránh việc tính toán lại các giá trị đã biết. Khi một hàm đệ quy được gọi với một bộ tham số cụ thể, kết quả được lưu trữ trong một bảng tra cứu (lookup table). Nếu hàm đệ quy được gọi lại với cùng bộ tham số đó, kết quả được lấy từ bảng tra cứu thay vì tính toán lại. Memoization có thể giúp cải thiện hiệu suất của hàm đệ quy, đặc biệt là đối với các bài toán có nhiều lời gọi đệ quy trùng lặp, như tính dãy Fibonacci.

III. Ứng Dụng Đệ Quy Giải Quyết Bài Toán Cấu Trúc Dữ Liệu Hiệu Quả

Đệ quy là một công cụ mạnh mẽ để giải quyết các bài toán liên quan đến cấu trúc dữ liệu. Nó đặc biệt hữu ích trong việc duyệt và xử lý các cấu trúc dữ liệu có tính chất đệ quy, chẳng hạn như cây (tree traversal recursion), đồ thị (depth-first search recursion), và danh sách liên kết (linked list recursion). Với cây, đệ quy có thể được sử dụng để duyệt cây theo thứ tự trước, giữa, sau, hoặc theo chiều rộng. Với đồ thị, đệ quy có thể được sử dụng để tìm đường đi, kiểm tra tính liên thông, hoặc tìm chu trình. Với danh sách liên kết, đệ quy có thể được sử dụng để đảo ngược danh sách, tìm phần tử, hoặc xóa phần tử.

Việc sử dụng đệ quy trong các bài toán cấu trúc dữ liệu giúp tạo ra các giải pháp ngắn gọn, dễ hiểu và dễ bảo trì. Tuy nhiên, cũng cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow, và xem xét các giải pháp lặp nếu cần thiết.

3.1. Đệ quy trên cây nhị phân binary search recursion Duyệt và tìm kiếm

Đệ quy là phương pháp tự nhiên để duyệt và tìm kiếm trên cây nhị phân. Các thuật toán duyệt cây nhị phân như duyệt trước (preorder), duyệt giữa (inorder), và duyệt sau (postorder) đều có thể được triển khai một cách dễ dàng bằng đệ quy. Đối với tìm kiếm trên cây nhị phân tìm kiếm (binary search recursion), đệ quy cho phép tìm kiếm phần tử một cách hiệu quả bằng cách so sánh giá trị cần tìm với giá trị của nút hiện tại và tiếp tục tìm kiếm trên cây con trái hoặc cây con phải tùy thuộc vào kết quả so sánh.

3.2. Đệ quy trên danh sách liên kết linked list recursion Thao tác cơ bản

Đệ quy cũng có thể được sử dụng để thực hiện các thao tác cơ bản trên danh sách liên kết. Ví dụ, hàm đảo ngược danh sách liên kết có thể được triển khai đệ quy bằng cách đảo ngược phần còn lại của danh sách và sau đó thêm phần tử đầu tiên vào cuối danh sách đã đảo ngược. Các thao tác khác như tìm phần tử, xóa phần tử, hoặc chèn phần tử cũng có thể được triển khai đệ quy, mặc dù các giải pháp lặp thường hiệu quả hơn.

3.3. Ứng dụng thuật toán Depth First Search DFS bằng đệ quy

Depth-First Search (DFS) là một thuật toán duyệt đồ thị quan trọng có thể được triển khai một cách tự nhiên bằng đệ quy. DFS bắt đầu từ một đỉnh và duyệt sâu vào đồ thị cho đến khi không còn đỉnh nào chưa được thăm. Sau đó, nó quay lui và tiếp tục duyệt các nhánh khác của đồ thị. Đệ quy cho phép dễ dàng theo dõi trạng thái của các đỉnh đã được thăm và đảm bảo rằng tất cả các đỉnh trong đồ thị đều được duyệt qua.

IV. Đệ Quy Trong Sắp Xếp Tìm Kiếm Giải Thuật Nhanh và Hiệu Quả

Đệ quy đóng vai trò quan trọng trong nhiều thuật toán sắp xếp và tìm kiếm hiệu quả. Các thuật toán sắp xếp như Merge Sort (merge sort recursion) và Quick Sort (quick sort recursion) sử dụng divide and conquer, một kỹ thuật dựa trên đệ quy, để chia nhỏ bài toán sắp xếp thành các bài toán con nhỏ hơn, sắp xếp các bài toán con này, và sau đó kết hợp kết quả để tạo ra dãy đã sắp xếp.

Đối với tìm kiếm, binary search recursion là một thuật toán tìm kiếm hiệu quả trên dãy đã sắp xếp, sử dụng đệ quy để chia đôi không gian tìm kiếm mỗi lần, giúp giảm đáng kể thời gian tìm kiếm. Việc sử dụng đệ quy trong các thuật toán sắp xếp và tìm kiếm giúp tạo ra các giải pháp hiệu quả và dễ hiểu, mặc dù cũng cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow.

4.1. Phân tích giải thuật Merge Sort sắp xếp trộn đệ quy

Merge Sort là một thuật toán sắp xếp divide and conquer sử dụng đệ quy để chia dãy cần sắp xếp thành các dãy con nhỏ hơn, sắp xếp các dãy con này, và sau đó trộn các dãy con đã sắp xếp để tạo ra dãy đã sắp xếp. Hàm Merge Sort đệ quy chia dãy thành hai nửa, gọi đệ quy để sắp xếp hai nửa này, và sau đó trộn hai nửa đã sắp xếp. Độ phức tạp thời gian của Merge Sort là O(n log n), làm cho nó trở thành một thuật toán sắp xếp hiệu quả cho các dãy lớn.

4.2. Phân tích giải thuật Quick Sort sắp xếp nhanh đệ quy

Quick Sort là một thuật toán sắp xếp divide and conquer khác sử dụng đệ quy. Nó chọn một phần tử pivot từ dãy và chia dãy thành hai phần: các phần tử nhỏ hơn pivot và các phần tử lớn hơn pivot. Sau đó, nó gọi đệ quy để sắp xếp hai phần này. Hiệu suất của Quick Sort phụ thuộc vào việc chọn pivot tốt. Trong trường hợp tốt nhất và trung bình, độ phức tạp thời gian của Quick Sort là O(n log n), nhưng trong trường hợp xấu nhất, nó có thể là O(n^2). Tuy nhiên, Quick Sort thường nhanh hơn Merge Sort trong thực tế do ít tốn chi phí hơn.

4.3. Cài đặt tìm kiếm nhị phân binary search sử dụng đệ quy

Tìm kiếm nhị phân (binary search) là một thuật toán tìm kiếm hiệu quả trên dãy đã sắp xếp. Nó sử dụng đệ quy để chia đôi không gian tìm kiếm mỗi lần. Hàm tìm kiếm nhị phân đệ quy so sánh giá trị cần tìm với giá trị của phần tử ở giữa dãy. Nếu giá trị cần tìm nhỏ hơn giá trị ở giữa, nó tiếp tục tìm kiếm trên nửa đầu của dãy; nếu lớn hơn, nó tiếp tục tìm kiếm trên nửa sau của dãy. Nếu bằng, nó trả về vị trí của phần tử. Độ phức tạp thời gian của tìm kiếm nhị phân là O(log n), làm cho nó trở thành một thuật toán tìm kiếm rất hiệu quả cho các dãy lớn đã sắp xếp.

V. Đệ Quy Bài Toán Kinh Điển Tháp Hà Nội Giai Thừa Fibonacci

Đệ quy thường được sử dụng để giải quyết các bài toán kinh điển trong khoa học máy tính, chẳng hạn như Tháp Hà Nội (tower of hanoi), tính giai thừa (factorial recursion), và tính dãy Fibonacci (fibonacci recursion). Tháp Hà Nội là một bài toán về di chuyển các đĩa từ một cột sang một cột khác, tuân theo một số quy tắc. Giải pháp đệ quy cho bài toán này rất ngắn gọn và dễ hiểu. Tính giai thừa và dãy Fibonacci là các ví dụ khác về các bài toán có thể được giải quyết một cách tự nhiên bằng đệ quy. Tuy nhiên, cần lưu ý rằng giải pháp đệ quy cho bài toán Fibonacci có thể kém hiệu quả do nhiều lời gọi đệ quy trùng lặp, và nên sử dụng memoization hoặc giải pháp lặp để cải thiện hiệu suất.

5.1. Giải bài toán Tháp Hà Nội tower of hanoi bằng đệ quy

Bài toán Tháp Hà Nội là một bài toán kinh điển về di chuyển các đĩa từ một cột sang một cột khác, tuân theo các quy tắc: chỉ được di chuyển một đĩa tại một thời điểm, và không được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn. Giải pháp đệ quy cho bài toán này rất ngắn gọn và dễ hiểu. Nó bao gồm ba bước: di chuyển n-1 đĩa từ cột nguồn sang cột trung gian, di chuyển đĩa lớn nhất từ cột nguồn sang cột đích, và di chuyển n-1 đĩa từ cột trung gian sang cột đích.

5.2. Cài đặt hàm đệ quy tính giai thừa factorial

Hàm tính giai thừa có thể được cài đặt đệ quy như sau: factorial(n) = n * factorial(n-1) với trường hợp cơ sở factorial(0) = 1. Hàm này gọi chính nó với một giá trị nhỏ hơn của n cho đến khi đạt đến trường hợp cơ sở, tại đó nó trả về giá trị 1. Giải pháp đệ quy cho bài toán này rất ngắn gọn và dễ hiểu, nhưng cần lưu ý rằng nó có thể gây ra stack overflow nếu n quá lớn.

5.3. Cài đặt hàm đệ quy tính số Fibonacci fibonacci

Hàm tính số Fibonacci có thể được cài đặt đệ quy như sau: fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) với các trường hợp cơ sở fibonacci(0) = 0 và fibonacci(1) = 1. Hàm này gọi chính nó với hai giá trị nhỏ hơn của n cho đến khi đạt đến các trường hợp cơ sở, tại đó nó trả về giá trị 0 hoặc 1. Giải pháp đệ quy cho bài toán này rất dễ hiểu, nhưng nó kém hiệu quả do nhiều lời gọi đệ quy trùng lặp. Để cải thiện hiệu suất, có thể sử dụng memoization hoặc giải pháp lặp.

VI. Đệ Quy Trong Thực Tế Ngôn Ngữ Lập Trình Lời Khuyên

Đệ quy được hỗ trợ rộng rãi trong nhiều ngôn ngữ lập trình, bao gồm C++, Python, Java, và JavaScript. Mỗi ngôn ngữ có cú pháp và quy tắc riêng để sử dụng đệ quy. Trong C++, đệ quy được sử dụng tương tự như trong C. Trong Python, đệ quy được hỗ trợ tốt, nhưng có giới hạn độ sâu đệ quy mặc định để ngăn chặn stack overflow. Trong Java, đệ quy được sử dụng rộng rãi trong các bài toán cấu trúc dữ liệu và thuật toán. Trong JavaScript, đệ quy được sử dụng trong cả lập trình phía máy chủ và phía máy khách.

Khi sử dụng đệ quy trong thực tế, cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow. Nên sử dụng tail recursion và memoization khi có thể để cải thiện hiệu suất. Cũng nên xem xét các giải pháp lặp nếu đệ quy không phải là lựa chọn tốt nhất.

6.1. Đệ quy trong C Đệ quy trong C Cú pháp và ví dụ

Trong C++, đệ quy được sử dụng tương tự như trong C. Hàm đệ quy được định nghĩa bằng cách gọi chính nó trong thân hàm. Cần đảm bảo rằng hàm có một trường hợp cơ sở để ngăn chặn việc tự gọi vô hạn. Ví dụ, hàm tính giai thừa có thể được cài đặt đệ quy trong C++ như sau:

int factorial(int n) {
 if (n == 0) {
 return 1;
 } else {
 return n * factorial(n-1);
 }
}

6.2. Đệ quy trong Python Đệ quy trong Python Giới hạn và cách khắc phục

Trong Python, đệ quy được hỗ trợ tốt, nhưng có giới hạn độ sâu đệ quy mặc định để ngăn chặn stack overflow. Giới hạn này có thể được thay đổi bằng cách sử dụng hàm sys.setrecursionlimit(), nhưng cần cẩn thận để không đặt giới hạn quá cao, vì điều này có thể dẫn đến stack overflow. Ví dụ, hàm tính giai thừa có thể được cài đặt đệ quy trong Python như sau:

def factorial(n):
 if n == 0:
 return 1
 else:
 return n * factorial(n-1)

6.3. Đệ quy trong Java Đệ quy trong Java Ứng dụng và lời khuyên

Trong Java, đệ quy được sử dụng rộng rãi trong các bài toán cấu trúc dữ liệu và thuật toán. Ví dụ, hàm tính giai thừa có thể được cài đặt đệ quy trong Java như sau:

public static int factorial(int n) {
 if (n == 0) {
 return 1;
 } else {
 return n * factorial(n-1);
 }
}

Khi sử dụng đệ quy trong Java, cần lưu ý đến các vấn đề liên quan đến hiệu suất và stack overflow. Nên sử dụng tail recursion và memoization khi có thể để cải thiện hiệu suất. Cũng nên xem xét các giải pháp lặp nếu đệ quy không phải là lựa chọn tốt nhất.

Nội dung chính

Đánh Giá Học Thuật Và Tổng Quan Tài Liệu: Bài Tập Thực Hành Cấu Trúc Dữ Liệu Và Giải Thuật

Tài liệu "Bài Tập Thực Hành Học Phần: Cấu Trúc Dữ Liệu Và Giải Thuật" do Khoa Công nghệ Thông tin – Trường Đại học Sư phạm Kỹ thuật Hưng Yên biên soạn năm 2021 là học liệu phục vụ đào tạo trình độ đại học chính quy cho các ngành Công nghệ thông tin (CNTT), Kỹ thuật phần mềm (KTPM) và Khoa học máy tính (KHMT). Văn bản tập trung vào việc hiện thực hóa các cấu trúc dữ liệu và giải thuật nền tảng thông qua ngôn ngữ lập trình C#.

---

Tổng quan về giáo trình

Môn học và vị trí trong chương trình đào tạo

Học phần Cấu trúc dữ liệu và giải thuật (CTDL&GT) giữ vị trí cơ sở ngành bắt buộc trong khung chương trình đào tạo kỹ sư và cử nhân các ngành Công nghệ thông tin, Kỹ thuật phần mềm và Khoa học máy tính. Học phần đóng vai trò cầu nối giữa kỹ năng lập trình cơ sở và các môn học chuyên sâu về phát triển phần mềm, cơ sở dữ liệu và phân tích thiết kế thuật toán. Tài liệu thực hành được thiết kế đồng bộ với chương trình lý thuyết nhằm củng cố kỹ năng lập trình thực nghiệm trên máy tính.

Mục tiêu học tập (Learning Outcomes)

Tài liệu xác định các chuẩn đầu ra cụ thể sau khi sinh viên hoàn thành các bài thực hành:

• Chuẩn kiến thức: Trình bày được nguyên lý hoạt động, cấu trúc lưu trữ và giải thuật thao tác trên các kiểu dữ liệu trừu tượng gồm danh sách tuyến tính (mảng, danh sách liên kết đơn), ngăn xếp (Stack), hàng đợi (Queue), cấu trúc phi tuyến (cây nhị phân, cây nhị phân tìm kiếm) và các giải thuật sắp xếp, tìm kiếm, đệ quy.
• Chuẩn kỹ năng: Khai báo, cài đặt và thao tác thành thạo các cấu trúc dữ liệu bằng ngôn ngữ C#; phân tích và chuyển đổi các bài toán quản lý thực tế thành các mô hình dữ liệu phù hợp; giải thích được trình tự thực thi của máy tính và cơ chế quản lý bộ nhớ.
• Năng lực tư duy: Rèn luyện kỹ năng phân tích thuật toán, tư duy logic và khả năng đánh giá ưu – nhược điểm của các giải pháp lưu trữ dữ liệu khác nhau.

Cấu trúc và cách tiếp cận

Tài liệu gồm 6 bài thực hành chuyên đề (từ Bài 9 đến Bài 14 trong chương trình học phần), trải dài từ trang 3 đến trang 41. Mỗi bài học được tổ chức theo quy trình chuẩn mực:

1. Mục tiêu bài học: Nêu rõ các yêu cầu về kiến thức và kỹ năng cần đạt.
2. Bài tập mẫu: Đưa ra đề bài toán điển hình.
3. Phân tích: Giải thích cơ chế thuật toán, phân tích trường hợp suy biến/trường hợp đệ quy hoặc phân chia cấu trúc bộ nhớ.
4. Lời giải mẫu: Cung cấp mã nguồn hoàn chỉnh bằng ngôn ngữ C# đi kèm chú thích chi tiết.
5. Nhận xét chuyên môn: Đánh giá ưu nhược điểm kỹ thuật, lưu ý về quản lý vùng nhớ (tĩnh/động) và phương thức truyền tham số (ref, out).
6. Hệ thống bài tập thực hành: Các bài toán mở rộng từ mức độ cơ bản đến ứng dụng quản lý phức hợp.

Điểm đặc sắc của tài liệu

Học liệu kết hợp chặt chẽ giữa kỹ thuật cài đặt thuật toán kinh điển với các bài toán quản lý dữ liệu thực tế (quản lý bảng lương nhân viên, quản lý điểm học phần sinh viên theo tín chỉ, quản lý thông tin địa giới tỉnh thành, quản lý hồ sơ học sinh). Cách tiếp cận này giúp sinh viên hình dung rõ ràng ứng dụng của cấu trúc dữ liệu trong việc xây dựng các phần mềm ứng dụng.

---

Nội dung kiến thức cốt lõi

+-----------------------------------------------------------------------------------+
|               TIẾN TRÌNH CẤU TRÚC DỮ LIỆU & GIẢI THUẬT (BÀI 9 - 14)               |
+-----------------------------------------------------------------------------------+
|  Bài 9: Giải thuật Đệ quy & Quay lui (Fibonacci, Chuỗi căn lồng, Phân tích số N)  |
|                                         v                                         |
|  Bài 10: Danh sách bằng Mảng (Cấp phát tĩnh, Chèn/Xóa, Ma trận, Struct NhanVien)  |
|                                         v                                         |
|  Bài 11: Danh sách Liên kết Đơn (Node, Cấp phát động, Con trỏ pHead, Quản lý tỉnh)|
|                                         v                                         |
|  Bài 12: Ngăn xếp & Hàng đợi (Stack LIFO, Queue FIFO, Đổi cơ số, Kiểm tra ngoặc)  |
|                                         v                                         |
|  Bài 13: Cây Nhị phân (Node Tree, Duyệt Trước-Giữa-Sau, Đếm số nút đệ quy)        |
|                                         v                                         |
|  Bài 14: Sắp xếp & Cây Nhị phân Tìm kiếm (Selection Sort, BST Search, HocSinh)    |
+-----------------------------------------------------------------------------------+

Các chương và chủ đề chính

• Bài 9: Thực hành cài đặt giải thuật đệ quy (Trang 3–9): Tập trung vào việc xác định hai thành phần bắt buộc của đệ quy: trường hợp suy biến (điều kiện dừng) và trường hợp đệ quy. Tài liệu cung cấp bài mẫu tính số Fibonacci ($F(n) = F(n-1) + F(n-2)$ với điều kiện $n < 2$), thuật toán quay lui đệ quy sinh xâu nhị phân độ dài $N$ (PROCEDURE TÌM(K:INTEGER)), giải thuật tính lũy thừa $S(x, n) = x^n$, thuật toán Euclid tìm ước chung lớn nhất (UCLN), đếm chữ số, tính chuỗi căn lồng nhau $S(n) = \sqrt{1+\sqrt{2+\dots+\sqrt{n}}}$, và bài toán phân tích số tự nhiên $N$ thành tổng các số tự nhiên có lưu trạng thái trong mảng.
• Bài 10: Thực hành cài đặt danh sách bằng mảng (Trang 10–16): Hướng dẫn kỹ thuật tổ chức dữ liệu kế tiếp. Minh họa chi tiết thuật toán chèn phần tử $x$ vào vị trí $k$ và thuật toán xóa số nguyên tố thông qua mảng trung gian hoặc dồn dịch phần tử. Phân tích bài tập xử lý ma trận vuông $n \times n$ (đường chéo chính $i=j$, đường chéo phụ $j=(n-1)-i$) và các bài toán quản lý cấu trúc phức hợp như struct NhanVien (tính thực lĩnh, tìm lương thấp nhất, tăng lương 5%) và quản lý điểm sinh viên theo tín chỉ (tính điểm trung bình chung $TBC = \sum (Điểm \times TC) / \sum TC$, xét học bổng với điều kiện điểm học phần $\ge 5$ và điểm $TBC \ge 7.0$).
• Bài 11: Thực hành cài đặt danh sách bằng danh sách liên kết đơn (Trang 17–22): Thiết lập cấu trúc nút (class Node { public int info; public Node link; }) và biến quản lý đầu danh sách pHead. Hướng dẫn cài đặt các thao tác: khởi tạo, duyệt danh sách, đếm phần tử, tìm giá trị dương nhỏ nhất, và xóa nút (xét 3 trường hợp: xóa nút đầu p == pHead, xóa nút giữa và xóa nút cuối). Phần bài tập mở rộng ứng dụng trên cấu trúc danh sách liên kết đơn các tỉnh với các thuộc tính tên tỉnh, diện tích, dân số và thao tác sắp xếp tăng dần theo diện tích.
• Bài 12: Thực hành cài đặt Stack, Queue (Trang 23–32): Trình bày nguyên lý hoạt động "vào sau ra trước" (LIFO) của Stack và "vào trước ra trước" (FIFO) của Queue. Cài đặt Stack bằng mảng (class Stack với các hàm Push, Pop, Peak, Isempty, Isfull) và Queue bằng danh sách liên kết (class Queue với các hàm EnQueue, DeQueue, Front, EmptyQueue, Cleanup). Ứng dụng Stack vào bài toán chuyển đổi hệ cơ số 10 sang cơ số $a$, thuật toán kiểm tra chuỗi cặp dấu ngoặc hợp lệ; ứng dụng Queue vào sắp xếp dãy số và mô phỏng dòng chữ chạy, xử lý chuỗi thao tác hàng đợi dạng EAS*Y**QUE***ST***I*ON.
• Bài 13: Thực hành cài đặt cây nhị phân (Trang 33–34): Xây dựng cấu trúc nút cây (class Node { public int info; public Node left, right; }), hàm khởi tạo cây có gốc và 2 cây con (CreateTree2). Triển khai các thuật toán đệ quy duyệt cây theo thứ tự Trước – Giữa – Sau, thuật toán đếm số nút cây (Dem(Node T) = Dem(T.left) + Dem(T.right) + 1), tính tổng giá trị các nút và đếm số nút chẵn.
• Bài 14: Thực hành cài đặt các giải thuật sắp xếp – tìm kiếm (Trang 35–41): Cài đặt giải thuật sắp xếp lựa chọn (Selection Sort) trên mảng một chiều; xây dựng cấu trúc cây nhị phân tìm kiếm (BST), hàm chèn phần tử vào cây (Them), hàm tạo cây từ mảng (createTree) và hàm tìm kiếm giá trị $X$ trên cây (Search). Hệ thống bài tập áp dụng giải thuật sắp xếp và tìm kiếm trên danh sách học sinh theo cấu trúc struct hocSinh (Mã HS, Tên, Ngày sinh, Quê quán, Lớp, Điểm TB).

+-----------------------------------------------------------------------------------+
|                        SO SÁNH ĐẶC TÍNH KỸ THUẬT LƯU TRỮ                         |
+------------------------------------+----------------------------------------------+
| Cấu trúc Mảng (Array)              | Danh sách Liên kết (Linked List)            |
+------------------------------------+----------------------------------------------+
| - Cấp phát bộ nhớ tĩnh/cố định     | - Cấp phát bộ nhớ động linh hoạt             |
| - Truy xuất trực tiếp: O(1)        | - Truy xuất tuần tự: O(n)                    |
| - Chèn/Xóa: Phải dời phần tử       | - Chèn/Xóa: Cập nhật lại liên kết con trỏ    |
| - Nguy cơ tràn/lãng phí bộ nhớ     | - Tốn thêm bộ nhớ lưu trữ con trỏ (link)     |
+------------------------------------+----------------------------------------------+

Kiến thức nền tảng được xây dựng

• Mô hình lưu trữ dữ liệu: Phân định rõ ràng giữa lưu trữ kế tiếp (Contiguous Allocation) trên mảng và lưu trữ móc nối (Linked Allocation) trên danh sách liên kết.
• Quản lý bộ nhớ: Khái niệm cấp phát bộ nhớ tĩnh và cấp phát bộ nhớ động trong môi trường thực thi; cơ chế truyền tham số theo giá trị (tham trị) và theo địa chỉ/tham chiếu (ref, out) trong ngôn ngữ C# để bảo toàn trạng thái dữ liệu sau khi thực thi hàm.
• Kỹ thuật thiết kế giải thuật: Kỹ thuật đệ quy, kỹ thuật quay lui có nhánh cận và đánh dấu trạng thái (kt[]), kỹ thuật duyệt cây theo chiều sâu.

Kỹ năng phát triển

• Kỹ năng lập trình: Hiện thực hóa các cấu trúc dữ liệu bằng mã lệnh C# chuẩn xác, quản lý con trỏ tham chiếu, xử lý các tình huống ngoại lệ (throw new Exception).
• Kỹ năng phân tích thuật toán: Khả năng xác định các trường hợp biên của bài toán (danh sách rỗng, cây rỗng, ngăn xếp rỗng/đầy, vị trí đầu/cuối của danh sách).
• Kỹ năng mô hình hóa: Chuyển đổi các bài toán nghiệp vụ thực tiễn thành các cấu trúc dữ liệu dạng bản ghi (struct, class) và viết các hàm thao tác tương ứng.

---

Phương pháp giảng dạy và học tập

Phương pháp tiếp cận sư phạm

Tài liệu triển khai phương pháp giảng dạy thực hành có hướng dẫn (Guided Practical Learning). Tiến trình tiếp cận được chuẩn hóa theo từng bước:

1. Nêu mục tiêu học tập rõ ràng để định hướng kết quả cần đạt.
2. Phân tích nguyên lý toán học và cấu trúc dữ liệu của bài toán mẫu.
3. Cung cấp mã nguồn mẫu bằng C# có thể biên dịch và thực thi trực tiếp.
4. Nhận xét, rút ra các quy tắc kỹ thuật và cảnh báo lỗi lập trình thường gặp.
5. Giao bài tập thực hành độc lập đi kèm gợi ý thuật giải chi tiết.

Bài tập và các tình huống ứng dụng

Hệ thống bài tập trong tài liệu được thiết kế đa tầng:

• Tầng cơ bản: Cài đặt các phép toán nguyên mẫu trên cấu trúc dữ liệu số nguyên (Fibonacci, chèn/xóa trên mảng, duyệt danh sách liên kết, thêm/lấy trên Stack và Queue).
• Tầng ứng dụng thuật toán: Xử lý biểu thức dấu ngoặc, đổi cơ số, sinh chuỗi nhị phân, tìm đường chéo ma trận, phân tích số tự nhiên, duyệt cây nhị phân.
• Tầng ứng dụng nghiệp vụ: Thiết kế chương trình quản lý thông tin đa thuộc tính (nhân viên, sinh viên, học sinh, tỉnh thành) với các thao tác lọc, đếm, tính toán thống kê và sắp xếp dữ liệu.

Đánh giá và hướng dẫn tự học

• Phương pháp đánh giá: Đánh giá năng lực của người học dựa trên độ chính xác của thuật toán cài đặt, khả năng xử lý đầy đủ các điều kiện dừng, trường hợp suy biến và kết quả chạy thử nghiệm trên các bộ dữ liệu kiểm thử (test cases).
• Chỉ dẫn tự học: Sinh viên cần chủ động gõ lại mã nguồn mẫu, dịch và chạy thử trên môi trường lập trình C# (như Microsoft Visual Studio), quan sát kết quả hiển thị trên Console, sau đó tự phát triển mã nguồn cho các bài tập thực hành dựa trên phần phân tích và thuật giải gợi ý.

---

Điểm nổi bật và cập nhật

Nền tảng công nghệ hiện đại

Tài liệu sử dụng ngôn ngữ lập trình C# trên nền tảng .NET Framework làm công cụ thực hành chính thức. C# là ngôn ngữ hướng đối tượng hiện đại, cung cấp cơ chế quản lý bộ nhớ tự động, cú pháp tường minh và hỗ trợ mạnh mẽ việc định nghĩa lớp (class), cấu trúc (struct), và xử lý biệt lệ (Exception), giúp sinh viên tiếp cận gần hơn với công nghệ phát triển phần mềm doanh nghiệp.

Tính trực quan trong mô tả giải thuật

Các giải thuật phức tạp đều được mô tả chi tiết bằng mã giả hoặc từng bước phân tích logic (ví dụ: giải thuật quay lui đệ quy sinh xâu nhị phân, giải thuật phân tích số $N$ thành tổng có sử dụng mảng lưu trạng thái, thuật toán đổi cơ số bằng Stack). Điều này giúp sinh viên hiểu rõ cơ chế vận hành bên dưới của bộ nhớ và ngăn xếp hệ thống (Call Stack).

Gắn liền với các bài toán quản lý thực tiễn

Thay vì chỉ dừng lại ở các bài toán số học đơn thuần, tài liệu tích hợp nhiều bài toán quản lý mang tính ứng dụng cao:

• Quản lý danh sách nhân viên công ty với các nghiệp vụ tính tổng thực lĩnh, tìm nhân viên lương thấp nhất, lọc mức thưởng $\ge 1.200.000$ VNĐ, sắp xếp theo phòng ban và mã nhân viên.
• Quản lý điểm học phần và xét điều kiện nhận học bổng của sinh viên theo hệ thống tín chỉ.
• Quản lý hồ sơ học sinh và tra cứu thông tin trên cây nhị phân tìm kiếm.

---

Đối tượng sử dụng giáo trình

Phân loại người học và điều kiện tiên quyết

• Sinh viên mục tiêu: Sinh viên năm thứ nhất và năm thứ hai trình độ Đại học chính quy thuộc các ngành Công nghệ thông tin, Kỹ thuật phần mềm, Khoa học máy tính tại Trường Đại học Sư phạm Kỹ thuật Hưng Yên và các trường đại học đào tạo khối ngành kỹ thuật, công nghệ.
• Kiến thức tiên quyết: Người học cần hoàn thành học phần Cơ sở lập trình hoặc Lập trình nâng cao, nắm vững cú pháp ngôn ngữ C# cơ bản (kiểu dữ liệu, cấu trúc rẽ nhánh if-else, switch-case, vòng lặp for, while, do-while, hàm và truyền tham số, mảng một chiều và hai chiều).

Ứng dụng đối với giảng viên và tài liệu tham khảo

• Giảng viên: Sử dụng làm tài liệu hướng dẫn thực hành chính thức tại phòng máy; làm khung tham chiếu để xây dựng ngân hàng đề thi thực hành, bài tập lớn và các bài kiểm tra đánh giá quá trình học phần CTDL&GT.
• Tự học và tham khảo: Phù hợp làm tài liệu ôn tập và củng cố kỹ năng lập trình giải thuật cho lập trình viên chuẩn bị tham gia các kỳ thi tuyển dụng kỹ sư phần mềm.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng nào?

Tài liệu được biên soạn phục vụ trực tiếp cho sinh viên đại học chính quy các ngành CNTT, KTPM, KHMT và người học cần tài liệu thực hành cài đặt cấu trúc dữ liệu và giải thuật bằng ngôn ngữ C#.

2. Cần chuẩn bị những kiến thức nền tảng nào trước khi học?

Người học cần có kiến thức về kỹ thuật lập trình cơ bản trong C#, bao gồm cú pháp câu lệnh điều khiển, hàm, cấu trúc mảng, kiểu bản ghi struct và khái niệm lớp đối tượng class.

3. Điểm khác biệt của tài liệu này so với các sách lý thuyết khác là gì?

Tài liệu tập trung hoàn toàn vào khía cạnh thực hành và cài đặt. Mỗi bài học đều có phân tích thuật giải, mã nguồn C# hoàn chỉnh, nhận xét kỹ thuật về bộ nhớ/tham số và hệ thống bài tập thực hành gắn với ứng dụng quản lý thực tế.

4. Làm thế nào để tự học và thực hành hiệu quả với tài liệu?

Người học nên đọc kỹ phần phân tích bài tập mẫu, tự cài đặt lại mã nguồn trên Visual Studio, kiểm tra các trường hợp biên, đọc phần nhận xét kỹ thuật và sau đó tự giải quyết các bài tập thực hành theo các gợi ý được cung cấp.

5. Tài liệu có cung cấp mã nguồn mẫu không?

Có. Toàn bộ các bài tập mẫu từ Bài 9 đến Bài 14 đều có lời giải mẫu bằng mã nguồn C# hoàn chỉnh, bao gồm cấu trúc lớp, các hàm thành phần và hàm Main thực thi chương trình.

---

Kết luận

Tài liệu "Bài Tập Thực Hành Học Phần: Cấu Trúc Dữ Liệu Và Giải Thuật" (Khoa CNTT – Trường Đại học Sư phạm Kỹ thuật Hưng Yên, 2021) cung cấp hệ thống bài thực hành có cấu trúc rõ ràng, tính ứng dụng cao và bám sát chương trình đào tạo đại học chính quy. Lộ trình thực hành được thiết kế từ giải thuật đệ quy, cấu trúc dữ liệu tuyến tính (mảng, danh sách liên kết, ngăn xếp, hàng đợi) đến cấu trúc phi tuyến (cây nhị phân, cây nhị phân tìm kiếm) và giải thuật sắp xếp. Học liệu là tài liệu hướng dẫn thực hành và tự học hữu ích, giúp sinh viên làm chủ kỹ năng tổ chức dữ liệu và lập trình giải thuật trên nền tảng C#.

Trích đoạn nội dung tài liệu

TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT HƯNG YÊN KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP THỰC HÀNH HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trình độ đào tạo : Đại học chính quy Ngành đào tạo : CNTT, KTPM, KHMT Hưng Yên, năm 2021 MỤC LỤC Bài 9: Thực hành cài đặt giải thuật đệ quy. 3 Bài 10: Thực hành cài đặt danh sách bằng mảng. 10 Bài 11: Thực hành cài đặt danh sách bằng danh sách liên kết đơn. 17 Bài 12: Thực hành cài đặt danh sách Stack, Queue.

23 Bài 13: Thực hành cài đặt cây nhị phân. 33 Bài 14: Thực hành cài đặt các giải thuật sắp xếp - tìm kiếm. 35 Bài tập thực hành môn CTDL&GT Trang 2 Bài 9: Thực hành cài đặt giải thuật đệ quy Mục tiêu: Sau khi học xong bài này người học có khả năng: - Cài đặt được giải thuật đệ qui theo yêu cầu của các bài toán. - Giải thích được trình tự máy tính thực hiện khi thực thi các chương trình đệ qui.

- Rèn luyện kỹ năng lập trình, tư duy logic Bài tập mẫu Bài 1: Hãy viết giải thuật đệ quy tính số fibonaci thứ n; biết rằng f(n)=1 nếu n=1, f(n)=0 nếu n=0, f(n) = f(n-1)+ f(n-2) nếu n>1 Phân tích Từ công thức tính số fibonaci thứ n mà bài toán đặt rat a nhận thấy. - Trường hợp suy biến của bài toán xảy ra khi n<2 ta có f(n) =n - Trường hợp đệ quy xảy ra khi n>1: F(n) = F(n-1) + F(n-2) Giải thuật đệ quy để tính số fibonaci thứ n: int F(n){ if(n<2) return n; else return F(n-1) + F(n-2); } Lời giải mẫu using System; class Exam{ // Hàm đệ qui tính số fibonaci thứ n public static int f(int n){ if(n<2) return n; else return f(n-1)+f(n-2); } // Chương trình chính public static void main() { Console.ReadKey(); } Nhận xét Khi viết giải thuật đệ quy cần xác định được lời giải của giải thuật ứng với 2 trường hợp: suy biến và trường hợp đệ qui Kết quả thực hiện chương trình Bài tập thực hành môn CTDL&GT Trang 3 Bài 2: Viết chương trình thực hiện in ra tất cả các xâu nhị phân có độ dài N. Phân tích Ta có thuật toán tổng quát cho bài toán quay lui đệ quy. PROCEDURE TÌM(K:INTEGER); KHAI BÁO CÁC BIẾN NẾU CẦN; BEGIN NẾU LÀ BƯỚC SAU BƯỚC CUỐI CÙNG THÌ HIỆN NGHIỆM NGƯỢC LẠI VÒNG LẶP CHẠY CÁC TRƯỜNG HỢP CÓ THỂ LẤY LÀM PHẦN TỬ CỦA NGHIỆM BEGIN THỬ CHỌN MỘT ĐỀ CỬ TRONG CÁC BƯỚC TÌM PHẦN TỬ CỦA NGHIỆM; NẾU ĐỀ CỬ THỎA MÃN THÌ BEGIN LƯU PHẦN TỬ VÀO NGHIỆM; GHI NHẬN TRẠNG THÁI MỚI CỦA BÀI TOÁN; TÌM(K+1); TRẢ LẠI TRẠNG THÁI CỦ CỦA BÀI TOÁN TRƯỚC LÚC CHỌN ĐỀ CỬ; END; END; END; Theo yêu cầu của bài toán ta có thuật giải cho bài toán : - Mảng luu để lưu giá trị của chuỗi nhị phân - Đầu tiên ta sẽ tìm giá trị gán cho bít k=1 của chuỗi (là 0 or 1), sau đó gọi đệ quy tìm giá trị gán cho bít k=2, ….

- Lời gọi đệ quy kết thúc khi k== n+1 (nghĩa là ta đã thực hiện gán được giá trị cho n bít) khi đó sẽ hiển thị ra kết quả của chuỗi nhị phân Bài tập thực hành môn CTDL&GT Trang 4 Lời giải mẫu using System; namespace VDDeQui { class DeQui { static int n, d = 0; static int[] luu; // Hien thi ket qua ra man hinh static void Xuat(int[] luu) { for (int i = 0; i < n; i++) Console.0/n Bài 4: Tính S(x, n) = xn Gợi ý: Ta xây dựng hàm LuyThua(X, N) để tính XN với N dương.