Đề thi cao học chuyên ngành Tin Học (Môn CoSo)

MÔN CƠ SỞ

(3 đ)
Định nghĩa và biểu diễn cây tìm kiếm nhị phân bằng danh sách móc nối
Các phép toán: tìm kiếm, chèn, xoá trên cây tìm kiếm nhị phân
Cho dãy số: 17, 12, 23, 37, 41, 15, 9,13, 7:
Xây dựng cây tìm kiếm nhị phân (vẽ biểu diễn bằng danh sách móc nối)
Mô phỏng các thủ tục trong mục b): Liệt kê các đỉnh duyệt qua từ gốc để tìm đc giá trị 15; Quá trình thực hiện để chèn thêm giá trị 27; Quá trình xoá nút có giá trị 23.
(3đ)
Với những bài toán có tính chất gì thì có thể ứng dụng chiến lược chia để trị và đệ quy để thiết kế thuật toán để giải nó.
Thông qua một ví dụ tuỳ chọn để trình bày cấu trúc chung các thuật toán chia để trị và đệ quy
Mô phỏng thuật toán giải ví dụ đã chọn trong mục b)
(1.5đ) Khẳng định hoặc bác bỏ tính đúng của các mệnh đề sau:
Cho lược đồ quan hệ R(U), K
U là một khoá của R khi và chỉ khi U phụ thuộc hàm đầy đủ vào K+, (nghĩa là K+
A là một phụ thuộc hàm đầy đủ).
Hai khoá khác nhau của một lược đồ quan hệ không bao nhau.
Tồn tại một lược đồ quan hệ ko có khoá nào
Một lược đồ quan hệ có ko quá một siêu khoá đồng thời là khoá
Số khóa của một lược đồ quan hệ không thể lớn hơ số thuộc tính
(2.5đ) Một cơ sở dữ liệu cho một công ty đầu tư gồm các thuộc tính sau: B (người buôn cổ phiếu), O (văn phòng của người buôn cổ phiếu), I (người đầu tư), S (loại cổ phiếu), Q (số lượng của loại cổ phiếu mà người đầu tư có) và D (giá trị lãi của loại cổ phiếu đó). Như vậy có các phụ thuộc hàm sau: S
A, I
B, IS
Q, B
O
Tìm khoá của lược đồ quan hệ R(BOSQID)
Tìm một phép tách R thành những lược đồ ở dạng chuẩn 3, phép tách này vừa là tách kết nối không mất thông tin vừa bảo toàn các phụ thuộc đã cho
Nếu thay phụ thuộc hàm S
D bởi phụ thuộc đa trị S

D, hãy một phép tách kết nối không tổn thất đưa lược đồ đó về dạng chuẩn 4