Cấu trúc dữ liệu & Giải thuật (cuối khoá)

Tại sao chúng ta cần học cấu trúc dữ liệu và giải thuật?

• Để nhớ công thức tính toán nhanh hơn

• Để giải quyết bài toán hiệu quả hơn về thời gian và bộ nhớ

• Để tránh phải học lập trình nặng cao

• Để thay thế việc học ngôn ngữ lập trình

Big O notation được dùng để mô tả điều gì?

• Tốc độ mạng internet

• Chi phí điện năng khi chạy chương trình

• Độ phức tạp thời gian hoặc không gian của thuật toán

• Số lần biên dịch chương trình

Cấu trúc dữ liệu mảng (array) phù hợp nhất trong tình huống nào?

• Khi cần thêm/xoá phần tử thường xuyên

• Khi cần truy cập phần tử nhanh bằng chỉ số

• Khi dữ liệu có kích thước thay đổi liên tục

• Khi cần đảm bảo dữ liệu luôn được sắp xếp

Stack (ngăn xếp) sử dụng nguyên tắc nào?

• FIFO – First In First Out

• LIFO – Last In First Out

• Random Access

• Binary Access

Queue (hàng đợi) thường được áp dụng trong tình huống nào?

• Quản lý undo/redo trong editor

• Gọi khách hàng theo thứ tự đến trước – phục vụ trước

• Cây tìm kiếm nhị phân

• Hash Table lookup

Hash Table có ưu điểm gì so với mảng hoặc danh sách liên kết khi tra cứu dữ liệu?

• Truy cập nhanh hơn trung bình O(1)

• Luôn lưu dữ liệu theo thứ tự tăng dần

• Tự động tránh va chạm dữ liệu

• Có thể lưu trữ vô hạn dữ liệu

Đệ quy (recursion) thường hiệu quả trong trường hợp nào?

• Các bài toán có thể chia nhỏ thành bài toán con giống nhau

• Khi cần truy cập phần tử mảng nhanh

• Khi xử lý dữ liệu dạng bảng

• Khi viết các chương trình đồ hoạ 3D

Một Binary Tree được coi là cân bằng (balanced) khi nào?

• Tất cả node đều có đúng 2 con

• Chiều cao của cây trái và phải không chênh lệch quá nhiều

• Node gốc luôn lớn hơn node con

• Tất cả node là ở cùng một mức

Điểm yếu lớn nhất của Binary Search Tree (BST) khi dữ liệu được chèn theo thứ tự tăng dần là gì?

• Không thể lưu dữ liệu mới

• Trở thành danh sách liên kết, làm mất lợi thế tìm kiếm O(log n)

• Không thể xoá phần tử

• Luôn sinh ra lỗi tràn bộ nhớ

Heap được dùng chủ yếu trong ứng dụng nào sau đây?

• Quản lý lịch sử truy cập web

• Cài đặt Priority Queue

• Lưu trữ mảng tĩnh

• Duyệt đồ thị theo chiều rộng