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

ĐẠ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: 01 Câu 1( 2 điểm) Thế nào là giải thuật; cấu trúc dữ liệu, mối quan hệ giữa chúng? Hãy nêu một vài cấu trúc dữ liệu tiền định của ngôn ngữ lập trình mà anh (chị) biết? Câu 2( 5 điểm ) Giả sử cần quản lý một lớp học bao gồm các sinh viên. Mỗi sinh viên gồm các thông tin sau: Họ Tên, Lớp, Số báo danh, Điểm trung bình. Anh (chị) hãy: 1) Viết dạng cài đặt danh sách này bằng cấu trúc danh sách liên kết đơn, 2) Với cấu trúc danh sách đã cài đặt, viết các chương trình con thực hiện các yêu cầu như sau: a) Nhập vào danh sách gồm n sinh viên b) Loại bỏ khỏi danh sách những sinh viên có điểm trung bình < 5 c) Sắp xếp danh sách theo trường lớp tăng dần d) In ra màn hình danh sách sinh viên theo từng lớp (n là một số nguyên dương tự nhập từ bàn phím) Câu 3( 1 điểm ) Anh ( Chị ) hãy nêu ưu nhược điểm của cách cài đặt danh sách bởi danh sách liên kết đơn? ………………….....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 + Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng, xác định một dãy các thao tác trên một số đối tượng nào(dữ liệu) đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả mong muốn (0.5 đ) + Cách thức tổ chức biểu diễn dữ liệu mà theo đó dữ liệu được lưu trữ và được xử lý trong MTĐT, được gọi là cấu trúc dữ liệu (0.5 đ) + Mối quan hệ giữa cấu trúc dữ liệu và giải thuật: Giải thuật tác động trên dữ liệu lưu trữ trong các cấu trúc để cho ra kết quả mong muốn. Trong lập trình, chúng quan hệ với nhau theo ràng buộc sau: Giải thuật + cấu trúc dữ liệu = chương trình (0.5 đ) + Một vài cấu trúc dữ liệu của ngôn ngữ lập trình: Mảng, bản ghi, xâu ký tự, tệp tin ….. (0.5 đ) Câu 2 *) Dạng cài đặt danh sách (1 đ) Type Sinhvien = record Hoten: String; Lớp : String; SoBD: String; ĐTB: real; Next: ^ Sinhvien; ` end; List = ^Sinhvien; Var L: List; *) Viết giải thuật 1) Nhập danh sách gồm n sinh viên (1 đ) + Nhập số lượng sinh viên hiện có n: readln(n); + Sử dụng vòng lăp i chạy từ 1 -> n, mỗi lần lặp nhập 1 sinh viên và gắn vào danh sách: for i:=1 to n do begin - new(M); {yêu cầu MT cấp phát ô nhớ chứa dữ liệu của sinh viên cần nhập } - Nhập các thông tin về sinh viên, lưu vào ô nhớ được trỏ bởi M - Gắn kết ô nhớ được trỏ bởi M vào danh sách end; 2) Loại bỏ những SV có điểm trung bình <5 (1 đ) Kiểm tra xem danh sách L có rỗng hay không? Nếu rỗng trở về chương trình chính, nếu không rỗng thực hiện loại bỏ như sau: - Sử dụng con trỏ phụ q duyệt tử đầu đến cuối danh sách, nếu q^.dtb <5 thì gọi thủ tục loại bỏ phần tử được trỏ bởi q trong danh sách - Viết thủ tục loại bỏ phần tử được trỏ bởi con trỏ q trong danh sách L: a) Giả sử đã biết vị trí con trỏ q b) Sử dụng con trỏ phụ p di chuyển đến vị trí trước q: P:= L; While p^.next<> q do p:= p^.next; c) Loại bỏ phần tử ở vị trí q: p^.next := q^.next; dispose(q); q:= p^.next;// lưu vị trí tiếp theo vị trí loại bỏ để còn loại bỏ tiếp 3) Sắp xếp danh sách theo trường lớp tăng dần (1 đ) Có thể sử dụng một trong các thuật toán sắp xếp để sắp xếp dữ liệu trên danh sách liên kết, ở đây ta sử dụng giải thuật sắp xếp chọn trực tiếp (selection sort) và sử dụng cách tiếp cận:giữ nguyên mối liên kết của các nút trong danh sách và hoán vị nội dung của các nút: Giải thuật: Procedure ListSelection_Sort(var L: List) Var p, q, min: List; Begin p:=L; While (p<>nil) do Begin q:=p^.next; min:=p; While (q<>nil) do Begin If (q^.infor nil) do Begin Write(M^. hoten); Write(M^. Lop); Write(M^. sbd); P:=M; M := M^.next; If (M^.lop<>p^.lop) then writeln(‘Các sinh vien lop M^.lop la:’); End; Câu 3 Ưu điểm: (0.5 đ) - 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: (0.5 đ) - 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ử sau không truy cập ngược đến các phần tử đứng trước nó được - mỗi phần tử trong danh sách tốn thêm một ô nhớ có kích cỡ là 4byte để lưu địa chỉ của phần tử đứng sau nó trong danh sách