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

ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN ……………… ĐỀ THI HẾT HỌC PHẦN 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: 04 Câu 1( 2 điểm) Trình bày các đặc điểm của giải thuật đệ quy. Hàm đệ quy (viết bằng ngôn ngữ pascal) dưới đây cho kết quả là gì? Giải thích tại sao? Function Tinh(n,x: byte): Longint; Begin If n = 1 then Tinh := x Else Tinh := n* Tinh(n-1,x); End; Câu 2( 4 điểm ) Giả sử một đơn vị cần quản lý các cán bộ, mỗi cán bộ cần quản lý các thuộc tính sau: Họ tên, năm sinh, giới tính, địa chỉ, trình độ, chức danh . Anh(chị) hãy lựa chọn một cấu trúc dữ liệu để quản lý các thông tin của các cán bộ trong đơn vị đó, sao cho: - Dữ liệu được lưu trong bộ nhớ trong - Thuận lợi cho các phép toán: thêm, xóa cán bộ - Tiết kiệm không gian bộ nhớ nhất. Với cấu trúc dữ liệu mà anh(chị) đã lựa chọn. Anh(chị) hãy: 1) Viết dạng cài đặt của cấu trúc dữ liệu đó 2) Viết giải thuật đếm số lượng cán bộ trong đơn vị 3) Hiển thị thông tin của các cán bộ trong đơn vị 4) Loại bỏ những người đến tuổi về hưu (biết rằng nam: 60 tuối; nữ: 55 tuổi thì về hưu) Câu 3( 2 điểm ) Nêu khái niệm danh sách? các cách cài đặt danh sách bởi mảng, bởi danh sách liên kết đơn? ưu nhược điểm của từng dạng 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ộ Đáp án Câu 1 + Ba đặc điểm của giải thuật đệ quy: ( 1 đ) - Trong giải thuật đệ quy bao giờ cũng có lời gọi đến chính nó - Sau mỗi lời gọi đệ quy, kích thước của bài toán được thu nhỏ hơn trước - Có một trường hợp suy biến: bài toán được giải quyết theo một cách khác hẳn và giải thuật cũng kết thúc + Kết quả của hàm đệ quy là: x*n!, vì: ( 1 đ) n = 1 cho kết quả là: 1*x n = 2 cho kết quả là: 1*2*x n = 3 cho kết quả là: 1*2*3*x .......... n = n cho kết quả là: 1*2*3*.......*n*x = n! * x Câu 2 1) Cấu trúc dữ liệu lựa chọn là danh sách liên kết đơn ( 1 đ) Dạng cài đặt Type Canbo = record Hoten: String; Năm sinh : integer; Giớitinh: boolean; Diachi, trinhdo, chucdang: string; ` Next: ^ Canbo; end; List = ^Canbo; Var L: List; 2) Đếm số lượng cán bộ trong trong danh sách ( 1 đ) - Sử dụng biến đếm lưu số lượng cán bộ trong đơn vị, ban đầu dem:= 0 , - Sử dụng con trỏ phụ M duyệt từ đầu đến cuối danh sách, duyệt đến cán bộ nào thì tăng biến đếm lên 1: - In biến đếm ra màn hình 3) Hiển thị các cán bộ trong đơn vị: ( 1 đ) Sử dụng con trỏ phụ M duyệt từ đầu đến cuối danh sách, duyệt đến cán bộ nào thì hiển thị các thông tin của cán bộ đó lên màn hình: 4) Loại bỏ các cán bộ đến tuổi về hưu trong đơn vị: ( 1 đ) Cách làm: b1) Tìm cán bộ đầu tiên trong danh sách đến tuổi về hưu, giả sử vị trí được trỏ bởi p b2) Loại bỏ cán bộ ở vị trí p b3) Lặp đi lặp lại b1); b2) cho đến khi hết vị trí tìm thấy Chú ý: - để tìm cán bộ thỏa mãn điều kiện ta duyệt từ đầu danh sách p:=L đến khi tìm thấy thì dừng - để loại bỏ học sinh ở vị trí p: a) Di chuyển con trỏ phụ M đến vị trí trước p:  M:=L;  While M^.next <>p do M:=M^.next; b) Bứt liên kết, gắn liên kết, giải phóng p:  M^.next:=p^.next;  Dispose(p); Câu 3 + 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 đó (0.5 đ) + Có thể cài đặt danh sách bởi mảng và bởi con trỏ, tương ứng ta có danh sách kế tiếp và danh sách móc nối (danh sách liên kết). Các dạng cài đặt tương ứng: Cài đặt bởi mảng: ( 0.5 đ) Const n=maxlist; Type list = record Eles: array[1..n]of integer; Count: 0..n; end; Var L: list; Cài đặt bởi con trỏ: (0.5 đ) type list=^nut; nut = record infor: item; next:list; end; var l,f:pqueue; + Ví dụ để quản lý sinh viên, cán bộ ta có danh sách sinh viên, danh sách cán bộ…. Ưu nhược điểm của từng các cài đặt danh sách: (0.5 đ) a) Danh sách cài bởi mảng Ưu điểm i. truy cấp đến các phần tử là trực tiếp do đó nhanh và đồng đều đối với mọi phần tử ii. Các thao tác thực hiện tương đối dễ dàng Nhược điểm iii. Có hiện tượng dư thừa bộ nhớ: Hiện tượng giữ chỗ để đấy mà không dùng tới iv. Bị hạn chế bởi không gian kế tiếp trong bộ nhớ v. Là cấu trúc dữ liệu tĩnh, bị giới hạn không gian bộ nhớ trong thanh ghi dữ liệu và thanh ghi stack vi. có hiện tượng co giãn, dịch chuyển các phần tử khi thực hiện thao tác bổ sung phần tử, hoặc loại bỏ phần tử, do đó là số lượng phép tính trong giải thuật tăng= > độ phức tạp tính toán cũnh tăng theo b) Danh sách cài đặt bởi con trỏ Ưu điểm: - Không gây hiện tượng lãng phí bộ nhớ (Hiện tượng giữ chỗ để đấy mà không dùng đến như danh sách cài đặt bởi mảng) - Cấu trúc dữ liệu danh sách cài đặt bởi con trỏ còn gọi là cấu trúc dũ liệu động, không gian bộ nhớ được cấp phát trong heap, do đó nó không bị giới hạn bởi kích thước 64kb như đối với cấu trúc dữ liệu tĩnh - Các phần tử trong danh sách nằm ở những vị trí dải dác, do đó tận dụng được những không gian trống này, mà không cần một vùng nhớ kế tiếp như cài đặt bởi mảng Nhược điểm: - Tốc độ truy cập đến các phần tử trong danh sách là chậm, không đồng đều đối với mọi phần tử (truy cập tuần tự một chiều) - Từ phần tử trước không truy cập ngược lại phần tử đứng trước - mỗi phần tử trong danh sách tốn thêm một không gian là 4byte để lưu địa chỉ của phàn tử đứng sau nó trong danh sách