Page 202 - DCAP407_DATA_STRUCTURE

Unit 10: Trees

10.6 Keywords

Compression Ratio: The measurement of compressed data.
Data Encoding: The method by which certain communication devices encode digital data into an analog
signal for transmission.
Genealogy: The study of ancestry and family history.
Kalah: Kalah, also called Kalaha or Mancala, is a game in the Mancala family invented by William
Julius Champion Jr in 1940.
10.7 Self Assessment
1. State whether the following statements are true or false:

(a) Decision trees represent a program in the form of tree with branches.
(b) The null links in a node result in wastage of memory space.
(c) A game tree is an undirected graph whose nodes are positions in a game and whose edges
are moves.
(d) The major advantage of array representation of trees is that it helps in getting direct access to
any node.
(e) An AVL tree is a binary search tree having a balance factor of every node as 0 or +2 or −2.
(f) A binary tree could either have only a root node or have two disjoint binary trees called the
left sub-tree or the right sub-tree.

2. Fill in the blanks:
(a) An AVL tree is a ………………… tree.
(b) The two nodes of 2-3 tree are ……………… and …………………
(c) The ………………… node is tested first, in a decision tree.
(d) The information content of the node is stored in ………………… array.
(e) A …………………graph contains both directed and undirected edges.

3. Select a suitable choice for every question:
(a) A tree data structure in which every node has a maximum of two child nodes is known as a
…………………tree.
(i) Binary
(ii) AVL

(iii) Game
(iv) Huffman

LOVELY PROFESSIONAL UNIVERSITY 195