Algorithms Chapter 5 Write a module that will receive an array of 20 elements and will fill that array with the first

Quiz 5 Grading Criteria, Page 1 of 4

Confidential Teaching Materials:

Quiz 5 Grading Criteria

Note: To receive any credit whatsoever, the date, your name, your student number, and your answers must

be legible and readily readable in the judgment of the grader.

Add brief explanatory comments as necessary to make sure your answers are clear and unambiguous

to the grader.

[p1] 10 points

Find and correct any errors in the following module.

You may assume that all type declarations, headers, and comments are correct.

Tree_Node definesa record

data isoftype char

left_child isoftype ptr toa TreeNode

right_child isoftype ptr toa TreeNode

endrecord // Tree_Node

procedure BST_Insert (root isoftype in/out ptr toa TreeNode,

new_data isoftype in Char)

// Purpose: Adds the Char new_data to a binary search tree.

// Preconditions: root is initialized; if tree empty, it is nil.

// Postconditions: new_data is inserted into the tree such that BST

// ordering of nodes is maintained

if (root = NIL) then

root^.data <- new_data

root^.left_child <- NIL

root^.right_child <- NIL

else

if (new_data < root^.data) then

BST_Insert(root^.right_child, new_data)

else

BST_Insert(root^.left_child, new_data)

endif

endprocedure // BST_Insert

LINES=12

[c1] 10 points

2 errors.

Should be:

root <– new(Tree_Node)

Quiz 5 Grading Criteria, Page 2 of 4

Confidential Teaching Materials:

[p2] 30 points

You have just bought a new computer and have decided that you want to be able to keep track of all the software

you have on your computer. For each piece of software you want to store the title, the name of the company who

made it, and the year that you installed it. You have decided that a binary search tree sorted by year would

probably be the easiest method to store this information.

Declare the necessary data structures for your program.

LINES=13

Now write a module that, when passed the name of a company and the root of the tree, will print the title and

installation year for each piece of software installed on your computer that is manufactured by that company.

LINES=35

[c2] 30 points

Tree_Node definesa record

data isoftype SoftwareRec

Quiz 5 Grading Criteria, Page 3 of 4

Confidential Teaching Materials:

20 points for module

[p3] 30 points

Given the following code:

Tree definesa record

data isoftype Num

left_child isoftype ptr toa Tree

right_child isoftype ptr toa Tree

endrecord // Tree

procedure Print_Numbers ( root isoftype in ptr toa TreeNode )

if (root <> nil) then

Print_Numbers ( root^.right_child )

Print_Numbers ( root^.left_child )

print( root^.data )

endif

endprocedure // Print_Numbers

What would be the output of Print_Numbers( tree_head ) for the following tree?

tree_head

\

25

/ \

3 90

/ \ \

67 5 89

\ / \

42 8 31

/

100

LINES=30

[c3]

Quiz 5 Grading Criteria, Page 4 of 4

Confidential Teaching Materials:

[p4] 30 points

Write a module that will receive an array of 20 elements and will fill that array with the first 20 multiples of 5

(starting with 0). Be sure to declare the necessary data structures.

[c4] 30 points

Example solution (many are possible!):

MAX is 20