chuong 5+6 Data

Đối với mỗi nút trên cây tìm kiếm nhị phân, số lần so sánh để tìm thấy 1 nút X trên cây là…?

• Chiều cao của cây

• Số nút con của nút X

• Bằng độ dài đường đi từ nút gốc đến nút X

Việc xóa 1 nút X có đầy đủ 2 con trên cây tìm kiếm nhị phân thực chất là…?

• Tìm nút con lớn nhất trên cây trái hoặc nhỏ nhất trên cây phải của nút X và xóa 1 trong 2 nút này.

• Xóa nút lá là con của nút đó

• Thay thế nút X bằng nút con lớn nhất trên cây trái hoặc nhỏ nhất trên cây phải của nó.

Tìm đường đi ngắn nhất từ đỉnh 1 -> 3 trong đồ thị sau là...?

• 1, 1, 2, 3

• 1, 2, 3

• 1, 4, 3

• 1, 5, 3

Việc xóa 1 nút X có đầy đủ 2 con trên cây tìm kiếm nhị phân thực chất là…?

• Tìm nút con lớn nhất trên cây trái hoặc nhỏ nhất trên cây phải của nút X và xóa 1 trong 2 nút này.

• Xóa nút lá là con của nút đó

• Thay thế nút X bằng nút con lớn nhất trên cây trái hoặc nhỏ nhất trên cây phải của nó.

 

Cho đồ thị G=(V,E). Ta nói hai đỉnh u,v thuộc V là kề nhau nếu?

• Có đường đi từ v đến u

• Có đường đi từ u đến v

• Có đường đi từ u đến v và ngược lại

• Có cung (cạnh) nối u với v

Giả sử cây tìm kiếm nhị phân T có thành phần dữ liệu là Key, L và R là 2 con trỏ trỏ đến các nút con trái và phải của 1 nút, P là 1 con trỏ trỏ vào gốc của cây. Tìm kiếm nút có giá trị X trên cây, nếu X>P->Key  thì làm gì tiếp theo?

• P=T

• P=P->L

• P=P->R

Nếu dùng mảng A để mô tả 1 Max-Heap, giả sử A[i] là giá trị của nút cha thì  A[i] phải thỏa mãn điều kiện nào sau đây (chỉ số mảng bắt đầu từ 0)?

• A[i] ≥A[2*i+1] và A[i] ≥A[2*i+2]

• A[i]≤A[2*i] và A[i] ≤A[2*i+1]

• 14,12,3,20,0,11,28,22

  
  

• A[i]≥A[2*i+1] hoặc A[i] ≥A[2*i]

Cho đơn đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, E là tập các cặp  không có thứ tự gồm hai phần tử khác nhau của V gọi là?

• Các cạnh

• Các cung

• Các khuyên

• Các đỉnh

Chọn đáp án đúng. Cho đồ thị G có trọng số như hình vẽ. Đường đi ngắn nhất từ đỉnh A -> E có tổng trọng số là…. ?

• 18

• 38

• 8

• 28

Nhược đểm của việc sử dụng mảng để biểu diễn cây tìm kiếm nhị phân là gì?

• Khó tìm kiếm

• Lãng phí bộ nhớ trong trường hợp cây khuyết nhiều nút

• Khó lập trình