Đề Cương Ôn Tập Kiểm Tra Giữa Kỳ Tin Học 11 - Bài 22 & 23

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/30

flashcard set

Earn XP

Description and Tags

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.

31 Terms

1
New cards

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=1i = 1).

2
New cards

Ý 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.

3
New cards

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.

4
New cards

Để 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]<valueA[j] < \text{value}.

5
New cards

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ỗ.

6
New cards

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.

7
New cards

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.

8
New cards

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ả 44 lượt đổi chỗ.

9
New cards

Với dãy gồm nn 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?

n(n−1)2\frac{n(n - 1)}{2} phép so sánh.

10
New cards

Thuật toán sắp xếp chọn (Selection Sort) trên dãy gồm nn 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−1n - 1 phép đổi chỗ.

11
New cards

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=0i = 0), dãy trở thành gì?

Dãy trở thành: 1, 15, 31, 9, 78, 42.

12
New cards

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.

13
New cards

Độ 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)O(n^2).

14
New cards

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.

15
New cards

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);

16
New cards

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ó.

17
New cards

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.

18
New cards

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.

19
New cards

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 ii, dãy con A[0]...A[i]A[0] \text{...} A[i] đã được sắp xếp tăng dần.

20
New cards

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.

21
New cards

Độ 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.

22
New cards

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 .

23
New cards

Để kiểm thử chương trình tính n!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=0n = 0 và n=1n = 1.

24
New cards

Để 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.

25
New cards

Cho dãy A={3,6,1,8,5,4}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=186 + 8 + 4 = 18.

26
New cards

Hàm dem(n) đếm các ước số thực sự của nn (chạy từ 22 đến n−1n - 1). Với n=12n = 12, hàm dem(12) trả về bao nhiêu?

Trả về 44 (các ước thực sự gồm: 2, 3, 4, 6).

27
New cards

Với dãy đã sắp xếp A={1,3,5,7,9,11,13}A = \{1, 3, 5, 7, 9, 11, 13\}, hàm BinarySearch tìm kiếm khóa K=9K = 9 trả về chỉ số nào?

Trả về chỉ số 44 (vì A[4]=9A[4] = 9).

28
New cards

Cho hàm đệ quy Fibonacci f(n)f(n) với f(1)=1,f(2)=1f(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)f(6) trong bài kiểm tra trả về là bao nhiêu?

Trả về 88.

29
New cards

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}A = \{5, 2, 4, 1\} trả về kết quả là bao nhiêu?

Trả về 55 lần đổi chỗ.

30
New cards

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ề 66.

31
New cards

Với một thuật toán có độ phức tạp O(n)O(n), khi kích thước dữ liệu nn 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 22 lần.