Gợi ý: Mô tả các bước thực hiện các phép toán sau của danh sách liên kết để minh hoạ chúng đều có thời gian là O(1).

Tham khảo:

Tổ chức thực hiện:

– Lập các nhóm dự án, mỗi nhóm khoảng 5 đến 6 học sinh; chọn nhóm trưởng. - Cả nhóm cùng thực hiện Nhiệm vụ 1:

+ Đọc hướng dẫn để biết cách phân tích, lựa chọn và thiết kế các hàm. Hướng dẫn chỉ là gợi ý, không bắt buộc phải theo.

+Thảo luận, đưa ra thiết kế cuối cùng sau các sửa đổi, điều chỉnh.

- Dựa trên danh sách các hàm cần thực hiện, xác định các nhiệm vụ cụ thể; phân công mỗi nhiệm vụ (các bài thực hành tiếp theo) cho 1 đến 2 học sinh đảm nhiệm.

– Nhóm trưởng phụ trách tích hợp các kết quả thành chương trình hoàn chỉnh với sự cộng tác của các thành viên khác, dưới sự hỗ trợ của thầy, cô giáo.

- Ta có thể đặt tên các phần tử của danh sách học sinh là họ tên của các học sinh. Ví dụ: nếu lớp có 30 học sinh, chúng ta có thể tạo một danh sách với 30 phần tử và lưu trữ họ tên của các học sinh tại các chỉ số tương ứng của danh sách. Ví dụ: tên học sinh thứ nhất được lưu trữ tại vị trí danh sách thứ 0, tên học sinh thứ hai được lưu trữ tại vị trí danh sách thứ 1, và cứ như vậy.

- Để tổ chức dữ liệu khảo sát, chúng ta có thể sử dụng một cấu trúc dữ liệu gọi là "bảng điểm" (scoreboard) hoặc "bảng đánh giá" (rating table). Cấu trúc này có thể được triển khai dưới dạng một mảng.

- Em sẽ dụng cấu trúc dữ liệu 2 chiều để mô tả danh sách các địa điểm này

Tham khảo:

def nhapSinhVien(self):

    # Khởi tạo một sinh viên mới

    svId = self.generateID()

    name = input("Nhap ten sinh vien: ")

    sex = input("Nhap gioi tinh sinh vien: ")

    age = int(input("Nhap tuoi sinh vien: "))

    diemToan = float(input("Nhap diem toan: "))

    diemLy = float(input("Nhap diem Ly: "))

    diemHoa = float(input("Nhap diem Hoa: "))

    sv = SinhVien(svId, name, sex, age, diemToan, diemLy, diemHoa)

    self.tinhDTB(sv)

    self.xepLoaiHocLuc(sv)

    self.listSinhVien.append(sv)

1. Sắp xếp chèn (Insertion Sort)

Ý tưởng: Insertion Sort lấy ý tưởng từ việc chơi bài, dựa theo cách người chơi "chèn" thêm một quân bài mới vào bộ bài đã được sắp xếp trên tay.

2. Sắp xếp lựa chọn (Selection Sort)

Ý tưởng của Selection sort là tìm từng phần tử cho mỗi vị trí của mảng hoán vị A' cần tìm.

3. Sắp xếp nổi bọt (Bubble Sort)

Ý tưởng: Bubble Sort, như cái tên của nó, là thuật toán đẩy phần tử lớn nhất xuống cuối dãy, đồng thời những phần tử có giá trị nhỏ hơn sẽ dịch chuyển dần về đầu dãy. Tựa như sự nổi bọt vậy, những phần tử nhẹ hơn sẽ nổi lên trên và ngược lại, những phần tử lớn hơn sẽ chìm xuống dưới.

Dựa trên yêu cầu của bài toán, ta có thể đề xuất các bảng dữ liệu và các trường làm khoá chính và khoá ngoài như sau:

- Bảng HocSinh:

Trường: Mã số báo danh, Họ tên, Ngày sinh, Địa chỉ

Khoá chính: Mã số báo danh

Khoá ngoài: Không có

- Bảng MonHoc:

Trường: Tên môn học, Mã môn học

Khoá chính: Mã môn học

Khoá ngoài: Không có

- Bảng PhongThi:

Trường: Mã phòng thi, Tên phòng thi

Khoá chính: Mã phòng thi

Khoá ngoài: Không có

- Bảng ThiSinh_MonHoc:

Trường: Mã số báo danh, Mã môn học

Khoá chính: Mã số báo danh, Mã môn học

Khoá ngoài: Mã số báo danh tham chiếu đến bảng HocSinh, Mã môn học tham chiếu đến bảng MonHoc

- Bảng KetQuaThi:

Trường: Mã số báo danh, Mã môn học, Mã phòng thi, Điểm thi

Khoá chính: Mã số báo danh, Mã môn học, Mã phòng thi

Khoá ngoài:

Mã số báo danh tham chiếu đến bảng HocSinh

Mã môn học tham chiếu đến bảng MonHoc

Mã phòng thi tham chiếu đến bảng PhongThi

Lưu ý rằng, trong bảng ThiSinh_MonHoc, ta cần sử dụng một tập hợp các trường (Mã số báo danh, Mã môn học) để tạo thành khoá chính, bởi vì một thí sinh có thể đăng kí thi nhiều môn học khác nhau. Còn trong bảng KetQuaThi, ta cần sử dụng một tập hợp các trường (Mã số báo danh, Mã môn học, Mã phòng thi) để tạo thành khoá chính, bởi vì một thí sinh có thể thi cùng một môn học ở nhiều phòng thi khác nhau.

*Thuật toán sắp xếp chèn (Insertion Sort):

import time

def insertion_sort(arr):

 n = len(arr)

 for i in range(1, n):

  key = arr[i]

  j = i - 1

  while j >= 0 and arr[j] > key:

   arr[j + 1] = arr[j]

   j -= 1

  arr[j + 1] = key

# Dãy số nguyên đầu vào

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]

# In dãy số nguyên trước khi sắp xếp

print("Dãy số nguyên trước khi sắp xếp:", A)

# Bắt đầu đo thời gian thực hiện thuật toán

start_time = time.time()

# Gọi hàm sắp xếp chèn

insertion_sort(A)

# Kết thúc đo thời gian thực hiện thuật toán

end_time = time.time()

# In dãy số nguyên sau khi sắp xếp

print("Dãy số nguyên sau khi sắp xếp:", A)

# In thời gian thực hiện thuật toán

print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))

Thời gian thực hiện là 0 giây

*Thuật toán sắp xếp chọn:

import time

def selection_sort(arr):

 n = len(arr)

 for i in range(n):

  min_idx = i

  for j in range(i + 1, n):

   if arr[j] < arr[min_idx]:

    min_idx = j

  arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Dãy số nguyên đầu vào

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]

# In dãy số nguyên trước khi sắp xếp

print("Dãy số nguyên trước khi sắp xếp:", A)

# Bắt đầu đo thời gian thực hiện thuật toán

start_time = time.time()

# Gọi hàm sắp xếp chọn

selection_sort(A)

# Kết thúc đo thời gian thực hiện thuật toán

end_time = time.time()

# In dãy số nguyên sau khi sắp xếp

print("Dãy số nguyên sau khi sắp xếp:", A)

# In thời gian thực hiện thuật toán

print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))

Thời gian thực hiện là: 0 giây

*Thuật toán sắp xếp nổi bọt:

import time

def bubble_sort(arr):

 n = len(arr)

 for i in range(n - 1):

  for j in range(n - i - 1):

   if arr[j] > arr[j + 1]:

    arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Dãy số nguyên đầu vào

A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 1]

# In dãy số nguyên trước khi sắp xếp

print("Dãy số nguyên trước khi sắp xếp:", A)

# Bắt đầu đo thời gian thực hiện thuật toán

start_time = time.time()

# Gọi hàm sắp xếp nổi bọt

bubble_sort(A)

# Kết thúc đo thời gian thực hiện thuật toán

end_time = time.time()

# In dãy số nguyên sau khi sắp xếp

print("Dãy số nguyên sau khi sắp xếp:", A)

# In thời gian thực hiện thuật toán

print("Thời gian thực hiện thuật toán: {:.6f} giây".format(end_time - start_time))

Thời gian thực hiện là: 0 giây