Explanation of some questions on the final exam.


Object Oriented
---------------
#3
Look at what the function is returning. A boolean true or false.
Return type must be some sort of boolean or integral type to hole a 0 or 1.


Linked Lists
------------
#5
The addNode function must return a new head node.
Create a local Node, point it to the old head node, then return it.

Binary Search Trees
-------------------
#1
Show the numbers in some ascending or descending order.

#2
Choose the middle value first, then basically all mixed up from there.
If you start with 1 or 9, the tree will be pretty out-of-balance.

#3
Most forgot that levels is one more than height.
Traversals were ok, but some were not good.


Hash Tables
-----------
#1 n/size
#2 it tells you if re-size is necessary
#3 to turn some kind of data into an array index
#4
Actually write a C++ function here.
Some students wrote math formula and not C++ code.
int hash(int x, int size) {
	return (2 * x + 5) % size;
}

#5
About half of students did ok on this.

Stacks and queues
-----------------
#1
One solution is to ignore the pop and continue the program.
One solution is to throw an exception and end the program.
You will not stop and ask the user for help with a push or pop.
You should not display a message, unless you are ending the program,
then you could show a stack error.

In real programs, there is no need to check a stack for empty or full,
but a program might set a flag at startup that does not allow a pop
before a push is done.

The x86 assembly language push and pop do no error checking, and
many of the most important programs such as MS Windows run on x86.



Big O Analysis
--------------
#1 nested loops each iterating n times. n times n. O(n^2) -or- O(n*n)

#2 We did not study this. Wanted to see if you did reading on your own.
   n/2 + log n + 10n
   The dominant terms is n/2 and 10n
   log n is smaller so throw it out
   As n goes to infinity, n/2 is same as n
   As n goes to infinity, 10n is same as n
   This gives n + n
   Same as 2n
   As n goes to infinity, 2n is same as n
   O(n)


General
-------
#1
Write one boolean expression
  (x < 4 && x >= 24)
  (x < 4 && !(x < 24))

Most students want to write: (x < 4 && x > 24)

#2
    a. The pointer ptr (argument) is treated as a local variable
    b. Change the argument list to show (int *&ptr, int size)
       You could also return the allocated pointer value, but that
       would change how the function is called.

#3
Most students read outside the array bounds here.
Your for-loop should start i at 3 and increment to n-1, as you
copy arr[i] = arr[i+1]
There is now one less element in the array, so update n to n-1;

#4
The range of values from -5 to 5 is 11.
Mod by the range and add the starting value.

#5
It looked like some students put this code into a program.
That's ok, but then most could not explain what is happening in this line:
   a[6] = a[strlen(a)];
It is grabbing the null-terminator of the original string, and copying it
to a[6];
One student explained it correctly.
Most students said the string length was being placed into a[6].




Hope that helps.