DSA mid-term revision (FIT HANU) pt. 2

– 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)