Câu hỏi về cấu trúc dữ liệu và giải thuật

Tìm mô tả đúng nhất cho hàm TinhTong sau:
int TinhTong(int N)
{ int so = 2; int tong = 0; int dem = 0; while (dem <N)
{
if (KiemTra(so) == 1)
{
tong = tong + so;
dem ++;
}
so = so + 1;
}
return tong;
} Trong đó
int KiemTra(int so)
{
for (int i = 2; i<so; i++)
if (so%i == 0)
return 0;
return 1;
}

• Hàm tính tổng N số nguyên đầu tiên

• Hàm tính tổng N số nguyên tố nhỏ hơn N

• Cả a, b đều sai

• Cả a, b đều đúng

Mối quan hệ giữa cấu trúc dữ liệu và giải thuật có thể minh họa bằng đẳng thức:

• Cấu trúc dữ liệu + Giải thuật = Chương trình

• Cấu trúc dữ liệu + Chương trình = Giải thuật

• Chương trình + Giải thuật = Cấu trúc dữ liệu

• Cấu trúc dữ liệu = Chương trình

Các tiêu chuẩn đánh giá cấu trúc dữ liệu. Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí:

• Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong)

• Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán

• Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu

• Cả a, b, c đều đúng

Đoạn mã giả dưới đây mô tả thuật toán gì? Thuật toán: B1: k = 1 B2: IF M[k] == X AND k != N B2.1: k++ B2.2: Lặp lại B2 B3: IF k < N Thông báo tìm thấy tại vị trí k B4: ELSE Không tìm thấy. B5: Kết thúc

• Tìm nhị phân phần tử có giá trị X

• Tìm phần tử nhỏ nhất của mảng M bao gồm N phần tử

• Tìm tuyến tính phần tử có giá trị X

• Cả a, b, c đều sai

Cho hàm tìm kiếm tuyến tính như sau: int TimKiem (int M[], int N, int X) { int k = 0; M[N] = X; while (M[k] != X) k++; if (k < N) return (k); return (-1); } Chọn câu đúng nhất:

• Hàm sẽ trả về 0 nếu không tìm thấy phần tử có giá trị là X

• Hàm sẽ trả về 1 nếu tìm thấy phần tử có giá trị là X

• Hàm sẽ trả về -1 nếu không tìm thấy phần tử có giá trị là X

• Hàm sẽ trả về 1 nếu không tìm thấy phần tử có giá trị là X

Xét thủ tục sau: int TimKiemNP (int M[], int First, int Last, int X) { if (First > Last) return (-1); int Mid = (First + Last)/2; if (X == M[Mid]) return (Mid); if (X < M[Mid]) return(TimKiemNP (M, First, Mid - 1, X)); else return(TimKiemNP (M, Mid + 1, Last, X)); } Lựa chọn câu đúng nhất để mô tả thủ tục trên:

• A. Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last

• B. Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last

• C. Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

• D. Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

Lựa chọn câu đúng nhất để mô tả thủ tục trên:

• Thủ tục hỗ trợ tìm kiếm phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last

• Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ First đến chỉ số Last

• Thủ tục hỗ trợ tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

• Thủ tục hỗ trợ tìm kiếm không đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ số từ Last đến chỉ số First

Chọn câu đúng nhất để mô tả thuật toán sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử:

• Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N-1 lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng

• Đi từ đầu mảng về cuối mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng.

• Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nó thì hai phần tử này sẽ được đổi chỗ cho nhau. Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Sau N lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng

• Cả a, b, c đều sai

Hàm mô tả sắp xếp nổi bọt (Bubble Sort) trên mảng M có N phần tử void BubbleSort(int M[], int N) { [2] int Temp; [3] for (int I = 0; I < N-1; I++) [4] ………………………………….. [5] if (M[J] < M[J-1]) [6] { [7] Temp = M[J]; [8] M[J] = M[J-1]; [9] M[J-1] = Temp; [10] } [11] return; [12] } [13] Lệnh nào sau đây sẽ được đưa vào dòng lệnh thứ [5] của thủ tục:

• for (int J = N-1; J > I; J++)

• for (int J = N; J < I; J--)

• for (int J = N-1; J > I; J--)

• Không có dòng lệnh nào phù hợp, không cần thêm vào thuật toán vẫn chạy đúng

Chọn câu lệnh thích hợp để đưa vào [1], [2], [3] với mục tiêu hoán vị M[K] và M[PosMin]

• Temp = M[K] ; Temp = M[PosMin]; M[PosMin] = Temp;

• M[K] = Temp; M[K] = M[PosMin]; M[PosMin] = Temp ;

• Temp = M[K] ; M[PosMin] = M[K]; M[PosMin] = Temp ;

• Temp = M[K] ; M[K] = M[PosMin]; M[PosMin] = Temp ;