Preview

08 - Trees

 1. In computer science, a tree is a widely used data structure that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of _______________.

  linked nodes

  text-based nodes

  isolated nodes

  numbered (and with a maximum of 8) nodes

 2. Which of the following are valid applications of trees in the field of computer science?
1. Binary Space Partition
===========================
Used in almost every 3D video game to determine 
what objects need to be rendered.

2. Radix trees
===========================
Used in almost every high-bandwidth router 
for storing router-tables.

3. Huffman Coding Tree
============================
Used in compression algorithms,
such as those used by the .jpeg and .mp3 
file-formats.
binaryspacepartitioning.jpg

  1 only

  All the options are valid and are examples of the use of trees in computing

  1 and 2 only

  2 only

 3. Read the following excerpt that highlights the difference between Queues and Stacks and Trees. Fill in the blanks
The QUEUE and the STACK can essentially be thought of as linear lists. 
This means each data item only points to the one before it and after it.

Queues and Stacks have the concept or sense of order that is built into them, 
such as 'last' or 'first', but the reality is that there is no implication of
any relationship between the data items themselves.

The TREE however, is designed to represent ___________________________________

  the highest implementation (in the sense of being superior) of a stack

  the fastest implementation of a hybrid stack-queue data structure

  the relationship between data items

  the relationship between a stack and a queue

 4. The image below shows a simple unordered tree. Which of the following statements are accurate?
1. The node labeled 7 has two children, labeled 2 and 6, 

2. The node labeled 7 has one parent, labeled 2. 

3. The root node is 4 and has no parent

4. The node labeled 2 is known as the 'first child' node. 
simpleunorderedtree.png

  Statements 1 and 4 are correct

  Statements 3 and 4 are correct

  Only statement 1 is correct

  Only statements 1 and 2 are correct

 5. The tree with no nodes is called a null or empty tree

  TRUE

  FALSE

 6. A node with no children is called a:

  parent

  leaf

  internal or branch node

  edge

 7. A node with at least one child is called an:

  parent

  edge

  leaf

  internal or branch node

 8. The connection between one node and another node is called an:

  internal or branch node

  parent

  leaf

  edge

 9. A group of nodes with the same children are called 'siblings'

  FALSE

  TRUE

 10. The ______of a node is defined as: 1 + the number of edges between the node and the root

  depth of a node

  height of a tree

  level

  height of a node

 11. The ___________is the number of edges on the longest path between that node and a leaf.

  height of a node

  level

  height of a tree

  depth of a node

 12. The ________ is the height of its root node.

  depth of a node

  height of a tree

  height of a node

  level

 13. The _______ is the number of edges from the tree's root node to the node.

  height of a node

  height of a tree

  level

  depth of a node

 14. As a data type, a tree has a value and children, and the children are themselves _____

  level-free

  depth-first

  set to a height of zero

  trees

 15. A __________ is a type of tree in which a parent node has only two child nodes.

  sorted T-type tree

  binary tree

  height-first tree

  depth-first tree

 16. ____________ traversal would give: 4251637
traversalofthistreequestions.png

  post-order

  in-order

  breadth-first search

  pre-order

 17. ____________traversal would give: 1245367
traversalofthistreequestions.png

  post-order

  in-order

  pre-order

  breadth-first search

 18. ___________traversal would give: 7635421
traversalofthistreequestions.png

  pre-order

  breadth-first search

  in-order

  post-order

 19. __________ would give: 1234567
traversalofthistreequestions.png

  breadth-first search

  pre-order

  post-order

  in-order

 20. Which of the following statements are correct in either describing the advantages of the use of trees or defining the function of a tree.
1. Trees reflect structural relationships in data which are useful

2. Trees are used to represent heirarchies

3. Trees provide an efficient insertion and searching method

4. Trees are very flexible data structures, allowing the move of
sub-trees around with minimum effort. 

  Statement 3 only

  Statement 2 and 3

  Statement 1,2,3 and 4

  Statement 1 and 2