NEW
Font size
WorksheetsCâu hỏi về thuật toán sắp xếp
Total questions: 80
Worksheet time: 40mins
Khi sử dụng thuật toán sắp xếp chèn, dãy con bên trải của phần tử đang xét có tính chất gì?
Đã được sắp xếp
Chưa được sắp xếp
Tăng dần và giảm dần xen kẽ
Ngẫu nhiên
Trong sắp xếp chèn, bước nào được thực hiện đầu tiên khi chèn một phần tử vào dãy con đã sắp?
Dịch các phần tử lớn hơn sang phải
Tìm phần tử lớn nhất
Hoán đổi phần tử đầu tiên và cuối cùng
Xóa phần tử nhỏ nhất
Thuật toán sắp xếp chọn có đặc điểm gì nổi bật?
Chọn phần tử lớn nhất (hoặc nhỏ nhất) mỗi lượt
Dịch chuyển toàn bộ dãy
Sử dụng đệ quy
Tính ngẫu nhiên cao
Trong thuật toán sắp xếp chọn, ở mỗi bước thứ i, chương trình thực hiện việc gì?
Chọn phần tử lớn nhất để đưa về cuối dãy
Chọn phần tử nhỏ nhất trong đoạn còn lại để đưa về vị trí thứ 1
Đổi chỗ ngẫu nhiên hai phần tử
Sắp xếp dãy theo thứ tự giảm dần
Trong sắp xếp chọn giảm dần, phần tử nào được đưa về đầu dãy sau mỗi vòng lặp?
Nhỏ nhất
Lớn nhất
Ngẫu nhiên
Phần tử ở giữa
Trong Python, hàm open("diem.inp") có chức năng gì?
Mo file de ghi
Mở file để đọc
Xóa nội dung file
Thêm dữ liệu vào file
Sau khi đọc tệp điểm, danh sách điểm trung bình nên lưu vào kiểu dữ liệu nào?
Chuỗi
Danh sách (list)
Từ điển (dictionary)
Số nguyên
Trong sắp xếp chèn, khi nào vòng lặp dừng?
Khi tìm được vị trí chèn thích hợp
Khi dịch hết các phần tử
Khi tìm được phần tử lớn nhất
Khi danh sách bị đảo ngược
Trong nhiệm vụ 2, giá trị nào sẽ được chọn ở mỗi lượt của thuật toán sắp xếp chọn?
Giá trị lớn nhất còn lại
Giá trị nhỏ nhất
Giá trị trung bình
Giá trị ở giữa
Phát biểu nào đúng về sự khác nhau giữa sắp xếp chọn và sắp xếp chèn?
Sắp xếp chọn luôn nhanh hơn
Sắp xếp chèn tốt hơn khi dữ liệu gần sắp xếp
Sắp xếp chọn dùng cho dữ liệu lớn
Cả hai giống hệt nhau
Hàm float(line) trong Python có tác dụng gì?
Chuyển dòng văn bản thành số thực
Chuyển số thực thành văn bản
Làm tròn số
Kiểm tra kiểu dữ liệu
Trong Python, phương thức insert(i, x) của danh sách làm gì?
Thêm x vào vị trí i
Xóa phần tử ở vị trí i
Hoán đổi hai phần tử
Tìm phần tử lớn nhất
Phát biểu nào đúng với thuật toán sắp xếp chọn?
Số lần hoán đổi tối đa bằng số lượng phần tử
Hoán đổi liên tục các phần tử lân cận
Chỉ thực hiện tối đa một hoán đổi mỗi lượt
Không thực hiện hoán đổi
Phép so sánh nào quan trọng nhất trong sắp xếp chèn?
So sánh phần tử hiện tại với phần tử dứng trước
So sánh phần tử lớn nhất và nhỏ nhất
So sánh phần tử đầu và cuối
So sánh theo ngẫu nhiên
Hàm splitlines() trong Python dùng để?
Cắt chuỗi thành danh sách các dòng
Tính tổng các số
Đọc file
Chuyển số sang chuỗi
Trong nhiệm vụ 1, kết quả sau khi sắp xếp tăng dần là?
Danh sách có số lượng giảm dần
Danh sách có số lượng tăng dần
Danh sách không đổi
Danh sách bị đảo ngược
Phát biểu nào đúng về ưu điểm của sắp xếp chèn?
Dễ cài đặt, tốt khi dữ liệu gần sắp xếp
Luôn nhanh nhất
Phù hợp cho dữ liệu lớn
Dùng cho mọi loại dữ liệu
Trong sắp xếp chọn, điều gì xảy ra sau mỗi lượt?
1 ptu dc đặt đúng vtri
tất cả ptu bị hoán đổi
danh sách ngẫu nhiên
không thay đổi gì
Đâu là nhược điểm của thuật toán nổi bọt?
Tốn nhiều bộ nhớ
Tốc độ chậm khi danh sách dài
Khó cài đặt
Không chính xác
Trong nhiệm vụ 2, để sắp xếp giảm dần, ta cần tìm?
Phần tử nhỏ nhất
Phần tử lớn nhất
Phần tử trung bình
Phần tử ngẫu nhiên
Mục tiêu của kiểm thử chương trình là gì?
Chứng minh tính đúng tuyệt đối của chương trình
Tìm và sửa lỗi trong chương trình
Tăng số lượng dữ liệu đầu vào
Rút gọn chương trình
Phương pháp nào có thể chứng minh được tính đúng của thuật toán?
Kiểm thử với bộ dữ liệu mẫu
Lặp lại nhiều lần kiểm thử
Dùng bất biến vòng lặp và quy nạp toán học
So sánh với các chương trình khác
Độ phức tạp tính toán gồm mấy yếu tố chính?
1
2
3
4
Độ phức tạp thời gian phụ thuộc vào yếu tố nào?
Số lần thực hiện các phép toán/ câu lệnh
Số lần nhập dữ liệu
Dung lượng ổ cứng
Tốc độ bàn phím
Mục đích của phương pháp kiểm thử bằng bộ dữ liệu là gì?
Chứng minh thuật toán đúng
Kiểm tra tính đúng với nhiều tình huống
Giảm kích thước chương trình
Tăng tốc độ xử lý
Khi kiểm thử không phát hiện lỗi, ta có thể kết luận gì?
Chương trình hoàn toàn đúng
Chương trình có thể còn lỗi
Chương trình sai
Chương trình cần viết lại
Độ phức tạp không gian là gì?
Thời gian thực hiện chương trình
Dung lượng bộ nhớ cần dùng
Kích thước của màn hình
Tốc
Thuật toán/Chương trình được coi là hiệu quả khi:
Chạy chậm, tiêu tốn ít bộ nhớ
Tốn nhiều bộ nhớ, nhanh
Thời gian và bộ nhớ tiêu tốn ít
Chỉ cần chạy được
Bất biến vòng lặp thường dùng để:
Kiểm tra bộ nhớ
Chứng minh tính đúng thuật toán
Tinh tốc độ xử lý
Tính tổng số dòng lệnh
Để kiểm tra tính đúng chương trình, cách nào sau đây chưa đủ đảm bảo?
Chạy với nhiều bộ dữ liệu kiểm thử
Phân tích thuật toán bằng logic
Kiểm tra thủ công từng bước
Chi kiểm thử 1 dữ liệu
Độ phức tạp của chương trình phụ thuộc chủ yếu vào:
Dung lượng ổ cứng
Cấu trúc dữ liệu và thuật toán sử dụng
Màu sắc giao diện
Tên biến
Phát biểu nào dùng về kiểm thử chương trình?
Chứng minh được tính đúng tuyệt đối
Chỉ giúp phát hiện lỗi
Chứng minh đúng nhờ so sánh với chương trình khác
Giảm bộ nhớ cần dùng
Đánh giá hiệu quả chương trình KHÔNG bao gồm:
Tính rõ ràng
Tính dễ hiểu
Tính bất biến
Tính dễ bảo trì
Quy trình đánh giá hiệu quả chương trình phổ thông thường dựa vào:
Độ phức tạp thời gian
Số dòng code
Giao diện màu sắc
Phần mềm vẽ đồ thị
Tiêu chí nào sau đây KHÔNG đánh giá hiệu quả chương trình?
Tính dễ bảo trì
Số dòng lệnh
Tính rõ ràng
Tính dễ cài đặt
Phép quy nạp toán học thường dùng trong:
Thiết kế giao diện
Chứng minh thuật toán
Kiểm tra lỗi cú pháp
Tính toán tốc độ
Câu 37: Đối với các dịch vụ trực tuyến, điều quan trọng nhất là:
Tính dễ bảo trì và độ tin cậy
Tốc độ đánh máy
Màu nền đẹp
Ít dòng code
Câu 38: Phát biểu nào sau đây đúng?
Kiểm thử càng nhiều bộ dữ liệu càng tăng độ tin cậy
Kiểm thử 1 lần là đủ
Không cần kiểm thử với dữ liệu sai
Chỉ cần kiểm thử với dữ liệu đúng
Câu 39: Một chương trình tối ưu là chương trình có:
Độ phức tạp thấp
Số dòng lệnh dài
Giao diện đẹp
Nhiều hàm
Câu 40: Đánh giá độ phức tạp thời gian thường dựa vào:
Số lần thực hiện phép toán
Dung lượng tệp
Số ký tự tên biến
Số hình ảnh trên giao diện
Câu 41: Khi đánh giá thời gian thực hiện chương trình mà không cần chạy chương trình, ta làm gì?
Đo thời gian thực tế khi chạy chương trình
Tính tổng thời gian các phép tính và lệnh đơn của chương trình
Dùng đồng hồ đo thời gian
Cài đặt phần mềm kiểm thử
Câu 42: Trong phân tích thời gian chương trình, mỗi phép tính hoặc lệnh đơn thường được tính bằng:
Một đơn vị bộ nhớ
Một đơn vị thời gian
Một giây
Một vòng lặp
Câu 43: Tổng thời gian chạy của chương trình I là:
n + 1
n + 2
n + 3
n + 4
Câu 44: Tổng thời gian chạy của chương trình 2 là:
n^2 + 3
n + 3
n + 2
n2 + 2
Câu 45: Trong chương trình, phép toán thực hiện nhiều nhất và ảnh hưởng chính đến thời gian được gọi là:
Phép toán ngẫu nhiên
Phép toán tích cực
Phép toán bị động
Phép toán phụ
Hàm độ phức tạp thời gian của chương trình 1 được kí hiệu là:
O(n2)
O(1)
O(n)
O(log n)
Hàm độ phức tạp thời gian của chương trình 2 được kí hiệu là:
O(n^2)
O(1)
O(n)
O(log n)
Kí hiệu O-lớn dùng để:
Tính toán kết quả
Đo lường độ chính xác
Phân tích và so sánh bậc hàm thời gian
Đếm số vòng lặp
Quy tắc cộng trong tỉnh độ phức tạp thời gian là:
O(f(n) + g(n)) = O(f(n))
O(f(n)+g(n)) = O(g(n))
O(f(n)+g(n)) = O(max(f(n), g(n)))
O(f(n) + g(n)) = O(f(n)g(n))
Quy tắc nhân với hằng số là:
O(C.f(n)) = O(C)
O(C.f(n)) = O(f(n))
O(C.f(n))=C
O(C.f(n)) = C.f(n)
Quy tắc nhân trong độ phức tạp thời gian với hàm số là:
O(f(n).g(n)) = O(f(n))
O(f(n).g(n)) = O(g(n))
O(f(n).g(n)) = O(f(n).O(g(n)))
O(f(n).g(n)) = O(1)
Trong ví dụ, tại sao ta chọn c = 2 và n0 = 3 cho T1(n)=n+3?
Vì 2 là hằng số bất kì và 3 là số nhỏ nhất
Vì đảm bảo T1(n)<c.n khi n>10
Vì giúp độ phức tạp tăng nhanh hơn
Vì giảm số phép tính
Khi n rất lớn, bậc của O(n2) so với O(n) là:
Nhỏ hơn
Lớn hon
Bằng nhau
Không xác định
Trong chương trình 2, tổng số vòng lặp là:
n
n2
2n
2n2
Nếu chương trình có một vòng lặp n lần, độ phức tạp là:
O(1)
O(n)
O(n2)
O(log n)
Nếu chương trình có hai vòng lặp lồng nhau n lần, độ phức tạp là:
O(1)
O(n)
O(n2)
O(log n)
Tại sao phải phân tích độ phức tạp thuật toán?
Để tối ưu bộ nhớ
Để biết độ khó của chương trình
Để biết chương trình có chạy nhanh, hiệu quả không
Để cài đặt phần mềm
Khi nào dùng quy tắc cộng trong tính độ phức tạp?
Khi có hai đoạn chương trình nối tiếp
Khi có hai vòng lặp lồng nhau
Khi nhân hai hàm
Khi cộng hằng số
Độ phức tạp thời gian thường phụ thuộc vào:
Dữ liệu đầu vào
Màu sắc giao diện
Dung lượng ổ cứng
Thời tiết
O-lớn biểu diễn độ phức tạp khi:
n tiến về 0
n tiến về vô cùng
n=1
n=10
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự trong trường hợp tồi nhất là:
O(1)
O(n)
O(n2)
O(log n)
Trong tìm kiếm tuần tự, phép so sánh ở dòng nào là phép toán tích cực?
Dòng 2
Dòng 3
Dòng 4
Dòng 5
Tổng số phép toán cơ bản của thuật toán tìm kiếm tuần tự trong trường hợp tồi nhất là:
n
n+1
n2
1
Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là:
Tuyến tính
Bình phương
Lôgarit
Hằng số
Trong sắp xếp chọn, số vòng lặp bên ngoài chạy từ:
0 đến n-2
0 đến n-1
1 đến n
1 đến n-1
Ở mỗi bước của vòng lặp ngoài trong sắp xếp chọn, ta cần thực hiện:
Chọn phần tử lớn nhất
Chọn phần tử nhỏ nhất
Sắp xếp lại toàn bộ mảng
Không làm gì
Số lần lặp của vòng lặp trong của sắp xếp chọn ở bước 1 là:
n-i
n-1
i
n-i-1
Trong sắp xếp chọn, phép so sánh tại dòng 6 tiêu tốn:
1 đơn vị thời gian
2 đơn vị thời gian
3 đơn vị thời gian
0,5 đv tgian
Trong sắp xếp chọn, mỗi bước lặp của vòng lặp trong tốn tối đa:
1 đon vi
2 đơn vị
3 đơn vị
n don vi
Lệnh đổi chỗ ở dòng 8 trong sắp xếp chọn tiêu tốn:
1 đơn vị
2 đơn vị
3 đơn vị
n đơn vị
Tổng thời gian thực hiện sắp xếp chọn được tính là:
n
n2
n2+3n-3
2n
Độ phức tạp O-lớn của sắp xếp chọn là
O(n)
O(n2)
O(1)
O(log n)
Trong phân tích độ phức tạp, phép toán được thực hiện nhiều nhất gọi là:
Phép toán tích cực
Phép toán bị động
Phép toán ngẫu nhiên
Phép toán chính
Trong bài toán sắp xếp chọn, phép toán tích cực là:
Phép so sánh
Phép cộng
Phép nhân
Phép chia
Khi xác định độ phức tạp thời gian, hệ số hằng số:
Luôn giữ nguyên
Có thể bỏ qua
Luôn nhân thêm
Luôn chia
Nếu T(n) = n^ + 3n - 3, thì T(n)=?
O(n2)
O(n)
O(1)
O(n3)
Phép cộng có thể được coi là
Phép toán tích cực trong sắp xếp chọn
Phép toán tích cực trong tìm kiếm tuần tự
Không phải phép tích cực
Tất cả sai
Sắp xếp chọn hoạt động hiệu quả nhất khi
Mảng đã được sắp xếp
Mảng ngẫu nhiên
Mảng nghịch
Không có sự khác biệt
Tìm kiếm tuần tự hoạt động hiệu quả nhất khi:
Phần tử cần tìm ở đầu mảng
Phần tử cần tìm ở cuối mảng
Không tìm thấy
Không có sự khác biệt
Sắp xếp chọn thuộc loại:
Thuật toán sắp xếp đơn giản
Thuật toán chia để trị
Thuật toán đệ quy
Thuật toán tìm kiếm
