Bài Tập Thực Hành Môn Cấu Trúc Dữ Liệu & Giải Thuật - Trường Đại Học Duy Tân

Chuyên khảo phân tích Bài tập thực hành cấu trúc dữ liệu giải thuật, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Trường học: Trường Đại Học Duy Tân
• Đề tài: Bài Tập Thực Hành Cấu Trúc Dữ Liệu & Giải Thuật tại Trường Đại Học Duy Tân

Mục lục chi tiết

• 1. I. ĐỆ QUY
• 1.1. I. Lý thuyết
• 1.1.1. Khái niệm
• 1.1.2. Cấu trúc của giải thuật đệ quy
• 1.1.3. Xây dựng giải thuật đệ quy
• 1.2. B. BÀI TẬP LÝ THUYẾT
• 1.2.1. TRẮC NGHIỆM
• 1.2.2. TRẢ LỜI NGẮN
• 1.3. BÀI TẬP THỰC HÀNH
• 2. II. DANH SÁCH ĐẶC (MẢNG)
• 2.1. A. Định nghĩa danh sách
• 2.2. Định nghĩa danh sách đặc
• 2.3. Mảng
• 2.3.1. Mảng một chiều
• 2.3.2. Ma trận
• 2.4. Cấu trúc lưu trữ trên mảng một chiều
• 2.5. Một số thuật toán trên danh sách đặc
• 2.5.1. Duyệt mảng
• 2.5.2. Duyệt mảng để tìm kiếm
• 3. III. DANH SÁCH LIÊN KẾT
• 4. IV. NGĂN XẾP VÀ HÀNG ĐỢI
• 5. V. CÂY

Tóm tắt

I. Hướng Dẫn Bài Tập Cấu Trúc Dữ Liệu Giải Thuật Tại DTU

Môn học Cấu Trúc Dữ Liệu & Giải Thuật (mã môn học: CS316) là một trong những môn học nền tảng quan trọng nhất dành cho sinh viên ngành Công nghệ thông tin tại Trường Đại học Duy Tân. Môn học này cung cấp kiến thức cốt lõi về cách tổ chức, lưu trữ và truy xuất dữ liệu một cách hiệu quả. Theo Niklaus Wirth, mối quan hệ này được thể hiện qua công thức kinh điển: “Thuật toán + cấu trúc dữ liệu = chương trình”. Điều này nhấn mạnh rằng việc lựa chọn đúng cấu trúc dữ liệu là tiền đề để xây dựng các giải thuật tối ưu, tạo ra những chương trình máy tính mạnh mẽ và hiệu quả. Các bài tập thực hành Cấu Trúc Dữ Liệu & Giải Thuật được thiết kế để giúp sinh viên chuyển hóa lý thuyết thành kỹ năng lập trình thực tế. Chương trình học tập trung vào các khái niệm cơ bản nhưng thiết yếu như đệ quy, danh sách, ngăn xếp, hàng đợi và cây. Việc hoàn thành tốt các bài tập này không chỉ giúp sinh viên nắm vững kiến thức mà còn rèn luyện tư duy logic và khả năng giải quyết vấn đề phức tạp, chuẩn bị hành trang vững chắc cho các môn học chuyên ngành và sự nghiệp sau này.

1.1. Giới thiệu tổng quan về môn học CS316 tại Duy Tân

Môn học CS316 được xây dựng với 3 tín chỉ, bao gồm 2 tín chỉ lý thuyết và 1 tín chỉ thực hành, dành cho sinh viên các ngành Công nghệ phần mềm và Mạng máy tính. Mục tiêu chính là trang bị cho sinh viên kiến thức về các cấu trúc dữ liệu cơ bản và các giải thuật liên quan. Nội dung học phần đi từ các khái niệm cơ bản như kiểu dữ liệu trừu tượng, cách đánh giá độ phức tạp của giải thuật dựa trên thời gian và dung lượng bộ nhớ. Sinh viên sẽ học cách cài đặt và áp dụng các cấu trúc dữ liệu như mảng (danh sách đặc), danh sách liên kết, ngăn xếp (stack), và hàng đợi (queue). Việc hiểu rõ bản chất và ưu nhược điểm của từng loại cấu trúc dữ liệu giúp người học đưa ra lựa chọn phù hợp cho từng bài toán cụ thể. Tài liệu học tập của Đại học Duy Tân nhấn mạnh tầm quan trọng của việc thực hành để củng cố lý thuyết, đảm bảo sinh viên không chỉ hiểu mà còn có thể áp dụng thành thạo.

1.2. Vai trò của bài tập thực hành trong việc nắm vững kiến thức

Lý thuyết suông không đủ để tạo nên một lập trình viên giỏi. Các bài tập thực hành Cấu Trúc Dữ Liệu & Giải Thuật đóng vai trò là cầu nối thiết yếu giữa kiến thức trừu tượng và ứng dụng thực tiễn. Thông qua việc tự tay viết mã nguồn, gỡ lỗi và tối ưu hóa chương trình, sinh viên sẽ thấm nhuần các khái niệm đã học. Ví dụ, khi làm bài tập về đệ quy, sinh viên sẽ hiểu sâu sắc hơn về điểm dừng (phần neo) và các bước lặp lại (phần đệ quy). Tương tự, các bài tập về mảng giúp sinh viên làm quen với thao tác duyệt, tìm kiếm, sắp xếp trên một cấu trúc dữ liệu tuyến tính. Quá trình thực hành liên tục này giúp xây dựng tư duy thuật toán, một kỹ năng mềm cực kỳ quan trọng giúp giải quyết các vấn đề một cách có hệ thống và logic. Đây là nền tảng không thể thiếu để tiếp cận các lĩnh vực nâng cao hơn như trí tuệ nhân tạo, khoa học dữ liệu hay phát triển phần mềm quy mô lớn.

II. Thách Thức Khi Giải Bài Tập Đệ Quy Trong Cấu Trúc Dữ Liệu

Đệ quy là một trong những khái niệm gây nhiều khó khăn nhất cho sinh viên khi bắt đầu học về Cấu Trúc Dữ Liệu & Giải Thuật. Về bản chất, một đối tượng được gọi là đệ quy nếu nó được định nghĩa thông qua chính nó. Tài liệu của Đại học Duy Tân định nghĩa: “Nếu 1 lời giải của bài toán P được thực hiện bằng lời giải của 1 hay nhiều của bài toán P’ nhỏ hơn có dạng giống như P thì đó là một lời giải đệ quy”. Thách thức lớn nhất nằm ở việc thay đổi tư duy từ lập trình tuần tự, lặp theo vòng lặp (for, while) sang tư duy phân rã bài toán lớn thành các bài toán con giống hệt. Sinh viên thường gặp khó khăn trong việc xác định đúng “phần neo” (trường hợp suy biến) – điều kiện để dừng lời gọi đệ quy. Nếu thiếu hoặc xác định sai phần neo, chương trình sẽ rơi vào vòng lặp vô hạn và gây ra lỗi tràn bộ nhớ stack (stack overflow). Việc theo dõi luồng thực thi của một hàm đệ quy cũng phức tạp hơn nhiều so với một vòng lặp thông thường.

2.1. Khó khăn trong việc xác định trường hợp suy biến phần neo

Trường hợp suy biến, hay phần neo, là thành phần cốt lõi quyết định sự thành bại của một giải thuật đệ quy. Đây là điểm dừng của thuật toán, nơi bài toán có thể được giải quyết trực tiếp mà không cần gọi lại chính nó. Một lỗi phổ biến là thiết kế một hàm đệ quy mà không có trường hợp suy biến rõ ràng hoặc trường hợp đó không bao giờ đạt được. Ví dụ, trong bài toán tính giai thừa n!, nếu không xác định điều kiện dừng là n = 0 thì n! sẽ tiếp tục gọi (n-1)! với các giá trị âm, dẫn đến lặp vô hạn. Các bài tập thực hành tại Đại học Duy Tân như tính x^y hay đếm số chữ số của một số nguyên dương đều nhấn mạnh tầm quan trọng của việc xác định đúng phần neo ngay từ bước đầu tiên. Sinh viên cần rèn luyện kỹ năng phân tích bài toán để tìm ra trường hợp đơn giản nhất, từ đó xây dựng logic cho phần đệ quy một cách chính xác.

2.2. Lỗi tràn bộ nhớ Stack Overflow và cách nhận biết

Mỗi khi một hàm được gọi, một không gian bộ nhớ trên vùng nhớ stack sẽ được cấp phát để lưu trữ các biến cục bộ và địa chỉ trả về. Với giải thuật đệ quy, mỗi lần hàm tự gọi lại chính nó, một frame mới lại được đẩy vào stack. Nếu phần neo không được xác định đúng, hoặc nếu độ sâu của đệ quy quá lớn (ví dụ: tính Fibonacci F(n) với n rất lớn bằng phương pháp đệ quy thông thường), stack sẽ bị lấp đầy và gây ra lỗi tràn bộ nhớ (Stack Overflow). Đây là một lỗi nghiêm trọng khiến chương trình bị dừng đột ngột. Để tránh lỗi này, sinh viên cần đảm bảo rằng mỗi bước đệ quy đều đưa bài toán tiến gần hơn đến trường hợp suy biến. Ngoài ra, cần cân nhắc sử dụng các kỹ thuật khác như đệ quy có nhớ (memoization) hoặc khử đệ quy bằng cách sử dụng vòng lặp và cấu trúc dữ liệu như ngăn xếp để giải quyết các bài toán có độ sâu đệ quy lớn, tối ưu hóa cả về bộ nhớ và thời gian thực thi.

III. Phương Pháp Giải Bài Tập Đệ Quy Cốt Lõi Của Giải Thuật

Để chinh phục các bài tập thực hành Cấu Trúc Dữ Liệu & Giải Thuật liên quan đến đệ quy, sinh viên cần tuân thủ một phương pháp tiếp cận có hệ thống. Tài liệu hướng dẫn của Đại học Duy Tân đề xuất một quy trình ba bước rõ ràng để xây dựng một hàm đệ quy. Việc áp dụng đúng quy trình này giúp biến một khái niệm trừu tượng thành một giải thuật cụ thể, có thể cài đặt được. Bước đầu tiên và quan trọng nhất là phải hiểu rõ bài toán, xác định chính xác đầu vào (input) và đầu ra (output) mong muốn. Điều này giúp định hình cấu trúc của hàm, bao gồm tên hàm và các tham số cần thiết. Một khi đã có khung sườn, trọng tâm sẽ chuyển sang việc xác định hai thành phần không thể thiếu của mọi giải thuật đệ quy: phần neo và phần đệ quy. Nắm vững phương pháp này là chìa khóa để giải quyết không chỉ các bài tập trong chương trình mà còn nhiều vấn đề phức tạp trong thực tế.

3.1. Quy trình 3 bước xây dựng một giải thuật đệ quy hiệu quả

Tài liệu môn học CS316 trình bày một phương pháp luận chặt chẽ để cài đặt giải thuật đệ quy. Bước 1: Xác định mục đích và tiêu đề hàm. Cần làm rõ hàm sẽ làm gì, nhận vào tham số nào và trả về kết quả gì. Ví dụ, hàm tính tổng các chữ số của số nguyên N sẽ nhận vào N và trả về một số nguyên là tổng. Bước 2: Xác định trường hợp suy biến (neo). Đây là trường hợp đơn giản nhất mà lời giải có thể được đưa ra ngay lập tức. Với bài toán trên, khi N = 0, tổng các chữ số là 0. Đây chính là điểm dừng. Bước 3: Xây dựng trường hợp chung (phần đệ quy). Bước này phân tích cách đưa bài toán về một dạng tương tự nhưng với dữ liệu nhỏ hơn. Tổng các chữ số của N bằng chữ số hàng đơn vị (N % 10) cộng với tổng các chữ số của phần còn lại (N / 10). Tức là Tong(N) = (N % 10) + Tong(N / 10). Việc tuân thủ ba bước này giúp cấu trúc hóa tư duy và giảm thiểu lỗi logic khi lập trình.

3.2. Ví dụ minh họa Bài tập đảo ngược số nguyên dương

Một ví dụ điển hình trong bộ bài tập thực hành là đảo ngược một số nguyên dương. Áp dụng quy trình 3 bước: Bước 1: Mục đích là xuất đảo ngược số n, vậy hàm có thể là void xuat_dao_so(int n). Bước 2: Phần neo là khi không còn gì để xuất, tức là khi n <= 0, hàm sẽ dừng lại. Bước 3: Phần đệ quy là xử lý trường hợp chung n > 0. Để đảo ngược số, ta cần lấy chữ số cuối cùng ra trước, sau đó xử lý phần còn lại. Chữ số cuối cùng là n % 10. Phần còn lại là n / 10. Do đó, giải thuật sẽ là: in ra n % 10, sau đó gọi đệ quy xuat_dao_so(n / 10). Với n = 123, hàm sẽ in ra 3, sau đó gọi xuat_dao_so(12). Lần gọi tiếp theo in ra 2, gọi xuat_dao_so(1). Cuối cùng in ra 1, gọi xuat_dao_so(0) và kết thúc. Kỹ thuật này thể hiện sức mạnh của đệ quy trong việc giải quyết các bài toán một cách thanh lịch và ngắn gọn.

IV. Bí Quyết Xử Lý Danh Sách Đặc Và Mảng Trong Lập Trình

Danh sách đặc, thường được cài đặt bằng cấu trúc mảng, là một trong những cấu trúc dữ liệu cơ bản và được sử dụng rộng rãi nhất. Tài liệu học tập của Đại học Duy Tân định nghĩa danh sách đặc là một danh sách mà các phần tử được sắp xếp kế tiếp nhau trong bộ nhớ. Đặc điểm này cho phép truy cập trực tiếp vào bất kỳ phần tử nào thông qua chỉ số của nó, với độ phức tạp thời gian là O(1), rất hiệu quả. Tuy nhiên, chính vì tính liên tục trong bộ nhớ mà việc chèn hoặc xóa một phần tử ở giữa mảng trở nên tốn kém, đòi hỏi phải dịch chuyển các phần tử còn lại. Hiểu rõ bản chất lưu trữ và các phép toán cơ bản trên mảng là nền tảng để giải quyết các bài tập thực hành Cấu Trúc Dữ Liệu & Giải Thuật. Các thuật toán phổ biến như duyệt mảng, tìm kiếm, và sắp xếp đều được xây dựng dựa trên cấu trúc này, và việc nắm vững chúng là yêu cầu bắt buộc đối với mọi lập trình viên.

4.1. Cấu trúc lưu trữ và cách truy cập phần tử trong mảng

Mảng là một tập hợp các phần tử cùng kiểu dữ liệu, được lưu trữ trong các ô nhớ liên tiếp. Địa chỉ của phần tử đầu tiên, V[0] hoặc V[1] tùy ngôn ngữ, được gọi là địa chỉ gốc (base address), ký hiệu L0. Nhờ tính chất này, địa chỉ của bất kỳ phần tử thứ i nào cũng có thể được tính toán nhanh chóng. Công thức tính địa chỉ của phần tử a[i] là: LOC(a[i]) = L0 + m * (i-1) (với giả định chỉ số bắt đầu từ 1 và m là kích thước của một phần tử). Chính khả năng tính toán địa chỉ trực tiếp này giúp cho việc truy cập ngẫu nhiên (random access) vào mảng cực kỳ nhanh chóng. Sinh viên cần hiểu rõ cơ chế này để lý giải tại sao việc truy cập a[1000] không tốn nhiều thời gian hơn a[1]. Đây là một ưu điểm vượt trội của danh sách đặc so với các cấu trúc dữ liệu khác như danh sách liên kết.

4.2. Các thuật toán tìm kiếm cơ bản Tìm kiếm tuyến tính và nhị phân

Tìm kiếm là một trong những thao tác phổ biến nhất trên mảng. Hai giải thuật cơ bản thường được giới thiệu trong các bài tập thực hành là tìm kiếm tuyến tính (Linear Search) và tìm kiếm nhị phân (Binary Search). Tìm kiếm tuyến tính là phương pháp đơn giản nhất: duyệt qua từng phần tử của mảng từ đầu đến cuối để so sánh với giá trị cần tìm. Giải thuật này hoạt động trên mọi mảng nhưng có độ phức tạp O(n) trong trường hợp xấu nhất. Ngược lại, tìm kiếm nhị phân hiệu quả hơn rất nhiều với độ phức tạp O(log n), nhưng yêu cầu mảng phải được sắp xếp trước. Giải thuật này hoạt động bằng cách liên tục chia đôi không gian tìm kiếm: so sánh giá trị cần tìm với phần tử ở giữa, nếu không khớp thì loại bỏ một nửa mảng và lặp lại quy trình trên nửa còn lại. Việc lựa chọn giữa hai thuật toán này phụ thuộc vào trạng thái của dữ liệu (đã sắp xếp hay chưa) và tần suất thực hiện thao tác tìm kiếm.

V. Ứng Dụng Thực Tiễn Qua Bài Tập Nâng Cao Tại Đại Học Duy Tân

Sau khi nắm vững các khái niệm cơ bản về đệ quy và mảng, chương trình Cấu Trúc Dữ Liệu & Giải Thuật tại Đại học Duy Tân tiếp tục giới thiệu các bài toán kinh điển để sinh viên áp dụng kiến thức một cách tổng hợp. Các bài toán như tìm số Fibonacci hay bài toán Tháp Hà Nội không chỉ là những bài tập lập trình đơn thuần. Chúng là những ví dụ xuất sắc minh họa cho sức mạnh của tư duy thuật toán và tầm quan trọng của việc lựa chọn đúng phương pháp tiếp cận. Việc giải quyết những bài toán này đòi hỏi sinh viên phải phân tích sâu sắc cấu trúc của vấn đề, nhận diện các mẫu lặp lại và áp dụng giải thuật đệ quy một cách khéo léo. Qua đó, sinh viên không chỉ cải thiện kỹ năng viết mã mà còn phát triển khả năng phân tích và thiết kế giải pháp, những kỹ năng quan trọng cho sự nghiệp kỹ sư phần mềm trong tương lai. Đây là bước đệm để tiếp cận các cấu trúc dữ liệu phức tạp hơn như cây, đồ thị.

5.1. Phân tích bài toán Fibonacci Giải pháp đệ quy và khử đệ quy

Dãy số Fibonacci là một chủ đề quen thuộc trong các bài tập thực hành. Dãy được định nghĩa: F(n) = F(n-1) + F(n-2) với F(1)=F(2)=1. Cách cài đặt tự nhiên nhất là sử dụng giải thuật đệ quy trực tiếp theo định nghĩa. Tuy nhiên, giải pháp này không hiệu quả vì nó tính toán lại các giá trị F(k) nhiều lần, dẫn đến độ phức tạp thời gian theo cấp số mũ. Để tối ưu, tài liệu hướng dẫn đề xuất phương pháp khử đệ quy. Thay vì gọi đệ quy, ta có thể sử dụng một vòng lặp và ba biến phụ để tính toán các số Fibonacci một cách tuần tự. Phương pháp này chỉ cần một lần duyệt, giảm độ phức tạp xuống còn O(n) và không gây ra lỗi tràn bộ nhớ stack. Bài toán này dạy cho sinh viên một bài học quan trọng: một giải pháp trông có vẻ “thanh lịch” không phải lúc nào cũng là giải pháp hiệu quả nhất. Việc phân tích độ phức tạp của giải thuật là kỹ năng thiết yếu để đánh giá và lựa chọn giải pháp tối ưu.

5.2. Giải mã bài toán Tháp Hà Nội bằng tư duy đệ quy

Bài toán Tháp Hà Nội là một ví dụ kinh điển về vẻ đẹp và sức mạnh của đệ quy. Yêu cầu là chuyển n đĩa từ cọc A sang cọc C, sử dụng cọc B làm trung gian, với quy tắc đĩa lớn không được đặt trên đĩa nhỏ. Nếu giải bằng phương pháp lặp thông thường, bài toán sẽ trở nên vô cùng phức tạp. Tuy nhiên, với tư duy đệ quy, lời giải lại rất đơn giản và sáng sủa. Để chuyển n đĩa từ A sang C, ta thực hiện 3 bước: 1. Chuyển n-1 đĩa từ A sang B (lấy C làm trung gian) – đây là một bài toán con đệ quy. 2. Chuyển đĩa thứ n (lớn nhất) từ A sang C. 3. Chuyển n-1 đĩa từ B sang C (lấy A làm trung gian) – đây lại là một bài toán con đệ quy khác. Phần neo của bài toán là khi chỉ còn 1 đĩa, ta chỉ việc di chuyển nó trực tiếp. Lời giải này cho thấy đệ quy có thể biến một vấn đề phức tạp thành một chuỗi các bước logic, dễ hiểu và dễ cài đặt.

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

TRƯỜNG ĐẠI HỌC DUY TÂN KHOA CÔNG NGHỆ THÔNG TIN BÀI TẬP THỰC HÀNH Môn học: Cấu Trúc Dữ Liệu & Giải Thuật Mã môn học: CS316 Số tín chỉ: 3 Lý thuyết: 2 Thực hành: 1 Dành cho sinh viên ngành: Công nghệ phần mềm, mạng máy tính, cao đẳng tin Khoa: Công nghệ thông tin Bậc đào tạo: Đại học – Cao đẳng Học kỳ: 1 Năm học: 2017-2018 Đà Nẵng, tháng 8 năm 2017 NỘI DUNG THỰC HÀNH  Đệ quy - Danh sách đặt (mảng) - Danh sách liên kết - Ngăn xếp và hàng đợi - Cây I. Lý thuyết Khái niệm: Nếu 1 lời giải của bài toán P được thực hiện bằng lời giải của 1 hay nhiều của bài toán P’nhỏ hơn có dạng giống như P thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy. Cấu trúc của giải thuật đệ quy Một giải thuật đệ quy bao giờ cũng gồm 2 phần  Phần neo: Xác định điểm kết thúc của một giải thuật đệ quy.

Trường hợp này còn được gọi là trường hợp suy biến. Nếu một giải thuật đệ quy không có trường hợp suy biến thì sẽ dẫn đến lặp vô hạn và sinh lỗi khi thi hành.  Phần đệ quy: Phân tích và xây dựng trường hợp chung của bài toán (có nghĩa là đưa bài toán về bài toán cùng loại nhưng với dữ liệu nhỏ hơn). Xây dựng giải thuật đệ quy Khi cài đặt thuật toán đệ quy ta tiến hành những bước sau:  Bước 1: Xác định mục đích, đầu vào và đầu ra để từ đó xác định tên tiêu đề hàm (tên hàm và tham số hình thức của nó)  Bước 2: Xác định trường hợp suy biến (neo) Nguyễễn Minh Nhậ t Trang 1  Bước 3: Phân tích và xây dựng trường hợp chung của bài toán (phần đệ quy).

Có nghĩa là đưa bài toán về bài toán cùng loại nhưng với dữ liệu nhỏ hơn. Từ 3 bước trên, áp dụng nguyên tắc viết ngôn ngữ ta xây dựng được hàm đệ qui (thông thường sử dụng toán tử điều kiện (if…else) để viết hàm đệ quy. y y Ví dụ 1: Tính x với x được định nghĩa như sau:  x y  1x* xy1 khi y 0 khi y 0  Bước 1: Xác định tham số đầu vào là x và y, tham số đầu ra là xy. Ta luôn nhận được giá trị xy duy nhất, do đó ta sử dụng hàm có kiểu trả về.

 Bước 2: Phần neo: y=0 thì tổng x0 = 1  Bước 3: Phần đệ quy: là trường hợp thực hiện lại bài toán với giá trị nhỏ hơn y = y - 1. Tức là ứng với trường hợp thực hiện lại lời gọi cũng đều có chung tham số đầu vào là y nhưng với giá trị nhỏ hơn y = y – 1 và đều có khuynh hướng đến trường hợp suy biến y = 0. Giải thuật float x_mu_y (float x, int y) { if(y==0) return 1; else return x*x_mu_y(x,y-1); //gọi đệ quy x_mu_y(x,y-1) tính xy-1 } Ví dụ 2: Đếm số chữ số của số nguyên dương N. Ví dụ N = 152 có 3 chữ số  Bước 1: Xác đinh tham số đầu vào là n, tham số đầu ra là số chữ số của n.

Sử dụng hàm có kiểu trả về vì bài toán này trả về một giá trị duy nhất là số chữ số của n.  Bước 2: Phần neo: n = 0 thì số chữ số bằng 0.  Bước 3: Phần đệ quy: 0nếu n = 0 F(N) = 1 + F(N/10)nếu n > 0 Nguyễễn Minh Nhậ t Trang 2 Hàm đệ quy như sau: int dem(long n) { if(n==0) return 0; else return (1+ dem(n/10)); } //gọi đệ quy dem(n/10) để bớt đi số hàng đơn vị 1 Ví dụ 3: Xuất đảo ngược một số nguyên dương ra màn hình DS(1234) 2 Mod 10 Div 10 DS(123) 3 Màn hình4 Div 10 Mod 10 DS(12) 4 3 Mod 10 Div 10 DS(1) 5 2 Mod 10 Div 10 DS(0) suy biến 6 1 bbbbbbbiến,dừng 7 Giải thuật: 8 void xuat_dao_so(int n) 9 { if (n >0) 10 {cout<< n % 10; 11 xuat_dao_so(n / 10); //gọi đệ quy xuat_dao_so(n/10) để bớt đi số hàng đơn vị 12 } } B. BÀI TẬP LÝ THUYẾT  TRẮC NGHIỆM Nguyễễn Minh Nhậ t Trang 3 1.2 point) Theo cách tiếp cận của lập trình có cấu trúc, NiklausWirth đưa ra công thức thể hiện được mối liên hệ giữa cấu trúc dữ liệu và giải thuật như sau: *A.

Thuật toán + cấu trúc dữ liệu = chương trình B. Thuật toán + dữ liệu đầu vào = chương trình C. Kỹ thuật lập trình + cấu trúc dữ liệu = Kết quả đầu ra. Tất cả đều đúng 2.2 point) Chọn phát biểu đúng nhất *A.

Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái niệm về chính nó. Một chương trình gọi là đệ quy nếu trong chương trình có lời gọi đến một chương trình đệ quy khác. Một chương trình đệ quy là chương trình lặp đi lặp lại với số lần lặp không biết trước. Một chương trình đề quy là chương trình có chưa hàm main.2 point) Chọn phát biểu đúng nhất D.

Nếu một lời giải của bài toán P được thực hiện bằng lời giải của bài toán P’, có dạng giống như P thì đó là một lời giải đệ quy B. Giải thuật tương ứng với lời giải đệ quy gọi là giải thuật đệ quy C. Nếu giải thuật đệ quy được viết dưới dạng một thủ tục thì thủ tục ấy được gọi là thủ tục đệ quy. Tất cả đều đúng 4.2 point) Trong giải thuật đệ quy thành phần dừng là: A.

Thành phần neo của thuật toán. Xác định điểm dừng của thuật toán C. Thành phần không chứa khái niệm trong định nghĩa. Tất cả đều đúng 5.2 point) Nguyễễn Minh Nhậ t Trang 4 Giải thuật là … câu lênh chặt chẽ, rõ ràng và xác định các thao tác trên các đối tượng dữ liệu A.2 point) Sau một số ---- bước thưc hiện giải thuật cho chúng ta đạt được kết qua mong muốn A.2 point) Đánh giá độ phức tạp của giải thuật là việc xác định ……và…… mà giải thuật cần để thưc hiện giải một bài toán A, Khoảng thời gian, độ khó B.

Khoảng thời gian, độ phức tạp *C. Khoảng thời gian, dung lượng bộ nhớ máy tính D. Độ khó, dung lượng bộ nhớ máy tính 8.2 point) Các kiểu dữ liệu cơ bản là…… A. Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ máy tính B.

Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ tự nhiên *C. Các kiểu dữ liệu mà người lập trình được cung cấp sẵn từ ngôn ngữ lập trình D. Các kiểu dữ liệu mà người lập trìn được cung cấp sẵn từ ngôn ngữ này 9.2 point) Chỉ ra kiểu dữ liệu cơ bản: A. Hoten Nguyễễn Minh Nhậ t Trang 5 D.2 point) Chỉ ra kiểu dữ liệu không cơ bản A.2 point) Kiểu dữ liệu trừu tượng là….

Kiểu dữ liệu mà người lập trình tự xây dựng không dựa trên kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình B. Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên kiểu dữ liệu không cơ bản được cung cấp từ ngôn ngữ lập trình C. Kiểu dữ liệu mà người lập trình phải tự xây dựng dựa trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ này. *D Kiểu dữ liệu mà người lập trình phải tự xây dựng trên các kiểu dữ liệu cơ bản được cung cấp từ ngôn ngữ lập trình 12.2 point) Kiểu dữ liệu trừu tượng là kiểu nào sau đây: A.2 point) Kiểu dữ liệu cơ bản là kiểu nào sau đây A.

FILE Nguyễễn Minh Nhậ t Trang 6 14.2 point) Chọn đáp án đúng nhất A. Câu trúc dữ liệu cách lưu trữ dữ liệu trong bộ nhớ máy tình (ROM), sao cho nó có thể được sử dụng một cách hiệu quả. Câu trúc dữ liệu cách lưu trữ dữ liệu trong bộ nhớ máy tình (RAM), sao cho nó có thể được sử dụng một cách hiệu quả. Câu trúc dữ liệu cách lưu trữ dữ liệu trong bộ nhớ máy tình (HDD), sao cho nó có thể được sử dụng một cách hiệu quả.

Câu trúc dữ liệu cách lưu trữ dữ liệu trong bộ nhớ máy tình (USB), sao cho nó có thể được sử dụng một cách hiệu quả.2 point) Cho hàm sau: int A(int n){if(n==0) return 0; return n+A(n-1);}. Với n=3 hàm trả về giá trị nào sau đây: A.2 point) Cho hàm sau: int A(int n){if(n==0) return 0; return n*A(n-1);}. Với n=3 hàm trả về giá trị nào sau đây: A.2 point) Cho hàm sau: int A(int n,int m=0){if(n==0) return m; return A(n/10,m*10+n %10);}. Với lời gọi cout<<A(1200) nhận được kết quả nào sau đây: *A.

0021 Nguyễễn Minh Nhậ t Trang 7 C.2 point) Cho hàm sau: int A(int n,int m=0){if(n==0) return m; return A(n/10,m*10+n %10)}. Với lời gọi cout<<A(1200) nhận được kết quả nào sau đây: A.2 point) Cho hàm sau: int B(int n){if(n>0){B(n/10);cout<<n%10<<"\t";}} Với lời gọi cout<<B(102) nhận được kết quả nào sau đây: A.2 point) Chọn phát biểu đúng A. Một đối tượng được gọi là đệ quy, nếu nó không được mô tả thông qua định nghĩa của chính nó. Một đối tượng được gọi là đệ quy, nếu nó được mô tả thông qua định nghĩa của đối tượng khác.

Một đối tượng được gọi là đệ quy, nếu nó được mô tả thông qua định nghĩa của chính nó. Đối tượng đệ quy được định nghĩa bằng những khái niệm đơn giản nhất cùng dạng với nó.2 point) Cho hàm sau: int B(int n){if(n>0){ cout<<n%10<<"\t";B(n/10); }} Với lời gọi cout<<B(102) nhận được kết quả nào sau đây: A. 201 Nguyễễn Minh Nhậ t Trang 8 B.2 point) Cho hàm sau: int B(int n){if(n>0){B(n/2);cout<<n%2<<"\t";}}Với lời gọi cout<<B(10) nhận được kết quả nào sau đây: *A.2 point) Cho hàm sau: int B(int n){if(n>0){ cout<<n%2<<"\t";B(n/2); }}Với lời gọi cout<<B(10) nhận được kết quả nào sau đây: A.2 point) Cho hàm sau: int B(int A[],int n){if(n>0){cout<<A[n]<<"\t";B(A,n/2);}}. Cho A[]={1,2,3,4,5} Với lời gọi B(A,4) nhận được kết quả nào sau đây: *A.2 point) Cho hàm sau: int B(int A[],int n){if(n==0) return 0; return (A[n]+B(A,n-1));} Cho A[]={1,2,3,4,5} Với lời gọi cout<<B(A,4) nhận được kết quả nào sau đây: A.

13 Nguyễễn Minh Nhậ t Trang 9 D. 12  TRẢ LỜI NGẮN 1: Cấu trúc dữ liệu là gì? Cấu trúc dữ liệu khác cấu trúc lưu trữ ở những điểm nào? 2: Nêu khái niệm giải thuật là gì? Mối quan hệ giữa giải thuật và cấu trúc dữ liệu là gì? Nêu các tính chất của giải thuật 3: Một ngôn ngữ lập trình có nên cho phép người sử dụng tự định nghĩa thêm các kiểu dữ liệu có cấu trúc? Giải thích và cho ví dụ. BÀI TẬP THỰC HÀNH 1: Hãy viết mỗi yêu cầu sau bằng giải thuật đệ qui: a. Đổi số n hệ 10 sang hệ nhị phân (chỉ sử dụng đệ qui) d.

Tìm số đảo ngược 1 số nguyên dương.