Question 1 |

Of the following, which best approximates the ratio of the number of nonterminal nodes in the total number of nodes in a complete K-ary tree of depth N ?

1/N | |

N-1/N | |

1/K | |

K-1/K |

Question 1 Explanation:

Question 2 |

Consider the following rooted tree with the vertex labelled P as the root

The order in which the nodes are visited during an in-order traversal of the tree is

The order in which the nodes are visited during an in-order traversal of the tree is

SQPTRWUV | |

SQPTUWRV | |

SQPTWUVR | |

SQPTRUWV |

Question 2 Explanation:

Question 3 |

A complete n-ary tree is a tree in which each node has n children or no children.
Let I be the number of internal nodes and L be the number of leaves in a
complete n-ary tree. If L = 41, and I = 10, what is the value of n?

3 | |

4 | |

5 | |

6 |

Question 3 Explanation:

Question 4 |

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:

nk | |

(n-1)k+1 | |

n(k-1)+1 | |

n(k-1) |

Question 4 Explanation:

Question 5 |

The number of leaf nodes in a rooted tree of n nodes, with each node having 0
or 3 children is

n/2 | |

\frac{(n-1)}{3} | |

\frac{(n-1)}{2} | |

\frac{(2n+1)}{3} |

Question 5 Explanation:

Question 6 |

A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

x(n-1)+1 | |

xn-1 | |

xn+1 | |

x(n+1) |

Question 6 Explanation:

There are 6 questions to complete.