Đá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 - LT19

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM<br /> Độc lập – Tự do – Hạnh phúc<br /> ĐÁP ÁN<br /> ĐỀ THI TỐT NGHIỆP CAO ĐẲNG NGHỀ KHOÁ 2 (2008 - 2011)<br /> NGHỀ: LẬP TRÌNH MÁY TÍNH<br /> MÔN THI: LÝ THUYẾT CHUYÊN MÔN NGHỀ<br /> Mã đề số: DA LTMT - LT19<br /> Câu<br /> Nội dung<br /> I. Phần bắt buộc<br /> 1<br /> a. Trình bày được giải thuật Insertion Sort.<br /> - Trước hết: ta xem phần tử a[0] là một dãy đã có thứ tự.<br /> - Bước 1: xen phần tử a[1] vào danh sách đã có thứ tự a[0] sao<br /> cho a[0], a[1] là một danh sách có thứ tự.<br /> - Bước 2: xen phần tử a[2] vào danh sách đã có thứ tự a[0],<br /> a[1] sao cho a[0], a[1], a[2] là một danh sách có thứ tự.<br /> - Tổng quát ở bước i: xen phần tử a[i] vào danh sách đã có thứ<br /> tự a[0], a[1], … a[i-1] sao cho a[0], a[1],.. a[i] là một danh<br /> sách có thứ tự.<br /> - Sau n-1 bước thì kết thúc.<br /> <br /> Điểm<br /> <br /> 0,25<br /> 0.25<br /> <br /> 0,25<br /> <br /> 0,25<br /> <br /> b. Áp dụng giải thuật Insertion Sort với bộ dữ liệu<br /> K = {9, 3, 10, 0, 99, 35, 25, 88, 18}<br /> Khóa<br /> Bước<br /> Ban<br /> đầu<br /> Bước 1<br /> Bước 2<br /> Bước 3<br /> Bước 4<br /> Bước 5<br /> Bước 6<br /> Bước 7<br /> Bước 8<br /> Kết<br /> quả<br /> <br /> 2<br /> <br /> K[0] K[1] K[2] K[3] K[4] K[5] K[6] K[7] K[8]<br /> 9<br /> <br /> 3<br /> <br /> 10<br /> <br /> 0<br /> <br /> 99<br /> <br /> 35<br /> <br /> 25<br /> <br /> 88<br /> <br /> 18<br /> <br /> 3<br /> 3<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> 0<br /> <br /> 9<br /> 9<br /> 3<br /> 3<br /> 3<br /> 3<br /> 3<br /> 3<br /> 3<br /> <br /> 10<br /> 10<br /> 9<br /> 9<br /> 9<br /> 9<br /> 9<br /> 9<br /> 9<br /> <br /> 0<br /> 0<br /> 10<br /> 10<br /> 10<br /> 10<br /> 10<br /> 10<br /> 10<br /> <br /> 99<br /> 99<br /> 99<br /> 99<br /> 35<br /> 25<br /> 25<br /> 18<br /> 18<br /> <br /> 35<br /> 35<br /> 35<br /> 35<br /> 99<br /> 35<br /> 35<br /> 25<br /> 25<br /> <br /> 25<br /> 25<br /> 25<br /> 25<br /> 25<br /> 99<br /> 88<br /> 35<br /> 35<br /> <br /> 88<br /> 88<br /> 88<br /> 88<br /> 88<br /> 88<br /> 99<br /> 88<br /> 88<br /> <br /> 18<br /> 18<br /> 18<br /> 18<br /> 18<br /> 18<br /> 18<br /> 99<br /> 99<br /> <br /> 0,75<br /> <br /> 0,25<br /> <br /> a. Các dạng chuẩn 1NF, 2NF, 3NF<br /> - Một lược đồ quan hệ R là ở dạng chuẩn 1 (1NF) nếu miền 0,5<br /> giá trị của các thuộc tính của nó chỉ chứa các giá trị nguyên tử<br /> (đơn, không phân chia được) và giá trị của một thuộc tính bất<br /> kỳ trong một bộ giá trị phải là một giá trị đơn thuộc miền giá<br /> trị của thuộc tính đó.<br /> Trang: 1/4<br /> <br /> - Một lược đồ quan hệ R là ở dạng chuẩn 2 (2NF) nếu R đạt 0,5<br /> dạng chuẩn 1 và tất cả các thuộc tính không khoá của R đều<br /> phụ thuộc đầy đủ vào khoá (hay mỗi thuộc tính không khóa A<br /> của R đều không phụ thuộc bộ phận nào của một khóa bất kỳ<br /> của R)<br /> - Một lược đồ quan hệ R là ở dạng chuẩn 3 (3NF) nếu khi một 0,5<br /> phụ thuộc hàm X  A thỏa mãn trong R, thì:<br /> + Hoặc X là một siêu khóa của R<br /> + Hoặc A là một thuộc tính khóa của R<br /> b. Cho biết dạng chuẩn của các lược đồ quan hệ sau:<br /> - Q1(ABCDEG); F1={A→BC, C→DE, E→G}<br /> - Ta có: K ={A}<br /> 0,5<br /> - Vậy D, E, C, G là thuộc tính không khóa mà C→DE, E→G<br /> - Do vậy Q không thuộc dạng chuẩn 3, mà Q thuộc dạng<br /> chuẩn 2<br /> - Q2(ABCD) ; F2={AB → C ; D → B C → ABD}<br /> - Ta có: K1=[AB]; K2=[AD];K3=[C]<br /> 0,5<br /> là các khoá<br /> - Vậy Q2 không có thuộc tính không khoá nên Q2 đạt chuẩn 3<br /> - Q3(GMVNHP); F3={G→N; G→H; G→P; M→V;<br /> NHP→M}<br /> - Khoá của Q là G.<br /> - Thuộc tính không khoá là M, V, N, H, P.<br /> - Do các phụ thuộc hàm G → M; G → V; G → N; G → H; G<br /> → P là các phụ thuộc hàm đầy đủ, nên lược đồ quan hệ Q đạt<br /> dạng chuẩn 2 , Q không dạt dạng chuẩn 3.<br /> <br /> Trang: 2/4<br /> <br /> 0,5<br /> <br /> 3<br /> <br /> #include <br /> #include <br /> #include <br /> int uscln(int a,int b)<br /> {<br /> while (!(a%b==0) )<br /> {<br /> int r=b; b=a%b;a=r;<br /> }<br /> return b;<br /> }<br /> class PS<br /> {<br /> private:<br /> int t,m;<br /> public:<br /> void nhap();<br /> void hienthi();<br /> void rutgon();<br /> PS operator+(const PS &p2);<br /> void operator=(const PS &p2);<br /> <br /> 0,25<br /> <br /> };<br /> void PS:: nhap()<br /> {<br /> coutt;<br /> coutm;<br /> }<br /> void PS:: hienthi()<br /> {<br /> cout