Đ I H C THÁI NGUYÊNẠ Ọ
KHOA CÔNG NGH THÔNGỆ TIN
………………
Câu 1( 4 đi m)ể
Xây d ng m t c u trúc d li u thích h p ự ộ ấ ữ ệ ợ đ bi u di n ể ễ ễ đa th c P(x) có d ng : ứ ạ
P(x) = c1xn1 + c2xn2 +...+ck xnk
Bi t r ng:ế ằ
1) Các thao tác x lý trên đa th c bao g m :ử ứ ồ
+ Thêm m t ph n t vào cu i đa th cộ ầ ử ố ứ
+ In danh sách các ph n t trong đa th cầ ử ứ
theo: - th t nh p vàoứ ự ậ
- ng c v i th t nh p vàoượ ớ ứ ự ậ
+ H y m t ph n t b t kỳ trong đa th củ ộ ầ ử ấ ứ
2) S l ng các ph n t không h n chố ượ ầ ử ạ ế
3) Ch có nhu c u x lý đa th c trong b nh chính.ỉ ầ ử ứ ộ ớ
a) Gi i thích lý do ch n CTDL đã đ nh nghĩa.ả ọ ị
b) Vi t ch ng trình con c l ng giá tr c a đa th c P(x) khi bi t x.ế ươ ướ ượ ị ủ ứ ế
c) Vi t ch ng trình con rút g n bi u th c (g p các ph n t cùng s mũ)ế ươ ọ ể ứ ộ ầ ử ố
Câu 2 (4 đi m)ể
Cho m t cây nh phân tìm ki m có các khóa là các s nguyên nh hình v . ộ ị ế ố ư ẽ
Anh (ch ) hãy:ị
1) Vi t d ng cài đ t cây trên b ng con tr . Root là con tr tr t i g cế ạ ặ ằ ỏ ỏ ỏ ớ ố
c a câyủ
2) Tìm đ nh có khóa x trên câyỉ
3) Nêu ph ng pháp đ lo i b m t đ nh x = 39 trên cây, sao cho câyươ ể ạ ỏ ộ ỉ
sau khi lo i b đ nh đó v n là cây nh phân tìm ki mạ ỏ ỉ ẫ ị ế
4) Hi n th cây ể ị
5) H y câyủ
……………………H t……………………….ế
Thí sinh không đ c s d ng tài li u, không ghi vào đ thiượ ử ụ ệ ề
CB coi thi không gi i thích gì thêm và n p l i đ thi cho phòng ch c năng theo quy ch c aả ộ ạ ề ứ ế ủ
bộ
Mã đ thi: 19ề
Đ THI H T H C PH NỀ Ế Ọ Ầ
Đ THI H T H C PH NỀ Ế Ọ Ầ
Môn thi: C u trúc d li u và gi i thu t; H : Chính quyấ ữ ệ ả ậ ệ
Th i gian chu n b : 45 phút, không k th i gian giao đờ ẩ ị ể ờ ề
25
20
39
15
21
30
40
31
35