1/30
Bộ thẻ câu hỏi ôn tập giữa kỳ môn Tin học 11 về các thuật toán sắp xếp (chèn, chọn, nổi bọt), các phương pháp kiểm thử chương trình và đánh giá độ phức tạp tính toán.
Trong thuật toán sắp xếp chèn, vòng lặp chính duyệt các phần tử bắt đầu từ phần tử nào?
Bắt đầu từ phần tử thứ hai của dãy (chỉ số i=1).
Ý tưởng chính của thuật toán sắp xếp chèn (Insertion Sort) là gì?
Duyệt từ phần tử thứ hai đến cuối dãy, lần lượt chèn mỗi phần tử vào đúng vị trí trong phần dãy con đã sắp xếp phía trước.
Trong thuật toán sắp xếp chèn, câu lệnh điều kiện while (j >= 0 && A[j] > value) có ý nghĩa gì?
Dời các phần tử lớn hơn value sang phải để tìm chỗ chèn thích hợp.
Để sắp xếp chèn theo thứ tự giảm dần, điều kiện so sánh trong vòng lặp while cần sửa thành gì?
Sửa thành A[j]<value.
Thao tác đặc trưng của thuật toán sắp xếp nổi bọt (Bubble Sort) là gì?
So sánh hai phần tử cạnh nhau, nếu chưa đúng thứ tự thì đổi chỗ.
Vì sao thuật toán sắp xếp này lại được gọi là "sắp xếp nổi bọt"?
Vì sau mỗi lượt duyệt, phần tử lớn (hoặc nhỏ) dần "nổi" về đúng vị trí ở cuối dãy giống bọt khí nổi lên trên mặt nước.
Sau khi kết thúc lượt duyệt đầu tiên của thuật toán sắp xếp nổi bọt tăng dần, điều gì chắc chắn xảy ra?
Phần tử lớn nhất đã được đưa về đúng vị trí ở cuối dãy.
Cho dãy số: 5, 1, 4, 2, 8. Khi dùng thuật toán sắp xếp nổi bọt để sắp xếp tăng dần thì cần tất cả bao nhiêu lượt hoán đổi hai phần tử liền kề?
Cần tất cả 4 lượt đổi chỗ.
Với dãy gồm n phần tử, số phép so sánh tối đa của thuật toán sắp xếp nổi bọt (hai vòng lặp lồng nhau duyệt đầy đủ) là bao nhiêu?
2n(n−1) phép so sánh.
Thuật toán sắp xếp chọn (Selection Sort) trên dãy gồm n phần tử thực hiện tối đa bao nhiêu phép đổi chỗ (swap)?
Thực hiện tối đa n−1 phép đổi chỗ.
Cho dãy số: 15, 1, 31, 9, 78, 42. Dùng thuật toán sắp xếp chọn tăng dần, sau lượt lặp thứ nhất (i=0), dãy trở thành gì?
Dãy trở thành: 1, 15, 31, 9, 78, 42.
Cho dãy số: 15, 1, 31, 9, 78, 42. Dùng thuật toán sắp xếp nổi bọt tăng dần, sau lượt duyệt thứ nhất, dãy trở thành gì?
Dãy trở thành: 1, 15, 9, 31, 42, 78.
Độ phức tạp thời gian trong trường hợp xấu nhất của ba thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt là bao nhiêu?
Cả ba đều có độ phức tạp thời gian trong trường hợp xấu nhất là O(n2).
Trong thuật toán BubbleSort cải tiến, biến cờ daDoi có vai trò gì?
Cho phép thuật toán dừng sớm khi một lượt duyệt không còn phát sinh bất kỳ phép đổi chỗ nào.
Trong C++, câu lệnh nào thường dùng để chuyển hướng nhập chuẩn đọc dữ liệu từ tệp văn bản "kho.inp"?
Câu lệnh: freopen("kho.inp", "r", stdin);
Vai trò chính của việc kiểm thử chương trình là gì?
Làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng tuyệt đối của nó.
Một chương trình được kiểm thử với 10 bộ dữ liệu cho 9 lần đúng và 1 lần sai. Ta kết luận gì về chương trình?
Chương trình sai.
Cách tốt nhất và chặt chẽ nhất để chứng minh tính đúng của một thuật toán là gì?
Lập luận (chứng minh) bằng toán học, chẳng hạn như phương pháp quy nạp hoặc bất biến vòng lặp.
Mệnh đề nào được dùng làm bất biến vòng lặp để chứng minh tính đúng của thuật toán sắp xếp chèn tăng dần?
Sau mỗi bước lặp i, dãy con A[0]...A[i] đã được sắp xếp tăng dần.
Hai loại độ phức tạp tính toán phổ biến nhất là gì, và ở cấp phổ thông ta chủ yếu quan tâm loại nào?
Gồm độ phức tạp thời gian và độ phức tạp không gian; trong phạm vi phổ thông ta chủ yếu quan tâm tới độ phức tạp thời gian.
Độ phức tạp thời gian của chương trình thường bị ảnh hưởng trực tiếp bởi yếu tố nào?
Tổng số lần thực hiện các phép toán hoặc câu lệnh trong chương trình.
Trong C++, hàm và thư viện nào được dùng để đo thời gian chạy của một thuật toán?
Hàm high_resolution_clock::now() trong thư viện
Để kiểm thử chương trình tính n!, bộ dữ liệu nào nên được ưu tiên để phát hiện lỗi ở trường hợp biên?
n=0 và n=1.
Để kiểm tra tính đúng của chương trình sắp xếp trong nhiều tình huống, ta nên chọn bộ dữ liệu như thế nào?
Chọn nhiều dạng: dãy ngẫu nhiên, dãy đã sắp xếp, dãy sắp xếp ngược, và dãy có phần tử trùng nhau.
Cho dãy A={3,6,1,8,5,4}, hàm tongchan(A) tính tổng các phần tử chẵn trả về giá trị bao nhiêu?
6+8+4=18.
Hàm dem(n) đếm các ước số thực sự của n (chạy từ 2 đến n−1). Với n=12, hàm dem(12) trả về bao nhiêu?
Trả về 4 (các ước thực sự gồm: 2, 3, 4, 6).
Với dãy đã sắp xếp A={1,3,5,7,9,11,13}, hàm BinarySearch tìm kiếm khóa K=9 trả về chỉ số nào?
Trả về chỉ số 4 (vì A[4]=9).
Cho hàm đệ quy Fibonacci f(n) với f(1)=1,f(2)=1 (hoặc nháp tính bắt đầu: 1, 2, 3, 5, 8). Giá trị của f(6) trong bài kiểm tra trả về là bao nhiêu?
Trả về 8.
Hàm demDoiCho đếm số lần swap của sắp xếp nổi bọt với dãy A={5,2,4,1} trả về kết quả là bao nhiêu?
Trả về 5 lần đổi chỗ.
Thuật toán Euclid g(a, b) tìm ước chung lớn nhất. Với lệnh gọi g(48, 18), hàm trả về giá trị nào?
Trả về 6.
Với một thuật toán có độ phức tạp O(n), khi kích thước dữ liệu n tăng từ 100 lên 200 (gấp đôi) thì số phép toán cần thực hiện thay đổi như thế nào?
Số phép toán cần thực hiện tăng khoảng 2 lần.