(5/5)

**Data Structures and File Organization**

**QUIZ # 3 TAKE HOME**

Covers:

**Binary Trees Test I**

**Multiple Choice 10pts**

Choose the best answer from among the given choices and write the letter of your choice.

- 1.Consists of nodes and connecting arcs

A. Queue |
C. Recursion |

B. Stacks |
D. Tree |

- 2. The number of arcs in this sequence is known as the _______ of the path

A. length |
C. arc |

B. size |
D. mid |

- 3. A tree whose nodes have a maximum of 2 children

A. Tree |
C. Binary Tree |

B. Dynamic Tree |
D. Recursion |

- 4. A
*________*is a tree where every non-terminal node has 2 branches.

A. Tree |
C. Binary Tree |

B. Binary Search Tree |
D. Complete Binary Tree |

- 5. Sometimes also be called an ordered or sorted binary tree

A. Tree |
C. Binary Tree |

B. Binary Search Tree |
D. Complete Binary Tree |

- 6. Proceeding as far as possible to the right (or left), and then returning one level, stepping over and stepping down.

A. Tree Traversal |
C. Depth First Traversal |

B. Breadth-First Traversal |
D. Threaded Tree |

- 7. Starting at either the highest or lowest node and visiting each level until the other end is

reached.

A. Tree Traversal |
C. Depth First Traversal |

B. Breadth First Traversal |
D. Threaded Tree |

- 8. The process of visiting each node in the tree exactly once.

A. Tree Traversal |
C. Depth First Traversal |

B. Breadth First Traversal |
D. Threaded Trees |

- 9. Left nodes point to their predecessors, right nodes point to their successors

A. Tree Traversal |
C. Depth First Traversal |

B. Breadth First Traversal |
D. Threaded Trees |

- 10. Can easily be implemented using recursion

A. Tree Traversal |
C. Depth First Traversal |

B. Breadth First Traversal |
D. Threaded Trees |

**Test II**

**Balancing Binary Trees/Threaded Trees **

** **

1-4. Apply AVL rotation to balance each tree. Once balanced, denote whether RH,LH or EH and Convert the following trees to threaded trees. **(12pts each)**

**Test III**

**Binary Search Trees **

- Draw all possible binary search trees for the data elements 5,9 and 12. 2pts each
- Create Binary Search tree using the following data entered in sequential set. Then balance the tree using DSW algorithm: 10pts

7,10,14,23,33,44,50,56,66,70,80

- Given :

inorder: GHFIEABDC

postorder: GFEIHDCBA

** Draw the tree and find the preorder traversal of a tree. 10pts**

- Given the tree: 15pts

Get the infix, prefix and postfix traversal of a tree.

**Test III**

**Expression Trees (30pts)**

Draw the expression tree and find the prefix and postfix expression for the following infix expression (5pts each)

- (x * a) – y / (b * (c + d))
- x + a * b – c/d

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of