Chương 1: Tổng quan về Cấu trúc dữ liệu và giải thuật

Câu hỏi mức 1 : 12 câu
Câu 1: Thời gian thực hiện thuật toán thường được tính trong các trường hợp nào sau đây:
a.Trường hợp tốt nhất, xấu nhất hoặc trung bình.
Câu 2: Đặc trưng của thuật toán
a. Tất cả ý nêu ra
Câu 3: Tên kiểu nguyên là:
a. Integer
Câu 4: Các thuộc tính của một kiểu dữ liệu?
a. Tất cả các thuộc tính đưa ra
Câu 5: Kích thước lưu trữ kiểu số nguyên là:
a. 2 byte
Câu 6: Với giả thiết về T1(n) và T2(n là thời gian chạy của 2 đoạn chương trình P1 và P2, nếu 2 đoạn chương trình P1 và P2 không được thực hiện tuần tự mà lồng nhau thì thời gian chạy tổng thể sẽ là T1(n).T2(n) = O(f(n).(g(n)). Đây là quy tắc nào?
a. Quy tắc nhân
Câu 7: Giả sử T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1 và P2, trong đó T1(n) là O(f(n)) và T2(n) là O(g(n)). Khi đó, thời gian thực hiện của 2 đoạn chương trình trình nối tiếp P1, P2: là :
a.O(max(f(n), g(n))).
Câu 8: Xác định độ phức tạp tính toán
Nếu tương ứng với P1 và P2 là T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện P1 và P2 lồng nhau sẽ là:
a. T1(n)T2(n) = O(f(n)g(n))
Câu 9: Miền giá trị của Kiểu số nguyên là?
a. -32768 .. 32767
Câu 10: Chọn câu trả lời đúng nhất về thuật toán
a. Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra
Câu 11: Giả sử T1(n) và T2(n) là thời gian chạy của 2 đoạn chương trình P1 và P2, trong đó T1(n) là O(f(n)) và T2(n) là O(g(n)). Khi đó, thời gian thực hiện của 2 đoạn chương trình trình nối tiếp P1, P2 là O(max(f(n), g(n))). Đây là quy tắc nào?
a.Quy tắc cộng
Câu 12: Tập các toán tử kiểu số nguyên là:
a. +, -, *, /, %, các phép so sánh
Câu13* : Thời gian chạy của 1 chương trình phụ thuộc vào các yếu tố:
a. Dữ liệu đầu vào,chất lượng của mã máy được tạo ra bởi chương trình dịch,tốc độ thực thi lệnh của máy,độ phức tạp về thời gian của thuật toán
Câu 14*: Giả sử ta có 3 bước thực hiện chương trình lần lượt có thời gian chạy là O(n2), O(n3), O(nlog n). Khi đó, thời gian chạy của 2 đoạn chương trình là:
a.O(n3)
Câu 15*: Giả sử ta có 3 bước thực hiện chương trình lần lượt có thời gian chạy là O(n2), O(n3), O(nlog n). Khi đó, thời gian chạy của 3 đoạn chương trình là:
a. O(n3)
.Câu 16*: Thời gian thực hiện các lệnh đơn : gán, đọc, viết là"
a. O(1)
Câu 17*: Thời gian thực hiện lệnh hợp thành {.....} được xác định
a. quy tắc tổng
Câu 18*: Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì _
If E Then S1 Else S2
"Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là
a. O(max (f()n), g(n)))
Câu 19*: Nếu S là câu lệnh và E là biểu thức logic thì while E do S
"Giả sử thời gian thực hiện lệnh S (thân của while) là O(f(n)) . Giả sử g(n) là số tối đa các lần thực hiện lệnh while _
"Khi đó thời gian thực hiện lệnh while
a. O(f(n)g(n)).
Câu 20*: Thời gian thực hiện chuỗi tuần tự các lệnh được xác định theo quy tắc cộng cấp độ tăng. Có nghĩa là thời gian thực hiện của cả nhóm lệnh tuần tự được tính là thời gian thực hiện của lệnh :
a.Lớn nhất
Câu 21**: Cho đoạn chương trình sau . Hãy xác định độ phức tạp của thuật toán
void buble (int a[n]){
int i, j, temp;
1. for (i = 0; i < n-1; i++)
2. for (j = n-1; j>= i+1; j--)
3. if (a[j-1] > a[j]{
// Đổi chỗ cho a[j] và a[j-1]
4. temp = a[j-1];
5. a[j-1] = a[j];
6. a[j] = temp;
}
}
a. O(n2)
Câu 22**: Cho đoạn chương trình sau . Hãy xác định độ phức tạp của thuật toán
int MaxSubSum1(const int a[], int n) {
int maxSum=0;

for (int i=0; i<n; i++)
for (int j=i; j<n; j++) {
int thisSum=0;

for (int k=i; k<=j; k++)
thisSum+=a[k];

if (thisSum>maxSum)
maxSum=thisSum;
}
return maxSum;
}
a. O(n3)
Câu 23**: Cho đoạn chương trình sau . Hãy xác định độ phức tạp của thuật toán
void selection_sort(){
int i, j, k, temp;
for (i = 0; i< N; i++){
k = i;
for (j = i+1; j < N; j++){
if (a[j] < a[k]) k = j;
}
temp = a[i]; a[i] =a [k]; a[k] = temp;
}
}
a. O(n2)
Câu 24**: Cho đoạn chương trình sau . Hãy xác định độ phức tạp của thuật toán
void insertion_sort(){
int i, j, k, temp;
for (i = 1; i< N; i++){
temp = a[i];
j=i-1;
while ((a[j] > temp)&&(j>=0)) {
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}

a. O(n2)