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 - LT15

Nội dung Điểm

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

1 0,5 Phương pháp biểu diễn danh sách liên kết đơn:

- 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 INK

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:

- 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.

Trang: 1/4

{

0,75

{ new->link=L; L=new; }

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 }

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

- 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

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

0,75

}

else

Count<<”Khong ton tại nut thu

”<

}

2

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ệ.

Trang: 2/4

0,5 0,5 0,5

0,5 0,5 0,5 0,5

- 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  S và là tập hợp tất cả các bộ t sao cho t R hoặc t S Biểu diễn hình thức phép hợp có dạng: R  S ={t| t R hoặc t 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  S và là tập hợp tất cả các bộ t sao cho t R và t S Biểu diễn hình thức phép hợp có dạng: R  S ={t| t R và t 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 R nhưng t S Biểu diễn hình thức phép hợp có dạng: R- S ={t| t R và t S } b. Tính: r1  r2 ; r2 r1 ; r1 – r2 , r2 -r1 r1  r2 = ( A 1 0 1 1 0 1 1 0 r2 r1 = ( A 1 r1 – r2 = ( A 1 0 1 0 A r2 -r1 = ( 1 1 0 0 D) 1 1 0 1 1 0 1 0 D) 0 D) 1 1 1 1 D) 0 1 1 0 C 1 1 0 0 0 0 0 1 C 0 C 1 1 0 0 C 0 0 0 1 B 0 1 0 0 1 1 1 1 B 0 B 0 1 0 1 B 1 1 1 1

II. Phần tự chọn

Trang: 3/4

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

Trang: 4/4