Câu 1

1) Cấu trúc dữ liệu tiền định của ngôn ngữ lập trình bậc cao là các cấu trúc dữ liệu đã được định nghĩa sẵn trong ngôn ngữ lập trình đó, người lập trình chỉ việc sử dụng mà không cần định nghĩa lại (1 đ)

3) Một vài cấu trúc dữ liệu tiền định như: mảng, bản ghi, tệp tin, ...... (1 đ)

2) Các cấu trúc dữ liệu tiền định có sẵn trong ngôn ngữ lập trình không đáp ứng đầy đủ được nhu cầu lưu trữ dữ liệu lớn của mọi chương trình, không phản ánh đầy đủ bản chất của các đối tượng dữ liệu có trong thực tế = > người ta cần đến các cấu trúc dữ liệu do người lập trình tự định nghĩa. (0.5 đ)

Ví dụ: Xét bài toán quản lý hồ sơ sinh viên trong một khoa, các yêu cầu quản lý hồ sơ là: Thêm, sửa, xóa, tìm kiếm, .....hồ sơ.=> Sử dụng cấu trúc dữ liệu mảng (cấu trúc tiền định)để lưu các thông tin về hồ sơ là không phù hợp vì: cấu trúc mảng không cho phép thực hiện phép toán thêm, xóa, không gian không đủ để lưu trữ tất cả hồ sơ nếu số lượng hồ sơ thực tế lớn,..... (0.5 đ)

Câu 2

+ Dạng cài đặt ngăn xếp sử dụng mảng: (1 đ)

const n = <số phần tử tối đa trong ngăn xếp>;

type Stack = Record

Top: 0..n ;

Element : array [1.. n] of integer;

End;

+ Thêm phần tử x vào ngăn xếp S ở vị trí thứ k tính từ đỉnh ngăn xếp: (2 đ)

Kiểm tra xem ngăn xếp có rỗng không, nểu rỗng thì thêm vào đỉnh ngăn xếp, Nếu ngăn xếp không rỗng: Kiểm tra xem số k nhập vào có > top hay không? Nếu lớn hơn thì thêm x vào đỉnh ngăn xếp, nếu không: Lấy (top-k+1) phần tử kể từ đầu ngăn xếp ra một ngăn xếp phụ, thêm phần tử phần tử x vào ngăn xếp, đổ ( top - k+1) phần tử từ ngăn xếp phụ vào ngăn xếp ban đầu do đó đảm bảo không thay đổi trật tự các phần tử trong ngăn xếp ban đầu sau khi loại bỏ phần tử ở vị trí k.(thủ tục tương ứng tự viết)

Câu 3

(1 đ)

- Cấu trúc ngăn xếp thường được áp dụng cho những bài toán có trình tự truy xuất ngược với trình tự lưu trữ. Ví dụ:

+ Bài toán chuyển đổi cơ số, tìm ước số chung của hai số nguyên, bài toán tính giá trị biểu thức, ....

+ Thường áp dụng trong một số bài toán tìm đường đi trong lý thuyết đồ thị (lưu vết đường đi)

+ làm môi trường lưu trữ các biến toàn cục và cục bộ của các thủ tục trong chương trình dịch của ngôn ngữ lập trình.

(1 đ)

- Phân tích cách giải các bài toán trên để thể hiện rõ điều đã nêu