Data Structures Minor-1

What is the complexity of code

Sum=0

for(i=1; i<n; i*=2)

{

for(j=1;j<=n;j++)

                        sum++

• O (n² )

• O(n)

• O (n log n log n)

• O(log n)

Which of the following is the advantage of the array data structure?

• Amount of Memory allocated should be known beforehand

• Elements of array accessed in constant time

• Elements are stored in contiguous blocks

• Multiple other data structures can be implemented using Arrays.

   

Which of the following data structures finds its use in recursion

• Linked List

• Arrays

• Stacks

• Queues

There are unsorted Arrays A1,A2,….An. Assume that n is odd. Each of A1,A2,…An contains N distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of medians of A1,A2,….An is

• O(n)

• O(n log n)

• O(n^2)

• O(n^2 log n)

The no. of Comparisons done by a sequential Search is

• (n/2)+1

• (n+1)/2

• (n-1)/2

• (n+2)/2      

A function f defined on stacks of integers satisfies the following properties.

f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i

for all stacks S and integers i.

If a stack S contains the integers -10, -8, 5, 2 0, -1, 3, 6, -2 in order from bottom to top, what is f(S)?

Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A may be printed straight away or pushed to stack B. An entry popped out of stack B may be only be printed. Which of the subsequent permutations of a, b, c is not feasible in this arrangement?

Convert the subsequent infix expression into its equal postfix expression

K + L - M*N + (O^P) W/U/V T + Q

Which of the following is the correct recurrence relation for finding the time complexity of the Tower of Hanoi problem with n discs.

• T(n) = 2*T(n-2) + 2

• T(n) = 2*T(n-1) + n

• T(n) = 2*T(n/2) + 1

• T(n) = 2*T(n-1) + 1

Consider the following operations performed on a stack of size 5:

Push (a); Pop(); Push(b); Push(c); Pop();

Push(d); Pop(); Pop(); Push(e);Pop();Push(f);Pop();Pop()

What is the status of stack?