Mã đề 25

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 (0.5 đ)

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

Câu 2

+ Dạng cài đặt của danh sách: (1 đ)

Type Nut = record

infor: integer;

' Next: ^ nut;

end;

List = ^Nut;

Var L: List;

+ Đảo nhóm k phần tử đầu cho k phần tử cuối của danh sách L: (1 đ)

Cách làm: - Chia danh sách L làm 3 đoạn, lần lượt cho L1, L2, L3 trỏ tới đầu mỗi đoạn

+ Tách k phần tử đầu của L, L1 trỏ tới phần tử đầu của danh sách này

+ Đếm số nút trong danh sách L lưu vào d

+ Tách d-k phần tử đầu của L, L2 trỏ tới đầu đoạn này

+ Đoạn còn lại của L, cho L3 trỏ tới đầu đoạn

- Ghép các danh sách lần lượt theo trình tự: L3, L2, L1

- cho L trỏ tới đầu danh sách đã ghép

Câu 2

+ Có thể cài đặt cây bằng danh sách các con của mỗi đỉnh: Tương tự y1) câu 3 đề 09 (1đ)

+ Viết các chương trình con tương ứng với các yêu cầu:

1) Tạo cây (1 đ)

b1) Nhập gốc cây, lưu vào hàng đợi. mức của gốc:=1

b2) Lấy một đỉnh từ hàng đợi ra, nhập các con của nó, các con này có mức:=mức +1, gắn vào cây, mỗi khi nhập một con, lại đưa con đó vào hàng đợi,

b3) lặp đi lặp lại b2) cho đến khi nhập số 0. Ta thu được cây cần tạo

2) Có thể sử dụng một trong các phương pháp duyệt cây để tính số đỉnh trên cây(1 đ)

3) Tính chiều cao của cây : = mức(1 đ)

4) Tìm kiếm đỉnh có thông tin = x trên cây: Có thể sử dụng một trong các phương pháp duyệt cây để tìm kiếm đỉnh có thông tin = x(1 đ)