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

ĐẠ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: 26 Câu 1(2 điểm) Khái niệm danh sách? Cho một danh sách chứa các số nguyên. Anh(chi) hãy: 1) Viết dạng cài đặt của danh sách bằng danh sách liên kết đơn 2) Viết chương trình con đổi ngược mối liên kết của các nút trong DSLK trên Câu 2 ( 4 điểm) Cho một đa thức bất kỳ. Anh(chị) hãy: 1) Biểu diễn đa thức trên dưới dạng một danh sách liên kết đơn với mỗi phần tử là một cấu trúc chứa hệ số và số mũ của thành phần đó. 2) Viết các chương trình con tương ứng với các yêu cầu sau: 1) Tối giản một đa thức (gộp các thành phần có cùng số mũ lại và sắp xếp đa thức theo chiều số mũ giảm dần) 2) Tính tổng, hiệu và tích của hai đa thức bất kỳ 3) Hiển thị đa thức lên màn hình Câu 3 (2 điểm) Anh(Chị) trình bày các cách cài đặt danh sách mà anh(chị) đã đươc học và tự nghiên cứu (Viết dạng cài đặt, ưu nhược điểm của từng cách cài đặt ) ……………………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ộ Câu 1 1) khái niệm danh sách, dạng cài đặt (1 đ) + Danh sách là một cấu trúc dùng để lưu trữ một tập hợp hữu hạn biến động các phần tử thuộc cùng một lớp đối tượng nào đó + Cài đặt danh sách bởi danh sách liên kết đơn: type list=^nut; nut = record infor: iteger; next:list; end; var L: list; 2) 2) Đảo ngược mối liên kết của các phần tử trong d/s (1 đ) + Giả sử L là con trỏ trỏ tới nút đầu tiên trong danh sách. + Để có thể đảo ngược danh sách ta làm như sau: 1. L1:=nil; { khởi tạo danh sách L1 rỗng} 2. Loại bỏ phần tử đầu tiên của danh sách L, p trỏ tới phần tử này 3. Gắn p vào L1: p^.next:=L1, L1:=p Lặp đi lặp lại bước 3 cho đến khi danh sách L rỗng; L:=L1 Câu 2 1)Biểu diễn đa thức (1 đ) type list=^nut; nut = record heso: real; somu: integer; next:list; end; var L: list; 2) Các chương trình con y1) Tối giản đa thức(1 đ) Cách làm: 1. Giả sử đa thức là một danh sách có nút đầu được trỏ bởi L 2. Sắp xếp đa thức giảm dần theo số mũ 3. duyệt đa thức từ đầu đến cuối, xét 2 nút kế tiếp trong danh sách L: + nếu cùng số mũ thì cộng hệ số của 2 nút lại:  nếu tổng = 0, thì loại bỏ 2 nút đó khỏi danh sách L  Nếu tổng khác 0, thì lặp lại bước 3 cho đến khi gặp nút có hệ số khác nó thì: loại bỏ các nút có cùng số mũ ra khỏi L, gắn vào danh sách L1 + Nếu khác số mũ, thì tách nút đứng trước ra khỏi L, gép vào L1 4. Lặp đi lặp lại bước 3 cho đến khi L rỗng; L:=L1 ý 2) Cách làm(1 đ) a) Giả sử cần tính tổng 2 đa thức có các nút đầu được trỏ bởi con trỏ A,B - Sử dụng 2 con trỏ p,q di chuyển đến các nút của 2 danh sách A,B từ đầu đến cuối: p:=A; q:=B; {xuất phát từ nút đầu tiên} + Nếu p^.somu=q^.somu, thì:  Cộng 2 hệ số tương ứng của 2 nút được trỏ bởi p, q: tong:=p^.heso + q^.heso  Nếu tong=0, p:=p^.next; q:=q^.next;  Nếu tong <>0 thì m^.heso:=tong, m^.somu:=p^.somu; gắn m vào cuối danh sách có nút đầu được trỏ bởi C, khởi tạo C:=nil + Nếu p^.somu>q^.somu, thì: m^.heso:= p^.heso; m^.somu:=p^.somu; gắn m vào cuối danh sách C; p:=p^.next + Nếu p^.somu độ phức tạp tính toán cũnh tăng theo