**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

CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,

Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This

7COM1028 Secure Systems Programming Referral Coursework: Secure

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme