DSA Unit Test -1

Total 23 Questions .Each Question will be of 1 or 2 marks

* Required

* This form will record your name, please fill your name.

1. Internal sorting algorithm is the__________ *

(1 Point)

Algorithm that uses tape or disk during the sort

Algorithm that uses main memory during the sort

Algorithm that involves swapping

Algorithm that are considered ‘in place’

2. void function(int n){

int i=0,div=0;
while(i<n){
if(i%2==0) i++;
if(n%i==0) div++;
i++; }}
Give frequency count of the code snippet given above. *
(2 Points)

nlogn

n^2

Logn

N2

10/13/2020
 3. Postfix of given expression is ((A-(b+c)*D)^(D+E)) *
(2 Points)

Abc+-D* D^E+

Abc+D* -DE+^

Abc+*D-DE+^

Abc+D*DE+-^

4. A queue of characters currently contained A,B,C,D. What would be the contents of

queue after the following operation DELETE, ADD W, ADD X, DELETE, ADD Y. *
(1 Point)

A,B,C,W,Y

A,B,C,D,W

C,D,W,X,Y

W,Y,X,C,D

5. Which of the following points is/are not true about Linked List data structure when it
is compared with array? *
(1 Point)

Arrays have better cache locality that can make them better in terms of performance

It is easy to insert and delete elements in Linked List

Random access is not allowed in a typical implementation of Linked Lists

Access of elements in linked list takes less time than compared to arrays

10/13/2020
 6. Consider the following declaration of a ‘two-dimensional array in C: char a[100]
[100]; Assuming that the main memory is byte-addressable and that the array is
stored starting from memory address 0, the address of a[40][50] is *
(1 Point)

4040

4050

5040

5050

7. What does the following piece of code do? for (int i = 0; i < arr.length-1; i++)
{
for (int j = i+1; j < arr.length; j++)
{
if( (arr[i].equals(arr[j])) && (i != j) )
{
cout<<(arr[i]);
}
}
}*
(2 Points)

Print the duplicate elements in the array

Print the element with maximum frequency

Print the unique elements in the array

Prints the element with minimum frequnecy

10/13/2020
 8. Consider the following C++program:
void foo(int n, int sum)
{
int k = 0, j = 0;
if (n == 0) return;
k = n % 10; j = n / 10;
sum = sum + k;
foo (j, sum);
cout<< k ;
}

int main ()
{
int a = 2048, sum = 0;
foo (a, sum);
cout<< sum);
}
""What does the above program print? *
(2 Points)

8, 4, 0, 2, 0

2, 0, 4, 8, 14

2, 0, 4, 8, 0

8, 4, 0, 2, 14

9. Consider a linked implementatin of queue with two pointers : front and rear. The
time needed to insert element in a queue of length n is *
(1 Point)

O(1)

O(log2 n)

(log n)

(n log n)

10/13/2020
 10. struct node{
int value;
struct node* next;
};
void rearrange (struct node* list)
{
struct node *p,q;
int temp;
if (! List || ! list->next) return;
p=list; q=list->next;
while(q)
{
temp=p->value; p->value=q->value;
q->value=temp;
p=q->next;
q=p?p->next:0;
}
}*
(2 Points)

2, 3, 4, 5, 6, 7, 1

1, 3, 2, 5, 4, 7, 6

1, 2, 3, 4, 5, 6, 7

2, 1, 4, 3, 6, 5, 7

11. The result evaluating the postfix expression 10 5 + 60 6 / * 2 – is *

(1 Point)

284

148

142

72

10/13/2020
 12. Suppose a circular queue of capacity (n – 1) elements is implemented with an array
of n elements. Assume that the insertion and deletion operation are carried out
using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT
= 0. The conditions to detect queue full and queue empty are *
(1 Point)

Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

13. Stack cant be used for *

(1 Point)

postfix expression evaluation

In recursion

expression conversion

Resource allocation by Operating system

14. Consider the situation in which assignment operation is very costly. Which of the
following sorting algorithm should be performed so that the number of assignment
operations is minimized in general? *
(1 Point)

Insertion sort

Selection sort

bubble sort

Cannot compare

10/13/2020
 15. The most appropriate matching for the following pairs
X: m=new int(5); m= NULL; 1: using dangling pointers

Y: free(n); n->value=5; 2: using uninitialized pointers

Z: char *p; *p = ’a’; 3. lost memory *

(1 Point)

X—1, Y—3 ,Z-2

X—3, Y—1 ,Z-2

X—3 ,Y—2 ,Z-1

X—2 ,Y—1, Z-3

16. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag
variable)The number of iterations in selection sort and bubble sort respectively are,
answer choices *
(1 Point)

5 and 4

1 and 4

0 and 4

4 and 1

17. What is the error in the following code fragment?

float average [20];
average[20] = 15.25; *
(1 Point)

A cast is required

data not initialized

A two-dimensional array is required

Array Out-of-bounds error

10/13/2020
 18. Solve the recurrence t(n)=2t(n/2)+c *
(2 Points)

O(N2)

O(LOGN)

O(N+LOGN)

O(N)

19. Apply Quick sort on a given sequence 7 11 14 6 9 4 3 12. What is the sequence after
first phase, pivot is first element? *
(1 Point)

6 4 3 7 11 9 14 12

6 3 4 7 9 14 11 12

7 6 14 11 9 4 3 12

7 6 4 3 9 14 11 12

20. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow
from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the
location of the topmost element in each of the stacks. If the space is to be used
efficiently, the condition for “stack full” is *
(1 Point)

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)

top1 + top2 = MAXSIZE

top1= top2 -1

(top1= MAXSIZE/2) or (top2 = MAXSIZE

10/13/2020
 21. Recurrence equal for worst case of quick sort?
a)t(n)=t(n-1)+c

b)t(n)=2t(n/2)+n

c)t(n)=t(n-1)+n

d)t(n)=2t(n/2)+c *
(1 Point)

t(n)=t(n-1)+c

t(n)=2t(n/2)+n

t(n)=t(n-1)+n

t(n)=2t(n/2)+c

22. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid
values(corresponding array elements) generated in the first and second iterations? *
(1 Point)

90 and 99

90 and 100

89 and 94

94 and 99

23. Given an array [ 1..8, 1..5, 1..7 ] of integers. Calculate address of element A[5,3,6], by
using rows major methods, if BA=900? *
(2 Points)

1000

1122

1123

1500

10/13/2020
 This content is neither created nor endorsed by Microsoft. The data you submit will be sent to the form owner.

Microsoft Forms

10/13/2020