Bản quyền tài liệu thuộc về diễn đàn
Câu 1 : (3 điểm) Giả sử tồn tại cây nhị phân tìm kiếm (CNPTK) T trên bộ nhớ, có dữ liệu
của mỗi phần tử là 1 điểm trên mặt phẳng như sau:

CODE struct point {

int x,y;

};
struct BSTree {

Node Root;

};
struct tagNode {

point data;

tagNode *Left, *Right;

};


| | |

| | |

|____________|_____________|

| | |

| | |

| Tím | Vàng |

| | |

| | |

|____________|_____________|

a) Hãy cho biết có bao nhiêu số lần phải chia.
b) Hãy cho biết có bao nhiêu hình vuông có diện tích nhỏ hơn b (cho trước).
Hết.
1. Cài đặt các giải thuật sắp xếp : nhị phân, Bubble sort, Select sort, Insert sort,

Heap sort, Quick sort.

2. Cài đặt thuật toán tìm kiếm nhị phân - Binary Search

3. Chương trình đổi cơ số, cài đặt bằng stack

4. Bài toán Josephus : có N người đã quyết định tự sát tập thể bằng cách đứng

Viết các hàm thực hiện các chức năng sau:

Nhập xuất, ghi dữ liệu vào file, đọc dữ liệu từ file

Thêm, xoá một sinh viên.

Tìm kiếm sinh viên theo mã số, theo điểm trung bình

Sắp xếp sv theo mã số

Sắp xếp sv theo điểm từ cao xuống thấp, xếp loại, xếp hạng, loại giỏi ở

trên cùng rồi đến khá trung bình yếu

điểm trung bình

< 5.0 : Yếu

< =6.5 : Nếu có môn dưới 4 : Yếu, ngược lại Trung Bình

Bản quyền tài liệu thuộc về diễn đàn
< 8.0 : Nếu có môn <6.5 : Trung Bình, ngược lại Khá

>=8.0 : Nếu có môn <7 : Khá, ngược lại Giỏi

In ra màn mình danh sách SV : Mã số, Họ tên, các điểm(T,V,L), điểm

trung bình, loại, xếp hạng (cùng điểm TB, cùng loại thì cùng hạng) theo thứ tự

hạng tăng dần.


Đánh dấu, sao chép khối

10. Viết các hàm xác định các thông tin của cây nhị phân T

(xét cách cài đặt đệ quy và không đệ quy)

Bản quyền tài liệu thuộc về diễn đàn
a. Số nút lá

b. Số nút có đúng 1 cây con

c. Số nút có đúng 2 cây con

d. Số nút có khóa nhỏ hơn x (giả sử T là CNPTK)

e. Số nút có khóa lớn hơn x (giả sử T là CNPTK)

f. Số nút có khóa lớn hơn x và nhỏ hơn y (T là CNPTK)

g. Chiều cao của cây

h. In ra tất cả các nút ở tầng (mức) thứ k của cây T

i. In ra tất cả các nút theo thứ tự từ tầng 0 đến tầng thứ h-1 của cây T (h

là chiều cao của T).

j. Kiểm tra xem T có phải là cây cân bằng hoàn toàn không


Anh chị hãy viết chương trình:
1. Đếm số node lá trong cây T (1 điểm)
2. Tạo 01 mảng a (các phần tử là các số nguyên) có số phần tử là số node lá của
cây T, mỗi phần tử mang giá trị là giá trị của các node là (2 điểm)
3. Tính trung bình tổng chiều dài đường đi từ gốc đến tất cả các node lá (2 điểm)

Câu 2 (5 điểm)
Anh chị hãy đề nghị xây dựng 01 cấu trúc dữ liệu (động) và các thủ tục để quản lý
các phần tử được mô tả như sau:
1. MỖi phần tử là một tam giác đều, được thể hiện qua toạ độ 03 đỉnh của tam
giác.
2.Từ 01 tam giác ta lấy toạ độ tâm của tam giác ta sẽ tạo được 03 tam giác mới có
quan hệ với tam giác cũ.
3. Việc phân chia sẽ hoàn tất khi khoảng cách từ tâm đến 01 đỉnh bất kì nhỏ hơn
epsilon cho trước.
4.Hãy cho biết có bao nhiêu tam giác được sinh ra khi phân chia như trên(với dữ
liệu là 01 tam giác có toạ độ xác định ban đầu)?
5. Diện tích tam giác nhỏ nhất là bao nhiêu?
6.Cho biết toạ độ các tam giác có diện tích nhỏ nhất?
7.Có bao nhiêu tam giác có diện tích nhỏ nhất?

Câu 1:

a)Định nghĩa cấu trúc dãy . Đua ra cấu trúc dữ liệu cho dãy số nguyên không quá 200
phần tử.
b) Nêu thuật toán và hàm xử lý :
+ Tính trung bình cộng của dãy.
+ Xuất ra các số nguyên tố trong dãy theo thứ tự tăng dần.

Câu 2 :

- Xuất và nhập 1 đa thức