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

Nội dung

Điểm

Câu I. Phần bắt buộc

a. Trình bày được giải thuật Selection Sort.

1

- 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 0,25

K[1] K[2] K[3] K[4] K[5] K[6] K[7] K[8] K[9]

9 0 3 99 35 10 25 88 18

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 0 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Kết quả 0

10 10 9 9 35 35 35 35 35 25 25 99 99 99 99 18 18 25 25 25 25 25 35 35 35 9 9 10 10 10 3 3 3 88 88 88 88 88 88 88 88 88 18 18 18 18 99 99 99 99 99

0,75 0,25

2

a. Định nghĩa khóa của lược đồ quan hệ

Trang: 1/4

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 0,25 0,50 0,25

c. Áp dụng Bước 1: Gán K = R = {A,B,C,D,E,G,H,I} Bước 2: Lần lượt loại bớt các thuộc tính của K - 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ì pth CG → AE khiến A thuộc về {C,D,E,G,H,I}+ và pth AC → B nên K ={C,D,E,G,H,I}. - Loại phần tử C, ta có {D,E,G,H,I}+ ≠ R nên K vẫn là {C, D,E,G,H,I} - Loại phần tử D, ta có: {C, E,G,H,I}+ = R vì pth CG → AE khiến A thuộc về {C, E,G,H,I}+ và pth AC → B nên K ={C,E,G,H,I}. - Loại phần tử E, ta có: {C, G,H,I}+ = R vì pth CG → AE , AC → B , ABC→ D nên K ={C,G,H,I}. - Loại phần tử G, ta có: {C, H,I}+ ≠ R nên K vẫn là {C, G,H,I}. - Loại phần tử H, ta có: {C, G,I}+ ≠ R nên K vẫn là {C, G,H,I}. - Loại phần tử I, ta có: {C,G,H}+ = R vì CG → AE , AC → B, ABC→ D nên K={C,G,H}. => Vậy K={ C,G,H} là một khóa của r ( R )

Trang: 2/4

3

0,25

0,1 0,1 0,25 0,1 0,25

#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(); PS operator+(const PS &p2); void operator=(const PS &p2); }; void PS:: nhap() { cout<<"\n Nhap tu so:"; cin>>t; cout<<"Nhap mau so:"; cin>>m; } void PS:: hienthi() { cout <

Trang: 3/4

0,25 0,5

0,2

mang cac cua phan so

void nhapmangPS(PS *a,int n) { for (int i=1;i<=n;i++) a[i].nhap(); } PS tongmangPS(PS *a,int n) { PS tg; tg=a[1]; for(int i=2;i<=n;i++) tg=tg+a[i]; tg.rutgon(); return tg; } void main() { int n; PS a[10],p2; cout<<"\nNhap so phan so:"; cin>>n; nhapmangPS(a,n); p2=tongmangPS(a,n); cout<<"Tong la:";p2.hienthi(); getch(); }

II. Phần tự chọn

………, ngày ………. tháng ……. năm ………

Trang: 4/4