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Á 3 (2009- 2012) NGHỀ: LẬP TRÌNH MÁY TÍNH MÔN THI: LÝ THUYẾT CHUYÊN MÔN NGHỀ Mã đề số: DA LTMT - LT14

Nội dung Điểm

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

1 a. Trình bày phương pháp biểu diễn danh sách liên kết đơn.

0,5

- Danh sách liên kết đơn là một cấu trúc dữ liệu bao gồm 1 tập hợp các phần tử, trong đó mỗi phần tử là một nút, trong mỗi nút có chứa một liên kết tới nút kế tiếp.

- Cấu trúc 1 nút của danh sách liên kết đơn

INFO LINK

Trong đó:

+ INFO: là trường chứa thông tin (dữ liệu) của nút

+ LINK: là con trỏ chứa địa chỉ của nút kế tiếp trong

danh sách.

- Nút cuối trong danh sách, trường link có giá trị là NULL có nghĩa là không chứa địa chỉ nút nào.

- Danh sách liên kết đơn luôn được quản lý bởi một con trỏ trỏ vào nút đầu tiên trong danh sách.

- Một danh sách liên kết đơn được biểu diễn tổng quát như sau:

L

Trang: 1/5

0,75

b. Áp dụng: - Thêm một nút có thông tin là X vào sau nút M đang trỏ, nếu không tồn tại nút M thì chèn vào đầu danh sách. void chen_sauM(L, M, X) { // Tạo nút mới new <= avail; // Cấp phát bộ nhớ new->info=X; // Tìm vị trí chèn và chèn P=L; while(p!=M && p!=NULL) {p=p->link;} if(p!=NULL) // tìm thấy

{

new->link=M->link; M->link=new;

}

else // Không tìm thấy

{

new->link=L; L=new;

}

}

0,75

- Xóa nút thứ k trong danh sách. Void Xoa_nut_thu_k(L,k) { // tìm đến nút thứ k p=L; dem=1; while(p!=null && dem

{dem++; q=p; p=p->link;}

if(p!=NULL) // tồn tại nút thứ k

{ if(p= =L) L=L->link; else q->link=p->link; free(p);

}

else

Count<<”Khong ton tại nut thu

”<

}

Trang: 2/5

2

0,5

0,5

0,5

a. Trình bày định nghĩa phép hợp, phép giao, phép trừ của hai lược đồ quan hệ. - Phép hợp: Hợp của hai quan hệ R và S khả hợp là một quan hệ, ký hiệu là R (cid:0) S và là tập hợp tất cả các bộ t sao cho t (cid:0) R hoặc t (cid:0) S Biểu diễn hình thức phép hợp có dạng: R (cid:0) S ={t| t (cid:0) R hoặc t (cid:0) S } - Phép giao: Giao của hai quan hệ R và S khả hợp là một quan hệ, ký hiệu là R (cid:0) S và là tập hợp tất cả các bộ t sao cho t (cid:0) R và t (cid:0) S Biểu diễn hình thức phép hợp có dạng: R (cid:0) S ={t| t (cid:0) R và t (cid:0) S } - Phép trừ: Hiệu của hai quan hệ R và S khả hợp là một quan hệ, ký hiệu là R- S và là tập hợp tất cả các bộ t sao cho t (cid:0) R nhưng t (cid:0) S Biểu diễn hình thức phép hợp có dạng: R- S ={t| t (cid:0) R và t (cid:0) S }

r2 ; r2 (cid:0) r1 ; r1 – r2 , r2 -r1

b. Tính: r1 (cid:0) r1 (cid:0) 0,5

0,5 r2 (cid:0)

0,5

r2 = ( A 1 0 1 1 0 1 1 0 r1 = ( A 1 0 r1 – r2 = ( A 1 0 1 B 0 1 0 0 1 1 1 1 B 0 1 B 0 1 0 C 1 1 0 0 0 0 0 1 C 0 0 C 1 1 0 D) 1 1 0 1 1 0 1 0 D) 0 1 D) 1 1 1

Trang: 3/5

0,25 3

#include #include #include class DT { private:

double a[20];// Mang chua cac he so da thuc

a0, a1,...

int n ;// Bac da thuc

public: void nhap(); void hienthi(); DT operator-(const DT &d2); double operator^(double x);// Tinh gia tri da thuc };

0,25

0,25

void DT::hienthi() { cout<> n; cout << "Nhap cac he so da thuc:" ; for (int i=0 ;i<=n ;++i) { cout << "\n He so bac"<> a[i] ; } }

0,75

DT DT::operator-(const DT &d2) { DT d; int k,i; k = (n > d2.n)?n:d2.n ; for (i=0;i<=k ;++i) if (i<=n && i<=d2.n)

d.a[i] = a[i] - d2.a[i];

else

if (i<=n) d.a[i] =a[i]; else d.a[i] = -d2.a[i]; i = k; while (i>0 && d.a[i]==0.0) --i; d.n=i; return d ;}

Trang: 4/5

0,25

0,25

double DT::operator^(double x) { double s=0.0 , t=1.0; for (int i=0 ;i<= n ;++i) { s+= a[i]*t; t *= x; } return s; } void main() { DT p,q,f; double x,g; clrscr(); cout <<"\n Nhap da thuc P :" ;p.nhap(); cout <<"\n Nhap da thuc Q :" ;q.nhap(); cout << "\n Nhap so thuc x :" ;cin >> x; f = (p-q); g = f^x; cout << "\n Da thuc f "; f.hienthi(); cout<<"\n x =" << x; cout << "\n f(x) = "<

II. Phần tự chọn, do trường biên soạn

1

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

Trang: 5/5