Đề cương ôn thi tốt nghiệp năm 2010 - Môn: Cấu trúc dữ liệu

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ạingữ (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ầusau...
Nội dung trích xuất từ tài liệu:
Đề cương ôn thi tốt nghiệp năm 2010 - Môn: Cấu trúc dữ liệu Đề cương ôn thi tốt nghiệp năm 2010 Môn: Cấu trúc dữ liệuI. Các nội dung lý thuyết1. 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ảo1. 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 ạingữ (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 ầusau:- 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êmdanh 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 và 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áctì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àythuậ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àythuậ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ị. -----------------