Luyện tập: Ôn thi tốt nghiệp

Bài: Luyện tập ôn thi tốt nghiệp – Lý thuyết trọng tâm

Giới thiệu

Chào các em, bài học hôm nay nằm trong phần Chương 4: Ôn thi tốt nghiệp của môn Tin học lớp 12. Mục tiêu của chúng ta là hệ thống lại những kiến thức cốt lõi đã học trong suốt năm học, đặc biệt là các nội dung liên quan đến lập trình Python và cấu trúc dữ liệu, giải thuật. Các em sẽ được củng cố lý thuyết, xem xét các ví dụ minh họa, và ghi nhớ những phần quan trọng để chuẩn bị tốt nhất cho kỳ thi sắp tới. Hãy tập trung nhé!

Lý thuyết trọng tâm

Trong phần ôn thi tốt nghiệp, chúng ta cần nắm vững các khái niệm cơ bản sau đây:

1. Cấu trúc dữ liệu mảng (List) và xử lý tuần tự

• Khái niệm: List (danh sách) là một cấu trúc dữ liệu có thứ tự, cho phép lưu trữ nhiều giá trị (có thể cùng kiểu hoặc khác kiểu) trong một biến duy nhất. Ví dụ: ds = [5, 2, 8, 1, 9].
• Thao tác chính:
  • Truy xuất phần tử theo chỉ số: ds[i] (i bắt đầu từ 0).
  • Duyệt list: dùng vòng lặp for x in ds: hoặc for i in range(len(ds)):.
  • Thao tác thêm, xóa: ds.append(x), ds.pop(i).

2. Giải thuật tìm kiếm và sắp xếp cơ bản

• Tìm kiếm tuần tự: Duyệt từ đầu đến cuối list để tìm phần tử thỏa mãn. Độ phức tạp O(n).
  Ví dụ: Tìm vị trí của số 8 trong list [5, 2, 8, 1, 9] – nếu gặp 8 thì trả về chỉ số.
• Sắp xếp nổi bọt (Bubble Sort): So sánh từng cặp phần tử liền kề và đổi chỗ nếu chúng sai thứ tự. Lặp lại cho đến khi toàn bộ list được sắp xếp tăng dần.
• Sắp xếp chèn (Insertion Sort): Xây dựng dần dãy đã sắp xếp bằng cách chèn từng phần tử mới vào đúng vị trí.

3. Xử lý chuỗi ký tự (String)

• Các hàm thường dùng:
  • len(s): trả về độ dài chuỗi.
  • s.upper(), s.lower(): chuyển thành chữ hoa/thường.
  • s.split(sep): tách chuỗi thành list theo dấu phân cách.
  • s.replace(old, new): thay thế chuỗi con.

4. Đệ quy và kỹ thuật chia để trị

• Đệ quy: Hàm tự gọi lại chính nó với bài toán nhỏ hơn. Cần có điểm dừng (base case).
  Ví dụ: Tính giai thừa n! với base case: n = 0 thì trả về 1; nếu không thì n * factorial(n-1).
• Chia để trị: Chia bài toán lớn thành các bài toán con độc lập, giải quyết chúng rồi kết hợp kết quả. Điển hình là sắp xếp trộn (Merge Sort) hoặc tìm kiếm nhị phân (Binary Search).

Ví dụ minh họa

Ví dụ 1: Cho list điểm số [7, 8, 5, 9, 6]. Viết hàm đệ quy tính tổng các phần tử của list.

Giải thích: Ta có thể dùng đệ quy để tính tổng: tổng của list rỗng là 0; nếu không, tổng = phần tử đầu + tổng các phần tử còn lại.

def tong_list(lst):
    if len(lst) == 0:
        return 0
    else:
        return lst[0] + tong_list(lst[1:])

print(tong_list([7, 8, 5, 9, 6]))  # Kết quả: 35

Ví dụ 2: Viết chương trình tìm kiếm tuần tự vị trí số lớn nhất trong list [4, 12, 7, 15, 9].

def vi_tri_max(lst):
    vt = 0
    for i in range(1, len(lst)):
        if lst[i] > lst[vt]:
            vt = i
    return vt

print(vi_tri_max([4, 12, 7, 15, 9]))  # Kết quả: 3 (vị trí của số 15)

Ví dụ 3: Cho chuỗi "Học sinh giỏi, lớp 12A". Hãy tách chuỗi thành các từ riêng biệt và đếm số từ.

chuoi = "Học sinh giỏi, lớp 12A"
danh_sach_tu = chuoi.split()  # Tách theo dấu cách
print(danh_sach_tu)  # ['Học', 'sinh', 'giỏi,', 'lớp', '12A']
print("Số từ:", len(danh_sach_tu))  # 5 từ

Ghi nhớ

• List là cấu trúc dữ liệu nền tảng; thành thạo các thao tác duyệt và chỉnh sửa list.
• Tìm kiếm tuần tự hoạt động với mọi dữ liệu; tìm kiếm nhị phân yêu cầu dữ liệu đã được sắp xếp.
• Đệ quy cần có điểm dừng và bước đệ quy – tránh vòng lặp vô hạn.
• Chuỗi trong Python không thay đổi được; các hàm xử lý trả về chuỗi mới.
• Khi giải bài toán, luôn xác định rõ đầu vào và đầu ra, sau đó chọn giải thuật phù hợp.

Bài tập gợi ý

1. Viết hàm đệ quy để tính lũy thừa aⁿ (với n là số tự nhiên). Gợi ý: base case n = 0 thì trả về 1.
2. Cho list [3, 7, 2, 9, 5]. Hãy sử dụng sắp xếp nổi bọt để sắp xếp list theo thứ tự giảm dần. Mô phỏng các bước thực hiện.
3. Viết chương trình nhập một chuỗi từ bàn phím, đếm số lần xuất hiện của ký tự 'a' (không phân biệt chữ hoa/thường).
4. Tìm hiểu và cài đặt giải thuật tìm kiếm nhị phân trên list đã sắp xếp tăng dần. Thử nghiệm với list [1, 4, 6, 9, 12, 15] và tìm số 9.

Chúc các em ôn tập thật tốt và đạt kết quả cao trong kỳ thi tốt nghiệp sắp tới!