Final Exam


1.  

What is a numbering system?

a numbering system is a way to count things and perform arithmetic.

2.  

What is the binary numbering system?

the binary numbering system is a number system that uses two digits to count things and perform arithmetic.

3.  

What is the purpose of an abstract data type?

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.  

What is a variable?

a variable is a reference to the memory location that you reserved using the declaration statement.

5.  

What is the integer abstract data type group ?

the integer abstract data type group consists of four abstract data types used to reserve memory to store whole numbers.

6.  

What does the term floating-point mean?

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.  

What is a character?

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.  

What is the difference between single and double precision?

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.  

What is an instance of a structure?

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.  

What kind of data type is a structure?

a structure is a user-defined data type.

11.  

How do you reference an element of an instance of a structure?

an element of an instance of a structure is referenced by using the dot operator, such as mystudent.grade .

12.  

What are three major elements of every class definition?

keyword class, class name, and class body.

13.  

What is the difference between a class definition and a structure definition?

a class definition defines both data and methods/functions. a structure definition defines only data.

14.  

What is the hexadecimal numbering system?

the hexadecimal numbering system consists of 16 digits that are represented as 0 through 9 and a through f.

15.  

How do you assign an address to a pointer?

an address of a variable is assigned to a pointer variable by using the address operator (&).

16.  

What value is stored in a pointer variable?

a pointer variable stores the address of another memory location.

17.  

Why do you use pointer arithmetic?

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.  

What is a pointer-to-pointer variable?

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.  

What is an array of elements?

an array element is similar to one variable except it is identified by the name of the array and an index value.

20.  

What is an index?

an index value is a number used to identify an array element.

21.  

What is an array of pointers?

an array of pointers is nearly identical to a pointer variable except each array element contains a memory address.

22.  

What is a multidimensional array?

a multidimensional array consists of two or more arrays defined by sets of array elements. each set of array elements is an array.

23.  

What is the purpose of using a multidimensional array?

a multidimensional array is useful in some situations to organize subgroups of data within an array.

24.  

What is the relationship between a pointer and an array?

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.  

What is the relationship between a stack and an array?

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.  

What is the action called that places data on a stack?

push is the action that places data on a stack.

27.  

What is the action called that removes data from a stack?

pop is the action that removes data from a stack.

28.  

Using an array, how do you determine whether the stack is empty?

the value of the top index is 1.

29.  

Using an array, how do you determine whether the stack is full?

the value of the top index is equal to the number of elements in the array minus 1.

30.  

What is a queue?

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.  

Where is data organized in a queue stored?

data organized in a queue is stored in an array or a linked list.

32.  

What does the term circular queue mean?

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.  

What is the modulus operator used for with respect to circular queues?

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 would you implement a queue using a linked list instead of an array?

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.  

What is the action called that places data on a queue?

enqueue is the action that places data on a queue.

36.  

What is the action called that removes data from a queue?

dequeue is the action called that removes data from a queue.

37.  

What is a linked list?

a linked list is a data structure that makes it easy to rearrange data without having to move data in memory.

38.  

What is an entry in a linked list called?

an entry in a linked list is called a node.

39.  

How are nodes linked together in a linked list?

each member of a node points to the next node in the linked list.

40.  

What is a doubly linked list?

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.  

What is the purpose of a doubly linked list?

a doubly linked list is used to enable a program to move up and down the linked list.

42.  

What is used to define a node of a linked list?

a structure definition is used to define a node of a linked list.

43.  

How do you delete an element from the middle of a linked list?

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.  

How do you delete a node from the front of a linked list?

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.  

How do you append a node onto a linked list?

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.  

How do you put a new node onto the front of the linked list?

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.  

What condition tells you the linked list is currently empty?

the front and back pointers are both null. you only need to check one of them.

48.  

What condition tells you there s only one node on the linked list?

the front and back pointers both point to the same node.

49.  

What is the size limitation on a linked list?

the size is limited by the amount of memory on the machine.

50.  

What is the destructor typically used for in a linked list?

the destructor typically releases all the memory that was allocated for the linked list.

51.  

What is a hashtable?

a hashtable is a common data structure used to store objects that have a key value relationship.

52.  

What is the key used for in a hashtable?

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.  

What is hashing?

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.  

What is the result of hashing?

hashing produces a hash value.

55.  

What is the significance of a hash value?

there is no real significance of a hash value other than it is a number used as an array index.

56.  

What major problem occurs with hashing?

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.  

How do you overcome the major problem that occurs with hashing?

a common way to deal with a collision is to create a linked list of entries that have the same hash value.

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?

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.  

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?

hashing typically uses bit shifting to pseudo-randomize the generated values. how could you deal with this?

60.  

With a hashtable, suppose your dataset gets unexpectedly large and you have an excessive number of collisions. How could you deal with this?

you could make the hashtable array larger, then rehash all the keys and insert them accordingly into the new hashtable.

61.  

How do you insert a node into a hashtable?

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.  

How do you delete a node from a hashtable?

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.  

How do you look up a value in a hashtable?

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.  

How do you list out all the values in a hashtable?

iterate the array. at each index, if it contains a value other than null, iterate the linked list and list out the values.

65.  

How would you check if a hashtable is empty?

iterate the hashtable array and see if all the values are null. if all the values are null, the hashtable is empty.

66.  

What is a binary tree?

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.  

What is the purpose of a branch node in a binary tree?

the branch node is the fork in the road that links the root node to two branches.

68.  

What is the starting node of a binary tree called?

the starting node is called the root node, which is the top-level node in the tree.

69.  

What is the node in a binary tree called that spawns another node?

a parent node spawns another node in a binary tree.

70.  

What are nodes at the end of a binary tree called?

nodes at the end of a binary tree are called leaf nodes.

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?

ten. 2^10 ~= 1000.

72.  

How is the maximum depth of a tree defined?

the depth is the number of hops to get to the lowest node in the tree.

73.  

If a binary tree is well balanced, approximately how many nodes are in the tree given the depth of the tree?

2^n 1 where n is 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?

both the child node pointers are set to null.

75.  

How do you delete a node from a binary tree that has two child nodes?

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.  

How do you delete a node from the binary tree that has one child node?

change the value of the pointer in the parent node to the value of the child node, and then delete the node.

77.  

How do you delete a leaf node from a binary tree?

change the value of the pointer in the parent node to null, and then delete the node.

78.  

What is the basic rule for where the nodes get placed into a binary tree?

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.  

How do you insert a node into a binary tree?

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.  

How would you check if a binary tree is empty?

the tree is empty if the root node of the tree is null.

81.  

What is a recursive function?

a recursive function is a function that calls itself.

82.  

When searching for a key in a binary tree, what stops the recursive function calls?

one of two conditions-either the key is found or a null pointer is found.

83.  

What is the sequence of function calls to do an in order traversal of a binary tree?

for each node, look to the left, process the node, and then look to the right.

84.  

What is a pointer?

a pointer is a variable whose value is an address of a location in memory.

85.  

What is memory allocation?

memory allocation is the task of reserving memory in order to store data in memory.

86.  

What does the new operator return?

the new operator returns an address of memory.

87.  

Does Java use pointers?

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.  

How do you declare an array of pointers?

an array of pointers is declared by preceding the array name with an asterisk.

89.  

How do you declare an array of pointers to pointers?

an array of pointers to pointers is declared by preceding the array name with two asterisks.

90.  

If an int pointer is incremented using pointer arithmetic, how many bytes is the pointer incremented?

an int pointer is incremented by the number of bytes of an int .

91.  

How is a binary tree s depth defined?

the number of nodes on the tree defines a binary tree s depth.

92.  

What is a balanced binary tree?

a balanced binary tree is where each node except for a leaf node has two children nodes.

93.  

Must all binary trees be balanced?

no.

94.  

What is the purpose of a key in a binary tree?

the key and the search criteria are compared to each other.

95.  

What is metadata?

 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.  

What is the purpose of the this operator?

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.  

What does a private access specifier do?

members defined within the private access specifier area of the class definition can only be accessed by member functions of the class.

98.  

If next and previous are pointers to the next and previous nodes, then what does this statement do?

 node->next->previous = NULL; 

this statement assigns the null value to the next node s previous pointer.

99.  

What is fifo?

first in, first out.

100.  

What is the purpose of a public access specifier?

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.

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.




Data Structures Demystified
Data Structures Demystified (Demystified)
ISBN: 0072253592
EAN: 2147483647
Year: 2006
Pages: 90

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net