Bài tập cấu trúc dữ liệu và giải thuật 2 năm 2024

Với các sinh viên chuyên nghành tin học thì cụm từ Cấu trúc dữ liệu (Data Structure) không còn là xa lạ. Đây là một môn học bắt buộc và sẽ là thực sự khó cho bất kỳ sinh viên nào nếu không có sự chuẩn bị kỹ lưỡng và dành cách tiếp cận tích cực cho môn học này. Vậy Cấu trúc dữ liệu là gì?

Cấu trúc dữ liệu là cách lưu trữ, tổ chức dữ liệu có thứ tự, có hệ thống để dữ liệu có thể được sử dụng một cách hiệu quả.

Dưới đây là danh sách các bài hướng dẫn trong loạt bài Cấu trúc dữ liệu và Giải thuật:

Cấu trúc dữ liệu và giải thuật

Cấu trúc dữ liệu là gì?

• Cấu trúc dữ liệu là gì ?
• Cài đặt môi trường

Một số khái niệm về Giải thuật

• Giải thuật là gì ?
• Giải thuật tiệm cận - Asymptotic Algorithms
• Giải thuật tham lam - Greedy Algorithms
• Giải thuật chia để trị - Divide and Conquer
• Giải thuật qui hoạch động - Dynamic Programming
• Giải thuật định lý thợ - Master Theorem

Quảng cáo

Cấu trúc dữ liệu mảng (Array)

• Cấu trúc dữ liệu mảng (Array)

Danh sách liên kết - Linked List

• Danh sách liên kết - Linked List
• Danh sách liên kết đôi - Doubly Linked List
• Danh sách liên kết vòng - Circular Linked List

Ngăn xếp & Hàng đợi

• Cấu trúc dữ liệu ngăn xếp - Stack
• Cấu trúc dữ liệu hàng đợi - Queue

Một số Giải thuật tìm kiếm

• Tìm kiếm tuyến tính - Linear Search
• Tìm kiếm nhị phân - Binary Search
• Tìm kiếm nội suy - Interpolation Search
• Cấu trúc dữ liệu Hash Table

Quảng cáo

Một số Giải thuật sắp xếp

• Giải thuật sắp xếp
• Sắp xếp nổi bọt - Bubble Sort
• Sắp xếp chèn - Insertion Sort
• Sắp xếp chọn - Selection Sort
• Sắp xếp trộn - Merge Sort
• Giải thuật Shell Sort
• Sắp xếp nhanh - Quick Sort
• Quay lui - Back Tracking

Cấu trúc dữ liệu đồ thị (Graph)

• Cấu trúc dữ liệu đồ thị
• Tìm kiếm theo chiều sâu - Depth First Traversal
• Tìm kiếm theo chiều rộng - Breadth First Traversal

Cấu trúc dữ liệu cây

• Cấu trúc dữ liệu cây
• Duyệt cây - Tree Traversal
• Cây tìm kiếm nhị phân - Binary Search Tree
• Cây AVL - AVL Tree
• Cây Slay - splay Tree
• Giải thuật Cây khung - Spanning Tree
• Cấu trúc dữ liệu Heap

Đệ qui (Recursion)

• Khái niệm cơ bản về Đệ qui
• Bài toán Tháp Hà Nội - Tower of Hanoi
• Dãy Fibonacci

  Loạt bài Cấu trúc dữ liệu và Giải thuật được viết dựa trên nguồn tài liệu nước ngoài cùng với tìm hiểu một số nguồn tài liệu khác cộng với sự hiểu biết của bản thân về Cấu trúc dữ liệu và giải thuật, do đó không tránh khỏi một số thiếu sót. Nếu bạn đọc hay độc giả có bất kỳ ý kiến đóng góp nào thì mong các bạn comment ngay phần dưới trang để bọn mình kịp thời sửa chữa để có thể cung cấp cho các bạn loạt bài hướng dẫn Cấu trúc dữ liệu và Giải thuật hoàn thiện nhất.

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS.

Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

Cho hai đa thức A bậc n và đa thức B bậc m được ghi lại tương ứng trong file dathuc1.in và dathuc2.in theo khuôn dạng sau:

• Dòng đầu tiên ghi lại số tự nhiên K là số các số hạng của đa thức;
• K dòng kế tiếp, mỗi dòng ghi lại hệ số và số mũ của số hạng hạng đa thức.

Hãy viết chương trình tính hiệu hai đa thức A và B và ghi lại đa thức kết quả vào file ketqua.out theo khuôn dạng như trên. Ví dụ với đa thức

Hôm nay mình sẽ hướng dẫn các bạn giải quyết một bài toán cấu trúc dữ liệu và giải thuật, đồng thời cũng chia sẻ source code luôn nhé! Đây là một bài tập cấu trúc dữ liệu và giải thuật tổng hợp bao gồm nhiều cấu trúc dữ liệu và giải thuật khác nhau được sử dụng trong 1 bài tập. Hi vọng các bạn có những kiến thức thật bổ ích.

Chúng ta sẽ áp dụng cấu trúc dữ liệu & giải thuật để giải bài tập Xây dựng phần mềm thi trắc nghiệm. Ta sẽ tổ chức các danh sách cho bài tập cấu trúc dữ liệu và giải thuật này như sau:

– Danh sách môn học : cây nhị phân tìm kiếm (MAMH (C15), TENMH).

– Danh sách Lop : mảng con trỏ có tối đa 500 lớp(MALOP, TENLOP, con trỏ dssv): con trỏ dssv trỏ đến danh sách sinh viên thuộc lớp đó. – Danh sách sinh viên : danh sách liên kết đơn (MASV, HO, TEN, PHAI, password, con trỏ): con trỏ sẽ trỏ đến điểm các môn đã thi trắc nghiệm.

– Danh sách Điểm thi (danh sách liên kết đơn) (Mamh, Diem)

– Danh sách Câu hỏi thi : chứa các câu hỏi nguồn của các môn học (Id, Mă MH, Nội dung, A, B, C, D, Đáp án); trong đó A, B, C, D là 4 chọn lựa tương ứng với nội dung câu hỏi. Danh sách câu hỏi thi là 1 mảng con trỏ có tối đa 2000 câu, và luôn có sắn thứ tự theo mã môn học.

Chương trình có các chức năng sau :

a/ Đăng nhập dựa vào mã sinh viên, password. Nếu tài khoản đăng nhập là GV, pass là GV thì sẽ có toàn quyền.

b/ Nhập lớp.

c/ In danh sách lớp.

d/ Nhập sinh viên của lớp : nhập vào mã lớp trước, sau đó nhập các sinh viên vào lớp đó.

e/ Nhập môn học: cho phép cập nhật (thêm / xóa / hiệu chỉnh ) thông tin của môn học.

f/ Nhập câu hỏi thi (Id là số ngẫu nhiên do chương trình tự tạo ).

g/ Thi Trắc nghiệm ( trước khi thi hỏi người thi môn thi, số câu hỏi thi, số phút thi-sau đó lấy ngẫu nhiên các câu hỏi trong danh sách câu hỏi thi của môn.

h/ In chi tiết các câu hỏi đã thi 1 môn học của 1 sinh viên.

i/ In bảng điểm thi trắc nghiệm môn học của 1 lớp (nếu có sinh viên chưa thi thì ghi “Chưa thi”.

Lưu ý: Chương trình cho phép lưu các danh sách vào file; Kiểm tra các điều kiện làm dữ liệu bị sai. Có thể tự thiết kế thêm danh sách để đáp ứng yêu cầu của đề tài.

Hướng dẫn giải bài tập

Bài tập cấu trúc dữ liệu và giải thuật này sử dụng rất nhiều cấu trúc dữ liệu và giải thuật khác nhau. Chúng ta cùng đi giải quyết nhé.

Tổ chức các danh sách lưu trữ dữ liệu

Ở trên bạn sẽ phải tạo các danh sách thuộc các kiểu: mảng, danh sách liên kết đơn, cây nhị phân…Cái này thì chắc hẳn ai cũng biết làm rồi.

Lưu ý: Để đơn giản thì các danh sách thuộc dạng mảng như danh sách câu hỏi và danh sách lớp ta nên cấp phát tối đa có thể lưu trữ.

Ta cần lưu danh sách câu hỏi và danh sách lớp vào file. Khi khởi động chương trình thì có thể lấy dữ liệu lên để sử dụng. Sau khi kết thúc chương trình cần lưu lại để cập nhật lại dữ liệu vào file để lần chạy tới chượng trình có thể sử dụng dữ liệu để cập nhật.

Bạn có thể tham khảo một số tài liệu ở đây để hiểu được bài tập cấu trúc dữ liệu & giải thuật này:

• Mảng
• Danh sách liên kết đơn
• Cây nhị phân

Xây dựng các chức năng của chương trình

Dưới đây là các chức năng của bài tập cấu trúc dữ liệu và giải thuật xây dựng phần mềm thi trắc nghiệm, mỗi chức năng đều có hướng dẫn chi tiết cho bạn.

a) Chức năng đăng nhập.

Với chức năng này bạn cần lấy dữ liệu của danh sách lớp từ file. Sau đó thực hiện các bước như sau:

• Kiểm tra xem user đó có phải là giáo viên hay không. Nếu phải thì hiện các chức năng mà giáo viên có thể sử dụng( hầu hết các chức năng giáo viên đều có thể sử dụng).
• Nếu không không phải là user giáo viên thì ta cần duyệt đến từng sinh viên trong danh sách lớp( Danh sách lớp -> Lớp -> Danh sách sinh viên -> Sinh viên). Sau đó kiểm tra user và passwork, nếu đăng nhập thành công thì hiện các chức năng mà sinh viên sử dụng( thi và xem lịch sử thi).

b) Chức năng nhập lớp.

Các bạn thực hiện như sau:

• Nhập số lượng lớp muốn thêm
• Tiến hành nhập dữ liệu cho từng lớp( mã lớp và tên lớp)

Lưu ý: Cần bắt trường hợp người dùng để trống( hay nhập chuỗi rỗng “”).

c) Chức năng in danh sách lớp.

Với chức năng này thì đơn giản, bạn chỉ cần duyệt từng lớp trong danh sách lớp. Sau đó từ lớp ta sẽ lấy danh sách sinh viên và in tất cả các sinh viên thuộc lớp đó ra màn hình.

d) Chức năng nhập sinh viên của lớp.

Các bạn thực hiện tuần tự như sau:

• Nhập mã lớp vào
• Tạo một sanh sách sinh viên
• Tiến hành nhập từng sinh viên theo yêu cầu
• Sau khi nhập xong thì gán danh sách sinh viên cho lớp đó

Lưu ý: Các bạn nên bắt lỗi các trường hợp người dùng nhập sai để chương trình có thể hoàn thiện hơn.

e/ Chức năng nhập môn học và cập nhật môn học.

Với chức năng thêm môn học: Các bạn chỉ cần tạo một node môn học sau đó chèn vào cây nhị phân tìm kiếm. Các bạn có thể đọc kĩ mục cây nhị phân ở trên để hiểu rõ cách chèn hơn. Một chú ý nhỏ là mình sẽ lấy tên môn học làm khóa cho một node.

Với chức năng xóa môn học: Các bạn chỉ cần nhập tên môn học sau đó tiến hành duyệt cây và xóa node.

Với chức năng hiệu chỉnh: Các bạn chỉ cần xóa node môn học đó và bắt người dùng nhập lại tên môn học và mã môn học là được( xóa node và lại thêm node mới ý! ).

f/ Chức năng nhập câu hỏi thi.

Bài tập cấu trúc dữ liệu và giải thuật này có chức năng nhập câu hỏi, với chức năng này thì bạn sẽ thực hiện như sau:

• Nhập số lượng câu hỏi muốn nhập.
• Nhập vào thông tin câu hỏi.
• Vì mỗi câu hỏi sẽ phải dùng hàm băm để xử lý( xem thêm tại đây) và lấy vị trí theo mã câu hỏi. Điều này giúp chúng ta khi lấy câu hỏi sẽ không phải duyệt từ đầu đến cuối mảng.
• Sau khi có vị trí thì tiến hành thêm vào danh sách câu hỏi thôi!

g/ Chức năng thi Trắc nghiệm

Bài tập cấu trúc dữ liệu và giải thuật này yêu cầu bạn lấy câu hỏi theo trình tự sau:

• Nhập vào tên môn học muốn thi.
• Duyệt sanh sách môn học để lấy mã môn học.
• Dùng hàm băm để xử lý mã môn học thành vị trí của câu hỏi( vị trí ở đây là vị trí của câu hỏi đầu tiên của môn học đó thôi nhé !).
• Sau khi có vị trí của câu hỏi đầu tiên rồi thì ta cứ duyệt đến khi hết câu hỏi của môn đó thì thôi( so sánh mã câu hỏi).
• Để đơn giản thì mình tạo thêm một danh sách câu hỏi thi theo môn khi tiến hành duyệt thì đồng thời mình sẽ thêm các câu hỏi vào danh sách này luôn.

Sau khi bạn đã có một danh sách các câu hỏi thi theo môn đã nhập thì việc tiếp theo chúng ta sẽ bắt người dùng nhập số câu hỏi muốn thi ( không được lớn hơn số lượng câu hỏi trong danh sách). Việc tiếp theo chúng ta chỉ cần chọn ngẫu nhiên các câu hỏi có trong danh sách mà thôi. Tham khảo cách chọn số ngẫu nhiên tại đây!

Sao khi đã có đánh dấu những câu hỏi được chọn thì tiến hành in câu hỏi ra màn hình và bắt người dùng nhập đáp án. Bước tiếp theo, bạn cần so sánh đáp án của câu hỏi với đáp án người dùng nhập để tính điểm.

Một lưu ý khi giải quyết bài tập cấu trúc dữ liệu và giải thuật này:

• Nếu user đăng nhập đăng là sinh viên thì bạn cần tạo một file để lưu các câu hỏi và đáp án mà sinh viên đã chọn lại để phục vụ cho chức năng bên dưới. Tên file bạn có thể đặt như sau: Tên file = mã sinh viên + tên môn thi
• Nếu user đăng nhập là sinh viên thì đồng thời sau khi thi xong bạn cần cập nhật điểm của môn thi vào danh sách điểm của sinh viên đó.
• Mẹo nhỏ là khi đăng nhập nếu là sinh viên thì bạn cần giữ một tham chiếu đến sinh viên đó( biến toàn cục) để các bước xử lý dễ dàng hơn. Ví dụ nếu tham chiếu là NULL thì user đó là giáo viên và bạn không cần lưu lại câu hỏi đã kiểm tra…

h/ Chức năng in chi tiết các câu hỏi đã thi 1 môn học của 1 sinh viên.

Chức năng này chỉ dành cho sinh viên. Ở trên các bạn đã lưu lại các câu hỏi đã thi và lựa chọn của sinh viên bây giờ ta chỉ cần tìm file đó và hiển thị lên thôi. Cần kiểm tra nếu file không tồn tại tức là sinh viên đó chưa thi. Bạn tìm file có tên như sau: Tên file = mã sinh viên + tên môn thi

i/ Chức năng in bảng điểm thi trắc nghiệm môn học của 1 lớp.

Bài tập cấu trúc dữ liệu và giải thuật này cũng yêu cầu phải in bảng điểm, các bước thực hiện như sau:

• Nhập vào mã lớp, nhập vào tên môn học.
• Từ mã lớp đó ta có thể lấy được danh sách sinh viên của đó.
• Duyệt từng sinh viên trong danh sách sinh viên, với mỗi sinh viên sẽ có danh sách điểm ta chỉ cần duyệt đến điểm của môn đó mà in ra( lưu ý trong trường hợp không tìm thấy điểm tức là sinh viên chưa thi, lúc này ta chỉ cần in ra “Chua thi” mà thôi).

Chia sẻ source code

Dưới đây là lời giải bâì tập cấu trúc dữ liệu và giải thuật Xây dựng phần mềm thi trắc nghiệm của mình, bạn đọc có thể tải về tại đây. Nếu các bạn có thắc mắc gì xin để lại comment phía dưới!