Final Exam - University of Texas at Austin



Exam 3

EE 322C - University of Texas at Austin - Fall ,2006

Name ____________________________________

Test taking instructions. No calculators, laptops or other assisting devices are allowed. Write your answers on these sheets. If you need scratch paper then use the backside of the page preceding the question. 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 template 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 */

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

private T element;

private Btnode left;

private Btnode right;

/* constructors: with (a) no parameters, or (b) an Object, left child, and right child. */

public Btnode( )

{ this( null, null, null );

}

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

{ element = theElement;

left = lt;

right = rt;

}

/* get and set methods */

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;}

}

1. Terminology. [22 pts.] Answer each of the following questions; choose the best answer from below.

A. ____An unordered collection of distinct elements (or values) chosen from the possible values of a base data type

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

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

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

E. ____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.

F. ____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.

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

H. ____A two-dimensional structure that corresponds to a row-column table of entries of a specified data type.

I. ____A binary tree in which all of the leaves are on the same level and every nonleaf node has exactly two children

J. ____A binary tree that is either full or full through the next-to-last level, with the leaves on the last level as far to the left as possible

K. ____A complete binary tree in which each node has a value stored in it that is greater than or equal to the value in each of its children.

L. ____Nodes in a binary tree that have only NULL children

M. ____A node in a binary tree that does not have a parent

N. ____A data structure that consists of a set of nodes and a set of edges that relate the nodes to each other

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

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

Q. ____A graph in which each edge carries a value

R. ____A sequential structure that is divided into b buckets, each bucket with s slots. Each slot holds one element. The address of an identifier X in the structure is gotten by computing some arithmetic function

S. ____This occurs when 2 different identifiers are hashed into the same bucket #

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

U. ____ A graph traversal method that visits the nodes from a starting vertex “level by level”

V. ____ An assertion based test generator tool for software testing

a) 2-3-4 tree

b) alloy

c) Array

d) AVL tree

e) Binary tree

f) Binary search tree

g) Black box testing

h) Breadth First Search

i) Collision

j) Complete

k) Depth First Search

l) Dijkstra’s algorithm

m) Digraph

n) Device miniaturization

o) Full

p) Hash table

q) Heap

r) Graph

s) korat

t) Leaf

u) Map

v) Matrix

w) Overflow

x) Partially filled array

y) Prim’s algorithm

z) Root

aa) Set

ab) Set difference

ac) Set intersection

ad) Tree

ae) Weighted graph

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

A. The linear probe method for hash tables suffers from the phenomenon known as

i. fatal collisions

ii. sparse distribution

iii. clustering

iv. broken chains

v. none of the above

B. What is a good reason for not using one of the Java collections classes in a program.

i) It might be too slow or memory consuming.

ii) Its too simple

iii) The operations are not well documented

iv) None of the above

C. Which tree below corresponds to the vector v?

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

Vector v = new Vector (arr);

[pic]

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

E. Which of the following 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

F. Hashing is an ______ search algorithm.

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

G. Which of the following are principles of agile software development?

i. Satisfy the customer through early and continuous delivery of valuable software

ii. Welcome changing requirements, even late in development. Harness change for the customer’s competitive advantage.

iii. Deliver working software frequently - from a couple of weeks to a couple of months - prefer shorter timescale

iv. Customers and developers work together daily throughout the project

v. By following the waterfall model of development, quality software is always produced

H. Which of the following represent current challenges in the field of mobile ubiquitous computing

i. Transient connectivity to resources

ii. Rapid change due to user and environment dynamics

iii. Lack of guaranteed connectivity to fixed infrastructure

iv. Managing large data sets in a distributed fashion

v. The speed and capacity of modern computer chips

3. Tree questions (20 pts)

A.(7 pts) For each subpart (a) – (g), use the following tree.

[pic]

(a) What is the parent of node 5? ___________________

(b) What is the depth of this tree? ____________________

(c) List the nodes in subtree 12. ___________________________

(d) List all of the non leaf nodes. ______________________________

(e) Give the order that the nodes are visited in a preorder traversal of the tree.

____________________________________________________________

(f) Give the order that the nodes are visited in an inorder traversal of the tree.

____________________________________________________________

(g) List all of the nodes at level 3 in the tree. _______________________________

B. (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, b, a);

C. (3 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 + (int)flag;

}

return ct;

}

D. (3 pts) Use the following tree traversal function. Assuming m is initially 0, what is the resultant value of m when calling this method as f ( Btnode root, m) where root is the base of the tree in Question 3A? _____________________________

public static void f(Btnode t, int n)

{ if (t != NULL)

{ n++;

f(t.getLeft(), n);

f(t.getRight(), n);

}

}

E. (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? ______________________

4. Heaps and Graphs (19 pts)

A. (3 pts) A heap can be represented by a vector. Start with the following 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) Erase 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 create a minimum heap. Draw the resulting tree.

[pic]

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

[pic]

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

[pic]

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

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 % someInt (where someInt 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, 7, 10, 21, 121, 23, 33, 71, 90 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 | |

6. Bitsets (8 pts.) A given bitset is established to hold possible data items that are integer values in the range from 0 to 99 inclusive. Using the declarations given below, write the rest of the code needed to insert the values from array arr into the bitset s, and then output all those values that are NOT members of s.

import java.util.*;

public class demo

{ public static void main(String[ ] s)

{ BitSet s = new BitSet(100);

int arr [6] = {22, 45, 10, 97, 3, 36};

}

}

7. Maps (7 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. After all characters in the file are processed, output a table to the screen that contains 2 columns with the character and its total number of occurrences. Note: all legal characters are counted.

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);

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

while ( )

{

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

}

}

}

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

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

Google Online Preview   Download