On tap CTDL

Những ưu điểm của phương pháp vét cạn là gì? (Chọn 3)

• Luôn đảm bảo tìm ra nghiệm chính xác.

• Đòi hỏi rất ít bộ nhớ

• Cài đặt đơn giản.

• Thời gian thực hiện nhanh

Trong bài toán 8 quân hậu, đường chéo "huyền" (song song với đường chéo phụ) có đặc điểm gì?

• Tổng giá trị chỉ số hàng và chỉ số cột bằng hằng số (i+j)

• Hiệu giá trị chỉ số hàng và chỉ số cột bằng hằng số (i-j)

• Chỉ số hàng bằng chỉ số cột (i==j)

Nếu T1(n) và T2(n) là thời gian thực hiện của 2 đoạn chương trình P1 và P2 trong đó (T1(n) = O(f(n)); T2 = (O(g(n))); thì thời gian thực hiện P1 và P2 lồng nhau là ?

• T(n)=O(max(f(n),g(n)))

• T(n)=O(1)

• T(n)= O(f(n).g(n))

• T(n)= O(min(f(n),g(n)))

Giả sử có đoạn chương trình sau

for( i = 1;i <=n ;i++)

x = x + 1;

Thời gian thực hiện chương trình là ?

• O(n.1) = O(n)

• O(max(n-1)) = O(n-1)

• O(n.n) = O(n2)

• O(min(n.i)) = O(i)

Sau mỗi lần phân hoạch, phương pháp Quick Sort chia dãy thành…

• Hai nửa bằng nhau

• Hai nửa gồm các phần tử đối xứng nhau

• Một nửa dãy gồm các phần tử nhỏ hơn chốt, một nửa gồm các phần tử lớn hoạc bằng chốt

• Các dãy mỗi dãy gồm 1 phần tử

Các bước sau đây thể hiện thuật toán sắp xếp nào ?

• Bước 1: i = 1;

• Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]

• Bước 3 : Hoán vị a[min] và a[i]

• Bước 4 : Nếu i < N-1 thì i = i+1; Lặp lại Bước 2

Ngược lại: Dừng. //N-1 phần tử đã nằm đúng vị trí.

• Sắp xếp chọn

• Sắp xếp chèn

• Sắp xếp nổi bọt

• Sắp xếp nhanh

Giả sử X là 1 véc tơ lưu vị trí đặt quân hậu trên hàng i, A là véc tơ đánh dấu tình trạng cột j có còn trống không (A[j]=1 nghĩa là cột j còn trống). Nếu đặt quân hậu vào hàng i cột j thì phải cập nhật lại giá trị nào sau đây?

• X[i]=j; A[j]=0;

• X[j]=i; A[i]=0

• X[i] = A[j] =1

Nhược điểm của việc sử dụng hàm đệ qui là …….

• Tốn bộ nhớ và gọi hàm quá nhiều

• Không hiệu quả.

• Nhiều dòng lệnh.

• Cả 3 đáp án sai

Chọn đáp án đúng điền vào chỗ chấm: “Chiến lược vét cạn là …”

• Thử tất cả các khả năng xem khả năng nào là nghiệm đúng của bài toán cần giải quyết.

• Tìm tất cả các nghiệm đúng của bài toán cần giải quyết.

• Thử tất cả các khả năng xem cái nào không phải là nghiệm đúng của bài toán cần giải quyết thì loại.

Cho dãy số sau có 9 phần tử.

12 4 20 11 15 27 17 9 13

Sử dụng phương pháp sắp xếp chọn (Selection Sort) để sắp xếp dãy này theo thứ tự không giảm. Khi kết thúc bước thứ 2 thì phần tử có giá trị 9 ở vị trí thứ mấy (vị trí của các phần tử trong dãy bắt đầu 1)?

• 1

• 2

• 3

• 4