CTDL&TG - Câu hỏi ôn tập
Câu hỏi ôn tập
Cấu trúc dữ liệu và thuật giải
Chương 1: Các khái niệm mở đầu
1- Từ dữ liệu thực tế đến dữ liệu trong chương trình
máy tính cần phải tượng hóa như thế nào;
2- Định nghĩa mô hình dữ liệu, kiểu dữ liệu trừu
tượng, cấu trúc dữ liệu; phân biệt sự khác nhau; Ví
dụ.
3- So sánh hiệu quả của thuật giải như thế nào, tại sao
cần tính hiệu quả, ví dụ.
4- Định nghĩa kí hiệu O lớn, ý nghiã, ví dụ.
5- Thế nào là phép toán sơ cấp. Cách xác định thời
gian thực hiện thuật giải bằng tổng số phép toán sơ
cấp. Cho ví dụ.
6- Định nghĩa chi phí thời gian tối đa, tối thiểu, trung
bình; Ví dụ.
Chương 2: Sắp xếp - các thuật giải cơ sở
1- Mô tả các thủ tục sắp xếp nổi bọt, chèn trực tiếp,
chọn trực tiếp; Phân tích ước lượng chi phí thời
gian thực hiện của mỗi thủ tục
2- Mô tả thủ tục sắp xếp hoà nhập hai đường; Phân
tích ước lượng chi phí thời gian thực hiện.
3- Mô tả thủ tục sắp xếp nhanh, ví dụ minh hoạ. Phân
tích ước lượng chi phí thời gian thực hiện.
Chương 3: Mô hình danh sách
1- Mô hình danh sách là gì, đặc tả các phép toán cơ
bản của một danh sách
2- Cửa sổ truy cập các thành phần là gì, phân biệt của
sổ truy cập hiển và cửa sổ truy cập ẩn. Ưu nhược
điểm của chúng.

2- Phân tích so sánh việc thực hiện danh sách nối đơn
có dùng và không dùng các nút đánh dấu
Beforefirst, Afterlast.
3- Nhược điểm của danh sách móc nối đơn, các cách
khắc phục.
4- Mô tả cấu trúc danh sách nối vòng, danh sách nối
vòng chỉ thêm bớt tại một chỗ, danh sách nối kép.
Mô tả việc thực hiện các phép toán, minh hoạ bằng
hình vẽ.
5- Xây dựng ngăn xếp và hàng đợi bằng cấu trúc móc
nối. Khai báo (bằng một ngôn ngữ lập trình cụ thể:
Pascal, C). Mô tả việc thực hiện các phép toán,
minh hoạ bằng hình vẽ.
Chương 6: Mô hình cây
__________________________
Nguyễn Đình Hóa – ĐHQG HN
2
CTDL&TG - Câu hỏi ôn tập
1- Định nghĩa các khái niệm cơ bản trong mô hình
cây, ví dụ minh hoạ. Đặc tả các phép toán trong
mô hình cây.
2- Định nghĩa cây nhị phân, cây hoàn chỉnh, cây đầy
đủ (trái), liên hệ giữa chiều cao của cây nhị phân
và kích thước (số nút) của cây.
3- Cây nhị phân dùng cấu trúc mảng, khai báo kiểu
(bằng một ngôn ngữ lập trình cụ thể: Pascal, C,
Java); ví dụ minh hoạ, thời gian thực hiện các phép
toán; ưu nhược điểm.
4- Cây nhị phân dùng danh sách nút. khai báo kiểu
(bằng một ngôn ngữ lập trình cụ thể: Pascal, C,

dần từng khoá.
2- Phân tích phép gỡ bỏ một khoá khỏi cây tìm kiếm,
minh hoạ bằng hình vẽ, cho ví dụ cụ thể.
3- Phân tích ước lượng thời gian thực hiện của các
phép toán trên cây tìm kiếm.
4- Định nghĩa cây cân đối AVL, ý nghĩa, ví dụ minh
hoạ. Mô tả phép quay đơn, phép quay kép bằng
hình vẽ; Trình bày thủ tục cân bằng lại sau phép
thêm khoá; Ví dụ minh họa.
5- Định nghĩa cây đỏ đen, ý nghĩa, ví dụ. Trình bày
thủ tục cân bằng lại sau phép thêm khoá vào cây
đỏ đen.
6- Định nghĩa cây tìm kiếm ngoài, ví dụ.
Chương 8: Tập hợp, bảng, tự điển.
1- Định nghĩa kiểu tập hợp và các phép toán; Phân
biệt kiểu bảng và kiểu tự điển. Các cách biểu diễn
tập hợp và thời gian thực hiện các phép toán.
2- Định nghĩa bảng băm, địa chỉ băm, vấn đề xung
đột địa chỉ, ví dụ minh hoạ, các cách giải quyết.
3- Định nghĩa bảng băm mở, trình bày các phép toán
của bảng băm mở; phân tích ước lượng thời gian
thực hiện.
4- Định nghĩa bảng băm đóng, trình bày các phép
toán trong bảng đóng, các phép băm lại tuyến tính,
băm lại bình phương.
5- Phân tích việc thực hiện tự điển bằng cây tìm
kiếm, khái niệm cây tìm kiêm tối ưu.
Chương 9: Phân hoạch
1- Định nghĩa phân hoạch, các phép toán cơ sở; trình
bày thực hiện phân hoạch bằng cây nối về nút cha,