Computer Science : Standard Operations & Algorithms
Study concepts, example questions & explanations for Computer Science
All Computer Science Resources
Example Questions
Example Question #1 : Searching
True or False.
Sequential search is more efficient than Binary Search.
True
False
False
Sequential search has a running time of O(N). Binary search has a running time of O(log(N)). Because sequential search has to go through each element in a list at least once it's less efficient.
Example Question #2 : Searching
What is the difference between inorder traversal of a binary search tree and a preorder traversal?
They are similar.
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
Preorder searches through the tree from lowest to highest, inorder does not.
In order traversal processes the right subtree, then the root node, then the left subtree, whereas preorder processes the left subtree, then the root node, the the right subtree.
The only difference is that in order processes the root node, whereas preorder does not.
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
In this case, the names help to identify the different types of traversals. In order traversal processes the binary tree "in order", meaning it will go through the left subtree, process the node, then go on to the right. Why is this in order? Because remember, a binary sort tree lists any value less than the node to the left, and any value greater to the right, so in order traversal will actually go from greatest to smallest.
Preorder traversal is the same except that it processes the root node first, hence the "pre" order.
Example Question #31 : Computer Science
public static int foo(int[] arr, int x) {
int a = 0;
int b = arr.length - 1;
while(b >= a) {
int c = (a + b) / 2;
int v = arr[c];
if(v == x) {
return c;
} else if(v < x) {
a = c + 1;
} else {
b = c - 1;
}
}
return -1;
}
What is the value of y in the code below:
int[] vals = {1,3,4,5,6,31,41,51};
int x = 41;
int y = foo(vals,41);
-1
6
5
41
7
6
The first thing to notice in the code for the method foo is that it implements the algorithm for a binary search. The value c functions as the midpoint for the algorithm. This requires that the list be in order. The values a and b are used to control the loop so as to let you search the correct portions of the list. If the value in the middle of the list is not equal to what you are looking for (i.e. x), then it looks either "above" or "below" in the list (since it is presumed to be in order). This is what is happening when either a or b is changed.
So, this searches for the value and returns the index number for that value if it is found. Otherwise, it returns -1. Since the value 41 is in the array, it returns 6.
If you do not recognize this algorithm, you are likely to have some problems—and will have to trace the code!!
Example Question #31 : Computer Science
Which of the following is true for a binary search algorithm?
The array must be converted into a binary search tree before searching for the value.
The array can be unsorted but will run slower than if it is sorted.
The array must be probed in order from its beginning to its end.
The array needs extra space in order to accomodate swap operations that are part of the search.
The array being searched must be sorted before searching.
The array being searched must be sorted before searching.
The binary search presumes that the array being searched is already sorted. This is because of how it probes the values in the array. It begins at the center of the array to see if the values match. If the value is smaller than this center element, it then presumes that the value is in the lower half of the array. Otherwise, it presumes that the value must be larger and hence in the upper half of the array. It then probes the center of whichever half it has chosen, continuing to do this until the value has certainly not been found.
Example Question #2 : Searching
What is the difference between inorder traversal of a binary search tree and a preorder traversal?
They are similar.
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
Preorder searches through the tree from lowest to highest, inorder does not.
In order traversal processes the right subtree, then the root node, then the left subtree, whereas preorder processes the left subtree, then the root node, the the right subtree.
The only difference is that in order processes the root node, whereas preorder does not.
In order traversal processes the left subtree, then the root node, then the right subtree, whereas preorder processes the root node, left subtree, then right subtree.
In this case, the names help to identify the different types of traversals. In order traversal processes the binary tree "in order", meaning it will go through the left subtree, process the node, then go on to the right. Why is this in order? Because remember, a binary sort tree lists any value less than the node to the left, and any value greater to the right, so in order traversal will actually go from greatest to smallest.
Preorder traversal is the same except that it processes the root node first, hence the "pre" order.
Example Question #31 : Computer Science
public static int foo(int[] arr, int x) {
int a = 0;
int b = arr.length - 1;
while(b >= a) {
int c = (a + b) / 2;
int v = arr[c];
if(v == x) {
return c;
} else if(v < x) {
a = c + 1;
} else {
b = c - 1;
}
}
return -1;
}
What is the value of y in the code below:
int[] vals = {1,3,4,5,6,31,41,51};
int x = 41;
int y = foo(vals,41);
-1
6
5
41
7
6
The first thing to notice in the code for the method foo is that it implements the algorithm for a binary search. The value c functions as the midpoint for the algorithm. This requires that the list be in order. The values a and b are used to control the loop so as to let you search the correct portions of the list. If the value in the middle of the list is not equal to what you are looking for (i.e. x), then it looks either "above" or "below" in the list (since it is presumed to be in order). This is what is happening when either a or b is changed.
So, this searches for the value and returns the index number for that value if it is found. Otherwise, it returns -1. Since the value 41 is in the array, it returns 6.
If you do not recognize this algorithm, you are likely to have some problems—and will have to trace the code!!
Example Question #31 : Computer Science
Which of the following is true for a binary search algorithm?
The array must be converted into a binary search tree before searching for the value.
The array can be unsorted but will run slower than if it is sorted.
The array must be probed in order from its beginning to its end.
The array needs extra space in order to accomodate swap operations that are part of the search.
The array being searched must be sorted before searching.
The array being searched must be sorted before searching.
The binary search presumes that the array being searched is already sorted. This is because of how it probes the values in the array. It begins at the center of the array to see if the values match. If the value is smaller than this center element, it then presumes that the value is in the lower half of the array. Otherwise, it presumes that the value must be larger and hence in the upper half of the array. It then probes the center of whichever half it has chosen, continuing to do this until the value has certainly not been found.
Example Question #31 : Standard Operations & Algorithms
What is the worst-case run-time of selection sort (in Big-O notation?)
Selection sort is comprised of outer and inner for loops that swap elements of the unsorted array into a sorted array. The largest possible number of times each loop can run is the number of elements in the array. Thus, the worst possible run time is 
Example Question #1 : Sorting
True or False.
Selection sort is quicker than MergeSort.
False
True
False
MergeSort is has a running time of O(N). Selection sort has a running time of O(N2). Selection sort has O(N2) comparisons due to the swap in the algorithm.
Example Question #31 : Standard Operations & Algorithms
What is the worst-case run-time of selection sort (in Big-O notation?)
Selection sort is comprised of outer and inner for loops that swap elements of the unsorted array into a sorted array. The largest possible number of times each loop can run is the number of elements in the array. Thus, the worst possible run time is
All Computer Science Resources
