GATE Exam: Date Structures And Algorithms! Quiz
-
What is the function of 'r+' module in opening a file ?
-
Write Only
-
For truncating and writing
-
Read in binary format
-
Read and Write
-
About This Quiz
This quiz is a gate exam on date structures and algorithms! Before you get that degree that shows you are well capable of handling your tasks as an engineer, you are expected to pass a series of tests to see how attentive you are in class. This quiz is an example of the type of questions to expect. How about See moreyou try it out!
Questions and Answers
- 2.
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
Correct Answer
A. P3, P1, P4, P2Explanation
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.Rate this question:
-
- 3.
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
Correct Answer
A. QMNPROExplanation
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.Rate this question:
-
- 4.
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
Correct Answer
A. 15j+ i+ 84Explanation
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.Rate this question:
-
- 5.
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
Correct Answer
A. BcExplanation
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".Rate this question:
-
- 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
Correct Answer
A. 6,7Explanation
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.Rate this question:
-
- 7.
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)
Correct Answer
A. Θ(1), Θ(n)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.Rate this question:
-
- 8.
Which one of the following is not an application of Stack Data Structure?
-
BFS Algorithm
-
Managing function calls
-
Recursion
-
DFS Algorithm
Correct Answer
A. BFS AlgorithmExplanation
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.Rate this question:
-
- 9.
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
Correct Answer
A. First In First OutExplanation
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.Rate this question:
-
- 10.
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
Correct Answer
A. Depth First SearchExplanation
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.Rate this question:
-
- 11.
User push 1 element in the stack having already five elements and having stack size as 5 then stack ___________.
-
Overflows
-
Underflows
-
Crash
-
User Flow
Correct Answer
A. OverflowsExplanation
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.Rate this question:
-
- 12.
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
Correct Answer
A. 1 & 3Explanation
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.Rate this question:
-
- 13.
In order traversal of binary search tree will produce −
-
Reverse of input
-
Sorted list
-
Unsorted list
-
None of the above
Correct Answer
A. Sorted listExplanation
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.Rate this question:
-
- 14.
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] ^ 1 ^ 2 ^ 3 ^ 2 ^ 3 ^ 4 ^ 4 ^ 5
-
List[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 4 ^ 3 ^ 2 ^ 4 ^ 5 ^ 6 ^ 2 ^ 4
-
List[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4]
Correct Answer
A. List[0] ^ list[1] ^ list[2] ^ list[3] ^ list[4] ^ 1 ^ 2 ^ 4 ^ 3 ^ 2 ^ 4 ^ 5 ^ 6 ^ 2 ^ 4Explanation
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.Rate this question:
-
- 15.
What will be the postfix expression for following infix expression - A + B * C ^ D
-
ABCD+*^
-
ABCD*+^
-
ABCD^*+
-
ABC+D*^
Correct Answer
A. 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^*+".Rate this question:
-
- 16.
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
Correct Answer
A. Multiplies 'a' with 3.5Explanation
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.Rate this question:
-
- 17.
What a function is called when its defined inside a class?
-
Another Function
-
Module
-
Class
-
Method
Correct Answer
A. MethodExplanation
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.Rate this question:
-
- 18.
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()
Correct Answer
A. O(n) for fun1() and O(2^n) for fun2()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.Rate this question:
-
- 19.
What is the time complexity in worst case for best possible implementation of QuickSort?
-
O(n)
-
O(nLogn)
-
O(n2)
-
O(Logn)
Correct Answer
A. O(nLogn)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).Rate this question:
-
- 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
Correct Answer
A. NExplanation
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.Rate this question:
-
Quiz Review Timeline (Updated): Mar 19, 2023 +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 19, 2023Quiz Edited by
ProProfs Editorial Team -
Feb 07, 2019Quiz Created by
Programming.quiz
Back to top