Bài tập — Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Phần 1: Câu hỏi Trắc nghiệm (Nhận biết & Thông hiểu)

Câu 1. Nội dung nào sau đây phản ánh đúng kiến thức cần ghi nhớ trong bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán? A. Bỏ qua các khái niệm cơ bản và chỉ học thuộc lòng kết quả cuối cùng mà không cần hiểu bản chất. B. Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n. C. Chỉ áp dụng kiến thức trong một trường hợp duy nhất, không cần kiểm tra điều kiện hay đơn vị. D. Các nội dung trong bài hoàn toàn độc lập và không có mối liên hệ nào với thực tiễn hay các bài học khác.

Câu 2. Khi học và vận dụng bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán, khẳng định nào dưới đây là chính xác? A. Không cần đọc kĩ đề bài hay phân tích dữ kiện trước khi thực hiện các bước giải. B. Mọi khái niệm trong bài đều có thể thay thế tùy ý cho nhau mà không làm thay đổi kết quả. C. Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất. D. Chỉ cần ghi đáp số ngắn gọn, bỏ qua toàn bộ bước lập luận, giải thích và kiểm tra lại.

Câu 3. Theo phần Kiến thức trọng tâm của bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán, phát biểu nào sau đây là đúng? A. Kết luận ngay kết quả khi chưa đối chiếu với quy tắc hoặc định nghĩa trong bài học. B. Thay đổi toàn bộ quy tắc trọng tâm của bài học theo cảm tính cá nhân. C. Bỏ qua việc rèn luyện qua ví dụ minh họa và bài tập thực hành của tiết học. D. Độ phức tạp thời gian đo lượng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên.

Câu 4. Để nắm vững và vận dụng tốt bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán, học sinh cần lưu ý điều nào sau đây? A. Để xác định độ phức tạp, ta đếm số lần thực hiện các phép toán cơ bản như gán, so sánh, cộng, trừ theo kích thước đầu vào n, rồi giữ lại thành phần tăng nhanh nhất, bỏ hằng số và hệ số. B. Không cần ghi nhớ các lưu ý trọng tâm vì chúng không ảnh hưởng đến việc làm bài tập. C. Áp dụng ngược lại hoàn toàn so với quy tắc và hướng dẫn trong phần kiến thức trọng tâm. D. Chỉ cần đọc lướt tiêu đề bài học mà không cần nắm vững nội dung chi tiết từng mục.

Phần 2: Bài tập Tự luận & Thực hành theo tiết học

Bài 1 (Cơ bản — Hệ thống hóa kiến thức trọng tâm). Dựa vào phần Kiến thức trọng tâm của bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán, em hãy trình bày các khái niệm, quy tắc hoặc nội dung cốt lõi của tiết học và nêu ý nghĩa của chúng.

Bài 2 (Thực hành — Phân tích & Giải mẫu theo ví dụ tiết học). Đọc kĩ tình huống/ví dụ trọng tâm của tiết học dưới đây, sau đó tự trình bày lại các bước thực hiện và nêu nhận xét rút ra:

Ví dụ 1: đoạn chương trình tính tổng các số từ 1 đến n bằng một vòng lặp cộng dồn. Mỗi lần lặp thực hiện một phép cộng và một phép gán, tổng cộng n lần. Vì vậy độ phức tạp là O(n).

Bài 3 (Vận dụng — Áp dụng quy tắc ghi nhớ vào bài tập). Vận dụng các điểm ghi nhớ trọng tâm của bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán để giải thích hoặc thực hiện yêu cầu thực hành mở rộng sau:

Ví dụ 2: đoạn chương trình in bảng cửu chương gồm hai vòng lặp lồng nhau, vòng ngoài chạy từ 1 đến 9, vòng trong cũng chạy từ 1 đến 9, tổng cộng 81 lần in. Nếu tổng quát hoá với n hàng và n cột thì số lần thực hiện là n × n, độ phức tạp là O(n²).

Bài 4 (Luyện tập học kì — Mức độ Cơ bản). Một cửa hàng quản lí bảng SanPham(MaSP, TenSP, Gia) và bảng DonHang(MaDH, MaSP, SoLuong). Hãy chỉ rõ khóa chính của mỗi bảng, khóa ngoại trong bảng DonHang, và viết câu lệnh SQL liệt kê tên sản phẩm cùng số lượng của các đơn hàng.

Bài 5 (Luyện tập học kì — Mức độ Thông hiểu). Viết chương trình Python nhập mảng hai chiều m hàng × n cột, tính tổng các phần tử ở hàng đầu tiên.

Bài 6 (Luyện tập học kì — Mức độ Vận dụng & Nâng cao). Trong bảng Sach, nếu xóa trường khóa chính thì điều gì xảy ra với khả năng phân biệt các bản ghi? Giải thích.

Phần 3: Đáp án & Hướng dẫn giải chi tiết

1. Đáp án phần Trắc nghiệm

Bảng đáp án: 1-B, 2-C, 3-D, 4-A.
Giải thích chi tiết:
- Câu 1 (B): Khẳng định đúng theo mục Ghi nhớ của bài: "Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n."
- Câu 2 (C): Khẳng định đúng theo nội dung cốt lõi của tiết học: "Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất."
- Câu 3 (D): Khẳng định chuẩn xác theo phần Kiến thức trọng tâm: "Độ phức tạp thời gian đo lượng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên."
- Câu 4 (A): Khẳng định đúng theo hướng dẫn trọng tâm của bài: "Để xác định độ phức tạp, ta đếm số lần thực hiện các phép toán cơ bản như gán, so sánh, cộng, trừ theo kích thước đầu vào n, rồi giữ lại thành phần tăng nhanh nhất, bỏ hằng số và hệ số."

2. Hướng dẫn giải phần Tự luận & Thực hành

Bài 1:
- Nội dung cốt lõi cần trình bày: Độ phức tạp thời gian đo lượng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên. Người ta thường dùng kí hiệu O lớn để mô tả tốc độ tăng trưởng, ví dụ O(1), O(log n), O(n), O(n log n), O(n²).
- Tổng kết ghi nhớ: Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n.; Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất.; O(1) < O(log n) < O(n) < O(n log n) < O(n²).
Bài 2:
- Hướng dẫn phân tích & trình bày: Dựa trực tiếp vào dữ kiện trong ví dụ minh họa của tiết học: Ví dụ 1: đoạn chương trình tính tổng các số từ 1 đến n bằng một vòng lặp cộng dồn. Mỗi lần lặp thực hiện một phép cộng và một phép gán, tổng cộng n lần. Vì vậy độ phức tạp là O(n).
- Lưu ý khi trình bày: Xác định rõ yêu cầu, áp dụng đúng quy tắc/khái niệm trong mục 1 và kiểm tra lại kết quả cuối cùng.
Bài 3:
- Phương pháp giải: Áp dụng các quy tắc ghi nhớ của bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán (Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n.; Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất.; O(1) < O(log n) < O(n) < O(n log n) < O(n²).).
- Lời giải mẫu/Nhận xét: Ví dụ 2: đoạn chương trình in bảng cửu chương gồm hai vòng lặp lồng nhau, vòng ngoài chạy từ 1 đến 9, vòng trong cũng chạy từ 1 đến 9, tổng cộng 81 lần in. Nếu tổng quát hoá với n hàng và n cột thì số lần thực hiện là n × n, độ phức tạp là O(n²).
Bài 4: Khóa chính: SanPham(MaSP), DonHang(MaDH). Khóa ngoại trong DonHang: MaSP tham chiếu tới SanPham(MaSP). sql SELECT SanPham.TenSP, DonHang.SoLuong FROM DonHang JOIN SanPham ON DonHang.MaSP = SanPham.MaSP;
Bài 5: python m = int(input("Nhập số hàng m: ")) n = int(input("Nhập số cột n: ")) a = [] for i in range(m): hang = [int(input(f"Nhập a[{i}][{j}]: ")) for j in range(n)] a.append(hang) print("Tổng hàng đầu tiên:", sum(a[0]))
Bài 6: Không còn trường nào đảm bảo tính duy nhất; các bản ghi có thể bị nhầm lẫn, nhất là khi có các bản ghi trùng tên hoặc trùng thông tin khác. Hệ quản trị CSDL cũng không thể kiểm soát trùng lặp.

Phần 1: Câu hỏi Trắc nghiệm (Nhận biết & Thông hiểu)

Phần 2: Bài tập Tự luận & Thực hành theo tiết học

Ví dụ 1: đoạn chương trình tính tổng các số từ 1 đến n bằng một vòng lặp cộng dồn. Mỗi lần lặp thực hiện một phép cộng và một phép gán, tổng cộng n lần. Vì vậy độ phức tạp là O(n).

Ví dụ 2: đoạn chương trình in bảng cửu chương gồm hai vòng lặp lồng nhau, vòng ngoài chạy từ 1 đến 9, vòng trong cũng chạy từ 1 đến 9, tổng cộng 81 lần in. Nếu tổng quát hoá với n hàng và n cột thì số lần thực hiện là n × n, độ phức tạp là O(n²).

Bài 5 (Luyện tập học kì — Mức độ Thông hiểu). Viết chương trình Python nhập mảng hai chiều m hàng × n cột, tính tổng các phần tử ở hàng đầu tiên.

Phần 3: Đáp án & Hướng dẫn giải chi tiết

1. Đáp án phần Trắc nghiệm

Bảng đáp án: 1-B, 2-C, 3-D, 4-A.

Giải thích chi tiết:

Câu 1 (B): Khẳng định đúng theo mục Ghi nhớ của bài: "Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n."
Câu 2 (C): Khẳng định đúng theo nội dung cốt lõi của tiết học: "Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất."
Câu 3 (D): Khẳng định chuẩn xác theo phần Kiến thức trọng tâm: "Độ phức tạp thời gian đo lượng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên."
Câu 4 (A): Khẳng định đúng theo hướng dẫn trọng tâm của bài: "Để xác định độ phức tạp, ta đếm số lần thực hiện các phép toán cơ bản như gán, so sánh, cộng, trừ theo kích thước đầu vào n, rồi giữ lại thành phần tăng nhanh nhất, bỏ hằng số và hệ số."

2. Hướng dẫn giải phần Tự luận & Thực hành

Bài 1:

Nội dung cốt lõi cần trình bày: Độ phức tạp thời gian đo lượng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên. Người ta thường dùng kí hiệu O lớn để mô tả tốc độ tăng trưởng, ví dụ O(1), O(log n), O(n), O(n log n), O(n²).
Tổng kết ghi nhớ: Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n.; Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất.; O(1) < O(log n) < O(n) < O(n log n) < O(n²).

Bài 2:

Hướng dẫn phân tích & trình bày: Dựa trực tiếp vào dữ kiện trong ví dụ minh họa của tiết học: Ví dụ 1: đoạn chương trình tính tổng các số từ 1 đến n bằng một vòng lặp cộng dồn. Mỗi lần lặp thực hiện một phép cộng và một phép gán, tổng cộng n lần. Vì vậy độ phức tạp là O(n).
Lưu ý khi trình bày: Xác định rõ yêu cầu, áp dụng đúng quy tắc/khái niệm trong mục 1 và kiểm tra lại kết quả cuối cùng.

Bài 3:

Phương pháp giải: Áp dụng các quy tắc ghi nhớ của bài Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán (Độ phức tạp thời gian mô tả xu hướng tăng của thời gian chạy theo n.; Đếm số lần thực hiện phép toán cơ bản, giữ thành phần tăng nhanh nhất.; O(1) < O(log n) < O(n) < O(n log n) < O(n²).).
Lời giải mẫu/Nhận xét: Ví dụ 2: đoạn chương trình in bảng cửu chương gồm hai vòng lặp lồng nhau, vòng ngoài chạy từ 1 đến 9, vòng trong cũng chạy từ 1 đến 9, tổng cộng 81 lần in. Nếu tổng quát hoá với n hàng và n cột thì số lần thực hiện là n × n, độ phức tạp là O(n²).

Bài 4: Khóa chính: SanPham(MaSP), DonHang(MaDH). Khóa ngoại trong DonHang: MaSP tham chiếu tới SanPham(MaSP). sql SELECT SanPham.TenSP, DonHang.SoLuong FROM DonHang JOIN SanPham ON DonHang.MaSP = SanPham.MaSP;

Bài 5:

python m = int(input("Nhập số hàng m: ")) n = int(input("Nhập số cột n: ")) a = [] for i in range(m): hang = [int(input(f"Nhập a[{i}][{j}]: ")) for j in range(n)] a.append(hang) print("Tổng hàng đầu tiên:", sum(a[0]))

Bài 6: Không còn trường nào đảm bảo tính duy nhất; các bản ghi có thể bị nhầm lẫn, nhất là khi có các bản ghi trùng tên hoặc trùng thông tin khác. Hệ quản trị CSDL cũng không thể kiểm soát trùng lặp.