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

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
ĐÁP ÁN và THANG ĐIỂM THAM KHẢO ĐỀ THI CUỐI KỲ
KHOA KHOA HỌC MÁY TÍNH
HỌC KỲ 2 – NĂM HỌC 2017-2018
Môn thi: Cấu trúc dữ liệu và giải thuật
Mã lớp: Các lớp IT003 - Hệ đại trà Câu 1 : (2 điểm)
Cho cấu trúc dữ liệu danh sách liên kết đơn và hàm RPrint như dưới ây : đ struct Node struct List { Node *Head ; { int info; Node *Tail; Node *Next; }; }; Hàm void RPrint(List ls)
Anh / chị hãy viết hàm RPrint để in lên màn hình các phần tử trong danh sách ls theo
thứ tự từ phần tử cu i
ố đến phần tử đầu (không dùng m ng ả
phụ hoặc danh sách phụ). Thang điểm :
- SV thực hiện theo đúng yêu cầu của câu hỏi (không dùng m ng ph ả
ụ ho c danh sách ặ phụ).
- SV có thể sử d ng hàm ụ đệ qui ho c vòng l ặ ặ để p
thực hiện đúng yêu cầu sẽ có trọn điểm câu hỏi.
Đáp án tham khảo : void RPrint(List ls) {
if (ls.pHead == NULL) return; Node *p = ls.pHead;
if (ls.pHead != ls.pTail) // Có thể không cần kiểm tra điều kiện này cũng được
{ ls.pHead = p->pNext; RPrint(ls); }
cout << p->info << " "; } Câu 2 : (2 điểm)
Cho chu i các thao tác nh ỗ ư sau: RTU*I**MUN***EB***1*ON
MSSV:............................ Trang 1 / 4 Biết rằng: với m i ch ỗ
ữ cái tượng trưng cho thao tác thêm chữ cái tương ứng vào Stack
(ngăn xếp); với m i
ỗ dấu * tượng trưng cho thao tác lấy n i ộ dung m t ộ phần tử trong
stack và in ra màn hình. Anh / chị hãy cho biết sau khi hoàn tất chu i ỗ thao tác trên,
những chữ cái nào còn trong stack và những chữ cái nào được in ra màn hình. Thang điểm :
SV có thể thực hiện theo một trong 4 phương án sẽ có tr n ọ điểm: - Thao tác l y n ấ i dung ph ộ
ần tử theo hàm pop, chuỗi thao tác bao gồm ký tự 1. - Thao tác l y n ấ i dung ph ộ
ần tử theo hàm pop, chuỗi thao tác không bao g m k ồ ý tự 1. - Thao tác l y n ấ i dung ph ộ
ần tử theo hàm top, chu i thao tác bao g ỗ m k ồ ý tự 1. - Thao tác l y n ấ i dung ph ộ
ần tử theo hàm top, chu i thao tác không bao g ỗ m k ồ ý tự 1. Câu 3 : (4 điểm) Cho dãy s nh ố
ư sau : {93, 11, 97, 65, 27, 70, 13, 83, 54, 101}
Anh / chị hãy thực hiện :
a. Xây dựng cây nhị phân tìm kiếm từ dãy s trên ố
lần lượt từ trái sang ph i ả (1.5 điểm) Đáp án :
- SV vẽ chính xác cây nhị phân tìm kiếm theo đúng thứ tự của dãy số trong câu h i ỏ
với s nút 93 là nút g ố c. ố
- SV có thể vẽ cây nhị phân tìm kiếm kết qu ả cu i ố cùng ho c
ặ vẽ từng bước đều được tính úng đ Thang điểm : - SV vẽ úng đ
cây nhị phân tìm kiếm theo yêu c u t
ầ ừ trái sang ph i ả c a dãy ủ s v ố ới nút
gốc là 93 sẽ được tr n s ọ ố điểm.
- SV vẽ được 1/2 s ố nút (5 nút) úng đ ho c
ặ 1/3 số nút (3 nút) úng đ sẽ có thang điểm
tương ứng là 1/2 ho c ặ 1/3 i đ ểm c a ủ câu h i, ỏ với i
đ ều kiện nút g c ố c a ủ cây phải là nút 93 theo yêu c u. ầ
- SV vẽ cây nhị phân tìm kiếm úng, đ nhưng nút g c ố sai (không ph i
ả 93) sẽ không có điểm.
b. Xóa lần lượt theo thứ tự các nút {54, 11, 93} (1.5 điểm) Lưu :
ý Khi xóa 1 nút, cân bằng cây khi xảy ra mất cân bằng, cho biết nút bị
mất cân bằng và loại mất cân bằng Đáp án : Sẽ ch p ấ nh n ậ các lời gi i ả đáp có l p ậ lu n
ậ hợp lý (như cân b ng ằ cây ở câu 3.a sau ó xoá 3 s đ /node ố hoặc áp d ng qui t ụ c cân b ắ
ằng cây nhị phân tìm kiếm cân
bằng khi xoá 3 s /node ố ho c
ặ duyệt cây lấy ra các s /node ố sau ó đ xây cây nhị
phân tìm kiếm cân b ng) ằ và cu i
ố cùng xây dựng được cây cân b ng ằ AVL với chuỗi s ố ã cho ( đ ã lo đ i b ạ 3 s ỏ ố/node).
MSSV:............................ Trang 2 / 4 Thang điểm :
- SV vẽ được cây cân bằng cu i ố cùng úng đ và có l p ậ lu n
ậ hợp lý sẽ có tr n ọ điểm (1.5 điểm)
- SV vẽ được cây cân b ng cu ằ i ố cùng úng, nh đ
ưng không trình bày lý do vì sao có cây kết qu : tr ả ừ 0.75 điểm.
c. Viết hàm đếm s nút trên câ ố
y chỉ có duy nhất 1 nút con phải (1 điểm) Thang điểm :
- SV có thể sử d ng hàm ụ đệ qui ho c vòng l ặ ặ để p thực hiệ đ
n úng yêu cầu sẽ có trọn điểm câu hỏi. Đáp án tham khảo : int count(Tree* pTree) { if (pTree==NULL) return 0;
if ((pTree->left==NULL && pTree->right!=NULL)
return 1+count(pTree->left)+count(pTree->right);
else return count(pTree->left)+count(pTree->right); } Câu 4 : (2 điểm)
Cho tập khóa K = {12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5} và hàm băm :,
H(key) = (2*key+5) %11 (key: khóa cần băm).,
Anh / chị hãy thực hiện : a. Vẽ hình từ ướ
ng b c việc lưu trữ từng khóa trong K vào bả ă ng b m có kích thước,
M=11, dùng hàm băm H và phương pháp nối kết trực tiếp để xử l ý xung t. độ (1 điểm) Đáp án : - SV ph i v
ả ẽ hình từng bước úng khi thêm t đ
ừng số vào bảng b m ă Thang điểm : - SV vẽ b ng b ả ăm g m 1 ồ
1 phần tử úng : 0.125 đ điểm - SV bố trí s ố u tiên vào b đầ ng b ả ăm úng : 0.125 đ điểm
- SV bố trí úng vào b đ ng b ả m nhóm ă ng đụ có s độ d
ố ư 4 (s 16, 5) : 0.125 ố
- SV bố trí úng vào b đ ng b ả m nhóm ă ng đụ có s độ d
ố ư 6 (s 39,94) : 0.125 ố
- SV bố trí úng vào b đ ng b ả m nhóm ă ng đụ có s độ d
ố ư 5 (s 44, 88, 94) : 0.25 ố
- SV bố trí úng vào b đ ng b ả m nhóm ă ng đụ có s độ d ố ư 7 (23) : 0.125
- SV bố trí úng vào b đ ng b ả m các s ă không ố ng đụ (20, 13) : 0.125 độ
MSSV:............................ Trang 3 / 4
b. Định nghĩa cấu trúc dữ liệu cho bả ă ng b m ở câu a (1 điểm) Thang điểm :
- SV định nghĩa CTDL úng : 0.5 đ điểm #define M 11 typedef struct tagNODE { int key; tagNODE *next }NODE, *NODEPTR; - SV khai báo b ng b ả m ă úng : 0.5 đ điểm
/* khai bao mang bucket chua M con tro dau cua Mbucket */ NODEPTR bucket[M]; HẾT
MSSV:............................ Trang 4 / 4