Phiếu bài tập Cấu trúc dữ liệu có đáp án

Trong đồ thị vô hướng, bậc của một đỉnh là gì?

1. ASố cạnh nối với nó
2. BVị trí của nó trong danh sách kề
3. CĐộ dài đường đi dài nhất từ nó
4. DSố đỉnh trong đồ thị

Các phần tử của mảng được lưu trong bộ nhớ như thế nào?

1. ATrong một cây các trang bộ nhớ
2. BỞ các vị trí ngẫu nhiên do hàm băm chọn
3. CRải rác, liên kết bằng con trỏ
4. DTrong một khối liên tục, nối tiếp nhau

Duyệt thứ tự sau (postorder) của cây nhị phân thăm các nút theo thứ tự nào?

1. ACây con trái, rồi cây con phải, rồi nút
2. BCây con phải, rồi nút, rồi cây con trái
3. CCây con trái, rồi nút, rồi cây con phải
4. DNút, rồi cây con trái, rồi cây con phải

Mục đích của nút lính canh (sentinel, nút giả) trong danh sách liên kết là gì?

1. ALàm cho danh sách được sắp xếp
2. BNgăn danh sách phát triển vượt quá một số nút tối đa cố định
3. CLưu số phần tử
4. DĐơn giản hóa mã bằng cách loại bỏ các trường hợp đặc biệt ở đầu hoặc cuối

Tìm một từ có độ dài L trong trie với bảng chữ cái cố định mất bao lâu?

1. AO(L), không phụ thuộc số từ được lưu
2. BO(n), với n là số từ
3. CO(log n), với n là số từ
4. DO(L × n)

Cây AVL và cây đỏ-đen đảm bảo:

1. ACác khóa được lưu theo thứ tự chèn
2. BChiều cao O(log n) nhờ cân bằng lại
3. CKhông nút nào có hai con
4. DTìm kiếm thời gian hằng số trong mọi trường hợp

Chèn một khóa vào cây AVL làm cây con trái của một nút quá cao, và khóa mới đi vào cây con trái của con trái của nó (trường hợp trái-trái). Cách sửa nào được áp dụng?

1. AMột phép xoay phải đơn tại nút mất cân bằng
2. BMột phép xoay trái đơn tại nút mất cân bằng
3. CXoay trái tại nút con, rồi xoay phải tại nút
4. DTô lại màu nút và con của nó

Cấu trúc dữ liệu nào hỗ trợ bộ nhớ đệm LRU (ít được dùng gần đây nhất) với get và put O(1)?

1. AMột mảng đã sắp xếp đơn lẻ
2. BChỉ một cây tìm kiếm nhị phân
3. CChỉ một ngăn xếp
4. DMột bảng băm kết hợp với danh sách liên kết đôi