Practice Problems for Section 7.3 with Solutions

Section 7.3 Worksheet 1. In a tree, the root is level: A) 0 B) 1 C) 2 D) 3 2. In a tree, the grandchildren are level: A) 1 B) 2 C) 3 D) 4 3. The number of vertices in a tree is the sum of the number of parents and the number of: A) levels B) stems C) branches D) leaves 4. In a binary tree, each parent has exactly one child. A) True B) False 5. A binary tree is _______________ if all the leaves are at the highest level. A) tall B) complete C) complex D) fully grown 6. In a complete binary tree of height H, the number of leaves equals: A) 2H B) 2H C) 2H + 1 D) 2H – 1 Page 1 7. In a complete binary tree of height H, the number of parents equals: A) 2H +1 B) 2H – 1 C) 2H + 1 D) 2H – 1 8. In a complete binary tree of height H, the number of vertices equals: A) 2H +1 B) 2H – 1 C) 2H +1 – 1 D) 2H – 1 + 1 9. At the heart of a spell-checker is a binary tree. A) True B) False 10. You want to use a dictionary so that you have to check any word at most six times. How big a dictionary can you accommodate? A) 64 words B) 63 words C) 12 words D) 120 words 11. Estimate the number of checks needed if you have a 16,000-word dictionary. A) 13 B) 14 C) 15 D) 16 12. Estimate the number of checks needed if you have a 60,000-word dictionary. A) 14 B) 15 C) 16 D) 17 Page 2 13. Suppose you tell a story to two of your friends. Some of them repeat the story to two others, and in turn some of these pass the story on. Each time the story is told, it is told to two new people and no one hears the story twice. Sometime later, 271 people know the story. How many people have related the story to others? A) 271 B) 270 C) 169 D) 135 14. One night you put a quarter into a slot machine and get back two quarters. The next night, you put these two quarters back in the machine one at a time, and each time two quarters came out. This pattern continued through the sixth night, after which you took your winnings and went home. How much money did you take home? A) 64 quarters B) 48 quarters C) 32 quarters D) 16 quarters 15. One night you put a quarter into a slot machine and get back two quarters. The next night, you put these two quarters back in the machine one at a time, and each time two quarters came out. This pattern continued through the sixth night, after which you took your winnings and went home. How many quarters were fed into the machine? A) 64 B) 63 C) 47 D) 31 16. What size dictionary can be accommodated by a spell-checker that uses 30 checks? A) 1.1 million words B) 1.1 billion words C) 1.1 trillion words D) 1.1 quadrillion words 17. There are 65 members of an organization. The plan for disseminating news requires one member to contact two others with the information. Each member who receives the news contacts two members who have not yet gotten the news. This continues until all members have the information. How many members contact others? A) 64 B) 48 C) 32 D) 16 Page 3 18. We have a dictionary consisting of 500 words. If we use a binary tree as a spell-checker, how many checks might be required to test whether “tat” is a valid word? A) 7 B) 8 C) 9 D) 10 19. Which of the following is not a parent in the tree below? A) B) C) D) A C G H 20. Which of the following is not a leaf in the tree below? A) B) C) D) F G H J Page 4 21. Which of the following is not a child in the tree below? A) B) C) D) A D G H 22. Make a tree with 10 vertices and exactly 4 parents. 23. For a chain letter, each mailer sends letters to 2 new people. Some letter recipients continue the chain, and some do not. No one gets the same letter twice. Sometime later, there are a total of 500 letter recipients. How many people received letters but did not mail anything? Page 5 Answer Key 1. A 14. A 2. B 15. B 3. D 16. B 4. B 17. C 5. B 18. C 6. B 19. D 7. D 20. B 8. C 21. A 9. A 22. 10. B 11. B 12. C 13. D 23. 251 people Page 6