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 - LT12<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 Insertion Sort.<br />
- Trước hết: ta xem phần tử a[0] là một dãy đã có thứ tự.<br />
- Bước 1: xen phần tử a[1] vào danh sách đã có thứ tự a[0] sao<br />
cho a[0], a[1] là một danh sách có thứ tự.<br />
- Bước 2: xen phần tử a[2] vào danh sách đã có thứ tự a[0],<br />
a[1] sao cho a[0], a[1], a[2] là một danh sách có thứ tự.<br />
- Tổng quát ở bước i: xen phần tử a[i] vào danh sách đã có thứ<br />
tự a[0], a[1], … a[i-1] sao cho a[0], a[1],.. a[i] là một danh<br />
sách có thứ tự.<br />
- Sau n-1 bước thì kết thúc.<br />
<br />
Điểm<br />
<br />
0,25<br />
0.25<br />
<br />
0,25<br />
<br />
0,25<br />
<br />
b. Áp dụng giải thuật Insertion 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<br />
quả<br />
<br />
2<br />
<br />
K[0] K[1] K[2] K[3] K[4] K[5] K[6] K[7] K[8]<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 />
3<br />
3<br />
0<br />
0<br />
0<br />
0<br />
0<br />
0<br />
0<br />
<br />
9<br />
9<br />
3<br />
3<br />
3<br />
3<br />
3<br />
3<br />
3<br />
<br />
10<br />
10<br />
9<br />
9<br />
9<br />
9<br />
9<br />
9<br />
9<br />
<br />
0<br />
0<br />
10<br />
10<br />
10<br />
10<br />
10<br />
10<br />
10<br />
<br />
99<br />
99<br />
99<br />
99<br />
35<br />
25<br />
25<br />
18<br />
18<br />
<br />
35<br />
3<br />
35<br />
35<br />
99<br />
35<br />
35<br />
25<br />
25<br />
<br />
25<br />
25<br />
25<br />
25<br />
25<br />
99<br />
88<br />
35<br />
35<br />
<br />
88<br />
88<br />
88<br />
88<br />
88<br />
88<br />
99<br />
88<br />
88<br />
<br />
18<br />
18<br />
18<br />
18<br />
18<br />
18<br />
18<br />
99<br />
99<br />
<br />
0,75<br />
<br />
a. Nêu 4 tính chất của phụ thuộc hàm<br />
- Phản xạ: Nếu Y X thì X → Y<br />
- Bắt cầu: Nếu X → Y và Y → Z thì X → Z<br />
- Phân rã: Nếu X → YZ thì X → Y và X → Z<br />
- Bắt cầu: Nếu X → Y và X → Z thì X → YZ<br />
Trang: 1/4<br />
<br />
0,25<br />
0,25<br />
0,25<br />
0,25<br />
0,25<br />
<br />
b. Áp dụng: Tìm chuỗi suy diễn AB → EG<br />
1) AB AB (tính phản xã)<br />
2) AB B (phân rã)<br />
3) B D (F2)<br />
4) AB D (tính bắc cầu 2 &3)<br />
5) AB C (F1)<br />
6) AB DC (kết hợp 4&5)<br />
7) CD E (F3)<br />
8) AB E (bắc cầu 6&7)<br />
9) AB CE (kết hợp 5&8)<br />
10)CE HG (F4)<br />
11)CE G (phan rã)<br />
12)AB G (bắc cầu 9&11)<br />
13)AB EG (kết hợp 8&12)<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 />
int operator>(const PS &p2);<br />
void operator=(const PS &p2);<br />
};<br />
<br />
Trang: 2/4<br />
<br />
1,0<br />
<br />
1,0<br />
0,25<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 đủ
