Đề cương

Trường ĐH Công Nghệ Thông Tin
Ngày thi: xx-xx-2010
Hội đồng thi: ĐH CNTT
Đề thi mẫu môn: Cơ sở
Kỳ thi: TN CN CNTT TXQM
Mã Đề: 408
Số lượng câu: 100
Thời gian làm bài: 150 phút


PHẦN I: CẤU TRÚC DỮ LIỆU
Câu 1: 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:
A. Cấu trúc dữ liệu + Chương trình = Giải thuật
B. Cấu trúc dữ liệu + Giải thuật = Chương trình

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



Câu 2: Chọn phát biểu đúng nhất trong các phát biểu sau
Các tiêu chuẩn của cấu trúc dữ liệu. Để đánh giá một cấu trúc dữ liệu ta thường dựa vào một số tiêu chí
A. Phải biểu diễn đúng và đầy đủ thông tin của bài toán
B. Phải phù hợp với các thao tác trên đó

C. Phải tiết kiệm tài nguyên hệ thống
D. Cả a,b,c đều đúng



Câu 3: Chọn phát biểu đúng nhất trong các phát biểu sau
Các tiểu chuẩn của một thuật toán. Để đánh giá một thuật toán ta thường dựa vào một số tiêu chí
A. Tính xác định
B. Tính hữu hạn

C. Tính đúng
D. cả a,b,c đều đúng



Câu 4: Cho đoạn mã sau:
Bước 1: S=0, i=1;
Bước 2: nếu i Ngược lại: qua bước 4;
Bước 3:
i=i+1;
Quay lại bước 2;
Bước 4: Xuất S ra màn hình
Cho biết đoạn mã trên biễu diễn thuật toán gì?
A. Tính n!
B. Tổng giá trị từ 1 đến n-1

C. Tổng giá trị từ 1 đến n
D. Tính (n-1)!



Câu 5: Cho n là số phần tử cần thao tác, gọi O ký hiệu biểu diễn độ phức tạp của thuật toán
Chọn phát biểu nào sau đây đúng
A. O(n) < O(log(n))
B. O(n2) > O(2n)

C. O(n) > O(log(n))
D. O(n2) > O(n!)



Câu 6: Cho mảng a có n phần tử, xét đoạn mã sau
Bước 1: Khởi gán i=0;
Bước 2: So sánh a[i] với giá trị x cần tìm, có 2 khả năng
+ a[i] == x tìm thấy x. Dừng;
+ a[i] != x sang bước 3;
Bước 3: i=i+1
Nếu i==N: Hết mảng. Dừng và không tìm thấy.
Ngược lại: Lặp lại bước 2;
Đoạn mã trên biểu diễn thuật toán gì?
A. Tìm kiếm nhị phân phần tử mang giá trị bằng x trong mảng
B. Tìm kiếm tuyến tính phần tử mang giá trị x trong mảng

C. Tìm kiếm phẩn từ mang giá trị lớn nhất trong mảng
D. Tìm kiếm phẩn từ mang giá trị nhỏ nhất trong mảng



Câu 7: Cho hàm tìm kiếm tuyến tính sau
int TimTuyenTinh(int a[],int n, int x)
{ int i=0;
while((i i++;
if(i==n)
return 0;
else
return 1;
}
Chọn phát biểu đúng?
A. Hàm trả về 0 nếu tìm thấy phần tử mang giá trị bằng x
B. Hàm trả về phần tử tại chỉ số 0 trong mảng

C. Hàm trả về 1 nếu tìm thấy phần tử mang giá trị bằng x
D. Hàm trả về phần tử tại chỉ số n trong mảng



Câu 8: Xét hàm tìm kiếm nhị phân phần tử mang giá trị bằng x trên mảng có thứ tự tăng dần sau
1: int BinarySearch(int a[],int n,int x)
2: { int left, right, mid; left=0; right=n-1;
3: do{
4: mid=(left+right)/2;
5: if(a[mid]==x) return 1;
6: ……………………………………………
7: ……………………………………………
8: }while(left<=right);
9: return 0;
!0:}
Chọn