Đề thi cuối kỳ năm 2015 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 2015 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!
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:
Tác giả:
Thông tin :
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
Tác giả:
Tài liệu liên quan:
Preview text:
ĐÁP ÁN ĐỀ THI CUỐI KỲ CTDL>
HỌC KỲ II, 2015-2016 Câu 1: (2.0 điểm)
a. So sánh ưu khuyết điểm của việc tổ chức lưu trữ và tìm kiếm giữa danh sách
liên kết và mảng (1.0 điểm).
- (0.5 điểm) Tìm kiếm một khoá trong một DSLK không có cách nào khác ngoài
cách di chuyển trên danh sách mỗi lần một phần tử, và do đó việc tìm kiếm trên DS L K
luôn là tìm kiếm tuần tự . Việc tìm kiếm sẽ trở nên nhanh hơn nhiều nếu
chúng ta sử dụng mảng và tìm kiếm nhị phân .
- (0.5 điểm) Mảng lại không phù hợp với sự biến động dữ liệu. Nếu việc thêm
các phần tử mới hoặc loại các phần tử hiện có xảy ra thường xuyên, mảng sẽ
chậm hơn nhiều so với DSLK. Do việc thêm và loại phần tử trong mảng mỗi
lần đều đòi hỏi phải di chuyển nhiều phần tử sang các vị trí khác. Trong DSLK
chỉ cần thay đổi một vài con trỏ.
b. Trình bày định nghĩa CNPTK. Giả sử cho CNPTK gồm N nút, trong trường
hợp xấu nhất chiều cao của CNPTK sẽ bằng bao nhiều? Giải thích và cho ví
dụ minh hoạ (1 điểm).
- (0.25 điểm) CNPTK là cây nhị phân và đảm bảo nguyên tác bố trí khoá tại mỗi
nút thoả điều kiện sau: o
Các nút con trái nhỏ hơn nút hiện hành o
Các nút con phải lớn hơn nút hiện hành
- (0.25 điểm) Trong trường hợp xấu nhất chiều cao của CNPTK sẽ bằng h N (số lượng nút của cây).
- (0.25 điểm) Vì trong trường hợp xấu nhất mỗi nút của CNPTK chỉ có 1 nhánh con duy nhất trừ nút lá.
- (0.25 điểm) Cho được một ví dụ đúng. 1
Câu 2: Cây cân bằng (3.5 điểm)
a. Thêm lần lượt các nút: {45 40 54 17 64 62 47 6 16 50 60 15 90 67 27 59 33 31} (2.0 điểm).
Mất cân bằng tại sau khi thêm những nút: {62, 6, 50, 60, 15, 67, 33}.
(Đúng một chỗ cân bằng từ trái qua phải được 0.25 điểm/ lần cân bằng, đúng hết được tròn 2đ) Hình cụ thể:
Sau khi thêm {45, 40, 54, 17, 64}
Thêm 62 cây mất cân bằng. Cây cân bằng lại có hình dạng: Thêm 47: 2
Thêm 6 bị mất cân bằng. Cân bằng lại: Thêm 16:
Thêm 50 mất cân bằng. Cân bằng lại: 3
Thêm 60 mất cân bằng. Cân bằng lại:
Thêm 15 mất cân bằng. Cân bằng lại: Thêm 90:
Thêm 67 mất cân bằng, cân bằng lại: 4 Thêm 27, 59:
Thêm 33 mất cân bằng, cân bằng lại: Thêm 31. Kết thúc 5
b. Xóa lần lượt các nút 50, 45 (0.5 điểm)
Chú ý mỗi lần xóa một nút đúng được (0.25 điểm)
Xóa nút 50. Hình cây còn lại:
Xóa nút 45. Hình cây còn lại:
c. Hàm in ra mức K sao cho có tổng giá trị các nút là lớn nhất (1 điểm)
Cơ bản viết 2 hàm/bước: 6
1. Hàm/bước tính tổng giá trị các nút tại mức K của cây (0.5 điểm)
2. Hàm in ra mức: tìm và in mức K có tổng giá trị các nút lớn nhất (0.5 điểm)
Câu 3: Danh sách liên kết (2.5 điểm)
a. Mô tả cấu trúc dữ liệu (0.5 điểm). typedef struct res { char name[30]; int rate; float distance; }Restaurant; typedef struct pNode { Restaurant info; struct pNode* next; } ; Node typedef struct pList { Node* head; Node* tail; }List;
b. Viết hàm nhập 10 nhà hàng bằng giải thuật thêm vào cuối danh sách (1.0 điểm). Node* GetNode(Restaurant r) { Node* p = new Node ; if (p==NULL) exit(1); p->info = r; p->next = NULL; return p; }
void AddTail(List& l, Restaurant r) 7 { Node *p = GetNode(r); if (l.head== ) NULL { l.head = p; l.tail = p; } else { l.tail->next = p; l.tail = p; } } Restaurant Input_ARestaurant() { Restaurant r; fflush(stdin); cout<<"Nhap ten:"; gets(r.name); cout<< ; "Nhap ty le:" cin>>r.rate;
cout<<"Nhap khoang cach:"; cin>>r.distance; return r; } void InsertList(List &l) { for (int i=0;i<5;i++) {
cout<<"Nhap nha hang thu "<<(i+1)<<"\n";
Restaurant r = Input_ARestaurant(); AddTail(l, r); cout<<"\n"; } } 8
c. Viết hàm sắp xếp danh sách nhà hàng theo thứ tự tỷ lệ đánh giá mức độ
tốt giảm dần và khoảng cách tới nhà hàng tăng dần (1.0 điểm).
void Swap(Restaurant &a Restaurant , &b) { Restaurant temp; temp = a; a=b; b=temp; } void SortList(List &l) {
Node* p = l.head, *q, *m; //p là phầ n tử đang xét; q là nhữ ng phầ n t
ử sau p; m là phầ n tử hoán vị vớ i p nế u có thay đổ i while (p!=l.tail) { m = p; q=p->next; while(q!=NULL) { if (m->info.rateinfo.rate) m = q;
else if (m->info.rate == q->info.rate) {
if (m->info.distance > q->info.distance) m=q; } q=q->next; } if (m!=p) Swap(p->info, m->info); p=p->next; } 9 }
Câu 4: Bảng băm (2.0 điểm)
a. Liệt kê các phương pháp giải quyết đụng độ trong cấu trúc bảng băm (1.0 điểm). Bài giải:
SV chỉ cần trình bày được tên các phương pháp đề cập trong chương trình học là
được. Nếu sinh viên trình bày ngoài thì vẫn tính điểm.
Có một số phương pháp giải quyết xung đột như: phương pháp (0.5 điểm)
nối kết và phương pháp băm lại.
Các loại bảng băm giải quyết sự xung đột bằng phương pháp (0.25 điểm)
nối kết như: bảng băm với phương pháp nối kết trực tiếp, bảng
băm với phương pháp nối kết hợp nhất.
Các loại bảng băm giải quyết sự xung đột bằng phương pháp (0.25 điểm)
băm lại như: bảng băm với phương pháp dò tuyến tính, bảng
băm với phương pháp dò bậc hai, bảng băm với phương pháp băm kép.
b. Cho bảng băm kích thước 13 ô và tập khóa K = {20, 54, 40, 29, 99, 64, 87,
53}, hàm băm F1(key) =key %13 (key: khóa cần băm). Trình bày từng
bước việc lưu trữ từng khóa trong tập K vào bảng băm sử dụng hàm băm
F1, khi xảy ra đụng độ sử dụng hàm băm F2(key)=(F1(key)+3) % 13 (1.0 điểm). Bài giải:
Mỗi lần thêm vào mà không trình bày rõ lý do, trừ (0.25 điểm).
Không biết xử lý đụng độ, trừ (0.5 điểm).
Tổng điểm trừ tối đa là (1.0 điểm) 10