Dưới đây là Đá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 - LT12 dành cho các bạn chuyên ngành Lập trình máy tính. Tài liệu giúp các bạn có thêm tư liệu trong việc luyện thi tốt nghiệp cho chuyên ngành này. | 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 - LT12 Câu Nội dung I. Phần bắt buộc 1 a. Trình bày được giải thuật Insertion Sort. - Trước hết: ta xem phần tử a[0] là một dãy đã có thứ tự. - Bước 1: xen phần tử a[1] vào danh sách đã có thứ tự a[0] sao cho a[0], a[1] là một danh sách có thứ tự. - Bước 2: xen phần tử a[2] vào danh sách đã có thứ tự a[0], a[1] sao cho a[0], a[1], a[2] là một danh sách có thứ tự. - Tổng quát ở bước i: xen phần tử a[i] vào danh sách đã có thứ tự a[0], a[1], a[i-1] sao cho a[0], a[1], a[i] là một danh sách có thứ tự. - Sau n-1 bước thì kết thúc. Điểm 0,25 0,25 0,25 b. Áp dụng giải thuật Insertion 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[0] K[1] K[2] K[3] K[4] K[5] K[6] K[7] K[8] 9 3 10 0 99 35 25 88 18 3 3 0 0 0 0 0 0 0 9 9 3 3 3 3 3 3 3 10 10 9 9 9 9 9 9 9 0 0 10 10 10 10 10 10 10 99 99 99 99 35 25 25 18 18 35 3 35 35 99 35 35 25 25 25 25 25 25 25 99 88 35 35 88 88 88 88 88 88 99 88 88 18 18 18 18 18 18 18 99 99 0,75 a. Nêu 4 tính chất của phụ thuộc hàm - Phản xạ: Nếu Y X thì X → Y - Bắt cầu: Nếu X → Y và Y → Z thì X → Z - Phân rã: Nếu X → YZ thì X → Y và X → Z - Bắt cầu: Nếu X → Y và X → Z thì X → YZ Trang: 1/4 0,25 0,25 0,25 0,25 0,25 b. Áp dụng: Tìm chuỗi suy diễn AB → EG 1) AB AB (tính phản xã) 2) AB B (phân rã) 3) B D (F2) 4) AB D (tính bắc cầu 2 &3) 5) AB C (F1) 6) AB DC (kết hợp 4&5) 7) CD E (F3) 8) AB E (bắc cầu 6&7) 9) AB CE (kết hợp 5&8) 10)CE HG (F4) 11)CE G (phan rã) 12)AB G (bắc cầu 9&11) 13)AB EG (kết hợp 8&12) 3 #include #include #include int uscln(int a,int b) { while (!(a%b==0) ) { int r=b; b=a%b;a=r; } return b; } class PS { private: int t,m; public: void nhap(); void hienthi(); void rutgon(); int
