mid Flashcards
Which of the following are types of LinkedList?
d.
singly-linked, doubly-linked, multi-linked
An example of logarithmic time complexity is:
a.
Binary search
Consider the following recursive function fun(x, y).
What is the value of fun(4, 3)
int fun(int x, int y){
if (x == 0) return y; return fun(x - 1, x + y);
}
d.
13
Linear data structure that follows a particular order in which the operations are performed
c.
Queue
Look at square numbers: square(1) = 1; square(N) = square(N-1) + 2N -1
Which method below successfully implements this definition?
d.
int square( int N ){
if ( N==1 ) {
return 1;
}
else
{
return square(N-1) + 2*N - 1; }
}
Algorithm times are measured in terms of growth of an algorithm.
False
What does the notation O(n) represent in asymptotic analysis?
b.
The worst-case time complexity of an algorithm
Which of the following is not a typical application of stacks?
c.
Sorting algorithms
What is the time complexity of deleting an element from a singly linked list?
c.
O(n)
What is complexity independent of inputs?
a.
Complexity that doesn’t depend on the number of inputs
Which of the following usees FIFO method?
a.
Queue
For a binary search algorithm to work, it is necessary that the array list must be
a.
sorted
When the function with loops or recursive calls can have constant complexity?
b.
Number of iterations or calls independent of input size
What is the limitation of calling recursion?
limit of the heap memory
Specify ArrayList advantages over LinkedList
c.
arrayList is better for storing and accessing the data
What will Repeat(82, 3) return from the following method declaration?
public static int Repeat(int i, int j){
if (i==0)
return 0;
else
return Repeat(i/j, j)+1;
}
b.
6
Algorithm speed is measured in seconds.
False
Can a program have loops or recursive calls and still have time complexity that is constant?
c.
Yes, as long as the loops or recursive calls have a constant number of iterations or calls
Which operation returns the front element from the queue without removing it?
b.
peek()
What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
X will always be a better choice for large inputs
Which one of the below mentioned is linear data structure
a.
All of the above
b.
Queue
c.
Arrays
d.
Stack
Queue operation .Pop:
d.
remove from the front
Recursion is implemented by the queue, and each time you invoke a method, the method is placed on top of the queue.
False
What is the main difference between a stack and a queue?
a.
A stack is a LIFO data structure, a queue is a FIFO data structure.
How does the call stack work in relation to recursive functions?
d.
It keeps track of the function calls made
What is the time complexity of popping an element from a stack?
d.
O(1)
Which of the following is not a typical application of queues?
d.
Depth-first search algorithm
Which of the following factors does not affect the time complexity of an algorithm?
c.
The speed of the computer executing the algorithm
Linearithmic complexity’s Big-O notation is:
c.
O(nlogn)
The run time of algorithms is expressed in Big O notation.
False