Mã đề

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

DH 20151 - 01

***

Họ tên: ……………………………
Lớp: …………………………………
SHSV: ……………………………….

ĐỀ THI MÔN: CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT

Hà nội, .…. /….. / …...
Trưởng bộ môn

Ngày thi: …../…../….

Thời gian 90’

(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á độ phức tạp của hàm đệ quy sau theo O-lớn
void fx(int n)

45
nhau có giá trị chêch lệch là -1 hoặc +1, và một số nguyên x. Hãy
đưa ra thuật toán tìm vị trí của x trong danh sách một cách
nhanh nhất mà không cần phải duyệt toàn bộ các phần tử.
10
27
33
VD. Danh sách 1,2,1,2,3,4,3,2,1,2,3,4,5,4,3,4 và x=5 thuật toán
trả về 12 (bắt đầu từ 0)

1|Page


Bài 4. Cho tập hợp gồm n điểm đen và n điểm trắng cách đều nhau. Hãy mô tả thuật toán kết nối một
điểm đen với một điểm trắng sao cho tổng khoảng cách là nhỏ nhất.

Bài 5. Hoàn thiện hàm trộn 2 danh sách liên kết đơn đã sắp xếp thành danh sách sắp xếp
struct Node
{
int data;
struct Node * pNext;
};
struct Node * mergeLists(struct Node * List1, struct Node * List2)

2|Page