Suppose the sign ^ denotes the power operator. Maximum number of nodes in a binary tree with height k, where root is height 1, is
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "2^k – 1". Với quy ước gốc ở chiều cao 1, tầng thứ i nhiều nhất có 2 mũ (i-1) nút vì mỗi nút sinh tối đa hai con, nên cây k tầng chứa nhiều nhất 2^0 + 2^1 + ... + 2^(k-1) nút, và đó là tổng cấp số nhân bằng 2^k - 1. Thử lại: k bằng 1 cho 1 nút, đúng là một gốc; k bằng 3 cho 7 nút, đúng là cây đầy ba tầng 1 + 2 + 4. Vì vậy "2^(k+1) - 1" sai vì nó là số nút của cây k+1 tầng, tức cộng thêm một tầng không tồn tại, với k bằng 1 nó cho 3; "2^(k-1) + 1" sai vì 2 mũ (k-1) chỉ là sức chứa của riêng tầng cuối, cộng 1 không thay được tổng các tầng trên, với k bằng 3 nó cho 5 thay vì 7; "2^k + 1" sai vì nó vượt sức chứa thật đúng 2 nút, với k bằng 1 nó cho 3 trong khi cây cao một tầng chỉ có thể có một nút.
Cùng phần 4
What is the minimum number of nodes in a nearly complete binary tree with height 4?
(In a tree the height of root is 1, and a binary tree with height h is called nearly complete if the tree is complete at level d for d = 1, 2, ..., h-1, and the leaves in the last level are all in the leftmost positions).Có lời giảiCâu hỏiTo implement an AVL tree, a concept balance factor is introduced (bal = height(right)-height(left)). Suppose an AVL tree is created by inserting to the tree the following keys sequentially:
6, 3, 7, 2, 5, 1
What is the balance factor of the node 6? (please note that the tree is still AVL)Có lời giảiCâu hỏiSuppose the binary search tree T is made by inserting the following keys consequently: 6, 7, 8, 9, 3, 2, 5, 4
What is the result of breadth-first traverse of T?Có lời giảiCâu hỏiCả 76 câu của chủ đề76 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây