Đề thi môn Cấu trúc dữ liệu và thuật toán - Mã đề: CDK54-2010-02
ĐỀ THI: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
(Thời gian 90’)
Mã đề CDK54-2010-02
Sinh viên được sử dụng tài liệu
Bài 1.
a) Trình bày sự khác biệt giữa mảng cấp phát bộ nhớ động và mảng cấp phát tĩnh? Khi nào dùng mảng cấp
phát động, mảng cấp phát tĩnh, cho ví dụ.
b) Đánh giá thời gian thực hiện của thuật toán tính mũ nhanh sau theo mô hình O-lớn
double fastPower(double x, int n)
{
double fract;
if(n==0) return 1;
fract = fastPower(x,n/2);
if(n%2==0) return fract*fract;
else return fract*fract*x;
}
Thuật toán trên sẽ thực hiện việc tính 푥푛
Bài 2.
a) Trong các phương pháp sắp xếp: lựa chọn, chèn, đổi chỗ(nổi bọt), quicksort (sắp xếp nhanh), mergesort
(sắp xếp trộn), thì phương pháp nào là phù hợp nhất để sắp xếp trên mảng với số lượng các phần tử
lớn? Giải thích lựa chọn của bạn.
b) Cho mảng A={14,45,21,12,7,87,25,56,91,64,33,41,72,89,62}
Hãy minh họa lần lặp thứ nhất của thuật toán sắp xếp nổi bọt trên A.
Bài 3.
a) Hàng đợi vòng (Circle Queue) là gì ? Tác dụng của việc tổ chức hàng đợi dạng vòng?
b) Áp dụng thuật toán định giá biểu thức hậu tố bằng stack để tính giá trị biểu thức dạng hậu tố sau (cần
nêu rõ các bước trung gian trong quá trình tính)
15 2 3 + / 2 ^ 4 12 2 − % +
Bài 4. Cho đồ thị
a. Biểu diễn đồ thị dùng ma trận kề
b. Thực hiện thuật toán PRIM và đưa ra cây khung có trọng số nhỏ nhất trên đồ thị (cần mô tả rõ các
bước thực hiện)
Bài 5. Viết hàm nhận đầu vào là 1 ma trận kề biểu diễn cho 1 đồ thị vô hướng , và số lượng đỉnh trên đồ thị.
Hàm kiểm tra xem đồ thị có liên thông hay không. Nếu đồ thị liên thông thì hàm trả về giá trị 1, ngược lại
thì hàm trả về giá trị 0.
int ktLienThong(int Adj[100][100], int n)
{
//Thân hàm
}
Trong đó 푛 là số lượng đỉnh thực sự trên đồ thị ( 0 < 푛 ≤ 100), Adj là ma trận kề lưu trữ đồ thị.
Chú ý : đồ thị liên thông nếu mà giữa hai cặp đỉnh bất kỳ luôn tồn tại đường đi.
Hãy đưa ra đánh giá thời gian thực hiện của thuật toán của bạn theo O-lớn
Chú ý: chương trình sử dụng thuật toán tối ưu hơn sẽ được đánh giá cao hơn!
2 trang
17960
Free
Bạn đang xem tài liệu "Đề thi môn Cấu trúc dữ liệu và thuật toán - Mã đề: CDK54-2010-02", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_thi_mon_cau_truc_du_lieu_va_thuat_toan_ma_de_cdk54_2010_0.pdf
