Đề thi môn Cấu trúc dữ liệu và thuật toán - Mã đề: CDK54-2010-01
ĐỀ THI: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
(Thời gian 90’)
Mã đề CDK54-2010-01
Sinh viên được sử dụng tài liệu
Bài 1.
a) Kích thước của 1 biến kiểu char là 1 Byte, biến kiểu int là 4 byte, kiểu double là 8 byte. Kích thước của 1
con trỏ kiểu char là ? con trỏ kiểu double là ?
b) Đánh giá thời gian thực hiện của thuật toán đệ quy sau theo mô hình O-lớn
Cho ma trận A kích thước 푛 × 푚, ma trận B kích thước 푚 × 푙
for(i = 0; i < n; i++)
for( k = 0; k < m; k++)
for( j = 0; j < l; j++)
C[i][j] += A[i][k] * B[k][j];
Hãy đánh giá độ phức tạp của đoạn chương trình trên theo O-lớn
Bài 2. Trả lời các câu hỏi sau
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 danh sách liên kết đơn? Giải thích
lựa chọn của bạn.
b) Danh sách tên của 1000 sinh viên được lưu trữ trong mảng nhưng không theo 1 thứ tự nào.Hãy nêu
những ưu điểm và nhược điểm của phương pháp lưu trữ này
(các tiêu chí đánh giá: bộ nhớ, thời gian tìm kiếm, thêm, xóa)
Bài 3.
a) Trong mạng LAN có 1 máy in mạng được sử dụng chung. Các công việc in gửi đến máy được lưu trữ
trong 1 hàng đợi, địa chỉ của các công việc được lưu trữ cho đến khi máy sẵn sàng. Công việc mới sẽ
được xếp cuối cùng trong hàng đợi. Nêu các lý do tại sao nên dùng hàng đợi cài đặt bằng danh sách liên
kết thay vì cài đặt bằng mảng.
b) Áp dụng thuật toán chuyển biểu thức dạng trung tố sang dạng hâu tố bằng stack để chuyển biểu thức
sau sang dạng hậu tố (cần nêu rõ các bước trung gian trong quá trình tính)
3 + 5 ^ (12 / 6 + 1) – 7 ∗ 15 / 3 + 6
Bài 4. Cho đồ thị
a. Biểu diễn đồ thị dùng danh sách kề
b. Thực hiện duyệt đồ thị theo chiều sâu (DFS) xuất phát từ đỉnh A, vẽ cây khung thu được
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
15840
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-01", để 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
