Sewickley Academy Programming Team
Programming Contest:  25-Mar-2002
David Kosbie (Faculty Advisor)
Sewickley Academy
Link to Programming Contests home page .
Team Questions (StBon/USC-style)

The contest runs for 3 hours.

Read these problems very carefully.

Question 1:  The Leaves of Spring.  Here you will read in a tree and you will output two numbers -- the depth and the number of leaves.  The format of the tree:  each interior node will have a non-numeric name, followed by a number N>0 (the number of children of this node), followed by each of the N children.  A leaf is always just an integer.  All input is space-delimited.  Also, we define the "depth" as the maximum number of edges traversed from the root to the deepest leaf.

Question 2:  Tree Expression Evaluator.  Here we use the same tree format as in Question 1, but we assume that all the labels will be one of:  plus, minus, times, and divide.  Note that minus 3 12 13 14 would evaluate to ((12 - 13) - 14), and the same goes for the other operators.  All results are integers, and division by zero equals zero, as does any other error (so, for instance, an illegal label).  Read in a tree and output the value it evaluates to.

Question 3:  PrePost Nodes.    Here again we use the same tree format as in Question 1.  Consider the "pre-position" of a node to be the position of that node when the nodes are printed out in preorder (root, then children in order).  Similarly, the "post-position" of a node is the position of that node when the nodes are printed out in postorder (children in order, then root).  A node is a "PrePost Node" if its pre-position equals its post-position.  Read in a tree and print out the count of PrePost Nodes in the tree.

Question 4:  Peer Nodes.    Again we use the same tree format as in Question 1.  Here we define a "Peer Node" as any interior node which has another node (not itself) in the tree with the same depth and same name.  Read in a tree and output the number of Peer Nodes.

Question 5:  Isomorphic Trees.   Yet again we use the same tree format as in Question 1.  Here we define two trees as "isomorphic" if you can rearrange the children of one tree so that the resulting rearranged tree is identical to the second tree (all the same interior and leaf nodes in the exact same order).  Read in two trees and output "Yes" if they are isomorphic, and "No" otherwise.

Question 6:  String Hash Table.  Repeatedly read in strings (which do not contain spaces and are space-delimited) and map each string to an integer, where the kth unique string entered is mapped to the integer k (and this is 0-based).  Keep reading in until you read in the string "done", then continue reading in strings and printing out their mapped integer value until you again read the string "done" (which is not part of the input).