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

TRƯỜNG ĐẠI HỌC PHENIKAA KHOA CÔNG NGHỆ THÔNG TIN ĐỀ THI HỌC PHẦN Học kỳ: II Năm học: 2021-2022
Hệ đào tạo: Chính quy Bậc học: Đại 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ố: 3 Câu 1. (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.
1.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)
1.2. Giả thiết A[i] nhận giá trị bất kỳ và mảng A đã được sắp xế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 2. (2 điểm) 2.1.
Các khóa 12, 18, 13, 2, 3, 23, 5 và 15 được chèn vào một bảng băm rỗng độ dài 10 sử
dụng nguyên tắc địa chỉ mở với hàm băm h(k) = k mod 10 và phép dò tuyến tính. Kết quả của
dãy thao tác trên là bảng băm nào dưới đây? Giải thích kết quả của từng phép chèn. (1 điểm) 1 2.2.
Cho bảng băm kích thước 100, phép xử lý đụng độ được thực hiện sử dụng liên kết.
Giả sử hàm băm là hàm phân phối đều, xác suất ba vị trí đầu tiên đều trống sau khi thực hiện
ba phép chèn là bao nhiêu? (1 điểm)
Câu 3. 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 4. (2 điểm)
4.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)
4.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ả 2
// 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 } // 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 5. Cho một lưới ô vuông, mỗi ô của lưới là 1 ký tự 0 hoặc 1. Hai ô là kề nhau nếu chúng cùng giá
trị ‘1’, nằm trong lưới, và có chung đỉnh hoặc chung cạnh. Hãy đếm xem trong lưới có bao nhiêu
nhóm các ô 1 mà mỗi nhóm chỉ gồm các ô 1 liên thông với nhau. Hai ô là liên thông với nhau nếu có 3
thể đi từ ô này sang ô còn lại thông qua 1 dãy các ô chứa các ký tự ‘1’ mà hai ô liên tiếp chung đỉnh hoặc chung cạnh.
5.1. Mô tả và đưa bài toán về bài toán đồ thị. (0.5 điểm)
5.2. Sắp xếp thứ tự các câu lệnh trong hai hàm sau đây để đưa về kết quả đúng. Sinh viên ghi thứ tự
các dòng lệnh, gồm cả dòng lệnh chỉ gồm các dấu đóng/mở ngoặc. (1.5 điểm) Ví dụ:
Hàm dfs(int i, int j, int n, int m, vector>& vis, vector>& grid): thứ tự các
dòng lệnh là 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
// hàm tìm kiếm theo chiều sâu trên lưới grid kích thước nxm từ ô (i,j)
//ma trận vis kích thước nxm đánh dấu ô (i,j) đã được duyệt hay chưa
void dfs(int i, int j, int n, int m, vector>& vis, vector>& grid) { 1. vis[i][j] = 1; 2.
if (grid[i][j] == '0') return; 3.
if (i < 0 || j < 0) return; 4.
if (i >= n || j >= m) return; 5. if (!vis[i][j]) 6.
dfs(i - 1, j, n, m, vis, grid); 7.
dfs(i + 1, j, n, m, vis, grid);8.
dfs(i, j - 1, n, m, vis, grid); 9.
dfs(i, j + 1, n, m, vis, grid); 10.
dfs(i - 1, j - 1, n, m, vis, grid); 11.
dfs(i - 1, j + 1, n, m, vis, grid); 12.
dfs(i + 1, j - 1, n, m, vis, grid); 13.
dfs(i + 1, j + 1, n, m, vis, grid); 14. { 15. } }
//Hàm đếm số đảo liên thông chỉ gồm các số 1.
//grid: ma trận chứa thông tin về lưới chỉ gồm các ký tự 0 và 1.
//kích thước của lưới được lấy thông qua hàm size()
int numIslands(vector>& grid) { 1. int n = grid.size(); 2. int m = grid[0].size(); 3. for (int i = 0;i < n;i++) 4. dfs(i, j, n, m, vis, grid); 5. int count = 0; 6. count++; 7. for (int j = 0;j < m;j++) 8.
if (!vis[i][j] && grid[i][j] == '1') 9. return count; 10.
vector>vis(n, vector(m, 0)); 11. { 12. { 13. { 14. } 15. } 16. } } 4 TRƯỞNG BỘ MÔN/KHOA GIẢNG VIÊN RA ĐỀ 5