Bài tập Cấu trúc dữ liệu và Giải thuật
| |

Bài tập cấu trúc dữ liệu và giải thuật tổng hợp

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.

Đề bài tập cấu trúc dữ liệu và giải thuật
Đề bài tập cấu trúc dữ liệu và giải thuật

Bài tập cấu trúc dữ liệu & giải thuật

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:

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!

Demo kết quả bài tập cấu trúc dữ liệu và giải thuật
Demo kết quả bài tập cấu trúc dữ liệu và giải thuật, sử dụng hiển thị phân trang

Similar Posts

Subscribe
Notify of
guest
4 Bình luận
Inline Feedbacks
View all comments