NEW
Font size
WorksheetsPhần 8: Thuật toán, lập trình, chương trình
Total questions: 64
Worksheet time: 32mins
Thuật toán phải có đặc điểm:
Dừng sau vô hạn bước
Dừng sau hữu hạn bước
Không cần dừng
Các bước mập mờ
Tính xác định của thuật toán nghĩa là:
Mỗi bước có thể thực hiện theo nhiều cách khác nhau
Mỗi bước của thuật toán được xác định rõ ràng
Mỗi người hiểu theo cách riêng
Có thể bỏ qua một số bước
Một thuật toán có thể có nhiều cách biểu diễn khác nhau không?
Không
Có
Tùy ngôn ngữ
Không cần thiết
Các cách biểu diễn thuật toán phổ biến là:
Lưu đồ và mã giả
Biểu đồ Use Case
Sơ đồ lớp
Sơ đồ mạng
Mục đích của lưu đồ (flowchart) là:
Biểu diễn cấu trúc dữ liệu
Minh họa trình tự thực hiện các bước của thuật toán
Viết mã nguồn
Thống kê dữ liệu
Mã giả (pseudocode) thường dùng để:
Mô tả ý tưởng thuật toán một cách gần gũi với lập trình
Trình bày kết quả thực nghiệm
Biên dịch chương trình
Định nghĩa biến
Trong lưu đồ, hình thoi thể hiện:
Khởi đầu
Kết thúc
Lệnh gán
Kiểm tra điều kiện
Độ phức tạp thời gian của thuật toán thể hiện:
Số lượng phép toán cần thực hiện
Số dòng mã
Dung lượng bộ nhớ
Tốc độ CPU
Độ phức tạp không gian (bộ nhớ) thể hiện:
Thời gian chạy
Số biến hoặc vùng nhớ sử dụng
Số lệnh
Kết quả đầu ra
Một thuật toán được xem là tốt khi:
Đúng và nhanh
Dễ nhìn
Có nhiều bước
Khó hiểu
Ký hiệu Big-O dùng để:
Chỉ tốc độ CPU
Mô tả độ phức tạp thời gian hoặc không gian
Đo tốc độ mạng
Kiểm tra lỗi
Nếu thuật toán có độ phức tạp O(n²), khi n tăng gấp đôi thì thời gian thực hiện:
Tăng gấp đôi
Tăng gấp bốn
Giữ nguyên
Giảm đi
Chiến lược “Chia để trị” (Divide and Conquer) hoạt động bằng cách:
Giải toàn bộ bài toán một lần
Chia bài toán thành các bài toán con nhỏ hơn
Dùng thuật toán ngẫu nhiên
Không chia nhỏ
Chiến lược “Tham lam” (Greedy) có đặc điểm:
Chọn phương án tối ưu toàn cục ngay từ đầu
Chọn phương án tối ưu cục bộ tại mỗi bước
Luôn chọn phương án cuối cùng
Không tối ưu hóa
Thuật toán quy hoạch động (Dynamic Programming) dựa vào:
Lưu trữ kết quả các bài toán con
Chọn ngẫu nhiên
Thử tất cả khả năng
Đệ quy vô hạn
Chương trình là:
Một tập hợp câu lệnh cụ thể của ngôn ngữ lập trình
Một sơ đồ thuật toán
Một phần cứng
Một hệ điều hành
Lập trình là quá trình:
Viết và chạy thử chương trình dựa trên thuật toán
Viết báo cáo
Chỉnh sửa phần cứng
Giao tiếp với người dùng
Lỗi cú pháp xảy ra khi:
Sai logic
Sai cấu trúc ngôn ngữ lập trình
Kết quả sai
Dữ liệu sai
Gỡ lỗi (debug) là:
Xoá dữ liệu
Tìm và sửa lỗi trong chương trình
Viết lại chương trình
Dừng chương trình
Ngôn ngữ lập trình bậc cao có đặc điểm:
Gần với ngôn ngữ máy
Gần với ngôn ngữ tự nhiên
Khó hiểu
Không biên dịch được
Bước đầu tiên khi viết chương trình là:
Phân tích bài toán
Gỡ lỗi
Viết mã
Biên dịch
Sau khi viết xong chương trình, ta cần:
Nộp ngay
Chạy thử và kiểm tra
Xoá đi
Không cần kiểm tra
Việc thiết kế thuật toán là bước:
A. Trước khi lập trình
B. Sau khi chạy
C. Trong lúc biên dịch
D. Khi xuất kết quả
Sau khi chương trình chạy đúng, bước cuối cùng là:
Viết báo cáo hoặc đóng gói chương trình
Xoá dữ liệu
Dùng máy
Lặp lại
Môi trường lập trình là:
Tập hợp công cụ hỗ trợ lập trình
Một ngôn ngữ mới
Một thuật toán
Hệ điều hành
Ví dụ về môi trường lập trình:
Visual Studio
Photoshop
Excel
AutoCAD
IDE là viết tắt của:
Integrated Design Environment
Integrated Development Environment
Internal Debug Environment
Intelligent Data Engine
Một IDE thường bao gồm:
Trình soạn thảo mã, trình biên dịch, và trình gỡ lỗi
Hệ điều hành
Bộ vi xử lý
Mạng Internet
Lợi ích của IDE là:
Giảm tốc độ lập trình
Hỗ trợ biên dịch và gỡ lỗi nhanh
Chỉ để viết văn bản
Không cần thiết
Tính đúng đắn của thuật toán được đảm bảo khi:
Chạy không lỗi
Cho kết quả đúng với mọi dữ liệu đầu vào
Nhanh hơn các thuật toán khác
Không sử dụng biến
Trong lập trình, thiết kế chương trình con (hàm) giúp:
Giảm khả năng tái sử dụng
Dễ bảo trì, dễ đọc
Tăng độ phức tạp
Giảm hiệu suất
Thuật toán đệ quy cần có:
Gọi lại chính nó
Vòng lặp vô hạn
Không cần điều kiện dừng
Biến toàn cục
Nếu một thuật toán có độ phức tạp O(1), nghĩa là:
Không phụ thuộc vào kích thước dữ liệu
Tỷ lệ thuận với n
Tuyến tính
Rất chậm
Tại sao cần phân tích độ phức tạp thuật toán?
Để chọn thuật toán tối ưu nhất
Để viết chương trình dễ hơn
Để dịch sang ngôn ngữ máy
Để tạo giao diện
Khi một bài toán có nhiều cách giải, việc chọn thuật toán dựa trên:
Sự quen thuộc
Hiệu quả tính toán và bộ nhớ
Độ dài mã
Màu sắc IDE
Kỹ thuật “Backtracking” được dùng để:
Tối ưu hoá tuyến tính
Tìm tất cả lời giải có thể bằng cách thử và loại bỏ
Đếm số phần tử
Giảm độ phức tạp
Một thuật toán tham lam không luôn đảm bảo tối ưu vì:
Chỉ chọn tối ưu cục bộ
Không dừng
Không dùng đệ quy
Không lưu dữ liệu
Khi thuật toán có độ phức tạp O(2n) , nó thuộc loại:
Tuyến tính
Lũy thừa
Logarithmic
Hằng số
Mã giả giúp cho:
Chuyển ý tưởng thành code dễ dàng hơn
Làm báo cáo
Gỡ lỗi
Thiết kế giao diện
Trong thuật toán, “break” có nghĩa là:
Dừng hẳn chương trình
Thoát khỏi vòng lặp hiện tại
Quay lại đầu vòng lặp
Tiếp tục bước sau
Khi viết thuật toán, việc xác định rõ đầu vào và đầu ra giúp:
Kiểm tra tính đúng đắn
Làm đẹp mã
Giảm số dòng
Tăng tốc độ
Cho mã giả: Tổng ← 0 For i ← 1 to 5 Tổng ← Tổng + i EndFor Kết quả cuối cùng là:
A. 5
B. 10
C. 15
D. 20
Cho mã giả: If x > 0 then y ← 1 Else y ← -1 EndIf Nếu x = -3 thì y bằng:
1
-1
0
Không xác định
Cho mã giả: For i ← 1 to 3 print(i * 2) EndFor Kết quả in ra:
A. 2, 4, 6
B. 1, 2, 3
C. 3, 6, 9
D. 6, 4, 2
Cho mã giả: f ← 1 For i ← 1 to n f ← f * i EndFor Nếu n = 4 thì f = ?
A. 12
B. 16
C. 24
D. 10
Cho mã giả: a ← 10 b ← 5 If a < b then max ← b Else max ← a EndIf Giá trị của max là:
5
10
15
0
Cho mã giả: If n mod 2 = 0 then Print("Even") Else Print("Odd") EndIf Nếu n = 9 thì in ra:
Even
Odd
9
Error
Cho mã giả:
i ← 1
While i < 4 do
Print(i)
i ← i + 1
EndWhile
Kết quả in ra:
1, 2, 3
2, 3, 4
0, 1, 2
1, 2, 3, 4
Cho mã giả: sum ← 0 For i ← 1 to 3 sum ← sum + i*i EndFor Kết quả:
6
14
9
10
Cho mã giả: count ← 0 For i ← 1 to 5 If i mod 2 = 0 then count ← count + 1 EndIf EndFor Giá trị count là:
A. 2
B. 3
C. 4
D. 5
Cho mã giả: max ← a If b > max then max ← b If c > max then max ← c Nếu a=5, b=9, c=7 thì max =
5
7
9
12
Cho mã giả trong C/C++: int x = 5, y = 10; x = x + y - (y = x); printf("%d %d", x, y); Kết quả in ra là:
5 10
0 5
10 5
5 5
Cho mã giả trong C/C++: int i, sum = 0; for(i = 1; i <= 5; i++) if(i % 2 == 0) sum += i; printf("%d", sum); Kết quả là:
A. 6
B. 8
C. 6
D. 10
Cho mã giả trong C/C++: int i = 0; while(i < 5) { if(i == 3) break; i++; } printf("%d", i); Kết quả là:
A. 3
B. 4
C. 5
D. 0
Cho mã giả trong C/C++: int a = 2, b = 3, c = 4; printf("%d", a + b * c / a);
A. 7
B. 8
C. 9
D. 12
Cho mã giả trong C/C++: int n = 5, fact = 1; for(int i = 1; i <= n; i++) fact *= i; printf("%d", fact); Kết quả là:
A. 24
B. 120
C. 60
D. 720
Cho mã giả trong C/C++: int arr[5] = {1, 2, 3, 4, 5}; int sum = 0; for(int i = 0; i < 5; i += 2) sum += arr[i]; printf("%d", sum); Kết quả là:
A. 6
B. 9
C. 10
D. 8
Cho mã giả trong C/C++: int a = 10, b = 20; if(a = b) printf("Equal"); else printf("Not Equal"); Kết quả là:
Equal
Not Equal
Error
Không in gì
Cho mã giả trong C/C++: int i = 1; do { printf("%d ", i); i += 2; } while(i < 8);
1 2 3 4 5 6 7
1 3 5 7
1 3 5
2 4 6 8
Cho mã giả trong C/C++; void func(int n) { if(n == 0) return; printf("%d ", n); func(n - 1); } int main() { func(3); } Kết quả là:
A. 3 2 1
B. 1 2 3
C. 3 3 3
D. 0 1 2 3
Cho mã giả trong C/C++; int f(int n) { if(n <= 1) return 1; return n * f(n - 2); } int main() { printf("%d", f(5)); } Kết quả là:
A. 15
B. 15
C. 10
D. 120
Cho mã giả trong C/C++; int f(int n) { if(n == 1) return 1; else return n + f(n - 1); } int main() { printf("%d", f(4)); } Kết quả là:
A. 6
B. 10
C. 4
D. 7
Cho mã giả trong C/C++; int a = 10; if(a > 5) if(a < 15) printf("A"); else printf("B"); else printf("C"); Kết quả là:
A. A
B. B
C. C
D. Không in gì
Cho mã giả trong C/C++; int a = 0, b = 1, c, i; printf("%d %d ", a, b); for(i = 2; i < 6; i++) { c = a + b; printf("%d ", c); a = b; b = c; } Kết quả là:
A. 0 1 1 2 3 5
B. 0 1 1 3 5 8
0 1 2 3 5 8
1 1 2 3 5 8
