Đề thi Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

Đề thi Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!

55 28 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (ET2100)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

2 trang 1 tháng trước

Tác giả:

Profile Thùy Dương
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
***
Họ tên: ……………………………
Lớp: …………………………………
SHSV: ……………………………….
ĐỀ Ấ THI MÔN: C U TRÚC D LI U Ữ Ệ
VÀ GI I THU T Ả Ậ
Ngày thi: …../…../….
Thời gian 90’
(Sinh viên được sử d ng tài liụ ệu)
Hà n ội, .…. /….. / …...
Trưởng bộ môn
Bài 1. Cho hàm khai báo như sau (tham s ố 𝑎, 𝑏 là các s nguyên không âm) ố
long int mistery(int a, b)
{
if(a==0) return 0;
if(a%2==0) 2*mistery(a/2,b); return
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 ừ ầ
Chú ý: là ký hi u c a toán t c hai √ ệ ủ ử căn bậ
Bài 3. Cây nh phân tìm kiị ếm
a) Thêm l t các nút 25, 32, 14, 21, 19, 17, 23, 5, 9 vào cây nh ần lượ ị
phân tìm ki u r ng, v cây k t qu thếm ban đầ ỗ ẽ ế ả u đượ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
c) Cho cấu trúc một nút trên cây c khai báo đượ như sau
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 trên cây x
int struct *CountNodes( BinaryNode *root, double x)
struct BinaryNode
{
double data;
struct BinaryNode *Left, *Right;
}
Mã đề
CD 2012 - 03
+
b 3 /
a 4
Bài 4.
a) Để bi u di c b c n ể ễn đa thứ ậ
𝑃
𝑛
(
𝑥
)
= 𝑎
𝑛
𝑥
𝑛
+ 𝑎
𝑛−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 c s ết trướ ố
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ủ ạn đểa b :
Thực hi n vi c tìm ki m khách hàng m t cách nhanh nh t ệ ệ ế ộ ấ
Thực hi và tìm ki m ti t kiện lưu trữ ế ế ệ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. ớ
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
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
Đưa ra các loại cạnh trên cây khung DFS t i B. ạ
A
B H
C
G
F
E
D
Figure 2 th G (V, E) Đồ ị
| 1/2
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

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 Hà n ội, .…. /….. / …...
Họ tên: ……………………………
VÀ GIẢI THUẬT
Trưởng bộ môn Lớp
Ngày thi: …../…../….
: …………………………………
Thời gian 90’
SHSV: ……………………………….
(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
Chú ý: √ là ký hiệu của toán tử căn bậc hai b 3 /
Bài 3. Cây nhị phân tìm kiếm
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ị a 4
phân tìm kiếm ban đầu rỗng, vẽ cây kết quả thu được
Figure 1 Cây biểu thứ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
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ự E thăm các đỉnh
Đưa ra các loại cạnh trên cây khung DFS tại B. G C F
Figure 2 Đồ thị G (V, E)