tailieunhanh - Đề 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ạ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. | Đề 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, cài đặt (đệ quy hoặc lặp). - Các thuật toán và cài đặ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 sách kề, danh sách cạnh. - 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 toán tìm đường đi, cài đặ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. - Trình bày thuật toán, cài đặt các thao tác: + Thêm một cán bộ vào đầu danh + Thêm một cán bộ vào cuối danh + Xóa một cán bộ đầu danh + Xóa một cán bộ cuối danh + Tìm một cán bộ theo họ + Đếm số cán bộ thuộc một phòng nào + Liệt kê những cán bộ biết tiếng + 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 + 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. Trình bày thuật toán và cài đặt các thao tác: - 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ị. -----------------