AVL rotation to balance each tree. Once balanced, denote whether RH,LH or EH and Convert the following trees to threaded trees

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

1. Draw all possible binary search trees for the data elements 5,9 and 12. 2pts each
2. 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

 

3. Given :

    inorder: GHFIEABDC

    postorder: GFEIHDCBA

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

4. 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)

1. (x * a) – y / (b * (c + d))
2. x + a * b – c/d

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

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

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

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. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

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

. 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 Sea Ports. Here are the classes and their instance variables we wish to define:

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