›
›

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

Download
Mã đề  
CD 2011 - 02  
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.  
a) So sánh ưu nhược điểm khi lưu trữ cây nhị phân chiều cao ℎ dùng: (1) mảng, (2) cấu trúc liên kết  
struct BNode  
{
DATA_TYPE data; //là kiểu dữ liệu lưu trữ tại nút  
struct BNode * Lchild, *Rchild; //con trỏ tới cây con trái và con phải  
}
Theo các tiêu chí:  
•
•
•
Bộ nhớ,  
thời gian truy cập một nút bất kỳ,  
tìm nút cha của một nút bất kỳ trên cây  
b) Đánh giá thời gian thực hiện tồi nhất của hàm sau theo 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;  
}
c) So sánh ưu nhược điểm của phương pháp tổ chức tìm kiếm dùng mảng và áp dụng thuật toán tìm kiếm  
nhị phân, cây nhị phân tìm kiếm và dùng bảng băm theo các tiêu chí sau  
Tiêu chí  
Tìm kiếm nhị phân  
Cây nhị phân tìm kiếm  
Bảng băm  
Bộ nhớ dùng lưu trữ các  
phần tử  
Thời gian tìm kiếm  
Thêm phần tử  
Xoá phần tử  
In ra danh sách các phần tử  
hiện có  
1 | P a g e  
Bài 2.  
a) Biểu thức dạng hậu tố là gì? Ưu điểm của biểu thức dạng hậu tố?  
b) Định giá biểu thức dạng hậu tố sau (trình bày rõ các trạng thái trung gian của STACK  
10 2 3 + / 2 ^ 4 12 8 − % +  
c) Vẽ cây biểu thức biểu diễn cho biểu thức ở phần b (không cần phải trình bày các bước trung gian)  
Bài 3.  
a) Cho cây nhị phân tìm kiếm ban đầu như hình  
thêm lần lượt dãy khóa 33, 43, 12, 36, 78, 29, 16, 9, 65, 27, 32. Hãy vẽ cây nhị ph
kết quả thu được cuối cùng (không cần trình bày các bước trung gian).  
b) Với cây nhị phân tìm kiếm thu được ở phần a, thực hiện xóa lần lượt khóa 18  
và 33. Hãy vẽ cây kết quả thu được sau mỗi lần xóa  
Chú ý: chọn nút thay thế là nút phải nhất trên cây con trái  
Bài 4. Cho một đơn đồ thị vô hướng 퐺(푉, 퐸) như sau  
푉 = {퐴, 퐵, 퐶, 퐷, 퐸, 퐹, 퐺, 퐻}  
퐸 = {(퐴, 퐵), (퐴, 퐶), (퐴, 퐸), (퐵, 퐸), (퐵, 퐺), (퐶, 퐷), (퐶, 퐵), (퐷, 퐸), (퐹, 퐷), (퐹, 퐸), (퐹, 퐺), (퐻, 퐵), (퐻, 퐺)}  
a) Hãy biểu diễn đồ thị trên dùng danh sách kề.  
b) Thực hiện BFS từ đỉnh B, hãy đưa ra thứ tự các đỉnh được thăm.  
c) Hãy đưa ra các loại cạnh thu được khi BFS tại đỉnh B (BackEdge, CrossEdge, TreeEdge và ForwardEdge).  
Lưu ý: Các đỉnh trên đồ thị được thăm theo thứ tự ABC  
Bài 5. Để biểu diễn các tập hợp số nguyên ta dùng danh sách liên kết đơn với cấu trúc một phần tử được  
khai báo như sau:  
typedef struct Node  
{
int data;  
struct node *pNext;  
} NODE;  
a) Hãy xây dựng hàm tìm và trả về giá trị phần tử chẵn lớn nhất trong tập hợp trong trường hợp biết các  
phần tử của tập hợp được sắp xếp theo thứ tự tăng dần về giá trị.  
int FindMax (NODE *pHead)  
{
}
b) Hãy đánh giá thời gian thực hiện trong trường hợp tồi nhất của hàm bạn viết theo O-lớn  
2 | P a g e  
pdf 2 trang Thùy Anh 26/04/2022 8600
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 2011-02 - 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_2011_02_t.pdf