tailieunhanh - Đáp án đề thi tốt nghiệp cao đẳng nghề khoá II (năm 2008 - 2011) nghề Lập trình máy tính môn thi lý thuyết chuyên môn nghề - Mã đề thi: DA LTMT - LT11

Nhằm mục đích giúp các bạn có thêm tư liệu trong việc ôn tập tố nghiệp chuyên ngành Lập trình máy tính môn Lý thuyết chuyên môn nghề chúng tôi giới thiệu tới các bạn Đáp án đề thi tốt nghiệp cao đẳng nghề khoá II (năm 2008 - 2011) nghề Lập trình máy tính môn thi lý thuyết chuyên môn nghề - Mã đề thi: DA LTMT - LT11. | CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc ĐÁP ÁN ĐỀ THI TỐT NGHIỆP CAO ĐẲNG NGHỀ KHOÁ 2 (2008 - 2011) NGHỀ: LẬP TRÌNH MÁY TÍNH MÔN THI: LÝ THUYẾT CHUYÊN MÔN NGHỀ Mã đề số: DA LTMT - LT11 Câu Nội dung I. Phần bắt buộc 1 a. Trình bày được giải thuật Selection Sort. Điểm - Bước 0: chọn phần tử có giá trị nhỏ nhất trong n phần tử từ a[0] đến a[n-1] và hoán vị nó với phần tử a[0]. - Bước 1: chọn phần tử có giá trị nhỏ nhất trong n-1 phần tử từ a[1] đến a[n-1] và hoán vị nó với a[1]. - Tổng quát ở bước thứ i: chọn phần tử có giá trị nhỏ nhất trong n-i phần tử từ a[i] đến a[n-1] và hoán vị nó với a[i]. - Sau n-1 bước (từ bước 0 đến n-2) thì mảng đã được sắp xếp. 0,25 0,25 0,25 b. Áp dụng giải thuật Selection Sort với bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25, 88, 18} Khóa Bước Ban đầu Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Kết quả 2 K[1] K[2] K[3] K[4] K[5] K[6] K[7] K[8] K[9] 9 3 10 0 99 35 25 88 18 0 3 3 10 10 9 9 9 10 10 99 99 99 99 18 35 35 35 35 35 25 25 25 25 25 25 35 35 0 3 9 10 18 25 35 88 88 88 88 88 88 88 88 88 18 18 18 18 99 99 99 99 99 0,75 a. Định nghĩa khóa của lược đồ quan hệ Trang: 1/4 0,25 Cho lược đồ quan hệ R với các tập thuộc tính U={A1,A2, ., An} và các phụ thuộc hàm F, X U. Ta nói X là một khóa của R nếu: - X U F+ . Nghĩa là X xác định hàm tất cả các thuộc tính (các phụ thuộc hàm này thuộc F hoặc được suy diễn logic từ F). - Không có Y X mà Y U F+ . b. Thuật toán tìm một khóa của lược đồ quan hệ Vào: lược đồ quan hệ R với tập thuộc tính U và tập phụ thuộc hàm F Ra: Tập K là khóa của R Thuật toán: - Đặt K=U - Lặp lại quá trình loại bỏ khỏi K thuộc tính A mà {K-A}+ =U. 0,25 0,25 0,25 0,25 c. Áp dụng Bước 1: Gán K = R = {A,B,C,D,E,G,H,I} 0,25 Bước 2: Lần lượt loại bớt các thuộc tính của K 0,50 + - Loại phần tử A: ta có {B,C,D,E,G,H,I} = R vì pth CG → AE khiến A thuộc về {B,C,D,E,G,H,I}+ nên K = {B,C,D,E,G,H,I}. - Loại phần tử B, ta có {C,D,E,G,H,I}+ = R vì