Ôn tập Cấu trúc dữ liệu & Giải thuật (No Graph)

Trong phân tích độ phức tạp thuật toán, ký hiệu O(n) có nghĩa là gì?

• Thời gian thực thi tăng tuyến tính theo kích thước đầu vào

• Thời gian thực thi luôn cố định

• Thuật toán luôn chạy nhanh hơn O(log n)

• Bộ nhớ sử dụng giảm theo kích thước đầu vào

Ưu điểm chính của mảng (array) là gì?

• Truy cập phần tử bất kỳ nhanh, O(1)

• Thêm/xóa phần tử giữa mảng nhanh

• Tiết kiệm bộ nhớ khi dữ liệu thay đổi nhiều

• Luôn lưu trữ dữ liệu theo dạng cây

Nhược điểm lớn nhất của mảng so với danh sách liên kết là gì?

• Truy cập phần tử đầu chậm

• Chèn/xóa giữa mảng tốn nhiều chi phí

• Không thể lưu dữ liệu dạng số

• Mảng không hỗ trợ duyệt tuần tự

Ứng dụng thực tế thường dùng ngăn xếp (stack) là gì?

• Hệ thống xử lý hàng chờ tại quầy vé

• Quản lý lời gọi hàm trong chương trình

• Tìm đường đi ngắn nhất trong đồ thị

• Tìm kiếm nhị phân

Đặc điểm chính của queue là gì?

• Last In First Out (LIFO)

• First In First Out (FIFO)

• Dữ liệu luôn được sắp xếp tăng dần

• Chỉ lưu trữ kiểu số nguyên

Trong hệ thống in tài liệu, để đảm bảo công bằng, cấu trúc dữ liệu phù hợp nhất để quản lý tài liệu chờ in là gì?

• Stack

• Queue

• Hash Table

• Binary Search Tree

Trong Python, chuỗi (string) có đặc điểm gì?

• Có thể thay đổi từng ký tự trực tiếp

• Không thể thay đổi (immutable)

• Luôn được lưu dạng danh sách liên kết

• Chỉ lưu được ký tự chữ cái, không lưu số

Độ phức tạp thời gian của việc nối chuỗi s1 + s2 (dài m và n) trong Python là gì?

• O(1)

• O(m + n)

• O(log(m+n))

• O(mn)

Điểm mạnh lớn nhất của hash table so với array là gì?

• Lưu trữ dữ liệu tuần tự

• Tìm kiếm phần tử theo key chỉ mất O(1)

• Không bao giờ xảy ra va chạm (collision)

• Dùng ít bộ nhớ hơn mảng

Ưu điểm chính của linked list so với array là gì?

• Truy cập phần tử nhanh

• Thêm/xóa linh hoạt ở giữa danh sách

• Dễ dàng sắp xếp

• Bộ nhớ sử dụng luôn nhỏ hơn