Final Exam

1.�	What is a numbering system?
2.�	What is the binary numbering system?
3.�	What is the purpose of an abstract data type?
4.�	What is a variable?
5.�	What is the integer abstract data type group?
6.�	What does the term “floating-point” mean?
7.�	What is a character?
8.�	What is the difference between single and double precision?
9.�	What is an instance of a structure?
10.�	What kind of data type is a structure?
11.�	How do you reference an element of an instance of a structure?
12.�	What are three major elements of every class definition?
13.�	What is the difference between a class definition and a structure definition?
14.�	What is the hexadecimal numbering system?
15.�	How do you assign an address to a pointer?
16.�	What value is stored in a pointer variable?
17.�	Why do you use pointer arithmetic?
18.�	What is a pointer-to-pointer variable?
19.�	What is an array of elements?
20.�	What is an index?
21.�	What is an array of pointers?
22.�	What is a multidimensional array?
23.�	What is the purpose of using a multidimensional array?
24.�	What is the relationship between a pointer and an array?
25.�	What is the relationship between a stack and an array?
26.�	What is the action called that places data on a stack?
27.�	What is the action called that removes data from a stack?
28.�	Using an array, how do you determine whether the stack is empty?
29.�	Using an array, how do you determine whether the stack is full?
30.�	What is a queue?
31.�	Where is data organized in a queue stored?
32.�	What does the term “circular queue” mean?
33.�	What is the modulus operator used for with respect to circular queues?
34.�	When would you implement a queue using a linked list instead of an array?
35.�	What is the action called that places data on a queue?
36.�	What is the action called that removes data from a queue?
37.�	What is a linked list?
38.�	What is an entry in a linked list called?
39.�	How are nodes linked together in a linked list?
40.�	What is a doubly linked list?
41.�	What is the purpose of a doubly linked list?
42.�	What is used to define a node of a linked list?
43.�	How do you delete an element from the middle of a linked list?
44.�	How do you delete a node from the front of a linked list?
45.�	How do you append a node onto a linked list?
46.�	How do you put a new node onto the front of the linked list?
47.�	What condition tells you the linked list is currently empty?
48.�	What condition tells you there’s only one node on the linked list?
49.�	What is the size limitation on a linked list?
50.�	What is the destructor typically used for in a linked list?
51.�	What is a hashtable?
52.�	What is the key used for in a hashtable?
53.�	What is hashing?
54.�	What is the result of hashing?
55.�	What is the significance of a hash value?
56.�	What major problem occurs with hashing?
57.�	How do you overcome the major problem that occurs with hashing?
58.�	Ideally, how should a hash function behave with respect to the values it generates? If you feed in a list of keys, what would you expect for the output?
59.�	Many different hashing algorithms have been developed to provide a more even distribution of hash values. What is the essence of the hashing algorithm—in other words, what do these functions typically have in common?
60.�	With a hashtable, suppose your dataset gets unexpectedly large and you have an excessive number of collisions. How could you deal with this?
61.�	How do you insert a node into a hashtable?
62.�	How do you delete a node from a hashtable?
63.�	How do you look up a value in a hashtable?
64.�	How do you list out all the values in a hashtable?
65.�	How would you check if a hashtable is empty?
66.�	What is a binary tree?
67.�	What is the purpose of a branch node in a binary tree?
68.�	What is the starting node of a binary tree called?
69.�	What is the node in a binary tree called that spawns another node?
70.�	What are nodes at the end of a binary tree called?
71.�	If you have 1,000 nodes in a balanced binary tree, approximately how many comparisons do you need to do to find a particular node?
72.�	How is the maximum depth of a tree defined?
73.�	If a binary tree is well balanced, approximately how many nodes are in the tree given the depth of the tree?
74.�	What condition do you check for to see if a node in a binary tree is a leaf node?
75.�	How do you delete a node from a binary tree that has two child nodes?
76.�	How do you delete a node from the binary tree that has one child node?
77.�	How do you delete a leaf node from a binary tree?
78.�	What is the basic rule for where the nodes get placed into a binary tree?
79.�	How do you insert a node into a binary tree?
80.�	How would you check if a binary tree is empty?
81.�	What is a recursive function?
82.�	When searching for a key in a binary tree, what stops the recursive function calls?
83.�	What is the sequence of function calls to do an “in order” traversal of a binary tree?
84.�	What is a pointer?
85.�	What is memory allocation?
86.�	What does the new operator return?
87.�	Does Java use pointers?
88.�	How do you declare an array of pointers?
89.�	How do you declare an array of pointers to pointers?
90.�	If an int pointer is incremented using pointer arithmetic, how many bytes is the pointer incremented?
91.�	How is a binary tree’s depth defined?
92.�	What is a balanced binary tree?
93.�	Must all binary trees be balanced?
94.�	What is the purpose of a key in a binary tree?
95.�	What is metadata?
96.�	What is the purpose of the this operator?
97.�	What does a private access specifier do?
98.�	If next and previous are pointers to the next and previous nodes, then what does this statement do? ��node->next->previous = NULL;
99.�	What is fifo?
100.�	What is the purpose of a public access specifier?

Answers

1.�	A numbering system is a way to count things and perform arithmetic.
2.�	The binary numbering system is a number system that uses two digits to count things and perform arithmetic.
3.�	The purpose of an abstract data type is to specify the amount of memory needed to store data and the kind of data that will be stored in that memory location.
4.�	A variable is a reference to the memory location that you reserved using the declaration statement.
5.�	The integer abstract data type group consists of four abstract data types used to reserve memory to store whole numbers.
6.�	The term “floating-point” refers to the way in which decimals are referenced in memory. There are two parts of a floating-point number. The first part is the real number, which is stored as a whole number. The second part is reference to the position of the decimal point within the whole number.
7.�	A character is represented as an integer value that corresponds to a character set. A character set assigns an integer value to each character, punctuation, and symbol used in a language.
8.�	Single precision refers to the accuracy of the first 7 numbers to the right of the decimal point. Double precision refers to the accuracy of the first 15 numbers to the right of the decimal point.
9.�	A structure definition is like a cookie cutter in that it describes the shape of something. A cookie cutter describes the shape of a cookie. A structure definition describes the size and data type of a group of primitive data types. You use a cookie cutter to make cookies. You use a structure to declare an instance of the structure in memory.
10.�	A structure is a user-defined data type.
11.�	An element of an instance of a structure is referenced by using the dot operator, such as myStudent.grade.
12.�	Keyword class, class name, and class body.
13.�	A class definition defines both data and methods/functions. A structure definition defines only data.
14.�	The hexadecimal numbering system consists of 16 digits that are represented as 0 through 9 and A through F.
15.�	An address of a variable is assigned to a pointer variable by using the address operator (&).
16.�	A pointer variable stores the address of another memory location.
17.�	Pointers are used to step through memory sequentially by using pointer arithmetic and the incremental (++) or decremental (- -) operator. The incremental operator increases the value of a variable by 1 and the decremental operator decreases the value of a variable by 1.
18.�	A pointer to a pointer is also a variable that contains a memory address except a pointer to a pointer contains the memory address of another pointer variable.
19.�	An array element is similar to one variable except it is identified by the name of the array and an index value.
20.�	An index value is a number used to identify an array element.
21.�	An array of pointers is nearly identical to a pointer variable except each array element contains a memory address.
22.�	A multidimensional array consists of two or more arrays defined by sets of array elements. Each set of array elements is an array.
23.�	A multidimensional array is useful in some situations to organize subgroups of data within an array.
24.�	There is a close-knit relationship between a pointer and an array. The array name is like a pointer variable in that the array name by itself references the address of first element of the array.
25.�	A stack and an array are two different things. An array stores values in memory. A stack tracks which of the array elements is at the top of the stack.
26.�	Push is the action that places data on a stack.
27.�	Pop is the action that removes data from a stack.
28.�	The value of the top index is –1.
29.�	The value of the top index is equal to the number of elements in the array minus 1.
30.�	A queue is a sequential organization of data. A queue is like the checkout line at the supermarket where the first customer is at the front of the line and the second customer is next in line, and so on, until you reach the last customer who is at the back of the line.
31.�	Data organized in a queue is stored in an array or a linked list.
32.�	A circular queue is a queue implemented using an array. When the elements at the end of the array are used up, you start over at the beginning so the queue chases itself around in a circle.
33.�	The modulus operator can be used to make a linear pattern into a circular pattern. When the last element is used up, the modulus operator will take you back to the first element.
34.�	When you don’t know the number of nodes ahead of time. The linked list implementation is only limited by the amount of memory on the machine.
35.�	Enqueue is the action that places data on a queue.
36.�	Dequeue is the action called that removes data from a queue.
37.�	A linked list is a data structure that makes it easy to rearrange data without having to move data in memory.
38.�	An entry in a linked list is called a node.
39.�	Each member of a node points to the next node in the linked list.
40.�	A doubly linked list is a linked list where each member of a node points to the previous node and to the next node in the linked list.
41.�	A doubly linked list is used to enable a program to move up and down the linked list.
42.�	A structure definition is used to define a node of a linked list.
43.�	Declare a temporary pointer to the node being deleted. Change the next pointer in the previous node to the value of the next pointer in the node being deleted. Change the previous pointer in the next node to the value of the previous pointer in the node being deleted. Delete the node.
44.�	Declare a temporary pointer to the front node. Change the value of the front pointer to the next pointer in the node being deleted. Change the value of the previous pointer in the next node to NULL. Use the temporary pointer to delete the node.
45.�	Use the back pointer to get a reference to the last node on the linked list. Change the value of the next pointer in the back node to the address of the new node. Set the previous pointer of the new node to the current back node. Change the back pointer to the address of the new node.
46.�	Use the front pointer to get a reference to the first node on the linked list. Change the value of the previous pointer in the front node to the address of the new node. Set the next pointer of the new node to the current front node. Change the front pointer to the address of the new node.
47.�	The front and back pointers are both NULL. You only need to check one of them.
48.�	The front and back pointers both point to the same node.
49.�	The size is limited by the amount of memory on the machine.
50.�	The destructor typically releases all the memory that was allocated for the linked list.
51.�	A hashtable is a common data structure used to store objects that have a key value relationship.
52.�	A key is translated into a number that is used as the array index of the array element that references the value that is associated with the key.
53.�	Hashing is the process of translating the key into the array index of the array element that references the value that is associated with the key.
54.�	Hashing produces a hash value.
55.�	There is no real significance of a hash value other than it is a number used as an array index.
56.�	Hashing is not perfect. Occasionally, a collision occurs when two different keys hash into the same hash value and therefore are assigned to the same array element.
57.�	A common way to deal with a collision is to create a linked list of entries that have the same hash value.
58.�	In the most ideal case, the hash function should produce an even distribution of values for a given set of keys. The result is a minimum number of collisions.
59.�	Hashing typically uses bit shifting to pseudo-randomize the generated values. How could you deal with this?
60.�	You could make the hashtable array larger, then rehash all the keys and insert them accordingly into the new hashtable.
61.�	Call the hashing algorithm with the key. Go to the array and see if the value in the array index is NULL. If it is, then change this value to the address of the new node. If the array index is not NULL, then set the next pointer in the new node to the value at the array index and set the array index to the address of the new node. This makes the new node the first entry in the linked list.
62.�	Call the hashing algorithm with the key. Go to that index in the array. Traverse the linked list and find the value, and then delete this entry from the linked list. The entry is deleted by setting the next pointer in the previous node to the next pointer of the node being deleted.
63.�	Call the hashing algorithm with the key. Go to that array index and traverse the linked list until you find that key. Return the associated value.
64.�	Iterate the array. At each index, if it contains a value other than NULL, iterate the linked list and list out the values.
65.�	Iterate the hashtable array and see if all the values are NULL. If all the values are NULL, the hashtable is empty.
66.�	A binary tree is a tree where each stem has not more than two branches Typically the stem has two branches, but there can be situations when the stem has one branch or simply terminates resulting in no additional branches.
67.�	The branch node is the fork in the road that links the root node to two branches.
68.�	The starting node is called the root node, which is the top-level node in the tree.
69.�	A parent node spawns another node in a binary tree.
70.�	Nodes at the end of a binary tree are called leaf nodes.
71.�	Ten. 2^10 ~= 1000.
72.�	The depth is the number of hops to get to the “lowest” node in the tree.
73.�	2^n – 1 where n is the depth of the tree.
74.�	Both the child node pointers are set to NULL.
75.�	Replace the node being deleted with the leftmost child of the right subtree. You could also replace it with the rightmost child of the left subtree.
76.�	Change the value of the pointer in the parent node to the value of the child node, and then delete the node.
77.�	Change the value of the pointer in the parent node to NULL, and then delete the node.
78.�	All the nodes to the right have a key greater than the current node and all the nodes to the left have a key less than the current node. This rule applies to each and every node of the tree.
79.�	Start at the root of the tree. If the key is greater than this node, move to the right. If the key is less than this node, move to the left. Continue until a NULL pointer is found, and then change the value of this pointer to the address of the new node.
80.�	The tree is empty if the root node of the tree is NULL.
81.�	A recursive function is a function that calls itself.
82.�	One of two conditions—either the key is found or a NULL pointer is found.
83.�	For each node, look to the left, process the node, and then look to the right.
84.�	A pointer is a variable whose value is an address of a location in memory.
85.�	Memory allocation is the task of reserving memory in order to store data in memory.
86.�	The new operator returns an address of memory.
87.�	It is a misnomer that Java doesn’t use pointers. Java does use pointers, but a programmer doesn’t explicitly declare pointers. You can declare an array whose data type is a Java Object—an array of pointers. The value of each array element is an Object. When you switch those values to other array elements, you are moving memory addresses and not the Object itself.
88.�	An array of pointers is declared by preceding the array name with an asterisk.
89.�	An array of pointers to pointers is declared by preceding the array name with two asterisks.
90.�	An int pointer is incremented by the number of bytes of an int.
91.�	The number of nodes on the tree defines a binary tree’s depth.
92.�	A balanced binary tree is where each node except for a leaf node has two children nodes.
93.�	No.
94.�	The key and the search criteria are compared to each other.
95.�	“Metadata” is the term that refers to data that describes other data such as how an employee ID can be used to get the employee’s name.
96.�	The this operator tells the compiler that you want to refer to the data element of this instance of the structure instead of the parameter that was passed in.
97.�	Members defined within the private access specifier area of the class definition can only be accessed by member functions of the class.
98.�	This statement assigns the NULL value to the next node’s previous pointer.
99.�	First in, first out.
100.�	Members defined within the public access specifier area of a class definition can be accessed by member functions of the class and from outside the class.