NEW
Font size
WorksheetsDSA mid-term revision (FIT HANU) pt. 2
Total questions: 38
Worksheet time: 19mins
– Which of the following is a hash function?
Select one:
Folding
Quadratic probing
Chaining
Hashing
Open addressing
– If h(k) is any hash function and is used to hash N keys into a table of size M, where N < M,
the expected number of collisions involving a particular key X is?
Select one:
Less than M
Less than N
Less than (N+M)/2
Less than 1.
- The process of accessing data stored in a serial access memory is similar to manipulating data
on a?
Select one:
Queue.
Binary Tree.
Stack.
Heap.
– What is the time complexity of the following algorithm with respect to the input size N
s <- 0
For i<-0 to n-1 do
{
p<-1
if(i<>0)
for(k<-1 to i) do
p<-p*x;
s<-s+C[i]*p
}
return s;
O(N)
O(2N)
O(N^2)
O(1)
– What is the time complexity of the following algorithm with respect to the input size N
For i<-1 to n-1 do
if(a[i] = m) then
return i;
O(N^2)
O(N-1)
O(N)
O(2N)
– What is the time complexity of the following algorithm with respect to the input size N
i<-n
While(i>1) do
If(m is divisible by i) AND (n is divisible by i)
Return i
i--
Return 1
O(M)
O(N+M)
O(N)
O(N*M)
– What is the time complexity of the following algorithm with respect to the input size N
s<-0
for(i<-1 to n do)
s=s+i*i*i;
return s;
O(1)
O(N^2)
O(2N)
O(N)
– Estimate the time complexity in Big-Oh notation, with respect to the input size N, for the code
below:
public void reverse() {
SLNode prev = null;
SLNode current = head;
SLNode tmp;
while(current != null) {
tmp = current.getNext();
current.setNext(prev);
prev=current;
current=tmp;
}
___________;
}
O(N^2)
O(1)
O(N)
O(N^3)
– Estimate the time complexity in Big-Oh notation, with respect to the input size N for the code
below
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
sum++;
O(1)
O(N^2)
O(N^3)
O(N)
– Estimate the time complexity in Big-Oh notation, with respect to the input size N for the code
below
for(int i = 1; i < N; i++) {
for(int j = 1; j < i*i; j++)
sum++
}
O(N^2)
O(N)
O(1)
O(N^3)
– Estimate the time complexity in Big-Oh notation, with respect to the input size N for the code
below
for(i = 0; i < n; i++)
for(j = 0; j< i*i; j++)
for(k = 0; k < j; k++)
sum++;
O(N^4)
O(N^2)
O(N^5)
O(N^3)
– Consider three algorithms which have the time complexity in Big-Oh notation below. Please
arrange these algorithms in the ascending order of time efficiency (the slowest algorithm is the
first one in the order).
f1(n) = O(2n^5 + N); f2(n) = O(NlogN); f3(n) = O(2^n)
Algorithm 3, Algorithm 1, Algorithm 2
Algorithm 2, Algorithm 1, Algorithm 3
Algorithm 2, Algorithm 3, Algorithm 1
Algorithm 3, Algorithm 2, Algorithm 1
– Consider three algorithm which have the time complexity in Big-Oh notation below. Please
arrange these algorithms in the descending order of time efficiency (the fastest algorithm is the
first one in the order).
f1(n) = O(NlogN); f2(n) = O(logN); f3(n) = O(N)
Algorithm 1, Algorithm 2, Algorithm 3
Algorithm 2, Algorithm 1, Algorithm 3
Algorithm 2, Algorithm 3, Algorithm 1
Algorithm 3, Algorithm 2, Algorithm 1
Estimate the time complexity in Big-Oh notation, with respect to the input size N for the code below
int x =0;
for(i =0; i<n; i+=)
{
int j = n/2;
while(j>0)
{
x=x*i;
j--;
}
}
return x;
O(2N)
O(N)
O(N^2)
O(N/2)
– In a Singly Linked List implementation, what do we do when assigning head to null?
Select one:
Avoid traversing the list.
Delete all nodes from the list.
Remove the last node from the list.
Remove the first node from the list.
– In an Array-based list, what does this code do to the list?
for(int i = pos-1; i<length; i++)
items[i] = items[i+1];
length--;
Remove all item from the list except one.
Traversing the list.
Remove an item from the list.
Duplicate items in the list.
– In a Singly Linked List implementation, what does this code to to the list?
if(!isEmpty)
{
if(pos == 1)
head = head.getNext()'
else
{
SLNode prevNode = traversing(pos-1);
SLNode posNode = prevNode.getNext();
prevNode.setNext(posNode.getNext());
}
}
Search for a node in the list
Remove the tail node
Remove the node at the pos position from the list
Remove the head node
– In an Array-based list, what does this code do to the list?
if(length<maxSize)
{
length++;
for(int i = length; i>pos; i--)
items[i]=items[i-1];
items[pos-1]=newitem;
}
Insert an item to the list
Search for an item in the list
Traversing the list
Remove an item from the list
- Consider method F in Java and a singly linked list L below. Suppose that H is the head node of
the list L. What is the result if we call F(H.getNext())?
public static void F(SLNode node)
{
if(node != null)
{
System.out.println(node.getData());
if(node.getnext() != null)
F(node.getNext().getNext());
}
}
L={'A' --> 'B' --> 'C' --> 'D' --> 'E' --> 'F'}
H is the head node of L, H = 'A'
‘F’-->‘D’-->‘B’
‘E’-->‘C’-->‘A’
‘B’-->‘D’-->‘F’
‘A’-->‘C’-->‘E’
– What is the number of comparisons needed in the worst case to search for a given node in a
Singly Linked List of the length N nodes?
Select one:
N/2
log(N)
N
Nlog(N)
– Selection sort algorithm is used to sort the array A={23,78,45,8,32,56} in the ascending order.
What are the items of A after 03 sort pass?
Select one:
A={8,32,23,45,56,78}
A={23,32,8,45,56,78}
A={78,45,56,23,32,8}
A={78,45,56,8,32,23}
– Insertion sort algorithm is used to sort the array A={23,78,45,8,32,56} in the ascending order. What are
the items of A after 03 sort pass?
Select one:
A={45,56,78,32,23,8}
A={45,56,78,23,32,8}
A={8,23,45,56,32,78}
A={8,23,45,78,32,56}
– Bubble sort algorithm is used to sort the array A={23,78,45,8,32,56} in the ascending order.
What are the items of A after 03 sort pass?
Select one:
A={8,23,32,45,56,78}
A={23,45,8,32,56,78}
A={8,32,23,45,56,78}
A={23,32,78,56,45,8}
– A sorting algorithm is used to sort the array A={83,8,12,72,71,65,5}.. The item of A in each
sort pass are listed below. Which sorting algorithm is used?
Pass 1: 8 12 72 71 65 5 83
Pass 2: 8 12 71 65 5 72 83
Pass 3: 8 12 65 5 71 71 83
Pass 4: 8 12 5 65 71 72 83
Pass 5: 8 5 12 65 71 72 83
Pass 6: 5 8 12 65 71 72 83
Pass 7: 5 8 12 65 71 72 83
Selection sort
Merge sort
Bubble sort
Insertion sort
– Which array represents a Min-Heap?
Select one:
A={2,5,9,22,10,13,12,8,50}
A={50,22,13,12,10,8,9,5,2}
A={2,5,9,8,10,13,12,22,50}
A={9,5,2,8,10,13,12,22,50}
– Which array represents a Max-Heap?
Select one:
A={78,56,45,32,23,8,15}
A={8,15,23,32,56,45,78}
A={78,23,15,56,32,8,45}
A={8,78,56,32,15,23,45}
– An array A contains integer item in the range 0 to 5. A={1,2,5,3,2}. Counting sort algorithm is
used to sort A. What is the content of the counting array C before we used the information form
C to creates the sorted result array B?
Select one:
C={1,1,5,5,3,2}.
C={1,2,5,3,2,5}
C={0,1,2,1,0,1}
C={0,1,3,4,4,5}
– An array contains integer items, each item has 03 digits. A={170,145,275,900,802}. Radix
sort algorithm is used to sort A. What is the content of A after the second sort pass?
Select one:
A={900,802,145,170,275}
A={145,170,275,802,900}
A={900,802,275,170,145}
A={145,900,170,802,275}.
– The Merge method in Merge sort algorithm is used to combine two sorted array
A={3,27,38,43} and B={9,10,82}. What is the result array C?
Select one:
C={3,82,9,43,10,38,27}
C={3,27,38,43,9,10,82}
C={3,9,10,27,38,43,82}
C={9,10,82,3,27,38,43}
– Heap sort algorithm is used to sort the array A={15,19,10,7,17,16} in the ascending order
(using a Max-Heap). What is the content of A after calling BuildHeap() method?
Select one:
A={19,17,16,7,15,10}
A={10,15,17,19,7,16}
A={10,7,15,19,16,17}
A={19,10,17,7,15,16}
– A stack S has 05 character items, S={“A”,“B”,“C”,“D”,“E”} where “E” is the top of S. What is the
content of S if we perform the following list of operations on the stack: push(“F”) –-> pop() –-> pop() –->
pop() –-> push(“D”)?
Select one:
S={“A”,“B”,“D”,“F”}
S={“A”,“B”,“C”,“D”}
S={“C”,“D”,“E”,“F”}
S={“B”,“E”, “F” ,“D”}
A queue Q has 05 character items, Q={“A”, “B”, “C”, “D”, “E”} where “E” is the rear and “A”
is the front of the queue. What is the content of Q if we perform the following list of operations
on the queue: enqueue(“F”)-->dequeue()-->dequeue()-->dequeque()-->enqueue(“D”)?
Select one:
Q={“C”, “D”, “E”, “F”}
Q={“A”, “B”, “C”, “D”}
Q={“D”, “F”, “A”, “B”}
Q={“D”, “E” ,“F” ,“D”}
– A stack S has 05 character items, S={“5”, “4”, “3”, “2”, “1”} where “1” is the top of S. Which
operations must be perform to change S into a new state: S={“5”, “4”, “2”, “3”, “1”}?
Select one:
pop()-->pop()-->pop()-->push(“2”)-->push(“3”)-->push(“1”)
pop()-->push(“2”)-->pop()-->push(“3”)-->pop()-->push(“1”)
push(“2”)-->pop()-->push(“3”)-->pop()-->push(“1”)-->pop()
push(“2”)-->push(“3”)-->push(“1”)-->pop()-->pop()-->pop()
– A queue Q has 05 character items, Q={“5”, “4”, “3”, “2”, “1”} where “1” is the front and “5”
is the rear of Q. Which operations must be perform to change Q into a new state: Q={“3”, “2”,
“1”, “4”, “5”}?
Select one:
enqueue(“4”)-->enqueue(“5”)-->dequeue()-->dequeue()
dequeue()-->enqueue(“5”)-->dequeue()-->enqueue(“4”)
enqueue(“5”)-->enqueue(“4”)-->dequeue()-->dequeue()
dequeue()-->dequeue()-->enqueue(“5”)-->enqueue(“4”)
In method F below, the stack s contains character items. Which is the result if we call method F
with the input string text=“datastructure”?
public static void F(String text)
{
Stack s = new Stack();
for(int i =0; i <text.length; i++)
s.push(text.charAt(i));
while(!s.isEmpty())
System.out.print(s.pop())
}
erutcurtsatad
datastructure
erutcurtsataderutcurtsatad
datastructuredatastructure
– One difference between a queue and a stack is:
Select one:
Stacks use two ends of the structure, queues use only one.
Queues require linked lists, but stacks do not.
Queues use two ends of the structure; stacks use only one.
Stacks require linked lists, but queues do not.
– In an array-based stack, which operation has time complexity O(N) in the worst-case?
Select one:
push().
No operation that has time complexity O(N).
isEmpty().
pop().
– In an array-based circular queue, which operation has time complexity O(N) in the worst-
case?
Select one:
isFull().
enqueue().
No operation that has time complexity O(N).
dequeue().
