Tài liệu Đề thi tham khảo môn cấu trúc dữ liệu và giải thuật 25

ĐẠI HỌC THÁI NGUYÊN ĐỀ THI HẾT HỌC PHẦN KHOA CÔNG NGHỆ THÔNG TIN 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 đề Mã đề thi: 25 Câu 1 (1 điểm) Thế nào là cấu trúc dữ liệu tiền định(định sẵn) của ngôn ngữ lập trình bậc cao? Cho ví dụ minh họa Câu 1(2 điểm) Cho một danh sách liên kết đơn có n phần tử, các phần tử là các số nguyên. Hãy: Viết dạng cài đặt của danh sách, và viết chương trình con đảo nhóm k phần tử đầu và nhóm k phần tử cuối của danh sách cho nhau. Biết rằng: n > 2k Câu 2 ( 4 điểm) Cho một cây đa phân bất kỳ các đỉnh chứa các số nguyên. Anh(chị) hãy: 1) Viết dạng cài đặt của cây bởi danh sách các con của mỗi đỉnh. 2) Viết các chương trình con tương ứng với các yêu cầu sau: a) Tạo một cây (điều kiên dừng nhập là: nhập số <0) b) Tính số đỉnh trên cây c) Tính chiều cao của cây d) Tìm kiếm xem trên cây có chứa đỉnh có thông tin = x không? (x là số nguyên nhập từ bàn phím) ……………………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ã đề 25 Câu 1 1) Cấu trúc dữ liệu tiền định của ngôn ngữ lập trình bậc cao là các cấu trúc dữ liệu đã được định nghĩa sẵn trong ngôn ngữ lập trình đó, người lập trình chỉ việc sử dụng mà không cần định nghĩa lại (0.5 đ) 3) Một vài cấu trúc dữ liệu tiền định như: mảng, bản ghi, tệp tin, ...... (0.5 đ) Câu 2 + Dạng cài đặt của danh sách: (1 đ) Type Nut = record infor: integer; ` Next: ^ nut; end; List = ^Nut; Var L: List; + Đảo nhóm k phần tử đầu cho k phần tử cuối của danh sách L: (1 đ) Cách làm: - Chia danh sách L làm 3 đoạn, lần lượt cho L1, L2, L3 trỏ tới đầu mỗi đoạn + Tách k phần tử đầu của L, L1 trỏ tới phần tử đầu của danh sách này + Đếm số nút trong danh sách L lưu vào d + Tách d-k phần tử đầu của L, L2 trỏ tới đầu đoạn này + Đoạn còn lại của L, cho L3 trỏ tới đầu đoạn - Ghép các danh sách lần lượt theo trình tự: L3, L2, L1 - cho L trỏ tới đầu danh sách đã ghép Câu 2 + Có thể cài đặt cây bằng danh sách các con của mỗi đỉnh: Tương tự y1) câu 3 đề 09 (1đ) + Viết các chương trình con tương ứng với các yêu cầu: 1) Tạo cây (1 đ) b1) Nhập gốc cây, lưu vào hàng đợi. mức của gốc:=1 b2) Lấy một đỉnh từ hàng đợi ra, nhập các con của nó, các con này có mức:=mức +1, gắn vào cây, mỗi khi nhập một con, lại đưa con đó vào hàng đợi, b3) lặp đi lặp lại b2) cho đến khi nhập số 0. Ta thu được cây cần tạo 2) Có thể sử dụng một trong các phương pháp duyệt cây để tính số đỉnh trên cây(1 đ) 3) Tính chiều cao của cây : = mức(1 đ) 4) Tìm kiếm đỉnh có thông tin = x trên cây: Có thể sử dụng một trong các phương pháp duyệt cây để tìm kiếm đỉnh có thông tin = x(1 đ)