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

Hôm nay, chúng ta sẽ cùng nhau giải quyết một bài toán cấu trúc dữ liệu và giải thuật. Bài tập này được gọi là “Xây dựng phần mềm thi trắc nghiệm”. Bài tập này áp dụng nhiều cấu trúc dữ liệu và giải thuật khác nhau. Hãy cùng đi vào chi tiết nhé!

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

Ở bài tập này, chúng ta cần tạo các danh sách thuộc các kiểu dữ liệu khác nhau như mảng, danh sách liên kết đơn và cây nhị phân. Để đơn giản hóa, các danh sách dạng mảng như danh sách câu hỏi và danh sách lớp nên được cấp phát tối đa có thể chứa.

Chúng ta cũng cần lưu danh sách câu hỏi và danh sách lớp vào một tệp. Khi chương trình khởi động, chúng ta có thể nạp dữ liệu từ tệp để sử dụng. Sau khi chương trình kết thúc, chúng ta cần lưu dữ liệu để cập nhật lại tệp, để lần chạy tiếp theo có thể sử dụng dữ liệu đã cập nhật.

Đây là một số tài liệu tham khảo để hiểu rõ hơn về bài tập cấu trúc dữ liệu và 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 “Xây dựng phần mềm thi trắc nghiệm”. Mỗi chức năng sẽ được có hướng dẫn chi tiết đi kèm.

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

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

• Kiểm tra xem người dùng có phải là giáo viên hay không. Nếu phải, hiển thị các chức năng mà giáo viên có thể sử dụng (thường là hầu hết các chức năng).
• Nếu không phải là người dùng giáo viên, duyệt 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 tài khoản và mật khẩu. Nếu đăng nhập thành công, hiển thị các chức năng mà sinh viên có thể sử dụng (thi và xem lịch sử thi).

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

Thực hiện các bước sau:

• Nhập số lượng lớp muốn thêm.
• Nhập thông tin cho từng lớp (mã lớp và tên lớp).

Lưu ý: Hãy kiểm tra trường hợp người dùng để trống hoặc nhập chuỗi rỗng (“”).

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

Chức năng này rất đơn giản, bạn chỉ cần duyệt qua từng lớp trong danh sách lớp. Sau đó, từ lớp, ta có thể 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

Thực hiện theo các bước sau:

• Nhập mã lớp.
• Tạo một danh sách sinh viên.
• Nhập từng sinh viên theo yêu cầu.
• Sau khi nhập xong, gán danh sách sinh viên cho lớp đó.

Lưu ý: Bạn nên kiểm tra lỗi, ví dụ như trường hợp người dùng nhập sai để chương trình 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, bạn chỉ cần tạo một nút môn học và chèn nó vào cây nhị phân tìm kiếm. Bạn có thể đọc thêm về cây nhị phân để hiểu cách chèn rõ hơn. Lưu ý là tên môn học sẽ được sử dụng làm khóa cho một nút.

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

Với chức năng hiệu chỉnh, bạn chỉ cần xóa nút môn học đó và yêu cầu người dùng nhập lại tên môn học và mã môn học (xóa nút và thêm nút mới).

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

Bài tập này yêu cầu bạn nhập câu hỏi. Thực hiện các bước sau:

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

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

Bài tập này yêu cầu bạn lấy câu hỏi theo trình tự sau:

• Nhập tên môn học muốn thi.
• Duyệt danh sách môn học để lấy mã môn học.
• Sử dụng hàm băm để chuyển 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 đó).
• Duyệt đến khi hết câu hỏi của môn học đó (so sánh mã câu hỏi).
• Để đơn giản, chúng ta có thể tạo thêm một danh sách câu hỏi thi theo môn học và thêm các câu hỏi vào danh sách này ngay khi duyệt qua chúng.

Sau khi bạn đã có danh sách câu hỏi thi theo môn học đã nhập, tiếp theo, chúng ta sẽ yêu cầu 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). 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. Xem thêm cách chọn số ngẫu nhiên tại đây!

Sau khi đã đánh dấu những câu hỏi được chọn, hãy in câu hỏi ra màn hình và yêu cầu người dùng nhập đáp án. 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 này là:

• Nếu người dùng đăng nhập là sinh viên, bạn cần tạo một tệp để lưu câu hỏi và đáp án mà sinh viên đã chọn để phục vụ cho chức năng dưới đây. Tên tệp có thể được đặt như sau: Tên tệp = mã sinh viên + tên môn thi.
• Nếu người dùng đăng nhập là sinh viên, sau khi thi xong, hãy cập nhật điểm của môn thi vào danh sách điểm của sinh viên đó.
• Một mẹo nhỏ là khi đăng nhập, nếu là sinh viên, bạn cần giữ một tham chiếu đến sinh viên đó (biến toàn cục) để việc xử lý dễ dàng hơn. Ví dụ, nếu tham chiếu là NULL, người dùng đó 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. Với các câu hỏi đã lưu và lựa chọn của sinh viên, ta chỉ cần tìm tệp đó và hiển thị nội dung ra màn hình. Nếu tệp không tồn tại, tức là sinh viên chưa thi. Tên tệp có dạng: Tên tệp = 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 này yêu cầu in bảng điểm. Thực hiện các bước sau:

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

Chia sẻ source code

Dưới đây là lời giải 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”. Bạn đọc có thể tải file tại đây. Nếu bạn có bất kỳ thắc mắc nào, hãy để lại bình luận phía dưới!

Caption: 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