Struktur Diskrit : Latihan Soal Introduction to Tree
1. Which of these graphs are trees:
2. Which of these graphs are trees:
3. Answer these questions about the rooted tree illustrated
- Which vertex is the root?
- Which vertices are internal?
- Which vertices are leaves?
- Which vertices are children of j?
- Which vertex is the parent of h?
- Which vertices are siblings of o?
- Which vertices are ancestors of m?
- Which vertices are descendants of b?
- Is the rooted tree a full m-ary tree for some positive integer m?
- What is the level of each vertex of the rooted tree?
- Draw the subtree of the tree that is rooted at
- a
- c
- e
4. Answer these questions about the rooted tree illustrated
- Which vertex is the root?
- Which vertices are internal?
- Which vertices are leaves?
- Which vertices are children of j?
- Which vertex is the parent of h?
- Which vertices are siblings of o?
- Which vertices are ancestors of m?
- Which vertices are descendants of b?
- Is the rooted tree a full m-ary tree for some positive integer m?
- What is the level of each vertex of the rooted tree?
- Draw the subtree of the tree that is rooted at
- a
- c
- e
5. Suppose 1000 people enter a chess tournament. Use a rooted tree model of the tournament to determine how many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost. (Assume there are no ties.)
6. A chain letter starts with a person sending a letter out to 10 others. Each person is asked to send the letter out to 10 others, and each letter contains a list of the previous six people in the chain. Unless there are fewer than six names in the list, each person sends one dollar to the first person in this list, removes the name of this person from the list, moves up each of the other five names one position, and inserts his or her name at the end of this list. If no person breaks the chain and no one receives more than one letter, how much money will a person in the chain ultimately receive?
7. Build a binary search tree for the words
- banana, peach, apple, pear, coconut, mango, and papaya using alphabetical order.
- oenology, phrenology, campanology, ornithology, ichthyology,limnology, alchemy, and astrology using alphabetical order.
8. How many weighings of a balance scale are needed to find a lighter counterfeit coin among four coins? Describe an algorithm to find the lighter coin using this number of weighings.
9. How many weighings of a balance scale are needed to find a counterfeit coin among four coins if the counterfeit coin may be either heavier or lighter than the others?
9. How many weighings of a balance scale are needed to find a counterfeit coin among four coins if the counterfeit coin may be either heavier or lighter than the others?
10. Which of these codes are prefix codes?
- a: 11, e: 00, t: 10, s: 01
- a: 0,e: 1,t: 01, s: 001
- a: 101, e: 11, t: 001, s: 011, n: 010
- a: 010, e: 11, t: 011, s: 1011, n: 1001, i: 10101
11. Construct the binary tree with prefix codes representing these coding schemes
- a: 11, e: 0,t: 101, s: 100
- a: 1,e: 01, t: 001, s: 0001, n: 00001
- a: 1010, e: 0,t: 11, s: 1011, n: 1001, i: 10001
12. What are the codes for a, e, i, k, o, p, and u if the coding scheme is represented by this tree?
13. Use Huffman coding to encode these symbols with given frequencies: a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30. What is the average number of bits required to encode a character?
14. Use Huffman coding to encode these symbols with given frequencies: A: 0.10, B: 0.25, C: 0.05, D: 0.15, E: 0.30, F: 0.07, G: 0.08. What is the average number of bits required to encode a symbol?
Posting Komentar