Title cuối kì 2015.pdf ✅

1 Đề thi CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Học kỳ I, 2015-2016 Thời gian: 95 phút Lưu ý: Đề thi có 02 tờ. Thí sinh không được sử dụng tài liệu. Câu 1 (1 điểm) Tính độ phức tạp tính toán cho hàm sum() dưới đây: int sum(int m, int n, int K ) { int s = 0; for (int i = 0; i < m; i ++) { s += i; if (i == K) { for (int j = 0; j < n; j ++) { s += j; } } } return s; } Câu 2 (1 điểm) Cho một dãy A gồm n nguyên dương được lưu giữ dưới dạng một danh sách liên kết đơn (single linked-list). Mỗi nút trong danh sách có cấu trúc như sau: // C/C++ Node { int data; Node* next; } //Java class Node { int data; Node next; } Hãy viết hàm Node* find(Node* head, int key) với C/C++, hay Node find(Node head, int key) với Java để tìm xem phần tử có khoá key có trong dãy A hay không ? Trả về phần tử đó nếu có, còn nếu không trả về null (rỗng). Câu 3 (1.5 điểm) Giả sử có hàng đợi (queue) Q gồm các giá trị [4, 3, 2, 1] (trong đó 1 ở đầu hàng đợi (bên phải) có thể lấy ra, và 4 ở đuôi hàng đợi (bên trái) nơi có thể thêm tiếp vào); và có một ngăn xếp (stack) S rỗng. Chỉ sử dụng S, Q và thêm một biến duy nhất nếu cần (không được sử dụng thêm bất kỳ cấu trúc dữ liệu nào khác), hãy liệt kê các thao tác để có được ngăn xếp S như sau: a. [1, 2] b. [2, 4] c. [2, 1] (Trong đó đầu ngăn xếp ở bên phải, tức là 2 trong câu (a), và 1 trong câu (c)). Câu 4 (1 điểm) Trình bày ngắn gọn thuật toán sắp xếp nhanh (Quick sort). Minh hoạ bằng việc sắp xếp theo thứ tự tăng dần dãy số sau: 7, 6, 10, 8, 9, 4, 3, 5. (Nêu rõ cách chọn phần tử chốt (pivot) khi trình bày.)