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<min^.infor) then min:=q;

q:=q^.next;

End;

Hoanvi(min^.infor,p^.infor);

P:=P^.next;

End;

End;

4) Hiển thị danh sách sinh viên theo từng lớp: Sử dụng con trỏ M duyệt tử đầu đến cuối danh sách đã được sắp theo lớp ở câu 3, duyệt đến sinh viên nào thì hiển thị các thông tin về sinh viên đó: (1 đ)

M: = L; p:=M;

writeln('Các sinh vien lop M^.lop la:');

While (M<> 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