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

Trong cây tìm kiếm nhị phân, các giá trị ở cây con bên trái của một nút:

1. ATheo thứ tự ngẫu nhiên
2. BBằng giá trị của nút
3. CLớn hơn giá trị của nút
4. DNhỏ hơn giá trị của nút

Đồ thị có trọng số là gì?

1. AĐồ thị trong đó mỗi cạnh có một giá trị số như chi phí hoặc khoảng cách
2. BĐồ thị được lưu trên đĩa
3. CĐồ thị có nhiều cạnh hơn đỉnh
4. DĐồ thị trong đó một số đỉnh nặng hơn các đỉnh khác vì có nhiều cạnh hơn

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

1. ASố đỉnh trong đồ thị
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ố cạnh nối với nó

Duyệt thứ tự giữa (in-order) của cây tìm kiếm nhị phân thăm các khóa theo:

1. AThứ tự tăng dần đã sắp xếp
2. BThứ tự theo mức
3. CThứ tự chèn
4. DLuôn luôn thứ tự giảm dần

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. BĐơ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
3. CLưu số phần tử
4. DNgăn danh sách phát triển vượt quá một số nút tối đa cố định

Trong đống nhị phân min lưu trong mảng (chỉ số bắt đầu từ 0), các con của nút ở chỉ số i nằm ở:

1. Ai/2 và i/2 + 1
2. Bi + 1 và i + 2
3. C2i và 2i + 1
4. D2i + 1 và 2i + 2

Các khóa 5, 3, 8, 1 được chèn theo thứ tự này vào đống min nhị phân dùng mảng rỗng. Mảng cuối cùng là gì?

1. A[1, 3, 5, 8]
2. B[1, 5, 8, 3]
3. C[3, 1, 8, 5]
4. D[1, 3, 8, 5]

Phát biểu nào về heapsort là đúng?

1. ANó sắp xếp tại chỗ trong thời gian O(n log n) trường hợp xấu nhất nhưng không ổn định
2. BNó chạy trong thời gian O(n) với mọi đầu vào
3. CNó cần một cây tìm kiếm nhị phân làm bộ nhớ phụ, nên dùng thêm O(n) bộ nhớ
4. DNó ổn định và cần O(n) bộ nhớ thêm