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