Bài tập vẽ caây nhị phân có đáp án năm 2024
Working... Lời giải. Đồ thị trong trường hợp (a) được gọi là cây nhưng trong trường hợp (b) và (c) thì không phải. Câu 2. Có bao nhiêu đỉnh trong một cây tứ phân đầy đủ với 100 đỉnh lá? Lời giải. Câu 3.
Lời giải. 3 Bài tập cần giải Câu 4. Những đồ thị bên dưới đây có được gọi là cây? a) b) c) d) Lời giải. Đồ thị (a) là cây, các đồ thị còn lại không phải là cây (đồ thị (b),(d) có chu trình; đồ thị (c) là rừng). Câu 5. Có bao nhiêu đỉnh trong một cây ngũ phân đầy đủ với 100 đỉnh trung gian? Lời giải. Ta biết cây m−phân có u đỉnh trung gian thì sẽ có n = u × m + 1 đỉnh tất cả. Áp dụng công thức trên ta sẽ có n = 100 × 5 + 1 = 501 đỉnh tất cả. Câu 6. Có bao nhiêu cạnh trong một cây nhị phân đầy đủ với 1000 đỉnh trung gian? Lời giải. Tương tự câu (5), số đỉnh của cây sẽ là n = 1000 ∗ 2 + 1 = 2001. Từ đó suy ra số cạnh của đồ thị là n − 1 = 2000 Câu 7. Có bao nhiêu lá trong một cây tam phân đầy đủ với 100 đỉnh? Lời giải. n = 100, m = 3 số lá l = [(m − 1)n + 1]/m = (2 × 100 + 1)/3 = 67 Câu 8. Một cây m phân đầy đủ T có 81 lá và có chiều cao là 4. Hãy cho biết giá trị cận trên và cận dưới của m (nghĩa là xác định giá trị lớn nhất có thể và nhỏ nhất có thể). Nếu T là cây cân bằng thì m phải là bao nhiêu? Hãy giải thích rõ. Câu 9. Hãy cho biết tiền thứ tự, trung thứ tự và hậu thứ tự của những cây sau đây. Lời giải. Câu 10. Xây dựng cây nhị phân tìm kiếm cho các từ banana, peach, apple, pear, coconut, mango và papaya theo thứ tự ABC. Lời giải. Lần lượt thêm vào các nodes ta được cây tìm kiếm nhị phân Câu 11. Cần bao nhiêu lần so sánh để tìm thấy hoặc thêm các từ sau vào cây tìm kiếm ở Câu trên. a) pear b) banana c) kumquat d) orange Lời giải. a) 3 lần b) 1 lần c) 5 lần d) 6 lần Câu 12. a) Hãy dùng giải thuật tìm kiếm ưu tiên chiều sâu để tìm cây khung của các đồ thị G 12a , G 12b và G 12c . Chọn đỉnh a là gốc của cây khung.
Lời giải. Câu 13. a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G 2 . b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G 2 . Câu 14. a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G 3 . b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G 3 . Lời giải. Câu 15. a) Hãy dùng giải thuật Prim để tìm cây khung nhỏ nhất của đồ thị G 4 . b) Hãy dùng giải thuật Kruskal để tìm cây khung nhỏ nhất của đồ thị G 4 . BÀI TẬP CÂY NHỊ PHÂN – NP TÌM KIẾM (1) 1. Bài tập 1 Cho cây NPTK Hãy minh họa các bước: - Thêm phần tử 50 vào cây. - Xóa phần tử 40. - Xóa phần tử 37. - Xóa phần tử 44. 2. Bài tập 2 Hãy vẽ cây nhị phân tìm kiếm khi lần lượt thêm vào cây các nút sau: 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90 - Thực hiện duyệt tiền tự, hậu tự cây trên - Thêm phần tử 40, 19 vào cây trên - Xóa phần tử 50 từ cây trên. . 3. Bài tập 3: Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự left – right - node thì được dãy như sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8 Hãy duyệt cây T trên theo thứ tự node - left - right. 4. Bài tập 4 Hãy vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự Node – Left -Right thì được dãy: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, Hãy duyệt cây T trên theo thứ tự left – right – node, left -node-right. Hãy vẽ lại cây sau khi xoá nút 10 sao cho T vẫn là cây nhị phân tìm kiếm. 5. Bài tập 5 a) Hãy vẽ lại cây nhị phân T biết khi duyệt cây T ta được dãy số sau: NLR: 24 5 12 14 18 20 33 13 19 28 LNR: 12 5 18 14 33 20 24 19 28 13 b) Hãy vẽ cây nhị phân tìm kiếm T biết rằng thứ tự các số nhập vào là: 8, 3, 5, 2, 20,11, 30, 9, 18, 4. Sau đó, nếu hủy lần lượt các nút 5, 20 (theo thứ tự đó) thì cây sẽ thay đổi như thế nào trong từng bước hủy (vẽ lại cây cho mỗi bước). BÀI TẬP CÂY NHỊ PHÂN – NP TÌM KIẾM – CÀI ĐẶT (2) HƯỚNG DẪN: Cài đặt cây tìm kiếm nhị phân 1. Khai báo thư việ n include
include 2. Khai bao kieu, bien typedef int KeyType; typedef struct Node* NodeType; struct Node { KeyType key; NodeType left,right; }; typedef NodeType Tree; 3. Khoi tao cay rong void MakeNullTree(Tree *T) { (*T)=NULL; } 4. Kiem tra cay co rong hay khong int EmptyTree(Tree T) { return T==NULL; } 5. Them khoa x vao cay tree void InsertNode(KeyType x, Tree *Root) { if (*Root == NULL) { (*Root)=(NodeType)malloc(sizeof(struct Node)); (*Root)->key = x; (*Root)->left = NULL; (*Root)->right = NULL; |
