Question 1

Draw a parsing tree for (a − (3 + 2b))/(c2 + d).

Accepted Answer

Question 2

If T is a tree with 17 vertices, then there is a simple path in T of length 17.

Accepted Answer

A) True 
 B)False

Question 3

ﬁll in the blanks.
-If T is a binary tree with 100 vertices, its minimum height is ____.

Accepted Answer

The answer of ﬁll in the blanks.
-If T is a...

Question 4

ﬁll in the blanks.
-If T is a full binary tree of height h, then the minimum number of leaves in T is and the maximum number of leaves in T is ____.

Accepted Answer

The answer of ﬁll in the blanks.
-If T is a...

Question 5

Use the bubble sort to sort the list 5, 4, 3, 2, 1 in increasing order.

Accepted Answer

The answer of Use the bubble sort to sort the...

Question 6

ﬁll in the blanks.
-If T is a full binary tree with 50 internal vertices, then T has ____ vertices.

Accepted Answer

The answer of ﬁll in the blanks.
-If T is a...

Question 7

Is the code given by c : 00, h : 10, d : 1101, e : 101, z : 111 a preﬁx code?

Accepted Answer

No, the code for h i

Question 8

refer to this graph.  
-Using reverse alphabetical ordering, ﬁnd a spanning tree for the graph by using a breadth-ﬁrst search.

Accepted Answer

The answer of  refer to this graph.  
-Using...

Question 9

In a binary tree with 16 vertices, there must be a path of length 4.

Accepted Answer

A) True 
 B)False

Question 10

The string $- \cdot 2 - x a + 4 y$ is preﬁx notation for an algebraic expression. Write the expression in inﬁx notation.

Accepted Answer

The answer of The string \(- \cdot 2 - x...

Question 11

refer to this graph.  
-Using reverse alphabetical ordering, ﬁnd a spanning tree for the graph by using a depth-ﬁrst search.

Accepted Answer

The answer of refer to this graph.  
-Using reverse...

Question 12

ﬁll in the blanks.
-Every full binary tree with 50 leaves has ____ vertices.

Accepted Answer

The answer of ﬁll in the blanks.
-Every full binary tree...

Question 13

Suppose T is a full m-ary tree with l leaves. Prove that T has (l − 1)/(m − 1) internal vertices.

Accepted Answer

i + l = v = mi + 1.

Question 14

Suppose you have 50 coins, one of which is counterfeit (either heavier or lighter than the others). You use a pan balance scale to ﬁnd the bad coin. Prove that 4 weighings are not enough to guarantee that you ﬁnd the bad coin and determine whether it is heavier or lighter than the other coins.

Accepted Answer

Four weighings yield a 3-ary t

Question 15

Use Huﬀman coding to encode these symbols with given frequencies: a : 0.35, b : 0.4, c : 0.2, d : 0.05. What is the average number of bits required to encode a character?

Accepted Answer

The codes for a, b, c, and d a

Question 16

Every tree is planar.

Accepted Answer

A) True 
 B)False

Question 17

Suppose you have 5 coins, one of which is heavier than the other four. Draw the decision tree for using a pan balance scale to ﬁnd the heavy coin.

Accepted Answer

Weigh 1 and 2 against 3 and 4. If they b

Question 18

ﬁll in the blanks.
-Every 3-ary tree with 13 vertices has ____ leaves.

Accepted Answer

The answer of ﬁll in the blanks.
-Every 3-ary tree with...

Question 19

refer to this graph.  
-Using alphabetical ordering, ﬁnd a spanning tree for this graph by using a depth-ﬁrst search.

Accepted Answer

The answer of  refer to this graph.  
-Using...

Question 20

Prove that if T is a full m-ary tree with l leaves, then T has (ml − 1)/(m − 1) vertices.

Accepted Answer

mi + 1 = v and i = v

Exam 11: A: Trees

Draw a parsing tree for (a − (3 + 2b))/(c2 + d).

If T is a tree with 17 vertices, then there is a simple path in T of length 17.

ﬁll in the blanks. -If T is a binary tree with 100 vertices, its minimum height is ____.

ﬁll in the blanks. -If T is a full binary tree of height h, then the minimum number of leaves in T is and the maximum number of leaves in T is ____.

Use the bubble sort to sort the list 5, 4, 3, 2, 1 in increasing order.

ﬁll in the blanks. -If T is a full binary tree with 50 internal vertices, then T has ____ vertices.

Is the code given by c : 00, h : 10, d : 1101, e : 101, z : 111 a preﬁx code?

refer to this graph. -Using reverse alphabetical ordering, ﬁnd a spanning tree for the graph by using a breadth-ﬁrst search.

In a binary tree with 16 vertices, there must be a path of length 4.

The string −⋅2−xa+4y- \cdot 2 - x a + 4 y−⋅2−xa+4y is preﬁx notation for an algebraic expression. Write the expression in inﬁx notation.

refer to this graph. -Using reverse alphabetical ordering, ﬁnd a spanning tree for the graph by using a depth-ﬁrst search.

ﬁll in the blanks. -Every full binary tree with 50 leaves has ____ vertices.

Suppose T is a full m-ary tree with l leaves. Prove that T has (l − 1)/(m − 1) internal vertices.

Suppose you have 50 coins, one of which is counterfeit (either heavier or lighter than the others). You use a pan balance scale to ﬁnd the bad coin. Prove that 4 weighings are not enough to guarantee that you ﬁnd the bad coin and determine whether it is heavier or lighter than the other coins.

Use Huﬀman coding to encode these symbols with given frequencies: a : 0.35, b : 0.4, c : 0.2, d : 0.05. What is the average number of bits required to encode a character?

Every tree is planar.

Suppose you have 5 coins, one of which is heavier than the other four. Draw the decision tree for using a pan balance scale to ﬁnd the heavy coin.

ﬁll in the blanks. -Every 3-ary tree with 13 vertices has ____ leaves.

refer to this graph. -Using alphabetical ordering, ﬁnd a spanning tree for this graph by using a depth-ﬁrst search.

Prove that if T is a full m-ary tree with l leaves, then T has (ml − 1)/(m − 1) vertices.

The Foundations: Logic and Proofs

A: the Foundations: Logic and Proofs

Basic Structures: Sets, Functions, Sequences, Sums, Matrices

A: Basic Structures: Sets, Functions, Sequences, Sums, Matrices

Algorithms

A: Algorithms

Number Theory and Cryptography

A: Number Theory and Cryptography

Induction and Recursion

A: Induction and Recursion

Counting

A: Counting

Discrete Probability

A: Discrete Probability

Advanced Counting Techniques

A: Advanced Counting Techniques

Relations

A: Relations

Graphs

A: Graphs

Trees

Boolean Algebra

A: Boolean Algebra

Modeling Computation

A: Modeling Computation

Mathematics Problem Set: Set Theory, Number Theory, Combinatorics, and Boolean Algebra

Filters

Draw a parsing tree for (a − (3 + 2b))/(c² + d).

The string $- \cdot 2 - x a + 4 y$ is preﬁx notation for an algebraic expression. Write the expression in inﬁx notation.