›
›

Đề thi môn Cấu trúc dữ liệu và thuật toán - Mã đề: CD 2012-03 - Trường Đại học Bách khoa Hà Nội

Download
Mã đề  
CD 2012 - 03  
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI  
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG  
BỘ MÔN KHOA HỌC MÁY TÍNH  
***  
ĐỀ THI MÔN: CẤU TRÚC DỮ LIỆU  
VÀ GIẢI THUẬT  
Hà nội, .…. /….. / …...  
Trưởng bộ môn  
Họ tên: ……………………………  
Lớp: …………………………………  
SHSV: ……………………………….  
Ngày thi: …../…../….  
Thời gian 90’  
(Sinh viên được sử dụng tài liệu)  
Bài 1. Cho hàm khai báo như sau (tham số 푎, 푏 là các số nguyên không âm)  
long mistery(int a, int b)  
{
if(a==0) return 0;  
if(a%2==0) return 2*mistery(a/2,b);  
return b+2*mistery((a-1)/2,b);  
}
a.Hàm sau thực hiện công việc gì? Tính giá trị của hàm với a=5 và b=7  
b.Đánh giá độ phức tạp của hàm mistery theo O-lớn  
Bài 2. Cho cây biểu thức sau  
+
a.Duyệt cây biểu thức để đưa ra biểu thức dạng tiền tố, hậu tố  
b.Với a=36 và b=5, hãy minh họa thuật toán định giá biểu thức hậu tố  
trên biểu thức hậu tố thu được từ phần a  
 
 
b
3
/
Chú ý: √ là ký hiệu của toán tử căn bậc hai  
Bài 3. Cây nhị phân tìm kiếm  
a
4
a) Thêm lần lượt các nút 25, 32, 14, 21, 19, 17, 23, 5, 9 vào cây nhị  
phân tìm kiếm ban đầu rỗng, vẽ cây kết quả thu được  
b) Với cây kết quả trong phần b ta xóa nút 1, hãy vẽ cây kết quả thu được.  
Thay bằng nút trái nhất trên con phải  
Figure 1 Cây biểu thức  
c) Cho cấu trúc một nút trên cây được khai báo như sau  
struct BinaryNode  
{
double data;  
struct BinaryNode *Left, *Right;  
}
Hãy hoàn thiện hàm tìm và trả về số lượng nút có giá trị nhỏ hơn hoặc bằng x trên cây  
int *CountNodes(struct BinaryNode *root, double x)  
Bài 4.  
a) Để biểu diễn đa thức bậc n  
푛
푃 푥 = 푎푛푥 + 푎푛−1푥푛−1+. . +푎1푥 + 푎푛+1  
( )  
푛
Và thực hiện các thao tác cộng, trừ, nhân và chia với đa thức này thì ta nên sử dụng mảng hay danh  
sách liên kết? Hãy giải thích tại sao.  
b) Giả sử chúng ta có một danh sách gồm 100 phần tử kiểu double được lưu trữ trong mảng, và cần  
phải thực hiện sắp xếp. Khi đó ta nên chọn thuật toán sắp xếp nào trong các thuật toán đã học để  
thu được hiệu quả tốt nhất? Giải thích lý do?  
Nếu số lượng phần tử là 1 000 000 và được lưu trữ dùng danh sách liên kết đơn thì nên dùng thuật  
toán nào? Giải thích lý do?  
c) Giả sử chúng ta cần quản lý một danh sách khách hàng có tối đa 1000 người (không biết trước số  
lượng) và cần thực hiện tìm kiếm theo họ tên. Hãy mô tả phương pháp của bạn để:  
Thực hiện việc tìm kiếm khách hàng một cách nhanh nhất  
Thực hiện lưu trữ và tìm kiếm tiết kiệm bộ nhớ nhất có thể  
Hãy giải thích?  
d) Giả sử chúng ta có một danh sách các số nguyên gồm 1 000 000 số. Hãy đưa ra một thuật toán hiệu  
quả để thống kê các số trùng nhau trong danh sách.  
Đánh giá thời gian thực hiện của thuật toán của bạn theo  
O lớn.  
A
D
Bài 5. Cho đồ thị vô hướng như hình bên  
a) Minh họa cách lưu trữ đồ thị trên sử dụng ma  
B
H
trận kề và danh sách kề  
b) Thực hiện DFS tại đỉnh B, hãy đưa ra thứ tự  
thăm các đỉnh  
E
G
Đưa ra các loại cạnh trên cây khung DFS tại B.  
C
F
Figure 2 Đồ thị G (V, E)  
pdf 2 trang Thùy Anh 26/04/2022 6120
Download
Bạn đang xem tài liệu "Đề thi môn Cấu trúc dữ liệu và thuật toán - Mã đề: CD 2012-03 - Trường Đại học Bách khoa Hà Nội", để 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:

  • pdfde_thi_mon_cau_truc_du_lieu_va_thuat_toan_ma_de_cd_2012_03_t.pdf