Câu 1

* Khái niệm ngăn xếp, hàng đợi: (0,5 đ)

- Ngăn xếp là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử ra khỏi ngăn xếp đều được thực hiện ở một đầu, đầu đó gọi là đỉnh của ngăn xếp

- Hàng đợi là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu còn phép loại bỏ một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia

* Sự giống và khác nhau giữa ngăn xếp và hàng đợi (0,5 đ)

+ Giống nhau:

- Cũng là danh sách

- Có hai phép toán cơ bản là bổ xung và loại bỏ (đều đóng vai trò là bộ nhớ đệm)

+ Khác nhau:

- Việc thêm vào, lấy ra một phần tử từ ngăn xếp đều được thực hiện ở một đầu, do đó ngăn xếp hoạt động theo nguyên tắc LIFO, thích hợp với các ứng dụng có trình tự truy xuất ngược với trình tự lưu trữ

- Việc thêm vào, lấy ra một phần tử từ hàng đợi được thực hiện ở hai đầu khác nhau, do đó hàng đợi hoạt động theo nguyên tắc FIFO, thích hợp với các ứng dụng có trình tự truy xuất và trình tự lưu trữ như nhau

* Dạng cài đặt ngăn xếp và hàng đợi bằng mảng: (0,5 đ)

+ Ngăn xếp:

Const n = 100;

Type Stack = Record

Ele: Array [1.. n ] of Item;

Top: 0..n;

End;

+ Hàng đợi:

Const n = 100;

Type Queue = Record

Ele: Array [1.. n ] of Item;

Front, Real: 0..n;

End;

Trong đó:

- Item: Là kiểu dữ liệu chứa trong hàng đợi hoặc ngăn xếp

- Top: Trỏ tới đỉnh ngăn xếp; Front, Real: Trỏ tới lối trước và lối sau của hàng đợi,

- Ele: Mảng chứa các phần tử có trong hàng đợi hoặc ngăn xếp

* Hàng đợi không tròn có hiện tượng khi thêm một phần tử và vào hàng đợi mà Real = n thì không thêm được nữa, mặc dù lối trước có thể vẫn còn các ô nhớ trống. Hàng đợi tròn tận dụng tối đa được không gian trống trong hàng khi thêm một phần tử và hàng, khắc phục hạn chế của hàng đợi không tròn (0,5 đ)

Câu 2

a) Vẽ đồ thị biểu diễn S (1 đ)

b) Biểu diễn đồ thị bằng danh sách lân cận kề, hình ảnh đồ thị trong bộ nhớ (1 đ)

* Hình ảnh đồ thị trong bộ nhớ:

V[1] 1

V[2] 2

V[3] 3

V[4] 4

V[5] 5

V[6] 6

V[7] 7

* Dạng cài đặt:

const n = <số đỉnh tối đa trong đồ thị>;

Type Pointer = ^nut;

Nut = Record

Id: 0..n;

Next : Pointer;

End;

Graph = Pointer;

c) Các giải thuật duyệt : chiều sâu (1 đ), chiều rộng (1 đ)

Câu 3

* khái niệm cây nhị phân tìm kiếm (0.5 đ): Cây NPTK là một cây nhị phân thỏa mản 3 điều kiện:

Điều kiện 1: Khóa tại các đỉnh của cây con trái nhỏ hơn khóa tại gốc

Điều kiện 2: Khóa tại gốc > khóa tại các đỉnh của cây con bên phải

Điều kiện 3: Cây con bên trái và cây con bên phải đều là cây NPTK

* Cấu trúc cây NPTK trước hết thuận lợi chi phép toán tìm kiếm, độ phức tạp trong trường hợp xấu nhất về mặt thời gian O(h), với h là chiều cao của cây. Từ đó kéo theo các phép toán khác cũng thuận lợi như phép toán: Thêm, sửa, xóa, ..... (0.5 đ)

* Phân tích để thể hiện điều trên: Phân tích dựa vào độ phức tạp xâu nhất về mặt thời gian, với các dạng tồn tại của cây NPTK như: Dạng cây suy biến, cây đầy đủ hoặc hoàn chỉnh, cây bình thường(1 đ)