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 - LT11<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 Selection Sort.<br />
<br />
Điểm<br />
<br />
- Bước 0: chọn phần tử có giá trị nhỏ nhất trong n phần tử từ<br />
a[0] đến a[n-1] và hoán vị nó với phần tử a[0].<br />
- Bước 1: chọn phần tử có giá trị nhỏ nhất trong n-1 phần tử từ<br />
a[1] đến a[n-1] và hoán vị nó với a[1].<br />
- Tổng quát ở bước thứ i: chọn phần tử có giá trị nhỏ nhất<br />
trong n-i phần tử từ a[i] đến a[n-1] và hoán vị nó với a[i].<br />
- Sau n-1 bước (từ bước 0 đến n-2) thì mảng đã được sắp xếp.<br />
<br />
0,25<br />
0.25<br />
0,25<br />
0,25<br />
<br />
b. Áp dụng giải thuật Selection 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 quả<br />
<br />
2<br />
<br />
K[1] K[2] K[3] K[4] K[5] K[6] K[7] K[8] K[9]<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 />
0<br />
<br />
3<br />
3<br />
<br />
10<br />
10<br />
9<br />
<br />
9<br />
9<br />
10<br />
10<br />
<br />
99<br />
99<br />
99<br />
99<br />
18<br />
<br />
35<br />
35<br />
35<br />
35<br />
35<br />
25<br />
<br />
25<br />
25<br />
25<br />
25<br />
25<br />
35<br />
35<br />
<br />
0<br />
<br />
3<br />
<br />
9<br />
<br />
10<br />
<br />
18<br />
<br />
25<br />
<br />
35<br />
<br />
88<br />
88<br />
88<br />
88<br />
88<br />
88<br />
88<br />
88<br />
88<br />
<br />
18<br />
18<br />
18<br />
18<br />
99<br />
99<br />
99<br />
99<br />
99<br />
<br />
0,75<br />
<br />
a. Định nghĩa khóa của lược đồ quan hệ<br />
<br />
Trang: 1/4<br />
<br />
0,25<br />
<br />
Cho lược đồ quan hệ R với các tập thuộc tính U={A1,A2, ...,<br />
An} và các phụ thuộc hàm F, X U. Ta nói X là một khóa của<br />
R nếu:<br />
- X U F+ . Nghĩa là X xác định hàm tất cả các thuộc tính<br />
(các phụ thuộc hàm này thuộc F hoặc được suy diễn logic từ<br />
F).<br />
- Không có Y X mà Y U F+ .<br />
b. Thuật toán tìm một khóa của lược đồ quan hệ<br />
Vào: lược đồ quan hệ R với tập thuộc tính U và tập phụ thuộc<br />
hàm F<br />
Ra: Tập K là khóa của R<br />
Thuật toán:<br />
- Đặt K=U<br />
- Lặp lại quá trình loại bỏ khỏi K thuộc tính A mà<br />
{K-A}+ =U.<br />
<br />
0,25<br />
<br />
0,25<br />
<br />
0,25<br />
<br />
0,25<br />
<br />
c. Áp dụng<br />
Bước 1: Gán K = R = {A,B,C,D,E,G,H,I}<br />
0,25<br />
Bước 2: Lần lượt loại bớt các thuộc tính của K<br />
0,50<br />
+<br />
- Loại phần tử A: ta có {B,C,D,E,G,H,I} = R<br />
vì pth CG → AE khiến A thuộc về {B,C,D,E,G,H,I}+<br />
nên K = {B,C,D,E,G,H,I}.<br />
- Loại phần tử B, ta có {C,D,E,G,H,I}+ = R<br />
vì pth CG → AE khiến A thuộc về {C,D,E,G,H,I}+ và<br />
pth AC → B nên K ={C,D,E,G,H,I}.<br />
- Loại phần tử C, ta có {D,E,G,H,I}+ ≠ R nên K vẫn là {C,<br />
D,E,G,H,I}<br />
- Loại phần tử D, ta có: {C, E,G,H,I}+ = R vì pth<br />
CG → AE khiến A thuộc về {C, E,G,H,I} + và<br />
pth AC → B nên K ={C,E,G,H,I}.<br />
- Loại phần tử E, ta có: {C, G,H,I}+ = R vì<br />
pth CG → AE , AC → B , ABC→ D nên K ={C,G,H,I}.<br />
- Loại phần tử G, ta có: {C, H,I}+ ≠ R<br />
nên K vẫn là {C, G,H,I}.<br />
- Loại phần tử H, ta có: {C, G,I}+ ≠ R<br />
nên K vẫn là {C, G,H,I}.<br />
- Loại phần tử I, ta có: {C,G,H}+ = R<br />
vì CG → AE , AC → B, ABC→ D nên K={C,G,H}.<br />
=> Vậy K={ C,G,H} là một khóa của r ( R )<br />
0,25<br />
<br />
Trang: 2/4<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
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
