Tổng hợp đề thi môn Cấu trúc dữ liệu và thuật toán| Môn Cấu trúc dữ liệu và thuật toán| Trường Đại học Bách Khoa Hà Nội

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) Mã đề
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI DH 2013 - 01
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.
a) Cho cây AVL sau, vẽ cây kết quả khi thêm phần tử 29, và xóa phần tử 25 25
b) Cho một cây nhị phân tìm kiếm có khóa là các số nguyên, và
một giá trị k, Hãy viết hàm tìm và in ra tất cả các cặp phần
tử (a, b) trên cây sao cho 𝑎 + 𝑏 ≤ 𝑘
c) So sánh thời gian thêm và tìm kiếm của các cấu trúc dữ liệu 12 36
sau: Bảng băm, mảng, danh sách liên kết, hàng đợi
Bài 2. Cho hai văn bản A và B đã được tách từ, gọi số lượng từ 7 21 31 45
phân biệt của văn bản A là n, và của văn bản B là m
(𝑛 ≤ 𝑚). Hãy đưa ra thuật toán tìm tập từ chung của hai văn bản theo tiêu chí 10 27 33
a) Thời gian thực hiện nhanh nhất
b) Bộ nhớ phụ tốn ít nhất
Trong cả hai trường hợp, hãy chỉ rõ thời gian thực hiện theo O-lớn và bộ nhớ phụ cần sử dụng
Bài 3. Cho một từ điển tiếng anh gồm n từ, và một danh sách ký tự phân biệt độ dài m (𝑚 ≪ 𝑛). Hãy xây
dựng thuật toán tìm và đưa ra từ dài nhất trong từ điển được tạo từ các ký tự trong danh sách.
Thời gian của thuật toán cần là 𝑂(𝑛)
Bài 4. Cho một danh sách số nguyên dương gồm n phần tử (𝑛 ≈ 1 𝑡ỷ) và một số nguyên dương k(𝑘 ≪ 𝑛),
Hãy đưa ra thuật toán đếm số cặp trong danh sách ban đầu có tổng < 𝑘 với thời gian thực hiện nhỏ hơn 𝑂(𝑛 log 𝑛)
Bài 5. Cho một luồng các ký tự liên tục, hãy xây dựng thuật toán đưa ra danh sách ký tự không được lặp
trong luồng ký tự đó (giả sử rằng tồn tại ít nhất một ký tự như vậy).
Chú ý: với luồng ta chỉ có thể duyệt các ký tự 1 lần và theo 1 chiều 1 | P a g e CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Bài 6. Cho danh sách thông tin của n cuộc họp với thời điểm bắt đầu và thời điểm kết thúc. Hãy đưa ra thuật
toán sắp xếp các cuộc họp này vào các phòng sao cho số lượng phòng được sử dụng là nhỏ nhất có thể.
Độ phức tạp của thuật toán bạn đề xuất là bao nhiêu?
Bài 7. Trong một trình duyệt cần lưu trữ các URL đã được thăm theo tần số truy cập giảm dần.
Hãy xây dựng CTDL lưu trữ các URL hỗ trợ các thao tác  Thêm/xóa  Tìm kiếm
Với thời gian 𝑂(log 𝑛), liệu có thể lưu trữ để hực hiện các thao tác trên với thời gian 𝑂(1)?
Bài 8. Cho 2 Queue thông thường, hãy xây dựng thuật toán sắp xếp chỉ dung 2 queue đó (không sử dụng
thêm bộ nhớ phụ) để sắp xếp danh sách gồm n phần tử số nguyên.
Các thao tác được dùng chỉ là enqueue và dequeue J A
Bài 9. Cho m mảng số nguyên với số lượng G F
phần tử mỗi mảng là n, các phần tử trong B
mỗi mảng đều đã được sắp xếp. Hãy xây
dựng thuật toán để tìm khoảng nhỏ nhất sao K
cho mỗi mảng có ít nhất một phần tử ở trong khoảng đó. I H E Ví dụ. C A1={1,2,5,7,8} M A2={1,4,6,7,8} L A3={2,5,9,10,12} D
Thì khoảng nhỏ nhất có thể là [8,9]
Gợi ý: Dùng priority queue
Bài 10. Cho đồ thị sau a) Thực hiện DFS tại E
b) Đưa ra phân loại cạnh theo thứ tự duyệt ở phần a Thứ tự thăm theo ABC
Chú ý: Những bài yêu cầu viết hàm mới phải viết code cho hàm, các bài xây dựng thuật toán chỉ cần nêu
ý tưởng (và ví dụ minh họa cho ý tưởng) 2 | P a g e CuuDuongThanCong.com
https://fb.com/tailieudientucntt Mã đề CD 2011 - 01
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.
a) Phân biệt giữa mảng cấp phát động và mảng cấp phát tĩnh. Khi nào nên dùng mảng cấp phát động, hoặc
mảng cấp phát tĩnh? Cho ví dụ mình họa.
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;
if(n%2==0) return fastPower(x,n/2)*fastPower(x,n/2);
else return fastPower(x,n/2)*fastPower(x,n/2)*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ó 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) Chuyển biểu thức dạng trung tố sau sang dạng hậu tố
𝑎 + 3/(2 ∗ 𝑎 − 𝑐 ∗ 𝑏) − 𝑒
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) 1 | P a g e CuuDuongThanCong.com
https://fb.com/tailieudientucntt 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 43, 12, 36, 78, 29, 16, 9, 65, 27, 32. Hãy vẽ cây nhị phân 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à 36. 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 DFS từ đỉnh D, 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 DFS tại đỉnh D (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 CuuDuongThanCong.com
https://fb.com/tailieudientucntt
ĐỀ 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à ?
Gợi ý: Kích thước của con trỏ không phụ thuộc vào kiểu dữ liệu, mà phụ thuộc vào từng dòng máy. Máy 32
bit thì là 4 byte, máy 64 bit thì là 8 byte. Kiểu int sẽ có kích thước bằng số bit của kiểu máy đó, nếu mà kiểu
int là 32 bit tức là đó là máy 32 bit. Như vậy kích thước con trỏ ở đây là 4 byte (32 bit).
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
Lệnh cơ sở là lệnh C[i][j] += A[i][k] * B[k][j];
Có 3 vòng lặp lồng nhau, thời gian thực hiện 𝑛−1 𝑚−1 𝑙−1 𝑛−1 𝑚−1
𝑇(𝑛) = � � � 1 = � � (𝑙 − 1 + 1) =. . = 𝑛 × 𝑚 × 𝑙 𝑖=0 𝑘=0 𝑗=0 𝑖=0 𝑘=0
Vậy độ phức tạp cỡ 𝑂(𝑛 × 𝑚 × 𝑙)
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.
Các thuật toán trên được chia thành 2 loại là cơ bản (𝑂(𝑛2)) và nâng cao (𝑂(𝑛 log 𝑛))
Sắp xếp trên danh sách liên kết đơn thì mergesort là phù hợp hơn vì :
• Thời gian trung bình trong trường hợp tồi nhất cỡ 𝑂(𝑛 log 𝑛)
• Cài đặt đơn giản hơn QuickSort
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) CuuDuongThanCong.com
https://fb.com/tailieudientucntt Ưu điểm:
• Chỉ lưu mỗi tên, không cần lưu thêm thông tin phụ (con trỏ…)
• Có thể truy cập trực tiếp từng phần tử thông qua chỉ số Nhược điểm
• Có thể lãng phí bộ nhớ nếu không dùng hết
• Vì không cần sắp xếp theo thứ tự nên việc thêm phần tử đơn giản (chỉ cần thêm vào cuối). Tuy
nhiên việc tìm kiếm mất nhiều thời gian hơn do chỉ có thể tìm kiếm tuần tự (𝑂(𝑛)).
• Thời gian xóa gồm tìm kiếm khóa cần xóa (𝑂(𝑛)) và xóa phần tử (𝑂(1) do chỉ cần đổi chỗ với
phần tử cuối và giảm số lượng đi 1) 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.
Dùng hàng đợi cài đặt bằng danh sách liên kết vì:
• Số lượng công việc in ta không thể biết trước nên dùng danh sách liên kết sẽ tiết kiệm bộ nhớ hơn.
• Ta chỉ lưu trữ địa chỉ của công việc chứ không phải nội dung công việc (nội dung sẽ được để trên
máy có yêu cầu in) do đó tiết kiệm được bộ nhớ (do cần phải dùng ít bộ nhớ hơn rất nhiều)
Chú ý: ở đây là hàng đợi nên lấy ra là ở đầu hàng và thêm vào ở cuối hàng, ta không lấy ngẫu nhiên 1
phần tử trong hàng, và sau khi lấy ta cũng không phải dịch các phần tử còn lại.
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
Biểu thức hậu tố tương ứng là :
3 5 12 6 / 1 + ^ + 7 15 * 3 / - 6 + CuuDuongThanCong.com
https://fb.com/tailieudientucntt
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.
int ktLienThong(int Adj[100][100], int n) { //Thân hàm
int Queue[MAX];//Queue de cho BFS
int QStart,QEnd; //Dau va cuoi queue
int Color[MAX]; //mau cua cac dinh int u,i; for(i=0;i CuuDuongThanCong.com
https://fb.com/tailieudientucntt //khoi tao queue QStart=0; QEnd=0; //Bat dau tham tu dinh 0 Queue[0]=0; Color[0]=0; while(QEnd>=QStart) { u=Queue[QStart]; QStart++; for(i=0;i
if(Color[i]==-1 && Graph[u][i]==1) { QEnd++; Queue[QEnd]=i; Color[i]=0; } Color[u]=1; }
//kiem tra xem co ton tai dinh chua tham for(i=0;i return 1; }
Thời gian thực hiện 𝑂(𝑛2)
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! CuuDuongThanCong.com
https://fb.com/tailieudientucntt
ĐỀ THI: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (Thời gian 90’)
Mã đề CDK54-2010-02
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ụ. Xem trong vở
b) Đánh giá thời gian thực hiện của thuật toán tính mũ nhanh sau theo mô hình 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; }
Thuật toán trên sẽ thực hiện việc tính 𝑥𝑛
Thuật toán này là thuật toán đệ quy, ta có công thức đệ quy là 𝑛 𝑇(𝑛) = 𝑇 �2� + 1
Thời gian thực hiện theo O-lớn là O(logn)
Chú ý: Có thể dùng 1 trong 3 phương pháp đã học để chứng minh! Bài 2.
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 mảng với số lượng các phần tử
lớn? Giải thích lựa chọn của bạn.
QuickSort là phù hợp nhất để sắp xếp trên mảng với số lượng phần tử lớn vì:
• Thời gian cỡ 𝑂(𝑛 log 𝑛)
• So với mergersort thì nó không cần sử dụng thêm bộ nhớ phụ
• Không cần thực hiện thao tác trộn
b) Cho mảng A={14,45,21,12,7,87,25,56,91,64,33,41,72,89,62}
Hãy minh họa lần lặp thứ nhất của thuật toán sắp xếp nổi bọt trên A.
Tùy từng trường hợp sắp xếp tăng dần hoặc giảm dần mà kết quả sẽ khác nhau. Trong trường hợp tăng
dần thì lần lặp đầu tiên, khóa có giá trị lớn nhất sẽ bị đẩy về cuối dãy. CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Cụ thể xem ví dụ trong slide Bài 3.
a) Hàng đợi vòng (Circle Queue) là gì ? Tác dụng của việc tổ chức hàng đợi dạng vòng?
Hàng đợi vòng và tác dụng của hàng đợi vòng : Xem trong slide vì đây là phần lý thuyết căn bản
b) Áp dụng thuật toán định giá biểu thức hậu tố bằng stack để tính giá trị biểu thức dạng hậu tố sau (cần
nêu rõ các bước trung gian trong quá trình tính) 15 2 3 + / 2 ^ 4 12 2 − % +
Kết quả là 13, còn trình tự thực hiện xem các ví dụ đã chữa trên lớp CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Bài 4. Cho đồ thị
a. Biểu diễn đồ thị dùng ma trận kề
b. Thực hiện thuật toán PRIM và đưa ra cây khung có trọng số nhỏ nhất trên đồ thị (cần mô tả rõ các bước thực hiện)
Cây khung trọng số nhỏ nhất là 21
Trình tự thực hiện xem các ví dụ đã chữa trên lớp
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! CuuDuongThanCong.com
https://fb.com/tailieudientucntt
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI 1
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Học phần:.........CẤU TRÚC DL & TT.........Mã HP....IT3011......Mã lớp: ........ 119183 ........
Bài thi [ ] giữa kỳ .[ X] cuối kỳ.. Năm học... 2020-2021..... Ngày thi:.......13 / 01 / 2021...........
 Không sử dùng tài liệu.
Xác nhận của bộ môn
 Thời gian làm bài 90 phút. PHẦN CÂU HỎI
Câu 1 (2đ) Cho hàm sau:
int process(int a[], int i, int j){
if(i > j) return 0;
if(i == j) return a[i]; int m = (i+j)/2;
return process(a,i,m) + process(a,m+1,j); }
a) Hãy cho biết hàm process thực hiện công việc gì? Giải thích?
b) Với giả thiết các phép toán cần thực hiện đều có thể thực hiện trong thời gian O(1), hãy đưa ra
đánh giá thời gian tính của thuật toán trong trường hợp tối nhất theo O-lớn.
Câu 2 (1đ) Lịch trình di chuyển trong ngày của một cá nhân được lưu trữ trong danh sách liên kết theo
thứ tự tăng dần thời gian, với một nút được định nghĩa như sau: typedef struct aPlace{
int hour, min; // thoi diem ghe tham trong ngay theo gio va phut
char locName[255]; // ten dia diem
struct aPlace* next; // con trỏ đến nút kế tiếp }PLACE;
Giả sử để truy vết F1 của Covid mới xuất hiện, cục y tế dự phòng phát ra thông báo những người qua
một địa điểm tên reportLocName sau khoảng thời gian reportHour giờ, reportMin phút (cùng
ngày) đều phải trình báo y tế. Hãy hoàn thiện hàm
int needMedicalReport(PLACE* visitedPlaces, char* reportLocName, int
reportHour, int reportMin)
Hàm trả về 1 nếu cá nhân cần phải khai báo y tế, và 0 nếu ngược lại (trong đó visitedPlaces là con
trỏ đầu đến danh sách liên kết các địa điểm cùng với thời gian ghé thăm của người cần kiểm tra). Câu 3 (2đ)
a) Cho dãy số sau cần sắp xếp theo thứ tự không tăng 7, 9, 5, 3, 1, 6, 4, 8, 2. Hãy trình diễn thuật
toán sắp xếp trộn sắp xếp dãy đã cho. 1
b) Hãy lập trình ngôn ngữ C hàm int isMinHeap(int A[], int n) kiểm tra xem mảng A[]
chiều dài n (chỉ số các phần tử từ 0 đến n-1) có là đống min (min-heap) hay không ? (trả về 0 là sai, và 1 là đúng). Câu 4 (3đ)
a) Hãy vẽ cây nhị phân tìm kiếm (BST) thu được (không cần vẽ bước trung gian) bằng cách chèn liên
tiếp dãy khóa sau vào BST bắt đầu từ BST rỗng: 11, 4, 8, 21, 16, 1, 3, 27, 14
b) Hãy vẽ BST thu được sau khi loại bỏ nút có khóa bằng 11 khỏi BST thu được ở câu a)
c) Cấu trúc dữ liệu mỗi nút của một cây nhị phân được định nghĩa như sau: typedef struct TNode{
int key;// khóa của nút
struct TNode* left; // trỏ đến nút con trái
struct TNode* right; // trỏ đến nút con phải }TNode;
Hãy lập trình hàm int checkBST(TNode* p) trả về 1 nếu cây nhị phân gốc p là một BST và trả về 0 nếu ngược lại. Câu 5 (1đ)
a) Đưa ra kết quả duyệt cây theo thứ tự sau.
b) Cho a=3, b=5,c=-4,d=6,e=2,f=9 tính giá trị biểu
thức biểu diễn bởi cây biểu thức bên.
Câu 6 (1đ) Cho cấu trúc mô tả vị trí ngồi của n người trong một phòng họp typedef struct aLoc{
double x,y;// toa độ
char name[51];// tên của người họp } LOC;
Danh sách được cho bởi mảng listLoc (các phần tử đánh số từ 0 đến n-1). Giả sử sau khi xét nghiệm
covid có nguời ngồi ở vị trí tọa độ x1,y1 bị dương tính covid, và những người trong phạm vi khoảng cách
đến (x1,y1) nhỏ hơn hoặc bằng d cần được cách ly ngay. Hãy viết hàm
void listF1Covid(LOC *listLoc, int n, double x1, double y1, double d)
in ra danh sách (tên người) những người cần được cách ly (kể cả người ở vị trí tọa độ x1,y1).
(Chú ý: Khoảng cách tính theo Euclide)
------------------ Hết -------------------
Cán bộ coi thi không giải thích gì thêm 2 Mã đề CD 2011 - 01
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.
a) Phân biệt giữa mảng cấp phát động và mảng cấp phát tĩnh. Khi nào nên dùng mảng cấp phát động, hoặc
mảng cấp phát tĩnh? Cho ví dụ mình họa.
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;
if(n%2==0) return fastPower(x,n/2)*fastPower(x,n/2);
else return fastPower(x,n/2)*fastPower(x,n/2)*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ó 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) Chuyển biểu thức dạng trung tố sau sang dạng hậu tố
𝑎 + 3/(2 ∗ 𝑎 − 𝑐 ∗ 𝑏) − 𝑒
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) 1 | P a g e 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 43, 12, 36, 78, 29, 16, 9, 65, 27, 32. Hãy vẽ cây nhị phân 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à 36. 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 DFS từ đỉnh D, 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 DFS tại đỉnh D (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 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
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.
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ân
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