Đê c ng ôn thi t t nghi p năm 2010 ươ ố ệ
Môn: C u trúc d li uấ ữ ệ
I. Các n i dung lý thuy tộ ế
1. Mô hình d li u danh sáchữ ệ
- Danh sách liên k t đ n.ế ơ
- Các th t c cài đ t các thao tác: thêm, xóa, tìm ki m, s p x p trên danh sách.ủ ụ ặ ế ắ ế
2. Mô hình d li u câyữ ệ
- Cách bi u di n cây nh phân b ng liên k t.ể ễ ị ằ ế
- Các thao tác duy t cây: thu t toán, cai đăt (đ quy ho c l p).ệ ậ ệ ặ ặ
- Các thu t toán và cai đăt: thêm, tìm ki m trên cây tìm ki m nh phân.ậ ế ế ị
- Cây t ng quát: bi u di n b ng liên k t các nút anh em, duy t cây (chi u r ng, chi u sâu).ổ ể ễ ằ ế ệ ề ộ ề
3. Mô hình d li u đ thữ ệ ồ ị
- Ba cách bi u di n đ th : ma trân kê, danh sach kê, danh sach canh.ể ễ ồ ị
- Thu t toán duy t đ th theo chi u sâu, chi u r ng: thu t toán, cài đ t.ậ ệ ồ ị ề ề ộ ậ ặ
- Thuât toan tim đ ng đi, cai đăt. ươ
- Khái ni m cây khung, thu t toán tìm cây khung. ệ ậ
II. M t s bài t p tham kh oộ ố ậ ả
1. C n qu n lý m t danh sách cán b g m các thông tin: h tên, phòng làm vi c, h s l ng, ngo iầ ả ộ ộ ồ ọ ệ ệ ố ươ ạ
ng (m t ng i có th bi t nhi u ngo i ng nh ng t i đa không quá 5). Hãy th c hi n các yêu c uữ ộ ườ ể ế ề ạ ữ ư ố ự ệ ầ
sau:
- Khai báo cách t ch c d li u liên k t đ n đ bi u di n danh sách trên.ổ ứ ữ ệ ế ơ ể ể ễ
- Trinh bay thuât toan, cai đăt cac thao tac:
+ Thêm m t cán b vào đ u danh sách.okộ ộ ầ
+ Thêm m t cán b vào cu i danh sách.okộ ộ ố
+ Xóa m t cán b đ u danh sách.okộ ộ ầ
+ Xóa m t cán b cu i danh sách.okộ ộ ố
+ Tìm m t cán b theo h tên.okộ ộ ọ
+ Đ m s cán b thu c m t phòng nào đó.okế ố ộ ộ ộ
+ Li t kê nh ng cán b bi t ti ng Pháp.okệ ữ ộ ế ế
+ B sung ngo i ng ti ng Nga cho cán b có h tên x (gi s các cán b không trùng hổ ạ ữ ế ộ ọ ả ử ộ ọ
tên)ok
+ Hi n th danh sách cán b c a m t phòng.okể ị ộ ủ ộ
+ T o danh sách m i g m các cán b c a m t phòng nào đó.ạ ớ ồ ộ ủ ộ
+ Xóa m t cán b khi bi t h tên (ch xóa m t ng i đ u tiên tìm đ c).ộ ộ ế ọ ỉ ộ ườ ầ ượ
+ S p x p danh sách theo th t tăng c a phòng làm vi c.ắ ế ứ ự ủ ệ
+ Gi s danh sách đã s p theo phòng làm vi c. Hãy thêm m t nhân viên sao cho sau khi thêmả ử ắ ệ ộ
danh sách v n đ c s p theo phòng làm vi c.ẫ ượ ắ ệ
+ Xóa toàn b danh sách.ộ
2. Hãy khai báo cách t ch c d li u cho m t cây tìm ki m nh phân mà m i nút ch a m t s nguyên.ổ ứ ữ ệ ộ ế ị ỗ ứ ộ ố
Trinh bay thuât toan va cai đăt cac thao tac:
- Thêm m t s vào cây.ộ ố
- Tìm m t s trên cây.ộ ố
- Đ m s nút c a cây.ế ố ủ
- In các s c a cây theo th t tăng.ố ủ ứ ự
- Tính chi u cao cây.ề
- Đ m s nút c a cây ch a s l n h n ho c b ng s x.ế ố ủ ứ ố ớ ơ ặ ằ ố
- Đ m s nút ch a s ch n trong cây.ế ố ứ ố ẵ
- T o m t cây m i gi ng nh cây cho tr c.ạ ộ ớ ố ư ướ
- So sánh hai cây có gi ng nhau không?ố
- Ki m tra xem t t c các s trên cây1 đ u có trong cây2 không?ể ấ ả ố ề
- Đ a các s t cây ra m ng các s nguyên theo th t gi m.ư ố ừ ả ố ứ ự ả
3. Cho đ th có tr ng s đ c t ch c b ng danh sách k . Hãy trình bày thu t toán và cài đ t thao tácồ ị ọ ố ượ ổ ứ ằ ề ậ ặ
tìm đ ng đi t đ nh x đ n đ nh y tho mãn m t trong các đi u ki n:ườ ừ ỉ ế ỉ ả ộ ề ệ
+ Không qua đ nh z.ỉ
+ Qua không quá k c nhạ
+ Ch qua các c nh có tr ng s >=M.ỉ ạ ọ ố
4. Cho m t đ th vô h ng, không có tr ng s đ c bi u di n b ng danh sách c nh. Hãy trình bàyộ ồ ị ướ ọ ố ượ ể ễ ằ ạ
thu t toán và cài đ t thao tác ki m tra đ th có liên thông không?.ậ ặ ể ồ ị
5. Cho m t đ th vô h ng, không có tr ng s đ c bi u di n b ng danh sách c nh. Hãy trình bàyộ ồ ị ướ ọ ố ượ ể ễ ằ ạ
thu t toán và cài đ t thao tác tìm 1 cây khung c a đ th tho mãn đi u ki n ch a c nh (x,y) thu c đậ ặ ủ ồ ị ả ề ệ ứ ạ ộ ồ
th .ị
-----------------
