GATE Exam: Date Structures And Algorithms! Quiz

1. User push 1 element in the stack having already five elements and having stack size as 5 then stack ___________.

Overflows

Underflows

Crash

User Flow

When the user pushes an element into the stack that already has five elements and has a stack size of 5, it will result in an overflow. An overflow occurs when the stack is full and a new element is attempted to be added. This can lead to data loss or memory corruption if not handled properly.

Explanation

When the user pushes an element into the stack that already has five elements and has a stack size of 5, it will result in an overflow. An overflow occurs when the stack is full and a new element is attempted to be added. This can lead to data loss or memory corruption if not handled properly.

2. A queue is implemented by which of the following strategy ?

First In First Out

First In Last out

Random In Random Out

Last In First Out

A queue is implemented using the First In First Out (FIFO) strategy, where the element that is inserted first is the first one to be removed. This means that the elements are processed in the order they were added to the queue, resembling a real-life queue where the first person in line is the first to be served. Other strategies mentioned, such as First In Last Out (FILO) or Last In First Out (LIFO), are used in different data structures like stacks.

Explanation

A queue is implemented using the First In First Out (FIFO) strategy, where the element that is inserted first is the first one to be removed. This means that the elements are processed in the order they were added to the queue, resembling a real-life queue where the first person in line is the first to be served. Other strategies mentioned, such as First In Last Out (FILO) or Last In First Out (LIFO), are used in different data structures like stacks.

3. A language with string manipulation facilities uses the following operations . head(s) – returns the first character of the string s tail(s) – returns all but the first character of the string s concat(s1,s2) – concatenates string s1 with s2.

The output of [concat(head(tail(s)), head(tail(tail(s))))]

where s is abcb is :

Ac

As

Bc

Ab

The given expression [concat(head(tail(s)), head(tail(tail(s))))] can be evaluated step by step as follows:
- First, we evaluate tail(s), which returns "bcb".
- Then, we evaluate head(tail(s)), which returns "b".
- Next, we evaluate tail(tail(s)), which returns "cb".
- Finally, we evaluate head(tail(tail(s))), which returns "c".
- Now, we can concatenate the results of the previous steps, "b" and "c", giving us the final output "bc".

Explanation

The given expression [concat(head(tail(s)), head(tail(tail(s))))] can be evaluated step by step as follows:
- First, we evaluate tail(s), which returns "bcb".
- Then, we evaluate head(tail(s)), which returns "b".
- Next, we evaluate tail(tail(s)), which returns "cb".
- Finally, we evaluate head(tail(tail(s))), which returns "c".
- Now, we can concatenate the results of the previous steps, "b" and "c", giving us the final output "bc".

4. In order traversal of binary search tree will produce −

Reverse of input

Sorted list

Unsorted list

None of the above

In-order traversal of a binary search tree visits the nodes in ascending order. Therefore, the correct answer is "sorted list" as it accurately describes the result of the traversal.

Explanation

In-order traversal of a binary search tree visits the nodes in ascending order. Therefore, the correct answer is "sorted list" as it accurately describes the result of the traversal.

5. What will be the postfix expression for following infix expression - A + B * C ^ D

ABCD+*^

ABCD*+^

ABCD^*+

ABC+D*^

The given infix expression is "A + B * C ^ D". To convert this to postfix expression, we follow the rules of operator precedence. The operator with higher precedence is placed after the operands. In this case, the exponentiation operator (^) has the highest precedence, so it is placed after C and D. Next, the multiplication operator (*) is placed after B and C. Finally, the addition operator (+) is placed after A and the result of the multiplication. Therefore, the correct postfix expression is "ABCD^*+".

Explanation

The given infix expression is "A + B * C ^ D". To convert this to postfix expression, we follow the rules of operator precedence. The operator with higher precedence is placed after the operands. In this case, the exponentiation operator (^) has the highest precedence, so it is placed after C and D. Next, the multiplication operator (*) is placed after B and C. Finally, the addition operator (+) is placed after A and the result of the multiplication. Therefore, the correct postfix expression is "ABCD^*+".

6. If x is equal to 5 . Then what will be the output if we print the following two variables? Print( (++x)++,x) ;

7,7

5,6

6,6

6,7

The output will be 6,7.

In the given code, (++x)++ is used which is an invalid expression. The operator ++ is used twice in a row, which is not allowed. The correct usage would be either (++x) or (x++), but not both together. Therefore, the code will result in an error and the output cannot be determined.

Explanation

The output will be 6,7.

In the given code, (++x)++ is used which is an invalid expression. The operator ++ is used twice in a row, which is not allowed. The correct usage would be either (++x) or (x++), but not both together. Therefore, the code will result in an error and the output cannot be determined.

7. What is the function of 'r+' module in opening a file ?

Write Only

For truncating and writing

Read in binary format

Read and Write

The 'r+' module in opening a file allows for both reading and writing operations to be performed on the file. This means that the file can be accessed for reading data from it as well as writing data into it. It provides the flexibility to both read the existing content of the file and modify it by adding or deleting data.

Explanation

The 'r+' module in opening a file allows for both reading and writing operations to be performed on the file. This means that the file can be accessed for reading data from it as well as writing data into it. It provides the flexibility to both read the existing content of the file and modify it by adding or deleting data.

8. What a function is called when its defined inside a class?

Another Function

Module

Class

Method

When a function is defined inside a class, it is called a method. In object-oriented programming, a method is a behavior or action that an object of a class can perform. It is associated with the class and can access the class's attributes and other methods. Methods are used to manipulate the data of an object and provide functionality specific to that class.

Explanation

When a function is defined inside a class, it is called a method. In object-oriented programming, a method is a behavior or action that an object of a class can perform. It is associated with the class and can access the class's attributes and other methods. Methods are used to manipulate the data of an object and provide functionality specific to that class.

9. Change in value of a after the following operation? a = (a<<1) + a + (a>>1);

Multiplies 'a' with 3

Multiplies 'a' with 7

Multiplies 'a' with 7.5

Multiplies 'a' with 3.5

The given operation shifts the bits of 'a' to the left by 1 position, adds the original 'a' to it, and then shifts the bits to the right by 1 position. This operation is equivalent to multiplying 'a' by 3. Therefore, the correct answer is "Multiplies 'a' with 3.5", as none of the other options are correct explanations for the given operation.

Explanation

The given operation shifts the bits of 'a' to the left by 1 position, adds the original 'a' to it, and then shifts the bits to the right by 1 position. This operation is equivalent to multiplying 'a' by 3. Therefore, the correct answer is "Multiplies 'a' with 3.5", as none of the other options are correct explanations for the given operation.

10. Arrange the following functions P1, P2, P3, P4 in increasing order of their asymptotic complexity? P1(n) = n^2 P2(n) = 2^n P3(n) = Logn P4(n) = n^(Logn)

P2, P3, P4, P1

P3, P1, P4, P2

P3, P2, P4, P1

P2, P3, P1, P4

The correct answer is P3, P1, P4, P2.

The functions are arranged in increasing order of their asymptotic complexity.

P3(n) = Logn has the lowest complexity as it grows slower than the other functions.

P1(n) = n^2 has a higher complexity as it grows faster than P3(n) but slower than P4(n).

P4(n) = n^(Logn) has a higher complexity than P1(n) as it grows faster due to the exponential term.

P2(n) = 2^n has the highest complexity as it grows exponentially and surpasses the growth rate of all other functions.

Explanation

The correct answer is P3, P1, P4, P2.

The functions are arranged in increasing order of their asymptotic complexity.

P3(n) = Logn has the lowest complexity as it grows slower than the other functions.

P1(n) = n^2 has a higher complexity as it grows faster than P3(n) but slower than P4(n).

P4(n) = n^(Logn) has a higher complexity than P1(n) as it grows faster due to the exponential term.

P2(n) = 2^n has the highest complexity as it grows exponentially and surpasses the growth rate of all other functions.

11. Tick the option in which both statement is correct : 1. According to Access strategies, Linked list is a linear one. 2. According to Storage, Linked List is a linear one. 3. According to Storage, Linked List is a Non-linear one. 4. According to Access strategies, Linked list is a Non-linear one.

4 & 3

4 & 2

1 & 3

1 & 2

According to the given statements, option 1 and option 3 are both correct. According to access strategies, a linked list is a non-linear structure, while according to storage, a linked list is a linear structure.

Explanation

According to the given statements, option 1 and option 3 are both correct. According to access strategies, a linked list is a non-linear structure, while according to storage, a linked list is a linear structure.

12. Which one of the following is not an application of Stack Data Structure?

BFS Algorithm

Managing function calls

Recursion

DFS Algorithm

BFS Algorithm is not an application of Stack Data Structure because it uses a Queue Data Structure instead. BFS (Breadth-First Search) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first manner, meaning it visits all the vertices at the same level before moving to the next level. In BFS, a queue is used to store the vertices that need to be visited, whereas in Stack Data Structure, the last element added is the first one to be removed (LIFO - Last-In-First-Out), which is not suitable for BFS traversal.

Explanation

BFS Algorithm is not an application of Stack Data Structure because it uses a Queue Data Structure instead. BFS (Breadth-First Search) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first manner, meaning it visits all the vertices at the same level before moving to the next level. In BFS, a queue is used to store the vertices that need to be visited, whereas in Stack Data Structure, the last element added is the first one to be removed (LIFO - Last-In-First-Out), which is not suitable for BFS traversal.

13. A queue is implemented using a singly linked list. The queue has a head pointer and a tail pointer and next pointers, as shown in the figure. Let n denote the number of nodes in the queue. Let nodes are enqueued at the head, and dequeued from the tail. Which one of the following is the time complexity of the most time-efficient implementation of 'enqueue' and 'dequeue, respectively, for this data structure?

Θ(n), Θ(1)

Θ(1), Θ(n)

Θ(n), Θ(n)

Θ(1), Θ(1)

The time complexity of the most time-efficient implementation of 'enqueue' for this data structure is Θ(1) because adding a new node at the head of the linked list can be done in constant time, regardless of the number of nodes in the queue.

The time complexity of the most time-efficient implementation of 'dequeue' for this data structure is Θ(n) because removing a node from the tail of the linked list requires traversing the entire list to update the next pointers, which takes linear time proportional to the number of nodes in the queue.

Explanation

The time complexity of the most time-efficient implementation of 'enqueue' for this data structure is Θ(1) because adding a new node at the head of the linked list can be done in constant time, regardless of the number of nodes in the queue.

The time complexity of the most time-efficient implementation of 'dequeue' for this data structure is Θ(n) because removing a node from the tail of the linked list requires traversing the entire list to update the next pointers, which takes linear time proportional to the number of nodes in the queue.

14. Let A be a two dimensional array declared as follows: A: array [1 ... 15] [1 ... 10] of integer; Assuming that each integer takes one memory location, the array is stored in column-major order and the first element of the array is stored at location 100, what is the address of the element A[i][j] ?

15i+ j+ 89

10j+ i+ 89

15j+ i+ 84

10i+ j+ 84

The given array is stored in column-major order, which means that the elements are stored column by column. Since each integer takes one memory location, the number of columns (10) is multiplied by the row index (i) to get the offset within the column. The column index (j) is added to this offset. Additionally, the first element of the array is stored at location 100, so this constant offset (84) is added to the calculation. Therefore, the address of the element A[i][j] can be calculated as 15j + i + 84.

Explanation

The given array is stored in column-major order, which means that the elements are stored column by column. Since each integer takes one memory location, the number of columns (10) is multiplied by the row index (i) to get the offset within the column. The column index (j) is added to this offset. Additionally, the first element of the array is stored at location 100, so this constant offset (84) is added to the calculation. Therefore, the address of the element A[i][j] can be calculated as 15j + i + 84.

15. Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?

Depth First Search

Breadth First Search

Kruskal' Minimum Spanning Tree Algorithm

Prim's Minimum Spanning Tree Algorithm

Depth First Search (DFS) is an algorithm that can be used to most efficiently determine the presence of a cycle in a given graph. DFS explores the graph by traversing as far as possible along each branch before backtracking. During this traversal, if a visited node is encountered again, it indicates the presence of a cycle in the graph. DFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph, making it an efficient algorithm for cycle detection.

Explanation

Depth First Search (DFS) is an algorithm that can be used to most efficiently determine the presence of a cycle in a given graph. DFS explores the graph by traversing as far as possible along each branch before backtracking. During this traversal, if a visited node is encountered again, it indicates the presence of a cycle in the graph. DFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph, making it an efficient algorithm for cycle detection.

16.

int fun1(int n) { if (n <= 1) return n; return 2*fun1(n-1); }

int fun2(int n) { if (n <= 1) return n; return fun2(n-1) + fun2(n-1); }

Which option is correct regarding the complexity of two functions?

O(n) for fun1() and O(2^n) for fun2()

O(2^n) for fun1() and O(n) for fun2()

O(n) for both fun1() and fun2()

O(2^n) for both fun1() and fun2()

The complexity of the first function, fun1(), is O(n) because it recursively calls itself n times, decrementing n by 1 each time. Each recursive call takes constant time, so the overall time complexity is linear.

The complexity of the second function, fun2(), is O(2^n) because it recursively calls itself twice for each recursive call. This results in an exponential growth in the number of function calls as n increases. Each recursive call takes constant time, so the overall time complexity is exponential.

Explanation

The complexity of the first function, fun1(), is O(n) because it recursively calls itself n times, decrementing n by 1 each time. Each recursive call takes constant time, so the overall time complexity is linear.

The complexity of the second function, fun2(), is O(2^n) because it recursively calls itself twice for each recursive call. This results in an exponential growth in the number of function calls as n increases. Each recursive call takes constant time, so the overall time complexity is exponential.

17. What is the time complexity in worst case for best possible implementation of QuickSort?

O(n)

O(nLogn)

O(n2)

O(Logn)

The best possible implementation of QuickSort has a time complexity of O(nLogn) in the worst case. This means that the algorithm takes a time proportional to the product of the number of elements to be sorted (n) and the logarithm of the number of elements (Logn). This is considered efficient as it has a better time complexity compared to O(n2) and O(Logn).

Explanation

The best possible implementation of QuickSort has a time complexity of O(nLogn) in the worst case. This means that the algorithm takes a time proportional to the product of the number of elements to be sorted (n) and the logarithm of the number of elements (Logn). This is considered efficient as it has a better time complexity compared to O(n2) and O(Logn).

18. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

MNOPQR

QMNPRO

QMNPOR

NQMPOR

The Breadth First Search algorithm starts at the root node and explores all the neighboring nodes before moving on to the next level of nodes. In this case, the algorithm starts at node Q and visits its neighboring nodes M, N, and P. It then moves on to the next level and visits node R. The algorithm continues in this manner until all nodes have been visited. Therefore, the possible order of visiting the nodes in this graph is Q, M, N, P, R, O.

Explanation

The Breadth First Search algorithm starts at the root node and explores all the neighboring nodes before moving on to the next level of nodes. In this case, the algorithm starts at node Q and visits its neighboring nodes M, N, and P. It then moves on to the next level and visits node R. The algorithm continues in this manner until all nodes have been visited. Therefore, the possible order of visiting the nodes in this graph is Q, M, N, P, R, O.

19. You are given a list of 5 integers and these integers are in the range from 1 to 6. There are no duplicates in list. One of the integers is missing in the list. Which of the following expression would give the missing number. ^ is bitwise XOR operator. ~ is bitwise NOT operator. Let elements of list can be accessed as list[0], list[1], list[2], list[3], list[4]

~(list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4])

List[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4]

The given expression "list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 4 ^ 3 ^ 2 ^ 4 ^ 5 ^ 6 ^ 2 ^ 4" would give the missing number. The expression uses the XOR operator to perform bitwise XOR operations on all the elements in the list along with the numbers 1, 2, 4, 3, 2, 4, 5, 6, 2, and 4. The XOR operator returns a value that is 1 if the corresponding bits in the two operands are different, and 0 if they are the same. By XORing all the elements in the list and the additional numbers, the missing number will be obtained.

Explanation

The given expression "list[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 4 ^ 3 ^ 2 ^ 4 ^ 5 ^ 6 ^ 2 ^ 4" would give the missing number. The expression uses the XOR operator to perform bitwise XOR operations on all the elements in the list along with the numbers 1, 2, 4, 3, 2, 4, 5, 6, 2, and 4. The XOR operator returns a value that is 1 if the corresponding bits in the two operands are different, and 0 if they are the same. By XORing all the elements in the list and the additional numbers, the missing number will be obtained.

20.

You are given an array A[] having N 
random integers and a function OR(i,j) 
which will take two indexes from an array 
as parameters and will return the result 
of ( A[i] OR A[j] ) i.e bitwise OR. What is 
the minimum no of OR calls required so as to 
determine all the values inside the   array 
i.e. to determine every index of A[] ?

N

N-1

N*(N-1)/2

Not possible to determine the bit array

To determine every index of array A[], we need to compare each element with every other element in the array. This can be done by making OR calls between each pair of indexes. Since there are N elements in the array, we need to make N OR calls to determine all the values inside the array. Therefore, the minimum number of OR calls required is N.

Explanation

To determine every index of array A[], we need to compare each element with every other element in the array. This can be done by making OR calls between each pair of indexes. Since there are N elements in the array, we need to make N OR calls to determine all the values inside the array. Therefore, the minimum number of OR calls required is N.