Đề thi cuối kỳ năm 2016 Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Đề thi cuối kỳ năm 2016 Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

39 20 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (IT003)

Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

11 trang 5 tháng trước

Tác giả:

Profile Mai Nguyệt
ĐÁP ÁN GỢI Ý VÀ THANG ĐIỂM
MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
HỌC KỲ 2 - NĂM HỌC: 2016-2017
Câu 1:
Giả sử người ta muốn sử dụng cấu trúc Stack (ngăn xếp) để lưu dãy N số nguyên
(10<N<1000) không trùng nhau, trong đó mỗi phần tử của ngăn xếp lưu một số nguyên
có miền giá trị [1,50000].
Anh / chị hãy thực hiện các yêu cầu sau :
a. Định nghĩa cấu trúc dữ liệu ngăn xếp đáp ứng yêu cầu (0.5 điểm)
b. Viết hàm nhập vào ngăn xếp có N phần tử (10<N<1000), với N nhập vào từ bàn
phím và đảm bảo giá trị các phần tử trong ngăn xếp không trùng nhau (1 điểm)
c. Viết hàm đếm xem trong ngăn xếp có bao nhiêu số nguyên tố nhỏ hơn giá trị M
(1<M<60000) nhập từ bàn phím (0.75 điểm)
d. Viết hàm xóa 5 phần tử được thêm vào sau cùng vào trong ngăn xếp (0.75 điểm)
Đáp án:
Sinh viên có thể sử dụng cấu trúc dữ liệu mảng hoặc danh sách liên kết để cài đặt Stack.
Đáp án tham khảo bên dưới sử dụng CTDL mảng để cài đặt Stack.
1.a Định nghĩa cấu trúc dữ liệu ngăn xếp đáp ứng yêu cầu (0.5 điểm)
#define MAX 1000
struct Stack {
int n;
int arr[ ];MAX
};
1.b Viết hàm nhập vào ngăn xếp có N phần tử (10<N<1000), với N nhập vào từ bàn
phím và đảm bảo giá trị các phần tử trong ngăn xếp không trùng nhau (1 điểm)
Sinh viên có thể viết thành nhiều hàm, tùy theo số hàm phân chia do sinh viên làm bài mà
Thầy / Cô điều chỉnh thang điểm phù hợp.
Trong đáp án gợi ý này có 4 hàm, được phân chia theo độ quan trọng từ cao đến thấp :
void Init(Stack &s) // 0.125 đi mể
1
{
s.n = 0;
}
void int Push(Stack &s, ) x // 0.25 đi mể
{
s s. [arr .n] = x;
s.n++;
}
bool int IsDuplication(Stack s, value) // 0.125 đi mể
{
for int ( i = 0; i < ; i++)s.n
if ( [i] == s.arr value)
return true ;
return false ;
}
void InputStack(Stack &s) // 0.5 đi mể
{
int x, N;
bool false dup = ;
do {
std::cout << "Nhap so luong
phan tu N (10<N<1000):";
cin N;>>
} (N <= 10 || N >= 1000);while
cout << "Nhap cac phan tu vao Stack [1,50000]" << ;endl
do {
do {
cout ;<< "Nhap gia tri trong [1,50000]:"
cin x;>>
if (x < 1 || x > 50000)
cout << "Gia tri phai trong [1,50000],
vui long nhap lai" << ;endl
} (x < 1 || x>50000);while
if false (IsDuplication(s, x) == )
Push(s, x);
else
cout << "Gia tri bi trung lap,
vui long nhap lai" << ;endl
} ( < N);while s.n
2
}
1.c Viết hàm đếm xem trong ngăn xếp có bao nhiêu số nguyên tố nhỏ hơn giá trị M
(1<M<60000) nhập từ bàn phím (0.75 điểm)
Sinh viên có thể viết thành nhiều hàm, tùy theo số hàm phân chia do sinh viên làm bài mà
Thầy / Cô điều chỉnh thang điểm phù hợp
Trong đáp án gợi ý này có 2 hàm, được phân chia theo độ quan trọng từ cao đến thấp :
-hàm truy xuất stack lấy phần tử và đếm, nếu là số nguyên tố (0.5 điểm) ;
-hàm kiểm tra 1 số là số nguyên tố (0.25 điểm)
bool int IsPrimeNumber( number) // 0.25 đi mể
{
if (number < 2)
return false ;
for int float ( i = 2; i <= sqrt(( )number); i++)
if (number%i == 0)
return false ;
return true ;
}
void CountPrimeNumber(Stack ) s // 0.5 đi mể
{
int M, count = 0;
do {
cout << "Nhap so luong phan tu M (1<M<60000):";
cin M;>>
} (M <= 1 || M >= 60000);while
for int ( i = 0; i < ; i++) {s.n
if ( [i] < M && s.arr IsPrimeNumber( . [i]))s arr
count++;
}
if (count > 0)
cout count << "Stack co " << <<
" so nguyen to nho hon " << M;
else
cout << "Stack khong co so
nguyen to nao nho hon " M;<<
}
3
1.d. Viết hàm xóa 5 phần tử được thêm vào sau cùng vào trong ngăn xếp (0.75 điểm)
void Remove_5Elements(Stack &s) {
for int ( i = 0; i < 5; i++) {
s s. [arr .n - 1] = -1;
s.n--;
}
}
Câu 2:
Anh / chị hãy thực hiện các yêu cầu sau: …
Đáp án:
2.a Định nghĩa cấu trúc danh sách liên kết kép với mỗi phần tử là đối tượng Phân số
phù hợp theo sử dụng trong hàm main dưới đây (0.75 điểm)
struct PhanSo // 0.25 đi mể
{
int TuSo;
int MauSo;
};
struct LNODE // 0.25 đi mể
{
PhanSo data;
LNODE *Next;
LNODE *Prev;
} ;
typedef LNODE LPNODE * ;
struct DLIST // 0.25 đi mể
{
LPNODE Head;
LPNODE Tail;
};
2.b Viết các hàm in đậm để hàm main sau thực thi (1.75 điểm):
4
int main() {
PhanSo ps;
DLIST L;
CreateList(L);
while (1) {
Input_PhanSo(ps);
if break (ps.TuSo MauSo == 0 && ps. == 0) ;
AddHead(L, ps);
} // end while
cout << "S node có phân s có t s ố ố ử ố
chia h t cho m u s : "ế ẫ ố << (L); Count
//Node có T s là 3 và M u s là 20ử ố ẫ ố
LPNODE p = Search_Node(L, 3, 20);
if (p != NULL)
cout << "Có phân s 3 / 20 trong DS"ố ;
return;
} // end int main ()
Các hàm đều là cơ bản và đơn giản.
int AddHead(DLIST & , L PhanSo ps); // vi t đúng : 0.5 đi mế ể
void CreateList(DLIST &L); // vi t đúng : 0.25 đi mế ể
PhanSo PhanSo Input_PhanSo( &ps); // vi t đúng : 0.25 đi mế ể
int Count(DLIST L); // vi t đúng : 0.5 đi mế ể
LPNODE DLIST Search_Node( L, int int TuSo, MauSo);// vi t ế
đúng : 0.25 đi mể
Câu 3 :
3.a (1.25 điểm) Tạo cây nhị phân tìm kiếm bằng cách nhập lần lượt từ trái sang phải
dãy số sau đây {59, 96, 67, 81, 97, 41, 50, 43, 86, 9, 10, 16}
5
3.b (0.5đ) Cho biết kết quả duyệt cây theo dạng Left-Node-Right và Right-Left-Node
- Left-Node-Right: 9, 10, 16, 41, 43, 50, 59, 67, 81, 86, 96, 97. (0.25 điểm)
- Right-Left-Node: 97, 86, 81, 67, 96, 43, 50, 16, 10, 9, 41, 59. (0.25 điểm)
3.c (1.25 điểm) Hãy cân bằng lại cây: cho biết nút bị mất cân bằng, loại cân bằng và
vẽ cây kết quả sau cân bằng.
Đáp án gợi ý. Thầy / Cô xem và chấm theo trường hợp của sinh viên. Đáp án đề
xuất 2 trường hợp phổ biến nhất.
Trường hợp cân bằng 1: Cây mất cân bằng tại 2 nút ) và : nút 9 –Right Right (RR
nút 67 Right Right (RR). –
Trường hợp cân bằng 2: Cây mất cân bằng tại và nút 9 (RR) nút 96 (LR)
6
3.d Vẽ cây sau khi xóa nút 59 và 41 trên cây (0.5 điểm)
Đáp án gợi ý lựa chọn phần tử thế mạng (nút có 2 cây con) chỉ bên cây con trái
hoặc chỉ bên cây con phải
- Trường hợp , cây cân bằng 1 khi lựa chọn phần tử thế mạng bên cây con
trái.
- Trường hợp cây cân bằng 1, khi lựa chọn phần tử thế mạng bên cây con
phải, cây cuối cùng
7
- Trường hợp , cây cân bằng 2 khi lựa chọn phần tử thế mạng bên cây con
trái.
- Trường hợp cây cân bằng 2, khi lựa chọn phần tử thế mạng bên cây con
phải.
Trường hợp, cân bằng lại tại nút 81 (RR)
Trường hợp, cân bằng lại tại nút 81 (RL)
8
Câu 4: (1 điểm) Bảng băm
Cho bảng băm gồm 13 phần tử và tập khóa K (key) = {10, 40, 30, 8, 64, 22, 54, 41}, ta
cần nạp các giá trị khóa trong tập K vào bảng băm sử dụng hàm băm H(key) = key % 11.
Anh/ chị trình bày từng bước việc lưu trữ từng khóa trong K vào bảng băm, sử dụng kỹ
thuật dò tuyến tính (Linear Probing) để xử lý xung đột, biết hàm dò tuyến tính: H(key, i)
= (H(key) + i) % 13
Đáp án :
- Làm đúng được 4 phần tử không xảy ra đụng độ (10, 40,30, 22) khi thêm vào bảng
băm : 0.5 điểm
- Làm đúng được 4 phần tử xảy ra đụng độ (8, 64,54, 41) khi thêm vào bảng băm :
0.5 điểm
- Sai một trường hợp trừ 0.125 điểm
Bảng sau thể hiện các giá trị có trong bảng băm sau khi lần lượt thêm các khóa {10, 40,
30, 8, 64, 22, 54, 41} theo thứ tự từ trái sang phải vào:
Xử lý đụng độ bằng phương pháp Dò tuyến tính (Linear Probing)
Thêm
10
Thêm
40
Thêm
30
Thêm
8
Thêm
64
Thêm
22
Thêm
54
Thêm
41
0 22 22 22
1 41
9
2
3
4
5
6
7 40 40 40 40 40 40 40
8 30 30 30 30 30 30
9 8 8 8 8 8
10 10 10 10 10 10 10 10 10
11 64 64 64 64
12 54 54
Chi tiết thực hiện thêm các khóa:
- Thêm 10: H(10) = 10 % 11 = 10
- Thêm 40: H(40) = 40 % 11 = 7
- Thêm 30: H(30) = 30 % 11 = 8
- Thêm 8: H(8) = 8 % 11 = 8 => Đụng độ
Băm lại lần 1: H(8, 1)= (8+1)%13=9
- Thêm 64: H(64) = 64 % 11 = 9 => Đụng độ
Băm lại lần 1: H(64, 1)= (9+1)%13=10 => Đụng độ
Băm lại lần 2: H(64, 2)= (9+2)%13=11
- Thêm 22: H(22) = 22 % 11 = 0
- Thêm 54: H(54) = 54 % 11 = 10 => Đụng độ
Băm lại lần 1: H(54, 1)= (10+1)%13=11 => Đụng độ
Băm lại lần 2: H(54, 2)= (10+2)%13=12
10
| 1/11
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

ĐÁP ÁN GỢI Ý VÀ THANG ĐIỂM
MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
HỌC KỲ 2 - NĂM HỌC: 2016-2017 Câu 1:
Giả sử người ta muốn sử dụng cấu trúc Stack (ngăn xếp) để lưu dãy N số nguyên
(10có miền giá trị [1,50000].
Anh / chị hãy thực hiện các yêu cầu sau :
a. Định nghĩa cấu trúc dữ liệu ngăn xếp đáp ứng yêu cầu (0.5 điểm)
b. Viết hàm nhập vào ngăn xếp có N phần tử (10phím và đảm bảo giá trị các phần tử trong ngăn xếp không trùng nhau (1 điểm)
c. Viết hàm đếm xem trong ngăn xếp có bao nhiêu số nguyên tố nhỏ hơn giá trị M
(1d. Viết hàm xóa 5 phần tử được thêm vào sau cùng vào trong ngăn xếp (0.75 điểm) Đáp án:
Sinh viên có thể sử dụng cấu trúc dữ liệu mảng hoặc danh sách liên kết để cài đặt Stack.
Đáp án tham khảo bên dưới sử dụng CTDL mảng để cài đặt Stack.
1.a Định nghĩa cấu trúc dữ liệu ngăn xếp đáp ứng yêu cầu (0.5 điểm) #define MAX 1000 struct Stack { int n; int arr[MAX]; };
1.b Viết hàm nhập vào ngăn xếp có N phần tử (10phím và đảm bảo giá trị các phần tử trong ngăn xếp không trùng nhau (1 điểm)
Sinh viên có thể viết thành nhiều hàm, tùy theo số hàm phân chia do sinh viên làm bài mà
Thầy / Cô điều chỉnh thang điểm phù hợp.
Trong đáp án gợi ý này có 4 hàm, được phân chia theo độ quan trọng từ cao đến thấp :
void Init(Stack &s) // 0.125 đi m ể 1 { s.n = 0; }
void Push(Stack &s, int x) // 0.25 đi m ể { s.arr[s.n] = x; s.n++; }
bool IsDuplication(Stack s, int value) // 0.125 đi m ể {
for (int i = 0; i < s.n; i++) if (s.arr[i] == value) return true; return false; }
void InputStack(Stack &s) // 0.5 đi m ể { int x, N; bool dup = false; do {
std::cout << "Nhap so luong phan tu N (10cin >> N;
} while (N <= 10 || N >= 1000);
cout << "Nhap cac phan tu vao Stack [1,50000]" << endl; do { do {
cout << "Nhap gia tri trong [1,50000]:"; cin >> x; if (x < 1 || x > 50000)
cout << "Gia tri phai trong [1,50000], vui long nhap lai" << ; endl
} while (x < 1 || x>50000); if (IsDuplication(s false , x) == ) Push(s, x); else
cout << "Gia tri bi trung lap, vui long nhap lai" << ; endl } while (s.n < N); 2 }
1.c Viết hàm đếm xem trong ngăn xếp có bao nhiêu số nguyên tố nhỏ hơn giá trị M (1
Sinh viên có thể viết thành nhiều hàm, tùy theo số hàm phân chia do sinh viên làm bài mà
Thầy / Cô điều chỉnh thang điểm phù hợp
Trong đáp án gợi ý này có 2 hàm, được phân chia theo độ quan trọng từ cao đến thấp :
-hàm truy xuất stack lấy phần tử và đếm, nếu là số nguyên tố (0.5 điểm) ;
-hàm kiểm tra 1 số là số nguyên tố (0.25 điểm)
bool IsPrimeNumber(int number) // 0.25 đi m ể { if (number < 2) return false;
for (int i = 2; i <= sqrt((float)number); i++) if (number%i == 0) return false; return true; }
void CountPrimeNumber(Stack s) // 0.5 đi m ể { int M, count = 0; do {
cout << "Nhap so luong phan tu M (1cin >> M;
} while (M <= 1 || M >= 60000);
for (int i = 0; i < s.n; i++) {
if (s.arr[i] < M && IsPrimeNumber(s.arr[i])) count++; } if (count > 0)
cout << "Stack co " << count <<
" so nguyen to nho hon " << M; else
cout << "Stack khong co so
nguyen to nao nho hon " << M; } 3
1.d. Viết hàm xóa 5 phần tử được thêm vào sau cùng vào trong ngăn xếp (0.75 điểm)
void Remove_5Elements(Stack &s) {
for (int i = 0; i < 5; i++) { s.arr[s.n - 1] = -1; s.n--; } } Câu 2:
Anh / chị hãy thực hiện các yêu cầu sau: … Đáp án:
2.a Định nghĩa cấu trúc danh sách liên kết kép với mỗi phần tử là đối tượng Phân số
phù hợp theo sử dụng trong hàm main dưới đây (0.75 điểm) struct PhanSo // 0.25 đi m ể { int TuSo; int MauSo; }; struct LNODE // 0.25 đi m ể { PhanSo data; LNODE *Next; LNODE *Prev; } ; typedef LNODE *LPNODE; struct DLIST // 0.25 đi m ể { LPNODE Head; LPNODE Tail; };
2.b Viết các hàm in đậm để hàm main sau thực thi (1.75 điểm): 4 int main() { PhanSo ps; DLIST L; CreateList(L); while (1) { Input_PhanSo(ps);
if (ps.TuSo == 0 && ps.MauSo == 0) break; AddHead(L, ps); } // end while
cout << "S node có phân s ố ố có t s ử ố chia h t cho m ế u ẫ s : " ố << Count(L); //Node có T s ử ố là 3 và M u s ẫ là 20 ố
LPNODE p = Search_Node(L, 3, 20); if (p != NULL)
cout << "Có phân s 3 / 20 trong DS" ố ; return; } // end int main ()
Các hàm đều là cơ bản và đơn giản.
int AddHead(DLIST & L, PhanSo ps); // viết đúng : 0.5 đi m ể void CreateList(DLIST &L); // viết đúng : 0.25 đi m ể
PhanSo Input_PhanSo(PhanSo &ps); // viết đúng : 0.25 đi m ể int Count(DLIST L); // viết đúng : 0.5 đi m ể
LPNODE Search_Node(DLIST L, int TuSo, int MauSo);// vi t ế đúng : 0.25 đi m ể Câu 3 :
3.a (1.25 điểm) Tạo cây nhị phân tìm kiếm bằng cách nhập lần lượt từ trái sang phải
dãy số sau đây {59, 96, 67, 81, 97, 41, 50, 43, 86, 9, 10, 16} 5
3.b (0.5đ) Cho biết kết quả duyệt cây theo dạng Left-Node-Right và Right-Left-Node
- Left-Node-Right: 9, 10, 16, 41, 43, 50, 59, 67, 81, 86, 96, 97. (0.25 điểm)
- Right-Left-Node: 97, 86, 81, 67, 96, 43, 50, 16, 10, 9, 41, 59. (0.25 điểm)
3.c (1.25 điểm) Hãy cân bằng lại cây: cho biết nút bị mất cân bằng, loại cân bằng và
vẽ cây kết quả sau cân bằng.
Đáp án gợi ý. Thầy / Cô xem và chấm theo trường hợp của sinh viên. Đáp án đề
xuất 2 trường hợp phổ biến nhất.
Trường hợp cân bằng 1: Cây mất cân bằng tại 2 nút: nút 9 –Right Right (RR) và
nút 67 –Right Right (RR).
Trường hợp cân bằng 2: Cây mất cân bằng tại nút 9 (RR) và nút 96 (LR) 6
3.d Vẽ cây sau khi xóa nút 59 và 41 trên cây (0.5 điểm)
Đáp án gợi ý lựa chọn phần tử thế mạng (nút có 2 cây con) chỉ bên cây con trái
hoặc chỉ bên cây con phải
- Trường hợp cây cân bằng 1, khi lựa chọn phần tử thế mạng bên cây con trái.
- Trường hợp cây cân bằng 1, khi lựa chọn phần tử thế mạng bên cây con
phải, cây cuối cùng 7
- Trường hợp cây cân bằng 2, khi lựa chọn phần tử thế mạng bên cây con trái.
- Trường hợp cây cân bằng 2, khi lựa chọn phần tử thế mạng bên cây con phải.
Trường hợp, cân bằng lại tại nút 81 (RR)
Trường hợp, cân bằng lại tại nút 81 (RL) 8
Câu 4: (1 điểm) Bảng băm
Cho bảng băm gồm 13 phần tử và tập khóa K (key) = {10, 40, 30, 8, 64, 22, 54, 41}, ta
cần nạp các giá trị khóa trong tập K vào bảng băm sử dụng hàm băm H(key) = key % 11.
Anh/ chị trình bày từng bước việc lưu trữ từng khóa trong K vào bảng băm, sử dụng kỹ
thuật dò tuyến tính (Linear Probing) để xử lý xung đột, biết hàm dò tuyến tính: H(key, i) = (H(key) + i) % 13 Đáp án :
- Làm đúng được 4 phần tử không xảy ra đụng độ (10, 40,30, 22) khi thêm vào bảng băm : 0.5 điểm
- Làm đúng được 4 phần tử xảy ra đụng độ (8, 64,54, 41) khi thêm vào bảng băm : 0.5 điểm
- Sai một trường hợp trừ 0.125 điểm
Bảng sau thể hiện các giá trị có trong bảng băm sau khi lần lượt thêm các khóa {10, 40,
30, 8, 64, 22, 54, 41} theo thứ tự từ trái sang phải vào:
Xử lý đụng độ bằng phương pháp Dò tuyến tính (Linear Probing) Thêm Thêm Thêm Thêm Thêm Thêm Thêm Thêm 10 40 30 8 64 22 54 41 0 22 22 22 1 41 9 2 3 4 5 6 7 40 40 40 40 40 40 40 8 30 30 30 30 30 30 9 8 8 8 8 8 10 10 10 10 10 10 10 10 10 11 64 64 64 64 12 54 54
Chi tiết thực hiện thêm các khóa: - Thêm 10: H(10) = 10 % 11 = 10 - Thêm 40: H(40) = 40 % 11 = 7 - Thêm 30: H(30) = 30 % 11 = 8 -
Thêm 8: H(8) = 8 % 11 = 8 => Đụng độ
Băm lại lần 1: H(8, 1)= (8+1)%13=9 -
Thêm 64: H(64) = 64 % 11 = 9 => Đụng độ
Băm lại lần 1: H(64, 1)= (9+1)%13=10 => Đụng độ
Băm lại lần 2: H(64, 2)= (9+2)%13=11 - Thêm 22: H(22) = 22 % 11 = 0 -
Thêm 54: H(54) = 54 % 11 = 10 => Đụng độ
Băm lại lần 1: H(54, 1)= (10+1)%13=11 => Đụng độ
Băm lại lần 2: H(54, 2)= (10+2)%13=12 10