Font size
Worksheets221 quiz questions exam 2 prep
Total questions: 26
Worksheet time: 14mins
What is the recurrence relation for the code below?
T(n) = T(n-1) + O(1) and T(1)=0
T(n) = T(n-1) + O(n) and T(1)=0
T(n) = 2T(n-1) + O(1) and T(1)=0
T(n) = 2T(n-1) + O(n) and T(1)=0
How many recursive problems are solved by the Recur_fun(int n) for n=3?
5
8
7
6
How many recursive problems are solved for n>0?
n
2n
2n - 1
2n
How many recursive steps are required to reach the base case (the solutions to n=0)?
n
log2n
n/2
nlog2n
How can you classify this algorithm using the big-O asymptotic notation?
O(n)
O(log2n)
O(2n)
O(n2)
Is this recursive function correct?
True
False
What is the purpose of postfix form for algebraic expression?
The postfix form is used for find syntax errors of an algebraic expression.
The postfix form provides a more readable form of an algebraic expression.
The postfix form speeds up the evaluation process of an algebraic expression.
The postfix form decreases the arithmetic operations.
What is the postfix form for the expression: x+y-z+t
x y + z - t +
x y z + t + -
x y + - z t +
x y + z t - +
What is the purpose of using the stack data structure during the conversion from infix to postfix forms for an arithmetic expression?
To push the operands (numbers or variables) into the postfix form in the reverse order.
To push the arithmetic operators before enqueuing them in the right order into the postfix form.
A stack is used only to detect the end of an expression.
A stack is redundant during the conversion to postfix form and it should not be used.
Assume that an expression consists of one digit numbers and arithmetic operations on them and it is given in postfix form: 4 3 1 + / 2 *
What is the value of the expression?
-1
0
1
2
How many times is the push operation called by the algorithm for the evaluation of the expression in the postfix form: 4 3 1 + / 2 * from the previous question?
4
5
6
7
How many times is the pop operation called by the algorithm for the evaluation of the expression in the postfix form: 4 3 1 + / 2 * from the previous question?
2
3
4
5
6
Consider the quick sort algorithm to sort n consecutive integers and the middle element is selected as the pivot at each recursive call.
What is the recurrence relation that describes the quick sort algorithm on this input?
T(n)=2T(n/2) + n and T(1)=0
T(n)=T(n/2) + n and T(1)=0
T(n)=T(n-1) + n and T(1)=0
Consider the quick sort algorithm to sort n consecutive integers and the middle element is selected as the pivot at each recursive call.
What is the running time of the quick sort algorithm expressed in terms of the big-O asymptotic notation on this input?
O(nlog_2(n))
O(n^2)
O(n)
Which case of the quick sort algorithm cannot be solved by the Master method?
best
worst
average
The efficiency of the quick and merge sort algorithms expressed in the terms of the Big-O asymptotic notation is the same for
worst and best cases of the quick sort
worst and average cases of the quick sort
best and average cases of the quick sort
The merge sort algorithm reaches the base case after a certain number of recursive steps. Select the number of recursive steps for the merge sort.
nlog_2(n)
log_2(n)
n
2^n
How many recursive subproblems are solved by the merge sort algorithm applied to a sequence of n elements?
2^(n/2)
2^log_2(n) -1
2^n - 1
n/2
What is the recurrence relation equation for the merge sort algorithm?
T(n) = T(n/2) +O(n) and T(1) = 0
T(n) = T(n/2) +O(n log2n) and T(1) = 0
T(n) = 2T(n/2) +O(n) and T(1) = 0
T(n) = 2T(n/2) +O(n log2n) and T(1) = 0
Which recurrence relation cannot be solved by the Master method?
T(n) = T(n/2) + O(n) and T(1) = 0
T(n) = T(n/16) + O(1) and T(1) = 0
T(n) = T(n/2) + O(log2(n)) and T(1) = 0
T(n) = T(n-2) + O(n) and T(1) = 0
Is the merge sort an in-place algorithm?
Select: True for Yes and False for No.
True
False
Which statement is true about a singly linked list?
A linked list uses less memory to store data than an array
The insert operation does not change addresses of existing nodes within a linked list.
A linked list provides a direct access to data
A sorted linked list is a perfect data structure for implementing the binary search algorithm.
Which operation can be done in a constant time (O(1)) on singly linked list when we are at the node pointed to by (pointer) P?
Delete a node pointed to by P.
Insert a new node after the node pointed to by P.
Insert a new node before the node pointed to by P.
An insertion of a new node at the beginning of a singly linked list should update explicitly or implicitly how many pointers?
Three pointers
Two pointers
Four pointers
One pointer
Assume that the queue data structure is implemented based on a singly linked list. The enqueue operation takes a constant time when the following information is provided:
The address of (pointers to) the middle node
The address of (pointer to) the first node.
The queue size, number of nodes in a queue.
The address of (pointer to) the last node
We use the definition of type Link below to create an object of this type initialized with the string "Hello". Which statement is correct?
Link obj = Link('Hello');
Link* obj = Link("Hello");
Link obj = new Link("Hello");
Link obj = Link("Hello");
