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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- final exam university of texas at austin
- internet programming with java course
- it301 visual programming 2019 20 sir syed university of
- event handling in java
- more java gui applet and application design
- 1 james madison university
- institute of technology polytechnic navi mumbai
- mouse listeners and mouse details
Related searches
- university of texas at austin
- university of texas austin tx
- university of texas at austin online
- university of texas at dallas graduate school
- university of texas austin graduate
- university of texas at dallas housing
- university of texas at austin online masters
- university of texas austin graduate school
- university of texas austin nursing
- university of texas at austin athletics
- university of texas austin certificate
- university of texas austin tuition cost