Câu hỏi mở đầu trang 137

Đề bài: Cấu trúc danh sách liên kết (hay danh sách móc nối, linked list) là đối tượng có cấu trúc gần giống với mảng nhưng có liên kết không chặt chẽ như mảng. Một ví dụ của cấu trúc danh sách liên kết là mô hình các trang web. Khi duyệt web, em không thể đánh chỉ số cho từng trang web đã duyệt, mà chỉ có thể di chuyển đến các trang trước và trang sau.

Em hãy tìm thêm các ví dụ thực tế của mô hình danh sách liên kết.

Lời giải:

Một số ví dụ thực tế của mô hình danh sách liên kết:

• Lịch sử duyệt web (nút Back/Forward) – các trang được nối với nhau theo thứ tự đã xem.
• Danh sách bài hát trong playlist – chỉ có thể đến bài trước hoặc bài sau, không đánh chỉ số cụ thể.
• Đoàn tàu hoả – mỗi toa nối với toa tiếp theo, muốn đến toa cuối phải đi qua các toa trước đó.
• Hàng đợi in ấn – các văn bản được xử lí theo thứ tự nộp vào.
• Chuỗi các bước trong một quy trình – mỗi bước nối với bước tiếp theo.

1. Thiết lập thư viện cho chương trình

Hoạt động 1 trang 137

Đề bài: Em hãy đọc, thảo luận và trả lời các câu hỏi sau:

1. Vì sao lại cần thư viện chương trình?

Lời giải:

Cần thư viện chương trình vì:

• Tái sử dụng các hàm/thuật toán đã viết sẵn nhiều lần trong nhiều chương trình khác nhau.
• Tiết kiệm thời gian khi viết chương trình mới – không phải viết lại các thao tác quen thuộc.
• Chương trình chính trở nên gọn gàng, dễ đọc, dễ bảo trì.

2. Ý nghĩa của các hàm trong thư viện chương trình là gì?

Lời giải:

Các hàm trong thư viện:

• Cung cấp các chức năng đã được viết sẵn (tính toán, sắp xếp, tìm kiếm,…).
• Có thể dùng nhiều lần trong nhiều chương trình khác nhau chỉ bằng lệnh import.
• Giúp lập trình viên tập trung vào bài toán chính, không phải viết lại các thao tác cơ bản.

Câu hỏi củng cố mục 1 trang 138

Đề bài: Những câu nào sau đây là sai về ý nghĩa của việc sử dụng thư viện khi viết chương trình?

A. Chương trình sẽ ngắn hơn.

B. Các hàm thư viện được viết một lần và sử dụng nhiều lần.

C. Chương trình sáng sủa, dễ hiểu hơn.

D. Chương trình sẽ chạy nhanh hơn.

Lời giải:

Câu sai là D. Chương trình sẽ chạy nhanh hơn.

Giải thích: Thư viện không giúp chương trình chạy nhanh hơn – tốc độ chạy phụ thuộc vào thuật toán và độ phức tạp, không phụ thuộc vào việc code được đặt trong thư viện hay trong chương trình chính.

Các câu A, B, C đều đúng: thư viện giúp chương trình ngắn hơn, dễ tái sử dụng và sáng sủa hơn.

2. Cấu trúc danh sách liên kết

Hoạt động 2 trang 139

Đề bài: Đọc, trao đổi và thảo luận để biết cấu trúc dữ liệu của danh sách liên kết và các thao tác dữ liệu cơ bản trên danh sách liên kết.

Lời giải:

Cấu trúc dữ liệu:

• Node – đơn vị cơ bản của danh sách. Mỗi node có:
  • key: dữ liệu chính (khoá).
  • next: liên kết tới node tiếp theo (nếu là node cuối thì next = None).
• LL (linked list) – toàn bộ danh sách. Có thuộc tính head chỉ vào node đầu tiên.

Các hàm thao tác chuẩn:

• insert(L, k): chèn node có khoá k vào đầu danh sách.
• delete_first(L): xoá node đầu tiên của danh sách.
• search(L, k): tìm node có khoá k, trả về node đó hoặc None.
• delete(L, k): xoá node có khoá k.
• show(L): hiển thị toàn bộ danh sách.

Toàn bộ các hàm này được tập hợp trong tệp thư viện LinkedList.py.

Câu hỏi củng cố mục 2 trang 142

Đề bài:

1. Đoạn chương trình sau thực hiện công việc gì?

from LinkedList import *
L = LL()
insert(L, 10)
insert(L, 20)
show(L)

Lời giải:

Diễn biến từng lệnh:

→ Đoạn chương trình tạo danh sách liên kết chứa 2 node có khoá 20 và 10, sau đó in ra màn hình: 20 10.

2. Viết đoạn chương trình ngắn sử dụng thư viện LinkedList để thiết lập một danh sách liên kết L và bổ sung các tên “Bình”, “Hoa”, “Hà” vào danh sách này.

Lời giải:

from LinkedList import *

L = LL()
insert(L, "Bình")
insert(L, "Hoa")
insert(L, "Hà")
show(L)

Giải thích:

• Tạo danh sách rỗng L.
• Chèn lần lượt “Bình”, “Hoa”, “Hà” vào đầu danh sách.
• Khi in ra bằng show(L), thứ tự sẽ là: Hà Hoa Bình (vì mỗi lệnh insert đều chèn vào đầu, phần tử chèn sau nằm trước).

Luyện tập

Luyện tập trang 142

Đề bài:

1. Viết một thư viện bao gồm các hàm nhập dữ liệu là một dãy số và các hàm thư viện bao gồm sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.

Lời giải:

Tệp thư viện có thể đặt tên là lib_sort.py, gồm 4 hàm:

# lib_sort.py
def NhapDL():
    S = input("Nhập dãy số nguyên cách nhau bởi dấu cách: ")
    A = S.split()
    for i in range(len(A)):
        A[i] = int(A[i])
    return A

def InsertionSort(A):
    n = len(A)
    for i in range(1, n):
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value:
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = value

def SelectionSort(A):
    n = len(A)
    for i in range(n-1):
        iMin = i
        for j in range(i+1, n):
            if A[j] < A[iMin]:
                iMin = j
        A[i], A[iMin] = A[iMin], A[i]

def BubbleSort(A):
    n = len(A)
    for i in range(n-1):
        for j in range(n-1-i):
            if A[j] > A[j+1]:
                A[j], A[j+1] = A[j+1], A[j]

Chương trình sử dụng thư viện (đặt cùng thư mục với lib_sort.py):

from lib_sort import *

A = NhapDL()
InsertionSort(A)      # có thể đổi sang SelectionSort(A) hoặc BubbleSort(A)
print(A)

2. Cho trước danh sách liên kết L với cấu trúc như đã mô tả trong bài học, muốn lấy ra khoá của node đầu tiên của danh sách thì dùng lệnh nào?

Lời giải:

Dùng lệnh: L.head.key

Giải thích:

• L.head là node đầu tiên của danh sách.
• L.head.key là khoá (dữ liệu chính) của node đó.

Vận dụng

Vận dụng trang 142

Đề bài:

1. Cho trước một danh sách liên kết L. Viết một hàm đếm số lượng phần tử của danh sách liên kết này.

Lời giải:

def count(L):
    dem = 0
    x = L.head
    while x != None:
        dem = dem + 1
        x = x.next
    return dem

Giải thích:

• Bắt đầu từ node đầu (L.head) gán vào biến x.
• Chừng nào x khác None (chưa đi hết danh sách):
  • Tăng biến đếm dem lên 1.
  • Chuyển sang node tiếp theo bằng x = x.next.
• Kết thúc, trả về dem là tổng số node.

2. Viết hàm delete_last(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L.

Lời giải:

def delete_last(L):
    if L.head == None:                # danh sách rỗng
        return
    if L.head.next == None:            # danh sách chỉ có 1 node
        L.head = None
        return
    x = L.head
    while x.next.next != None:         # duyệt đến node kế cuối
        x = x.next
    x.next = None                      # cắt liên kết với node cuối

Giải thích:

• Trường hợp 1 – danh sách rỗng (L.head == None): không làm gì.
• Trường hợp 2 – danh sách chỉ có 1 node (L.head.next == None): gán L.head = None, danh sách trở thành rỗng.
• Trường hợp 3 – danh sách có nhiều node:
  • Duyệt biến x đi qua các node cho đến khi x là node kế cuối (điều kiện x.next.next != None đảm bảo x.next chưa phải node cuối).
  • Gán x.next = None để cắt liên kết với node cuối → node cuối bị bỏ ra khỏi danh sách.

Thầy Phạm Thành Danh

(Người kiểm duyệt, ra đề)

Chức vụ: Trưởng ban biên soạn môn Tin Học THPT

Trình độ: Cử nhân Sư phạm Tin học, Chứng chỉ hạng II, Chứng chỉ Tin học, Ngoại ngữ B1

Kinh nghiệm: 8+ năm kinh nghiệm tại Trường THPT Thuận Hóa