Final Exam - University of Texas at Austin



Exam 2

EE 322C - University of Texas at Austin - Summer 2009

Name ____________________________________

Test taking instructions. No calculators, laptops or other assisting devices are allowed. Write your answers on these sheets. Wherever code is required, write JAVA statements in the blank areas provided, or by modifying the given code in place. You are not required to follow the coding style guidelines when writing code on the exam, but be as neat as possible. If you are unsure of the meaning of a specific test question, then write down your assumptions and proceed to answer the question on that basis. If you see a typo or syntax error, fix it, circle it, and if you are right you will get a bonus point for each one fixed. In your programming solutions on this test you may use any of the classes/methods that you know from the library, or collections.

Questions about the exam questions will not be answered during the test.

For the binary tree related questions on this exam you may assume that this generic class has been defined for your use and is included. When the term Btnode is used on the exam it is referring to this generic class.

class Btnode

{ /* this generic class models a node of a binary tree */

/* here are the private data members of the binary tree node */

private T element;

private Btnode left;

private Btnode right;

/* the constructor given an Object,left child,and right child. */

Btnode(T theElement, Btnode lt, Btnode rt )

{ element = theElement;

left = lt;

right = rt;

}

/* here are the public get/set methods for the data members */

public T getElement( ){ return element;}

public Btnode getLeft( ) {return left;}

public Btnode getRight( ){return right;}

public void setElement( T x ){element = x;}

public void setLeft( Btnode t ) {left = t;}

public void setRight( Btnode t ){right = t;}

}

Question 0 - Terminology. [19 pts.] Answer each of the following questions; choose the best answer from the numbered list below. Answers can be reused.

A. ____A binary operation which takes two given sets and yields a set made up of all the items that are in

either set or both sets (without duplicates)

B. ____A collection of key-value pairs that associate a key with a value.

C. ____A hierarchical structure that place elements in nodes along branches that originate from a root.

D. ____A tree structure in which each node can have at most two children, and in which a unique path

exists from the root to every other node.

E. ____A type of tree in which the key value of each node is less than every key value in its right subtree,

and greater than every key value in its left subtree.

F. ____ A type of binary tree in which the height of each node’s subtrees differs by no more than one.

G. ____A graph in which each edge is directed from one vertex to another (or the same) vertex

H. ____A graph in which every vertex is directly connected to every other vertex

I. ____A graph in which each edge carries a value

J. ____A sequential structure that is divided into table elements. The address of an identifier X in the

structure is gotten by computing some arithmetic function

K. ____This occurs when 2 different identifiers are hashed into the same location

L. ____ A method for finding the shortest path from one vertex to another in a weighted digraph

M. ____ A type of Java program that runs inside of a web browser

N. ____ A document layout language for web pages

O. ____ The method that is called every time the surface of an applet window is redrawn

P. ____ A signal to the program that something has happened in the user interface

Q. ____ The method that is called when a printable character is pressed and released

R. ____ The type of object that event notifications are sent to

S. ____ a systematic approach to implementing a trial and error strategy in the search for a solution to a

problem

1) 2-3-4 tree

2) applet

3) AVL tree

4) backtracking

5) binary tree

6) binary search tree

7) black box testing

8) breadth first search

9) collision

10) complete

11) depth

12) depth first search

13) Dijkstra’s algorithm

14) digraph

15) event

16) functional

17) full

18) graph

19) hash table

20) heap

21) HTML

22) Infix

23) keyTyped

24) leaf

25) listener

26) map

27) matrix

28) overflow

29) paint

30) partially filled array

31) Prim’s algorithm

32) queue

33) RGB

34) root

35) set

36) set difference

37) set intersection

38) set union

39) stack

40) synchronization

41) ttree

42) weighted graph

43) White box

Question 1 - Multiple Choice. [2 pts. each - 12 pts total] For each of the following subparts, circle the best or all correct answers as indicated.

A. Which of the following sorting algorithms have a worst case performance that is better than O(n*n)?

i) selectionsort

ii) bubblesort

iii) insertionsort

iv) mergesort

v) heapsort

vi) quicksort

vii) radix (bin) sort

B. Which tree below corresponds to the vector v created by the code below?

int arr[ 8 ] = {3, 12, 15, 4, 67, 6, 55, 9};

Vector v = new Vector (8);

for (int i=0; i< 8; i++) { v.addElement(arr[i]); }

[pic]

C. Which of the following are true of sets?

i. A set with no elements in it is called an empty set

ii. Each element (ie, value) in a set is distinct

iii. The universal set is that which contains all the values of the base type

iv. The cardinality of a set denotes the number of elements in a set

v. New sets can be created by the union, intersection and difference operations

vi. The elements of a set are not ordered

D. Binary search is an ______ search algorithm for the average case.

(i) O(log2n) (ii) O(n2) (iii) O(n) (iv) O(1)

E. What is the value of the postfix expression 6 2 4 5 + * +

i) 10

ii) 24

iii) 25

iv) 33

v) none of the above

F. Given three arrays with L, M and N elements respectively, estimate the running time for the following algorithm in terms of the number of times that the pairwise comparison step is executed:

repeat the following for i from 1 to L for array1

repeat the following for j from 1 to M for array2

repeat the following for k from 1 to N for array3

pairwise compare array1[i], array2 [j] and array3 [k] and based on the result do one the following

case 1: if array1[i] and array2 [j] are equal then { do something 1}

case 2: if array1[i] and array3 [k] are equal then { do something 2}

case 3: if array3[k] and array2 [j] are equal then { do something 3}

end repeat

end repeat

end repeat

i. O ( log 2 (L+M+N) )

ii. O ( N 3 )

iii. O ( L * M * N )

iv. None of the above

Question 2. Evaluation. (2 points each = 6 pts. total) For each of the following code segments, write in the value of the variable x after the Java statements are executed. You may assume that the proper import statements have already appeared.

A. ______________ Vector alist = new Vector (3,2);

alist.add (40);

alist.add (10);

alist.add (20);

alist.add (8);

int x = alist.get(0 ) * alist.get( 2) + alist.size( ) * alist.capacity( ) ;

B. ______________ Stack intStack = new Stack ( );

intStack.push (5);

intStack.push (6);

intStack.push (13 + intStack.peek ( ));

int y = intStack.peek ( ) ;

intStack.pop ( ) ;

int x = y + intStack.peek ( ) ;

C. ______________ int array [ ] = {1,2,3,4,5,6,7,8,9, 10};

Queue s = new LinkedList ( );

for (int i = 0; i < 10; i++) s.add (array [ i ]);

s.remove ( );

int x = s.peek ( ) + array [5];

// hint: from the ADT for queue: add is enqueue, remove is dequeue, peek is front

Question 3. Handling exceptions [8 Points] Modify the following code to make it “bullet proof” (it will not fail in execution). You may ask the user to re-input the needed information if needed, so as to ensure the successful completion of the required computation in the try block.

import java.io.*;

public class Demo

{ public static void main(String args[ ])

{

Scanner input = new Scanner (System.in);

int a, n;

String s;

System.out.println ("Enter a quantity: ");

try // block of code to be monitored for exceptions

{

s = input.next( );

n = Integer.parseInt (s);

a = 356 / n;

}

catch (ArithmeticException e1) //catch arithmetic run time errors

{ System.out.println (“divide by zero attempted”);

}

catch (NumberFormatException e2)

{ //catch invalid conversions of a string to a numeric format

System.out.println (“invalid number in string”);

}

catch (IOException e3) //catch a bad input

{ System.out.println (“invalid input attempt by user”);

}

finally

{

}

System.out.println (“successfully completed with values ” + s + “ “ + n + “ “ + a);

}

}

4. Tree questions (11 pts)

A. (2 pts) Draw the tree created by the following statements. Btnode is defined on page 1.

Btnode root, a, b, c, d;

d = new Btnode (6, NULL, NULL);

c = new Btnode (9, d, NULL);

b = new Btnode (4, NULL, c);

a = new Btnode (12, NULL, NULL);

root = new Btnode (10, a, b);

B. (4 pts) Trace the method count() below and describe what it does

public static int count (Btnode t)

{ int ctLeft, ctRight, ct;

if (t == NULL)

ct = 0;

else

{ ctLeft = count(t.getLeft());

ctRight= count(t.getRight());

boolean flag = (t.getLeft()!= NULL && t.getRight()!= NULL);

ct = ctLeft + ctRight;

if (flag) ct++;

}

return ct;

}

C. (5 pts) Consider the following binary search tree. Use the original tree below when answering each subpart (a) through (e).

[pic]

(a) If the value 46 is inserted into this tree, which node becomes its parent? __________________

(b) If the value 64 is inserted into this tree, which node becomes its parent? ___________________

(c) If we delete node 65, which node should be its replacement node? ___________________

(d) If we delete node 90, which node should be its replacement node? __________________

(e) If we delete the root node 50, which node should be selected as its replacement node so that the fewest number of changes are made to the tree? ______________________

5. Heaps and Graphs (19 pts)

A. (3 pts) A heap can be represented by a vector. Start with the following maximum heap and list the elements after each operation. Execute the operations sequentially, using the result of the previous operation. The initial vector values for the heap are {50, 35, 15, 12, 3, 5}.

[pic]

(a) Insert 23: The vector values are now {____________________________}.

(b) Delete (pop) an element from the heap: The vector values are now {__________________}.

B. (3 pts) Start with following tree and "heapify" it to create a maximum heap. Draw the resulting tree.

[pic]

C. (3 pts) Start with following tree and heapify it to create a minimum heap. Draw the resulting tree.

[pic]

D. (3 pts) Show the minimum cost path from node B to node E in the following digraph G.

[pic]

E..(3 pts) Draw the node list and adjacency matrix representation for the following digraph G.

[pic]

F (4 pts) Draw the minimal spanning tree for the following graph G.

6. Hash Tables (6 pts) The following hash table is used to store integer values. Assume that we use the following hashing function to store values in the table.

h(x) = x % tableSize (tableSize is equal to the size of the hash table below - which is 20)

Show the resultant hash table after inserting the values: 12, 11, 2, 5, 7, 10, 21, 121, 23, 33, 71, 90, 52 in that order. Use the linear probing technique for collision resolution. That is, if the initial hash location yields a collision then probe forward until an empty slot can be found. The table is used in a circular manner for that purpose.

|Index |Value |

|0 | |

|1 | |

|2 | |

|3 | |

|4 | |

|5 | |

|6 | |

|7 | |

|8 | |

|9 | |

|10 | |

|11 | |

|12 | |

|13 | |

|14 | |

|15 | |

|16 | |

|17 | |

|18 | |

|19 | |

7. Maps (6 points)

Complete the program below whose purpose is to count and record the number of occurrences of each character found in a given text file (“in.txt”). You are to use the hash map m to store the number of occurrences of each character. You can use the default hashcode method for Character. After all characters in the file are processed, output a table to the screen that contains 2 columns with each character in column 1 and its total number of occurrences in column 2. Note: all legal characters are to be counted. Tip: read() returns a -1 if EOF is encountered.

import java.io.*;

public class CountingChars

{ public static void main(String[ ] args) throws IOException

{

Map m = new HashMap ( );

FileReader infile = new FileReader("in.txt");

BufferedReader in = new BufferedReader(infile);

// process all the characters in the file, one at a time

char c = (char) in.read( ); // read the first char from the file

while ( )

{

c = (char) in.read(); // read the next char in the file

}

// output the table of (char, count) pairs

}

}

Question 8 [13 points total]. There are 2 parts to this question in which you are to design a system using a new data type to support Big Integer Arithmetic for the following application.

Problem:

In the year 2050, in order to build the new version of Intergalactic Mapquest, you will need to keep track of large mileage values between interplanetary objects. For example, you will need to record that it is 3,647,200,000 miles from the center of our solar system to Pluto, and that it is 4,692,556,800,000,000 miles from our solar system to the Orion system. You will need to be able to add and subtract these large mileage values so that we can plan a starship travel route and compute the amount of fuel that will be needed. Unfortunately, in order to be backwards compatible with previous versions of the Mapquest product suite you will still be using the Java language for development; which sadly still uses a 32 bit representation for its int data type. So, you will need to design a BigInt data type for your purposes.

As seen in the figure below, you will represent a BigInt value by a list of nodes with int data values in each node. Each node stores a block of up to 3 consecutive digits. You will need to keep references to the beginning and end of the list as well. You will only need to represent positive BigInt values. For example, the number 9,145,632,884 would have the following BigInt representation.

Operations: You will need operations for inputting and outputting a BigInt, as well as, operations for adding and subtracting a pair of BigInts.

1. Input is done in blocks of 3 digit ints, left to right, separated by spaces. As each new block is entered, a node is added to the end of the list. The first block may have less than 3 digits.

2. Output is done by a forward traversal of the list, from left to right, separating each 3-digit block by a comma.

3. Addition adds the associated groupings of two given BigInts from right to left, handling any carry digits from group to group as needed, and creates a new BigInt as the result.

4. Subtraction is only legal when taking a smaller BigInt value from a larger BigInt value – that is, no negative answers are allowed. In the legal case, subtraction processes the groupings from right to left, handling any borrowing that is required from group to group as needed, and creates a new BigInt as a result.

3 [7 pts] Draw a UML class diagram for the new Intergalatic Mapquest system which uses the BigInt ADT. You must also include the class for representing a BigInt node, which will be contained inside the BigInt class.

B. [6 points] As part of your design you will need to select and justify any underlying data structures needed to implement the BigInt ADT. You should choose the most appropriate collection from the Collections framework classes to represent a BigInt. Write your justification (why you selected the implementation data structure) in terms of the suitability to support the necessary operations, and any performance considerations. Describe your choices and justification here.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download