Final Exam - University of Texas at Austin



Exam 2

EE 422C - University of Texas at Austin - Spring 2011

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 JCF.

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;

private Btnode parent;

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

Btnode(T theElement, Btnode lt, Btnode rt, Btnode pt )

{ element = theElement;

left = lt;

right = rt;

parent = pt;

}

/* 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 Btnode getParent( ){return parent;}

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

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

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

public void setParent( Btnode t ){parent = t;}

}

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

A. ____ a type of signal to your program that something has happened

B. ____ A data field contained within a mouse event object

C. ___ the scheme used for creating custom colors in the AWT

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

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

F. ____ A document layout language for rendering web pages downloaded from the internet

G. ____ The method that is called every time you move the mouse outside of an applet window

H. ____ The data format in which a relational database is stored

I. ____ The standard query language used for most commercial database management systems

J. ____ The method that is called when a printable character is pressed and released on the keyboard

K. ____ the degree to which a module performs one and only one function/task

L. ____ the degree to which a module is "connected" to other modules in the system

M. ____ concealing the details of a module’s implementation from the users of the module

N. ____ Sorting methods found in the Java library for arrays of objects are based on what algorithm

O. ____ a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources that can be rapidly provided and released with minimal management effort or service provider interaction.

P. ____ a sorting method that orders a sequence of elements by using queues as an intermediate data

structure

Q. ____ a type of binary search tree in which for each node the difference in height between its two

subtrees is at most 1

R. ____ a type of binary tree used to store a coding scheme that facilitates file compression

S. ____ the protocol for requesting web pages on the internet

T. ____ a collection of persistent data organized for rapid search and retrieval

U. ____ the SQL statement used to query a database

V. ____ the live description of a database’s data which can allow for intelligent reasoning

W. ____ The type of ordering discipline supported by a queue

X. ____ It specifies only the operations of a data structure and hides implementation details; thus, allowing

developers to switch internal implementations without affecting their clients.

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

problem

1) applet

2) ADT

3) AVL

4) backtracking

5) binary tree

6) binary search tree

7) breadth first search

8) clickCount

9) cloud computing

10) cohesion

11) conformity

12) coupling

13) complete

14) database

15) depth first search

16) Dijkstra’s algorithm

17) digraph

18) event

19) FIFO

20) FICA

21) functional

22) full

23) graph

24) hash table

25) heap

26) HTML

27) http

28) Huffman

29) Infix

30) Information hiding

31) JDBC

32) keyTyped

33) leaf

34) LIFO

35) listener

36) makeHeap

37) map

38) matrix

39) mergesort

40) Meta-data

41) mySQL

42) paint

43) procedure

44) quicksort

45) QL1

46) Radix sort

47) RGB

48) recursion

49) root

50) select

51) set

52) set difference

53) set intersection

54) SQL

55) Tables

56) tree

57) weighted graph

Question 2 - Multiple Choice. [2 pts. each - 18 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 O(n log n) or better?

i) selectionsort

ii) bubblesort

iii) insertionsort

iv) mergesort

v) heapsort

vi) quicksort

vii) radix (bin) sort

B. In the following applet skeleton, the purpose of the addKeyListener(keyDetector) statement is to:

public class KeySpyApplet extends Applet

{ public KeySpyApplet( )

{ KeyboardSpy keyDetector = new KeyboardSpy();

addKeyListener(keyDetector);

}

public void paint (Graphics g)

{ // . . .

}

}

I. create the event handling code for a keyboard event

II. to notify the source applet that a keyboard event has occurred

III. install the registered listener object into the applet

IV. none of the above

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 (i.e., value) in a set may be duplicated

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

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

v. The elements of a set are not ordered

D. What is the value of the postfix expression 5 2 3 4 + * +

i) 20

ii) 24

iii) 25

iv) 33

v) none of the above

E. 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 do something step is executed:

repeat the following for items i from 1 to N for array1

repeat the following for items j from 1 to M for array2

repeat the following for items k from 1 to L for array3

do something

end repeat

end repeat

end repeat

i. O (L+M+N)

ii. O ( N 3 )

iii. O ( L * M * N )

iv. None of the above

F. Some of the fundamental software design concepts that help manage complexity are the use of:

i. abstractions for data, procedure, and control

ii. compartmentalization of data and function into logical sub units called modules

iii. information hiding by creating controlled interfaces and hidden implementation details

iv. functional independence using single-minded functions with high cohesion and low coupling

v. stepwise refinement for the incremental elaboration of detail for all abstractions

G. Which of the following statements are true of heaps?

I. It is a binary tree

II. In terms of its shape, it must be complete

III. It can be either a maximal or a minimal heap

IV. The value of the root has no relationship to the value of any other nodes

V. Is useful for implementing a stack

VI. Is the most efficient representation for a priority queue

H. The top-level containers of a Swing GUI are:

I. JFrame

II. JPanel

III. JPane

IV. JDialog

V. JApplet

VI. JButton

I. Types of event listeners in Swing are:

I. ActionListener

II. WindowListener

III. MouseListener

IV. MouseMotionListener

V. WifeListener

Question 3. Tree questions (10 pts)

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

Btnode root, a, b, c, d;

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

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

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

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

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

B. (3pts) Fill in the statements in the method below to perform an inorder traversal of a binary tree like the above.

public static void inorder( Btnode tree )

{

}

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 64 is inserted into this tree, which node becomes its parent? __________________

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

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

(d) If we delete node 25, 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? ______________________

Question 4. Heaps and Graphs (16 pts)

A. (3 pts) A heap can be represented by an ArrayList with the values stored in top down, level-by-level, left to right order. 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 ArrayList values for this heap are

{50, 35, 15, 12, 3, 5}.

[pic]

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

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

B.(3 pts) Start with following tree and use the heapify algorithm to convert it into a maximum heap. Draw the resulting tree.

[pic]

C. (2 pts) Show the minimum cost path from node A to node E in the following digraph G.

[pic]

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

[pic]

E (5 pts) Draw the minimal spanning tree for the following graph G.

Question 5. Hash Tables (8 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: 20, 11, 2, 5, 7, 40, 121, 19, 23, 33, 71, 90, 39, 70 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 | |

Question 6. Sets. [5 Points] For the following program, show the output order of the printed words

import java.util.*;

public class SetExample2

{ public static void main(String[ ] args)

{

String[ ] words = { "ask", "not", "what", "your", "country", "can", “do”, “for”, “you”, “;”,

"but", "what", "you", "can", "do", "for", “your”, “country” };

Set mySet = new TreeSet( );

for (String word : words) { mySet.add(word); }

for (String word : mySet)

{

System.out.print(word + " ");

}

System.out.println();

}

}

Question 7. Maps [10 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 showing 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 character at a time

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

while ( )

{

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

}

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

}

}

Question 8. [8 points]. Evaluate the performance of your team on Assignment 4 (Word Ladders)

Rating scheme: Please give your own evaluation of your team’s overall performance by marking one and only one of:

A (we did a very excellent job)

B (we did a satisfactory job)

C (we managed somehow to finish the job)

D (we had no idea and probably we did not do well)

E (we did not finish this step)

in the following table

Substitute I for we in the above scheme for rating question 4. Substitute they for we in the above scheme for rating question 5.

| |Area |Self Assessment |

|1 |Identifying project goals and requirements |A B C D E |

|2 |Identifying what to do in order to achieve the goals |A B C D E |

|3 |Working together as a team |A B C D E |

|4 |My contributions to the overall team effort |A B C D E |

|5 |My teammates’ contributions to the overall team effort |A B C D E |

| | | |

| |Overall assessment |A B C D E |

Comments. If you give a D or E on any item above give the reason briefly.

Metrics: Provide the following data (approximations are fine) for assignment 4:

1. How many hours did YOU (individually) work on assignment 4? _________

2. Approximately what % of the overall effort did you contribute? __________

3. How big (# total LOC) was your team’s program? ________

4. How many logic errors did your team encounter? _________

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

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

Google Online Preview   Download