Đề thi học phần Cấu trúc dữ liệu và thuật toán năm 2022 | Trường Đại học Phenikaa

TRƯỜNG ĐẠI HỌC PHENIKAA Hệ ào tạo: Chính quy Bậc học: Đại học KHOA CÔNG NGHỆ THÔNG
TIN ĐỀ THI HỌC PHẦN Học kỳ: II Năm học:
Tên học phần: Cấu trúc dữ liệu và thuật toán Số tín chỉ: 3
Ngày thi: 14 tháng 7 năm 2022
Thời gian làm bài: 90 phút (Không kể thời gian phát ề) Đề số: 2 Câu 1. (2 iểm)
1.1. Trình bày ý tưởng của thuật toán sắp xếp trộn (merge sort). (0.5 iểm)
1.2. Hoàn thiện thuật toán sắp xếp trộn triển khai trên danh sách liên kết. (1.5 iểm) struct Node { int data; struct Node *next, *prev; };
// Hàm trộn hai danh sách liên kết lưu các giá trị tăng dần và trả về con trỏ trỏ tới danh sách kết quả
// first: con trỏ trỏ tới ầu danh sách liên kết thứ nhất //
second: con trỏ trỏ tới ầu danh sách liên kết thứ hai struct
Node *merge(struct Node *first, struct Node *second) { if (!first) // bố sung code ở ây if (!second) // bố sung code ở ây
if (first->data < second->data) { // bố sung code ở ây } else { // bố sung code ở ây } } // hàm chia
ôi một danh sách liên kết
ôi trỏ bởi head thành 2 danh sách liên kết ôi
rời nhau chênh lệch không quá một phần tử; 1 danh sách ược trỏ tới bởi head và một danh
sách ược trỏ tới bởi kết quả của hàm này (xem hàm mergeSort)
struct Node *split(struct Node *head) { // bố sung code ở ây } 1 // hàm mergesort
struct Node *mergeSort(struct Node *head)
{ if (!head || !head->next) return head;
struct Node *second = split(head); // ệ quy head = mergeSort(head); second = mergeSort(second);
// trộn hai dẫy sắp xếp return merge(head,second); } Câu 2. (2.5 iểm)
Cho một dãy số nguyên A[1..n]. Cho số nguyên X, kiểm tra X có nằm trong dãy số A hay không.
2.1 Nếu giá trị các dãy số ều nằm trong oạn 1 .. 1,000,000; cho phép sử dụng bộ nhớ phụ, ta
có thể lưu trữ như nào ể việc tìm kiếm số nguyên X bất kỳ có thể ược thực hiện với ộ phức tạp O(1). (1 iểm)
2.2. Giả thiết A[i] nhận giá trị bất kỳ và mảng A ã ược sắpxếp. Viết mã code (C/C++) hàm ếm
số phần tử X trong dãy A[1..n] với ộ phức tạp O(logn).
i) Độ phức phức tạp O(n): (0.5 iểm)
int linearCount(int A[], int N, int
X){ // bổ sung code cho hàm này }
ii) Độ phức tạp O(logn): (1 iểm)
// hàm trả về số phần tử bằng phần tử X trong mảng A với ộ phức tạp O(logn) int
logCount(int A[], int N, int X){ // bổ sung code cho hàm này }
Câu 3 (2 iểm) . Một bảng băm rỗng ộ dài 10 ược thiết kế là bảng băm sử dụng ịa chỉ mở với hàm băm
h(k)=k mod 10, tìm kiếm thông qua phép dò tuyến tính. Sau khi chèn 6 giá trị vào bảng băm rỗng, nội dung của bảng như sau: 2
a) Chọn và giải thích chuỗi nào là chuỗi cho kết quả của phép chèn hợp lệ (1 iểm) (A) 46, 42, 34, 52, 23, 33 (B) 34, 42, 23, 52, 33, 46 (C) 46, 34, 42, 23, 52, 33 (D) 42, 46, 33, 23, 34, 52
b) Giả sử các số 46, 42, 34, 52, 23, 33 ược chèn theo một thứ tự nào ó vào bảng băm rỗng như
mô tả bên trên. Có bao nhiêu chuỗi cho cùng kết quả như trong hình. (1 iểm)
Câu 4. Cho hai số nguyên N, K và một dãy số nguyên 32 bits A[1..N]. Yêu cầu của bài toán là ếm số
phần tử khác nhau trong mỗi oạn con gồm K phần tử liên tiếp và in ra số lượng phần tử ó cho mỗi oạn con. (1,5 iểm). Ví dụ: Input: 5 3 1 2 2 3 1 Output: 2 2 3
Giải thích: oạn A[1..3], A[2..4], A[3..5] lần lượt có 2, 2 và 3 phần tử khác nhau.
Nêu cấu trúc dữ liệu phù hợp (cây tìm kiếm nhị phân hoặc bảng băm) và viết oạn code thỏa mãn yêu
cầu trên với ộ phức tạp O(NlogK) hoặc O(N) sử dụng cấu trúc dữ liệu set hoặc unordered_set của STL C++.
vector differentNumbers(int A[], int N, int,
K){ // bổ sung code ở ây } Câu 5. Cho một
ồ thị G(V, A) ược biểu diễn bằng ma trận kề, cần tìm bao óng của ồ thị. Bao óng của
ồ thị là ma trận 0-1 kích thước |V|x|V| mà phần tử ở vị
trí (i,j) nhận giá trị bằng 1 nếu có
ường i từ i ến j, bằng 0 nếu ngược lại. 3
//graph: ma trận kề ầu vào
//node: iểm ang ược duyệt
//vis: các iểm ã duyệt (vis[i] = true)
//N: số ỉnh của ồ thị
void dfs(vector>& graph, int node, vector& vis, int N) 1. { 2. dfs(graph, i, vis, N); 3. if (graph[node][i] == 1) 4. if (vis[i] == 1) continue; 5.
for (int i = 0; i < N; i++) 6. vis[node] = 1; 7. { 8. } 9. { 10. } } //N: số ỉnh ồ thị
//graph: ma trận kề của ồ thị 1.
vector> transitiveClosure(int N, vector> graph) 2. { 3. dfs(graph, i, vis, N); 4.
for (int i = 0; i < N; i++) vis[i] = 0; 5.
for (int i = 0; i < N; i++) 6. vector> v; 7. vector vis(N, 0); 8. v.push_back(vis); 9. return v; 10. { 11. } 12. } TRƯỞNG BỘ MÔN/KHOA GIẢNG VIÊN RA ĐỀ 4