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

Chiều cao của một cây thường được định nghĩa là:

1. ASố con của gốc
2. BSố lá trong cây
3. CSố cạnh trên đường đi dài nhất từ gốc đến một lá
4. DTổng số nút trong cây, tính cả gốc và mọi lá

Bảng băm lưu dữ liệu dưới dạng:

1. AMột chuỗi có độ dài cố định
2. BMột cây có khóa được sắp thứ tự
3. CCác cặp khóa–giá trị được định vị bằng hàm băm
4. DChỉ một danh sách đã sắp xếp

Một cây có n nút thì có bao nhiêu cạnh?

1. An
2. B2n
3. Cn − 1
4. Dn + 1

Chương trình đang chạy dùng cấu trúc dữ liệu nào để theo dõi các lời gọi hàm đang hoạt động và biến cục bộ của chúng?

1. AHàng đợi bộ nhớ heap
2. BCây tìm kiếm nhị phân các khung
3. CBảng băm các hàm
4. DNgăn xếp lời gọi (call stack)

Extract-min hoạt động thế nào trong đống min nhị phân?

1. AChuyển phần tử cuối lên gốc và đẩy xuống
2. BXóa phần tử cuối của mảng
3. CTìm trong tất cả các lá giá trị nhỏ nhất mới
4. DXóa gốc và dịch tất cả phần tử sang trái một vị trí

Một cây nhị phân có gốc 1 với con trái 2 và con phải 3; nút 2 có các con 4 (trái) và 5 (phải). Duyệt thứ tự trước là gì?

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

Vì sao cây B được dùng trong cơ sở dữ liệu và hệ thống tệp?

1. AChúng không cần cân bằng lại
2. BChúng lưu dữ liệu không sắp xếp
3. CChúng dùng ít bộ nhớ hơn bất kỳ mảng nào, nên toàn bộ chỉ mục luôn vừa trong bộ nhớ chính
4. DHệ số phân nhánh cao giữ cây nông, giảm số lần đọc đĩa chậm

Với mỗi phần tử của mảng, bạn muốn tìm phần tử lớn hơn kế tiếp ở bên phải nó, trong tổng thời gian O(n). Cấu trúc nào giúp được?

1. AMột cây tìm kiếm nhị phân được xây lại cho mỗi phần tử
2. BMột ngăn xếp giữ các phần tử đang chờ câu trả lời
3. CMột hàng đợi chứa mọi cặp phần tử
4. DMột bảng băm của mọi phần tử