Font size
WorksheetsĐề Cương Ôn Tập KTCK2
Total questions: 57
Worksheet time: 34mins
Which statement best describes the meaning of the time complexity of an algorithm?
The actual time the algorithm runs on a specific computer.
The amount of memory resources the algorithm uses.
The growth rate of the execution time of the algorithm according to the input size.
The number of lines of code in the algorithm implementation.
Which operation typically has a time complexity of constant O(1)?
Iterating through all elements in an array of n elements.
Searching for an element in a sorted array using binary search.
Accessing an element at a specific position in an array.
Sorting an array of n elements using Bubble Sort.
A program segment with a for loop running from 1 to n, performing a finite number of operations with constant time inside the loop. What is the time complexity of this segment?
O(1)
O(logn)
O(n)
O(n2)
The time complexity of the binary search algorithm in a sorted array is:
O(1)
O(logn)
O(n)
O(n2)
What is the time complexity of the following code? tong = 0 for i in range(n): for j in range(m): tong += i * j
O(n)
O(m)
O(n×m)
O(max(n,m))
Given two algorithms A and B solving a problem with input size n. Algorithm A has a time complexity of O(nlogn) and algorithm B has a time complexity of O(n2). Which algorithm will generally run faster for large input sizes?
Algorithm A
Algorithm B
Both algorithms have equivalent running time
Cannot determine
The Python function len() to get the length of a list with n elements typically has a time complexity of:
O(1)
O(logn)
O(n)
O(nlogn)
Consider the following code: for i in range(n): k = 1 while k < n: # Some O(1) operations k = k * 2 What is the time complexity of this code?
O(n)
O(logn)
O(nlogn)
O(n2)
For the following code: for i in range(n): print(i) A student commented: "This code has a time complexity of O(1) because it only has one loop." Which explanation is most appropriate to evaluate this comment?
The student is correct, as the number of operations inside the loop is constant.
The student is mistaken, as this loop will execute n times, proportional to the input size.
The student could be correct if n is a small insignificant number.
The student should consider the actual running time on the computer to make an accurate conclusion.
Consider the following code: a = 10 b = 20 c = a + b print(c) A student said: "The time complexity of this code depends on the values of a and b." What do you think about this opinion?
This opinion makes sense, as larger numbers often take more time to process.
This opinion is inaccurate, as the number of operations here is fixed, regardless of the values of a and b.
This opinion is only correct if the addition operation is performed using a more complex algorithm.
This opinion needs to be verified by testing with various values of a and b.
Given two sorting algorithms A (O(n.logn)) and B (O(n2)) solving the problem of sorting an array of n elements. A student concluded: "Algorithm B always runs faster than algorithm A because n2 is greater than n.logn." Which explanation is correct?
The student is correct, as the expression n2 always yields a value greater than n.logn.
The student is mistaken, as time complexity describes the growth rate when the input size is very large, and nlogn grows slower than n2.
The student could be correct for small values of n, but
A student thinks that the time complexity of the following code is O(n). Why is this opinion not accurate? i = 1 while i < n: # Some O(1) operations i = i * 2
Because the while loop usually has a higher complexity than the for loop.
Because the variable i doubles after each iteration, leading to half the number of iterations of n.
Because there is a multiplication operation in the loop, significantly increasing execution time.
Because the stopping condition of the loop is i < n, indicating it depends on n.
For a sequential search algorithm on an array with n elements, in the worst case, the number of comparisons needed is n. A student says: 'So the time complexity of this algorithm is O(1).' Which explanation is appropriate?
The student is correct, as there is only a single loop in the algorithm.
The student does not understand clearly, as the number of comparisons increases with the number of elements in the array.
The student may be confusing it with the case of finding the element at the first position.
The student should consider other operations besides comparisons to evaluate complexity.
Consider the following code: for i in range(n): for j in range(n): # Some O(1) operations pass A student determines the time complexity as O(n). Which explanation shows that the student has reasoned incorrectly?
Because there are two nested for loops, the complexity will usually be the product of the number of iterations of each loop.
Because the pass operation does not take time, it does not affect the complexity.
Because both i and j run from 0 to n-1.
Because this is a common loop structure with linear complexity.
An algorithm has a time complexity of O(logn). What does this mean about the growth rate of the execution time of the algorithm as the input size increases?
The running time will increase linearly, for example, doubling when the input size doubles.
The running time will increase exponentially, for example, quadrupling when the input size doubles.
The running time will increase very slowly, for example, only increasing a small amount when the input size increases significantly.
The running time will not change when the input size increases.
Given the following code: list = [1, 2, 3, ..., n] first_element = list[0] A student concludes: 'The time complexity of this code is O(n) because there is a list with n elements.' Why might this conclusion be inaccurate?
Because creating the initial list may take time proportional to n.
Because accessing an element at a specific position in the list usually takes constant time.
Because assigning a value to the variable first_element is a simple operation.
Because time complexity only considers operations inside loops.
When comparing two algorithms with complexities O(n) and O(n2) to solve the same problem with very large input sizes, which algorithm is usually preferred in terms of time and why?
The O(n2) algorithm is preferred because n2 is always greater than n.
The O(n) algorithm is preferred because its growth rate of execution time is slower as the input size increases.
Both algorithms have equivalent performance when the input size is very large.
It cannot be determined which algorithm is better without knowing the hidden constant in the O notation.
Xét đoạn mã sau: for i in range(1000): print("Hello") Một bạn học sinh nhận xét: "Đoạn mã này có độ phức tạp thời gian là O(n) vì có một vòng lặp." Giải thích nào sau đây giúp bạn học sinh hiểu đúng hơn?
Bạn học sinh đã đúng vì vòng lặp này sẽ chạy n lần nếu thay 1000 bằng n.
Bạn học sinh chưa chính xác vì số lần lặp ở đây là một hằng số (1000), không phụ thuộc vào kích thước đầu vào nào cả.
Bạn học sinh có thể đúng nếu n được hiểu là số ký tự trong chuỗi "Hello".
Bạn học sinh nên chạy thử nghiệm với các giá trị khác nhau của 1000 để xác định độ phức tạp.
Phương pháp làm mịn dần trong thiết kế chương trình còn được gọi là:
Phương pháp thiết kế từ dưới lên (bottom-up design).
Phương pháp thiết kế hướng đối tượng (object-oriented design).
Phương pháp thiết kế chia để trị (divide and conquer design).
Phương pháp thiết kế tuyến tính (linear design).
Mục tiêu chính của phương pháp làm mịn dần là:
Viết code nhanh chóng và hiệu quả.
Tối ưu hóa hiệu suất chạy của chương trình.
Quản lý độ phức tạp của bài toán bằng cách chia nhỏ nó thành các bài toán đơn giản hơn.
Tạo ra giao diện người dùng thân thiện.
Bước đầu tiên trong phương pháp làm mịn dần thường là:
Viết mã chương trình chính.
Xác định bài toán lớn cần giải quyết.
Chia bài toán thành các bài toán con nhỏ nhất có thể lập trình trực tiếp.
Vẽ sơ đồ khối chi tiết cho toàn bộ chương trình.
Trong quá trình làm mịn dần, chúng ta tiếp tục chia nhỏ các bài toán con cho đến khi:
Số lượng bài toán con đạt đến một ngưỡng nhất định.
Tất cả các bài toán con đều có thể được giải quyết trực tiếp bằng các cấu trúc lập trình cơ bản.
Tổng thời gian ước tính để giải quyết các bài toán con là nhỏ nhất.
Tất cả các thành viên trong nhóm thiết kế đều hiểu rõ cách giải từng bài toán con.
Khi áp dụng phương pháp làm mịn dần để giải bài toán "Tính trung bình cộng của các số trong một danh sách", một bước làm mịn có thể là:
Nhập danh sách các số từ người dùng.
Tính tổng của tất cả các số trong danh sách.
In ra kết quả trung bình cộng.
Tất cả các đáp án trên đều là các bước làm mịn tiềm năng.
Trong quá trình thiết kế thuật toán cho bài toán "Kiểm tra một số có phải là số chẵn hay không" theo phương pháp làm mịn dần, bước làm mịn cuối cùng có thể là:
Nhận số đầu vào.
Chia số cho 2.
Kiểm tra xem số dư của phép chia cho 2 có bằng 0 hay không.
In ra kết quả "Số chẵn" hoặc "Số lẻ".
Mã giả thường được sử dụng trong phương pháp làm mịn dần để:
Viết chương trình bằng một ngôn ngữ lập trình cụ thể.
Mô tả thuật toán một cách chi tiết, gần với ngôn ngữ lập trình nhưng vẫn dễ hiểu.
Vẽ sơ đồ khối trực quan cho thuật toán.
Chạy thử nghiệm thuật toán với các bộ dữ liệu khác nhau.
Lợi ích của việc kết hợp các bài toán con đã giải để tạo thành chương trình hoàn chỉnh là:
Giảm thiểu thời gian viết code.
Tăng tính dễ đọc và bảo trì của chương trình.
Giúp dễ dàng phát hiện và sửa lỗi ở từng phần nhỏ của chương trình.
Tất cả các đáp án trên.
Khi kiểm tra và sửa lỗi trong quá trình thiết kế theo phương pháp làm mịn dần, chúng ta thường tập trung vào:
Lỗi cú pháp của ngôn ngữ lập trình.
Lỗi logic trong thuật toán của từng bài toán con và cách chúng tương tác.
Hiệu suất chạy của chương trình.
Giao diện người dùng của chương trình.
Phương pháp làm mịn dần giúp người thiết kế chương trình:
Giải quyết trực tiếp các bài toán phức tạp mà không cần phân tích.
Tiếp cận bài toán một cách có hệ thống, từ tổng quát đến chi tiết.
Viết code một cách ngẫu nhiên và sau đó sắp xếp lại.
Chỉ tập trung vào việc viết chương trình chính mà bỏ qua các chương trình con.
Khái niệm nào sau đây mô tả đúng nhất về một mô đun trong thiết kế chương trình?
Một dòng lệnh đơn lẻ thực hiện một phép toán.
Một biến được sử dụng để lưu trữ dữ liệu.
Một khối chương trình độc lập, thực hiện một chức năng cụ thể.
Một tệp chứa toàn bộ mã nguồn của chương trình.
Lợi ích chính của việc thiết kế chương trình theo mô đun là gì?
Làm cho chương trình chạy nhanh hơn.
Giúp chương trình dễ hiểu, dễ bảo trì và dễ tái sử dụng.
Giảm dung lượng bộ nhớ mà chương trình sử dụng.
Giúp chương trình có giao diện đồ họa đẹp mắt hơn.
Bước nào sau đây thường KHÔNG nằm trong quy trình thiết kế chương trình theo mô đun?
Phân tích bài toán.
Xác định các chức năng chính.
Viết toàn bộ mã nguồn trong một hàm duy nhất.
Chia các chức năng thành các mô đun nhỏ hơn.
Các mô đun (ví dụ như hàm) thường trao đổi dữ liệu với nhau thông qua:
Biến toàn cục (global variables) duy nhất.
Các tệp dữ liệu trung gian.
Tham số (parameters) và giá trị trả về (return values).
Sử dụng trực tiếp bộ nhớ của máy tính.
Trong ngữ cảnh của thiết kế chương trình theo mô đun, "giao diện" của một mô đun thường đề cập đến:
Giao diện đồ họa người dùng của mô đun.
Cách mô đun tương tác với người dùng thông qua bàn phím và màn hình.
Tên của mô đun, danh sách các tham số đầu vào và kiểu dữ liệu trả về (nếu có).
Kích thước của mã nguồn của mô đun.
Phương pháp làm mịn dần (top-down design) thường được sử dụng trong thiết kế theo mô đun để:
Tối ưu hóa hiệu suất của từng mô đun sau khi đã viết code.
Xác định các mô đun cần thiết bằng cách phân rã bài toán từ mức tổng quát đến chi tiết.
Vẽ sơ đồ khối cho toàn bộ chương trình trước khi chia thành mô đun.
Kiểm thử và gỡ lỗi cho toàn bộ chương trình sau khi đã tích hợp các mô đun.
Khi thực hiện "hiện thực hóa mô đun", công việc chính cần thực hiện là:
Vẽ sơ đồ khối cho mô đun.
Viết mã chương trình để thực hiện chức năng của mô đun.
Xác định tên và giao diện của mô đun.
Kiểm thử xem mô đun có hoạt động đúng hay không.
Tại sao việc kiểm thử từng mô đun riêng lẻ lại quan trọng trong thiết kế chương trình theo mô đun?
Để đảm bảo rằng toàn bộ chương trình chạy mà không có lỗi.
Để dễ dàng xác định và sửa lỗi trong phạm vi nhỏ của từng mô đun trước khi tích hợp.
Để tăng tốc độ biên dịch của chương trình.
Để giảm dung lượng mã nguồn của chương trình.
Tình huống nào sau đây thể hiện rõ nhất lợi ích của việc tái sử dụng mô đun?
Viết một hàm tính tổng hai số nguyên và chỉ sử dụng nó một lần trong chương trình.
Sao chép và dán đoạn code tính toán một công thức phức tạp nhiều lần trong chương trình.
Sử dụng một hàm đã được xây dựng sẵn để sắp xếp một danh sách trong nhiều chương trình khác nhau.
Thay đổi tên biến trong một hàm để phù hợp với ngữ cảnh sử dụng khác nhau.
Khi làm việc nhóm để phát triển một chương trình lớn theo phương pháp mô đun hóa, điều nào sau đây là quan trọng nhất để đảm bảo sự phối hợp hiệu quả?
Mỗi thành viên tự do phát triển các mô đun theo ý tưởng cá nhân.
Xác định rõ ràng giao diện (đầu vào, đầu ra) của từng mô đun và sự tương tác giữa chúng.
Sử dụng các biến toàn cục để chia sẻ dữ liệu giữa.
What is the purpose of a library in programming?
To store images and sounds for decorating the program.
To provide pre-built functions and modules for reuse in various programs.
To store input and output data of the program.
To speed up the compilation of the program.
In Python, to use a function from the math library, what syntax do you typically use?
use math.function_name()
include math.function_name()
math.function_name() or from math import function_name; function_name()
call math.function_name()
What does the statement from math import sqrt do?
Imports the entire content of the math library and assigns it to the variable sqrt.
Only imports the sqrt function from the math library and requires using the syntax math.sqrt() to call the function.
Imports only the sqrt function from the math library and allows calling the function directly by the name sqrt().
Creates a copy of the sqrt function in the math library.
When setting up a program library in Python, where do you typically store related functions and code snippets?
In the directory containing the main program with any name.
In a separate Python file (e.g., lib.py).
Directly in the variable declaration section of the main program.
In a special system directory of Python.
Given the following code in the file lib.py: def add(a, b): return a + b What action do you need to take at the beginning of another program file to use the add function?
import add
include lib.py
from lib import add or import lib
use lib
What functions does the math library in Python provide?
Functions for working with strings and text.
Functions for managing files and directories.
Mathematical functions like square root, exponentiation, sin, cos, etc.
Functions for creating graphical interfaces.
What is a significant benefit of using a program library?
Increases the size of the program file.
Helps save time and effort in programming by reusing existing code.
Reduces the security of the program.
Only suitable for small and simple programs.
According to 'SGK TIN 11 CS KNTT', which data structure is introduced as part of the lesson on setting up libraries (even though it is not a library in the traditional sense)?
Array
Queue
Linked list
Tree
When you want to use only a few specific functions from a large library in Python, which import method is usually preferred to keep the program's namespace tidy?
import library_name
from library_name import function1, function2, ...
import * from library_name
include library_name.*
What is the main purpose of setting up a program library?
To make the program code more complex.
To introduce a new way of writing code for the programming language.
To organize and reuse frequently used code snippets in various projects.
To increase the compatibility of the program with different operating systems.
A teacher presents a Python code: for i in range(n): for j in range(10): print(i + j) Some students give opinions about the time complexity:
The time complexity of this code is O(n^2) because there are two loops.
The inner loop runs
Some students commented on the time complexity of the code snippet. What is the time complexity of this code?
The time complexity of this code is O(n^2) because there are two loops.
The inner loop runs a constant number of times (10).
The time complexity of this code is O(n*10)=O(n).
If n is doubled, the execution time will increase by 10 times.
The teacher describes a binary search algorithm in a sorted array with n elements. Some students commented:
This algorithm always compares the target element with the middle element of the array.
In the worst case, the number of comparisons is proportional to log2(n).
The time complexity of this algorithm is O(n).
This algorithm cannot be applied to an unsorted array.
Given the following Python code using the function:
The function tinh_tong is a module that performs the addition of two numbers.
The variables a and b in the function definition are parameters.
The return value of the function is stored in the variable ket_qua.
We cannot call the function tinh_tong multiple times in the program.
What is the main purpose of dividing a large program into smaller modules?
To make the program run faster.
To increase the understandability and maintainability of the program parts.
To reduce the memory usage of the program.
To increase the reusability of the program parts.
In modular program design, how do modules typically exchange data?
By using global variables directly.
By storing and reading data from intermediate files.
By using parameters to pass data in.
By using return values to receive results.
With the requirement to design a sales management program with functions: input products, search products, sell products, and report revenue. According to the modular design method, some students commented:
Write the entire program in a single module for easier management.
Divide into separate modules corresponding to each main function: Input products, Search products, Sell products, and Report revenue.
Dividing into multiple modules is unnecessary for such a small program.
Divide into groups of modules handling business logic (e.g., product management, sales management) and reporting modules.
Given a code snippet containing a for or while loop. Identify the positive operations in that code and analyze to provide the time complexity in big O notation. Clearly explain the analysis steps and why that is the time complexity of the code.
For the following Python code:
