ANSWER MUST BE TYPED WITHIN THE QUESTIONS BELOW
Linked Lists
1. (a) Declare a class named User that contains the following information: (6 pts.)
String name
String username
String password
Include in the class a single constructor that is passed a particular name, username, and
password; setters and getters, and a toString method that returns the information in
a given User object as follows:
"Ashley Smith username: asmith password: aWjPP406!"
(b) Declare a class named UserNode that contains a single User object and a link to another
UserNode. Include an appropriate constructor and an appropriate set of methods for this
class. (4 pts).
2. Create a class named UserAccounts that maintains a list of users (implemented as a linked list
of UserNodes), with an appropriate constructor, and the following methods: (15 pts.)
isEmpty() – returns true if list is empty, and false otherwise
findPassword – returns the password for a given user name
changePassword – updates the password for a given user name and password. If they do
not match, the password is not updated.
addUser – passed a User object to add
deleteUser – deletes a user for a given user name and password. If they do not match,
the user is not deleted.
printUsers – prints a list of all users (including name, username and password)
Recursion
3. Determine what the following function calls return for recursive function func below.
(4 pts.)
public static int func(int n)
{
if(n == 1)
return n;
else
return 1 + func(n-1);
(a) func(1) = _________
(b) func(4) = _________
4. Does func above perform top down or bottom up computation? _________________ (2 pts.)
5. Determine the general result (in terms of n) of the following recursive function (4 pts.)
public static void func2(int n)
{
if(n == 1)
System.out.println(“*”);
else
{
for (int i = 1; i <= n; i++)
System.out.print(“*”);
System.out.println();
func2(n-1);
}
}
6. Does func2 above perform down or bottom up computation? ___________________ (2 pts.)
Searching and Sorting (Chapter XXXXXXXXXXpts.)
7. Regarding the behavior of algorithms (i.e., rate of growth, big-Oh analysis) (6 pts.)
(a) The rate of growth of a given algorithm can be determined either analytically
(by inspection of the algorithm and use of mathematics), or empirically (by
implementing it and executing on various size input). TRUE / FALSE
(b) To determine which of two algorithms that solve the same problem has the slowest rate
of growth (i.e., that is generally more efficient), it is sufficient to implement and execute
each on a sufficiently large problem and compare the run times. TRUE / FALSE
(c) For most algorithms, solving a problem that is twice as big takes more than
double the amount of time. TRUE / FALSE
8. For the following rates of growth, answer the following (selecting from the rates of growth
to the right): (12 pts.)
(a) Fastest can sort (for general sorting) ______ O(2n)
(b) Fastest can search a sorted list ______ O(n3)
(c) Fastest can search an unsorted list ______ O(n2 logn)
(d) Intractable rate of growth ______ O(n2)
(e) Average rate of growth of Bu
leSort ______ O(nlogn)
(f) Constant time regardless of problem size ______ O(n)
O(logn)
O(1)
9. Give the resulting lists after the first TWO passes of Selection Sort, Insertion Sort, Bu
leSort,
and QuickSort under the headings below. For QuickSort, assume that the FIRST ITEM in each
sublist is always chosen as the pivot value (which is not a problem when lists are randomly
ordered). (12 pts.)
Selection Sort Insertion Sort Bu
leSort QuickSort
20
31
6
19
28
4
9
36
Stacks and Queues
10. Answer the following related to stacks and queues.
(a) What are the basic operations of a queue? (2 pts.)
(b) Complete the following Stack class. (12 pts.)
public class Stack {
private int[] elements;
private int top;
public Stack(){
XXXXXXXXXXelements = new int[10];
XXXXXXXXXXtop = -1;
}
public boolean isEmpty(){
XXXXXXXXXXreturn ________________;
}
public boolean isFull(){
XXXXXXXXXX________________;
}
public void push(int item){
XXXXXXXXXXif (____________)
XXXXXXXXXXSystem.out.println("* STACK FULL- CANNOT PUSH *");
XXXXXXXXXXelse{
XXXXXXXXXX________________;
elements[top] = item;
}
}
public int pop(){
XXXXXXXXXXif (top == -1)
XXXXXXXXXXSystem.out.println("* STACK EMPTY - CANNOT POP *");
XXXXXXXXXXelse{
XXXXXXXXXXString top_item = elements[top];
XXXXXXXXXX________________;
XXXXXXXXXXreturn top_item;
}
}
}
Application of Stacks
11. Show the series of stack values for evaluating the postfix expression of XXXXXXXXXX * 4) below, (6 pts.)
XXXXXXXXXX * +
Binary Trees
12. Give the preorder, inorder, and postorder traversals of the following binary tree. (9 pts.)
A
B
E
C
D
F
PREORDER:
INORDER:
POSTORDER:
3. Create a binary search tree for the values given below, in which the value 21 is the root
of the tree, and that the tree overall is balanced (i.e., approximately the same number of
nodes in the left and right subtrees of every node in the tree). (8 pts.)
10, 16, 24, 9, 2, 27, 31, 45, 5, 38, 42, 37, 21, 7, 4