Exams › GATE › Technical › GATE 2023 Computer Science and Information Technology (CS)
19 questions with worked solutions.
Answer: 23, 17, 14, 7, 13, 10, 1, 5, 6, 12
This sequence satisfies the max-heap property where each parent node is greater than or equal to its child nodes, ensuring that the largest element is at the root and all levels of the heap maintain this order.
Answer: SLLdel is O(n) and DLLdel is O(1)
SLLdel has a worst-case time complexity of O(n) because it may need to traverse the list to find the node to delete, while DLLdel can delete a node in O(1) time since it has direct access to both the previous and next nodes, allowing for immediate adjustments to the pointers.
Answer: 1(0 + 11)*
The correct option, 1(0 + 11)*, accurately represents the language accepted by the DFA because it starts with a '1' followed by any combination of '0's and '11's, which aligns with the transitions and final state conditions of the automaton.
Answer: Number of attributes of its relation schema.
The degree, or arity, of a relation in a relational database refers to the number of attributes (or columns) in its schema, which defines the structure of the data within that relation.
Answer: Longer link length and higher transmission rate
In the Stop-and-Wait protocol, the utilization is affected by the round-trip time and the time taken to send a packet. A longer link length increases the round-trip time, which means the sender spends more time waiting for an acknowledgment, resulting in lower utilization, even if the transmission rate is higher.
Answer: Universal hashing method.
Universal hashing is designed to minimize the impact of an adversary by randomly selecting a hash function from a family of functions, making it difficult for the adversary to predict and exploit collisions. This randomness ensures that even if the keys are chosen maliciously, the expected number of collisions remains low, providing a robust defense against collision attacks.
Answer: D Latch
The circuit behaves like a D latch because it holds the value of the input when the control signal is active, allowing it to store data based on the input while being transparent to changes when the control signal is inactive.
Answer: Stack pointer
The stack pointer must be saved during a context switch because it indicates the current position in the stack for the thread, which is essential for maintaining the correct execution state when switching between threads.
Answer: OSPF implements Bellman-Ford algorithm to find shortest paths.
The statement is incorrect because OSPF actually uses Dijkstra’s algorithm, not Bellman-Ford, to calculate the shortest paths in a network. This distinction is crucial as it affects how OSPF determines the most efficient routing paths.
Q10. Which one or more of the following CPU scheduling algorithms can potentially cause starvation?
Answer: Priority Scheduling
Priority Scheduling can lead to starvation because lower-priority processes may be indefinitely postponed if higher-priority processes continuously arrive, preventing them from getting CPU time.
Answer: 12, 7
The correct option is 12 for V1 because with a binary semaphore, only one thread can modify X at a time, allowing for all increments to occur before any decrements, resulting in 10 + 5 - 3 = 12. For V2, the counting semaphore allows two threads to access X simultaneously, but even with this concurrency, the maximum value achievable after all operations is 10 + 5 - 3 = 12, but the minimum possible value is 7 due to potential interleaving of operations.
Answer: The language generated by G is a*(a + b)b*
S -> aSb gives a^n ... b^n wrapping X, and X -> aX | Xb | a | b generates a*(a+b)b*; the a^n/b^n wrappers are absorbed, so L(G) = a*(a+b)b*, which IS regular. Hence the correct statement is option index 1, not 'not regular'.
Answer: {a^m bⁿ | 0 ≤ n ≤ m}
The correct option describes a language where the number of 'b's can be equal to or less than the number of 'a's, which aligns with the PDA's ability to push and pop symbols based on the input, ensuring that for every 'b' processed, there is a corresponding 'a' that can be matched, thus maintaining the condition 0 ≤ n ≤ m.
Answer: (3, 4, 4, L01)
The correct option (3, 4, 4, L01) is right because the left shift operation in U1 must shift the value by 3 bits to multiply by 8 (2³), U2 should increment the address of array 'a' by 4 bytes (size of an int), and U3 should increment the address of array 'b' by 4 bytes as well. The jump back to L01 ensures the loop continues until the condition is met.
Answer: (1, 1, 0, 0, 1, 1, 1, 0)
The correct option (1, 1, 0, 0, 1, 1, 1, 0) satisfies the Boolean function A + A̅.C̅ + A.B.C by ensuring that for all combinations of A, B, and C, the output evaluates to true when A is true or when A is false and both B and C are false.
Answer: Both EXTRACT-MAX(A) and INSERT(A,key) run in O(log(n)).
Both operations, EXTRACT-MAX and INSERT, involve maintaining the heap property, which requires traversing the height of the heap. Since a max-heap is a complete binary tree, the height is logarithmic in relation to the number of elements, leading to a worst-case time complexity of O(log(n)) for both operations.
Answer: 3 8 5 13 11 10
The function recursively calculates the sum of values in the binary tree, printing the cumulative sum at each node after processing its left and right children. This results in the output reflecting the order of node processing and their respective sums.
Answer: The number of colors used is at most Δ(G) + 1.
The greedy coloring strategy ensures that each vertex is assigned the smallest color not used by its neighbors, which can require at most one additional color beyond the maximum degree of the graph, thus guaranteeing that the number of colors used does not exceed Δ(G) + 1.
Answer: 3
200.150.68.118 matches 200.150.68.0/24 (interface 3) but not 200.150.68.64/27 (range .64-.95, and 118>95). The longest matching prefix is the /24 entry, so it is forwarded to interface 3 (index 2).