Cộng đồng chia sẻ tri thức Lib24.vn

Giáo án môn Cấu trúc dữ liệu (CSDL&CTDL) và Thiết kế web - Cô Võ Thị Hường

bce1db85514c6d9bcac570a35917a249
Gửi bởi: Võ Thị Hường 12 tháng 4 2021 lúc 13:04:26 | Được cập nhật: 14 giờ trước (8:26:32) | IP: 10.1.29.62 Kiểu file: DOCX | Lượt xem: 990 | Lượt Download: 22 | File size: 0.063819 Mb

Nội dung tài liệu

Tải xuống
Link tài liệu:
Tải xuống

Các tài liệu liên quan


Có thể bạn quan tâm

Thông tin tài liệu

huongvt-csdlctdl-tkweb-1-276691674367-1618207062

NGÂN HÀNG ĐỀ THI TỐT NGHIỆP CAO ĐẲNG KHOÁ 11, TRUNG CẤP KHÓA 47

NGHỀ: THIẾT KẾ TRANG WEB

Phần I. Cơ sở dữ liệu; Cấu trúc dữ liệu và giải thuật (3 điểm)

Câu 1. (3 điểm)

Cho CSDL quản lý lao động gồm các quan hệ sau:

Congtrinh(MACT,TENCT,DIADIEM ,NGAYCAPGP,NGAYKC,NGAYHT)

Nhanvien(MANV,HOTEN,NGAYSINH,PHAI,DIACHI,MAPB)

Phongban(MAPB,TENPB)

Phancong(MACT,MANV,SLNGAYCONG)

Trong đó: MACT – mã công trình; TENCT – tên công trình, DIADIEM – địa điểm thực hiện công trình, NGAYCAPGP – ngày cấp giấy phép, NGAYKC – ngày khởi công, NGAYHT – ngày hoàn thành, MANV – mã nhân viên, HOTEN – họ tên nhân viên, NGAYSINH – ngày sinh, PHAI – phái , DIACHI – địa chỉ, MAPB – mã phòng ban, SLNGAYCONG – số lượng ngày công.

Hãy thực hiện các câu hỏi sau bằng lệnh SQL :

  1. Đếm số nhân viên ở “Hà Nội” có mã phòng là “PB01”

  2. Đếm những công trình được thực hiện tại “Nam Định”.

  3. Lập danh sách các công trình có thời gian thi công trên 2 năm.

Đáp án

TT Nội dung Điểm
1

  1. Đếm số nhân viên ở “Hà Nội” có mã phòng là “PB01”

Select count(MANV), MAPB

From Nhanvien

Where DIACHI=”Hà Nội”

And MAPB=”PB01”

Group by MAPB;

  1. điểm

b. Lập danh sách các công trình có thời gian thi công trên 2 năm

Select *

From Congtrinh

Where (year(NGAYKC) – year(NGAYHT)) >2

  1. điểm

c. Đếm những công trình được thực hiện tại “Nam Định”

Select count(MACT), DIADIEM

From Congtrinh

Where DIADIEM=”Nam Định”

Group by DIADIEM;

 1 điểm

Câu 2. (3 điểm)

Cho cơ sở dữ liệu “Hệ thống quản lý xe ô tô du lịch” ở một doanh nghiệp vận tải hành khách như sau:

LOAIXE (MaLX, TenLX, ThongTinLX, SoLuongXe)

Tân từ: mỗi loại xe ô tô có một mã số để phân biệt với các loại xe ô tô khác, tên loại xe (ví dụ tên loại xe 7-chỗ, 15-chỗ,…), và thông tin về loại xe đó, SoLuongXe là tổng số xe ô tô có loại xe này.

XE (MaXe, TenXe, CapSo, MaLX, HangSX, ThongTinXe)

Tân từ: mỗi xe ô tô được gán một mã số duy nhất để phân biệt với các xe ô tô khác, tên xe, biến số xe ô tô (CapSo), hãng sản xuất, thông tin về chiếc xe.

TAIXE (MaTX, HoTen, NgaySinh, GioiTinh, DiaChi)

Tân từ: mỗi tài xế của công ty có một mã số để phân biệt với các tài xế khác, họ tên tài xế, ngày sinh, giới tính (Nam/Nữ), địa chỉ.

CHUYENDI (SoCD, MaXe, MaTX, NgayDi, NgayVe, NoiDi, NoiDen, ChieuDai, SoNguoi)

Tân từ: mỗi tài xế (MaTX) được phân công lái xe (MaXe) theo một lộ trình (SoCD), ngày đi, ngày về, nơi đi, nơi đến, chiều dài đường đi ước lượng (tính theo km), chở số người đi (SoNguoi) cho chuyến đi đó.

Yêu cầu:

Thực hiện câu truy vấn sau bằng đại số quan hệ:

  1. Cho biết họ tên tài xế, ngày đi, ngày về của những chuyến đi có chiều dài lớn hơn hoặc bằng 300km đã chuyên chở từ 12 người trở lên trong mỗi chuyến.

Thực hiện các câu truy vấn sau bằng ngôn ngữ SQL:

  1. Cho biết họ tên tài xế, ngày đi, ngày về của những chuyến đi có chiều dài lớn hơn hoặc bằng 300km đã chuyên chở từ 12 người trở lên trong mỗi chuyến, thuộc xe có mã loại xe là ‘15-Cho’.

  2. Với mỗi tài xế, hãy cho biết tổng số chuyến đi mà tài xế được phân công lái xe trong năm 2019 (tính theo ngày đi). Thông tin hiển thị gồm 2 cột: Mã tài xế, họ tên và tổng số chuyến đi.

Đáp án

TT Nội dung Điểm

a

b

c

Câu a

(TaiXe (ChuyenDi: ChieuDai >=300 ∧ SoNguoi> = 12)) [HoTen, NgayDi, NgayVe]

Câu b

SELECT HoTen, NgayDi, NgayVe

FROM TaiXe t, Xe x, ChuyenDi c

WHERE t.MaTX = c.MaTX

AND x.MaXe = c.MaXe

AND x.MaLX = ‘15-Cho’

AND c.ChieuDai >= 300

AND c.SoNguoi >= 12

Câu c

SELECT t.MaTX,t.HoTen, count(c.SoCD) as TongSoChuyenDi

FROM TAIXE t, CHUYENDi c

WHERE c.MaTX = t.MaTX and Year(NgayDi) = 2019

GROUP BY t.MaTX, t.HoTen

1.0 điểm

1.0

điểm

1.0 điểm

Câu 3: ( 3 điểm)

Cho lược đồ quan hệ R(U,F) với U = {ABCDEG}

F={ BC → E;D →A; C → A; AE → D; BE → CG}

a. Tìm một khoá K của R

b. Lược đồ còn khoá nào khác không? vì sao?

c. Tập BCG có phải là khoá của R không? vì sao?

d. Tập BD có phải là khoá của R không? vì sao?

Đáp án

TT Nội dung Điểm

Cho lược đồ quan hệ R(U,F) với U = {ABCDEG}

F={ BC → E;D →A; C → A; AE → D; BE → CG}

 3 điểm
a Lược đồ trên có một khoá là: BC 0.5 điểm
b Lược đồ trên còn một khoá nữa là: BE vì theo đầu bài trên ta thấy rằng vế phải của F có thuộc tính B không xuất hiện --> B chắc chắn sẽ tham gia vào khoá của lược đồ trên. Vì B không phải là khoá của lược đồ nên nhất định lược đồ trên có ít nhất 2 khoá trở lên và cụ thể trong lược đồ này có 2 khoá là: BC và BE. 1 điểm
c

Tập BCG không phải là khoá vì:

Giả sử k là khoá thì k phải thoả mãn 2 điều kiện sau:

đk1: kF+ = U

đk2: ∀k’ ⊆ k, k’F+⊄ U

Rõ ràng tập con của BCG có BCF+ = U = ABCDEG do vậy vi phạm điều kiện 2 ==> BCG không phải là khoá.

 1.5 điểm

Câu 4. (3 điểm)

  1. Trình bày ý tưởng và giải thuật của thuật toán sắp xếp nổi bọt (bubble-sort).

  2. Hãy đưa ra một dãy khoá gồm 10 phần tử bất kỳ, sau đó sắp xếp dãy khoá đó theo thứ tự giảm dần bằng giải thuật sắp xếp kiểu nổi bọt.

  3. Cho biết độ phức tạp của giải thuật sắp xếp nổi bọt.

Đáp án

TT Nội dung Điểm
a Trình bày ý tưởng và giải thuật của thuật toán sắp xếp nổi bọt (bubble-sort) 1 điểm

*) Ý tưởng:

- Ban đầu có một dãy khóa k1,k2,k3….kn chưa được sắp xếp

- Duyệt toàn bộ dãy khóa, tại mỗi bước quét dãy khóa từ cuối dãy, nếu gặp hai phần tử liên tiếp nghịch thế thì tiến hành đổi chỗ.

- Trong quá trình sắp xếp phần tử nhẹ hơn sẽ nổi lên trên, phần tử nặng hơn sẽ chìm xuống dưới.

 0.5 điểm

*) Giải thuật:

void bubble-sort (int a[], int n)

{

int i,j,n,tg;

for (i=0; i<n; i++)

for (j=n-1; j>=i+1; j--)

if (a[j] <a[j-1])

tg=a[j];

a[j]=a[j-1];

a[j-1]=tg;

}

 0.5 điểm
b Hãy đưa ra một dãy khoá gồm 10 phần tử bất kỳ, sau đó đưa ra kết quả thực hiện các bước để sắp xếp dãy khoá đó theo thứ tự giảm dần bằng giải thuật sắp xếp kiểu nổi bọt. 1.5

Cho một dãy khoá chẳng hạn:

36 18 19 52 53 72 39 61 70 90.

Bước 1: 90 36 18 19 52 53 72 39 61 70
Bước 2: 90 72 36 18 19 52 53 70 39 61

Bước 3: 90 72 70 36 18 19 52 53 61 39

Bước 4: 90 72 70 61 36 18 19 52 53 39

Bước 5: 90 72 70 61 53 36 18 19 52 39

Bước 6: 90 72 70 61 53 52 36 18 19 39

Bước 7: 90 72 70 61 53 52 39 36 18 19

Bước 8: 90 72 70 61 53 52 39 36 18 19

Bước 9: 90 72 70 61 53 52 39 36 19 18

Kết quả 90 72 70 36 18 19 52 53 61 39
c

Cho biết độ phức tạp của giải thuật sắp xếp nổi bọt

Với mỗi i = 1,2,..,n-1 ta cần i phép so sánh. Do đó số nhiều nhất các lần so sánh và đổi chỗ trong giải thuật là:

Do đó độ phức tạp của giải thuật là khoảng O(n2).

 0.5

Câu 5. (3 điểm)

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

b. Áp dụng: Cho L quản lý một danh sách liên kết đơn, M là con trỏ đang trỏ vào một nút trong danh sách. Viết các giải thuật:

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

- Xóa nút thứ k trong danh sách.

Đáp án

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

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

0.25

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.

 2

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;

}

}

 1
- Xóa nút thứ k trong danh sách. 1

Void Xoa_nut_thu_k(L,k)

{

// tìm đến nút thứ k

p=L; dem=1;

while(p!=null && dem<k)

{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 ”<<k<< “trong danh sach”;

}

Phần II. HTML, CSS, JS (3 điểm)

Câu 1. (3 điểm)

Câu 2. (3 điểm)

Câu 3. (3 điểm)

Câu 4. (3 điểm)

Câu 5. (3 điểm)

Phần III. PHP (4 điểm)

Câu 1. (4 điểm)

Câu 2. (4 điểm)

Câu 3. (4 điểm)