Question 1

Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent(a,b) means a and b are equivalent. Which of the following first order logic statements represents

Accepted Answer

(∀x ∃y (fsa(x) ∧ pda(y) ∧ equivalent(x, y))). This statement correctly asserts that for every finite state automaton x, there exists a pushdown automaton y such that x and y are equivalent, fulfilling the requirement that each finite state automaton has a corresponding equivalent pushdown automaton.

Question 2

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to

Accepted Answer

arm starting and stopping inertia. The seek latency is affected by the physical limitations of the disk's read/write arm, which experiences inertia when starting and stopping. This means that the time taken to move the arm is not directly proportional to the distance it needs to travel, as it takes additional time to overcome inertia.

Question 3

Which of the following is/are true of the auto-increment addressing mode?
I. It is useful in creating self-relocating code
II. If it is included in an Instruction Set Architecture, then an additional ALU is required for effective address calculation
III. The amount of increment depends on

Accepted Answer

III only. The auto-increment addressing mode allows the address to be automatically incremented after each access, which means the increment size is determined by the data type being accessed, making statement III correct.

Question 4

Which of the following must be true for the RFE (Return from Exception) instruction on a general purpose processor?
I. It must be a trap instruction
II. It must be a privileged instruction
III. An exception cannot be allowed to occur during execution of an RFE instruction

Accepted Answer

I, II and III only. The RFE instruction is designed to safely return from an exception, which necessitates it being a trap and privileged instruction to ensure proper control over the execution environment. Additionally, preventing exceptions during its execution is crucial to maintain system stability and integrity.

Question 5

For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary?
I. L1 must be a write-through cache
II. L2 must be a write-through cache
III. The associativity of L2 must be greater than that of L1
IV. The L2 cache must be at

Accepted Answer

IV only. In a multi-level cache hierarchy, for inclusion to hold, the L2 cache must be at least as large as the L1 cache to ensure that all data stored in L1 can also be contained in L2. This size relationship is crucial for maintaining the inclusion property.

Question 6

In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is

Accepted Answer

during effective address calculation. The data TLB is accessed during effective address calculation because it is responsible for translating virtual addresses to physical addresses, which is a critical step that occurs while the effective address is being determined.

Question 7

Consider the following functions:
f(n) = 2ⁿ
g(n) = n!
h(n) = n^(log n)
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Accepted Answer

h(n) = O(f(n)); g(n) = Ω(f(n)). h(n)=n^(log n)=2^((log n)^2), which is sub-exponential, so h(n)=O(f(n)) with f(n)=2^n. Also n! grows faster than 2^n, so g(n)=Omega(f(n)). Thus the correct statement is 'h(n)=O(f(n)); g(n)=Omega(f(n))'. Stored option 0 fails because g(n)=n! is not O(h(n)).

Question 8

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Accepted Answer

Θ(log n). In a sorted array, we can efficiently find the target integer using binary search, which reduces the search space by half with each comparison, resulting in a time complexity of Θ(log n) to determine if the integer appears more than n/2 times.

Question 9

G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

Accepted Answer

There are two vertex-disjoint paths between every pair of vertices. The statement about having two vertex-disjoint paths between every pair of vertices is not necessarily true because while G has two edge-disjoint spanning trees, this does not guarantee that there are vertex-disjoint paths, as the paths may share vertices.

Question 10

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

Accepted Answer

T(n) ≤ T(n/5) + T(4n/5) + n. The correct option reflects the recursive nature of the Quicksort algorithm, where the list is divided into two parts: one containing at least one-fifth of the elements and the other containing the remaining elements. This ensures that the total number of comparisons includes the work done on both sub-lists, plus the linear time needed for partitioning.

Question 11

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

Accepted Answer

Q solves the subset-sum problem in polynomial time when the input is encoded in binary. The algorithm Q runs in O(nW) time, which is polynomial in terms of the input size when W is encoded in unary. However, when W is encoded in binary, the size of W can grow exponentially relative to its value, making the algorithm's time complexity exponential in practice, thus not polynomial.

Question 12

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

Accepted Answer

Θ(n). The correct option is Θ(n) because reconstructing a binary search tree from its postorder traversal involves processing each of the n elements exactly once to determine their positions in the tree, leading to a linear time complexity.

Question 13

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

Accepted Answer

Θ(n). Inserting n elements not necessarily one-by-one means placing all 2n elements and running build-heap (heapify), which is Theta(n). So the total time is Theta(n).

Question 14

Which of the following statements is false?

Accepted Answer

Every subset of a recursively enumerable set is recursive. This statement is false because while every recursively enumerable set can be recognized by a Turing machine, not all subsets of such sets are guaranteed to be recursive; some may be non-decidable.

Question 15

Match the following:

(E) Checking that identifiers are declared before their use
(F) Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function
(G) Arithmetic expressions with matched pairs of parentheses
(H) Palindro

Accepted Answer

(C) E – R, F – P, G – Q, H – S. Option C is correct because it accurately matches each concept with its corresponding language or grammar: E (checking identifiers) aligns with R (palindromes), F (parameter matching) corresponds to P (function parameters), G (parentheses in expressions) relates to Q (grammar for expressions), and H (palindromes) matches with S (grammar for palindromes).

Question 16

Which of the following are regular sets?

I. {aⁿ b^(2m) | n ≥ 0, m ≥ 0}
II. {aⁿ b^m | n = 2m}
III. {aⁿ b^m | n ≠ m}
IV. {xcy | x,y ∈ {a,b}*}

Accepted Answer

(A) I and IV only. Option I represents a regular set because it can be described by a regular expression, allowing any number of 'a's followed by an even number of 'b's. Option IV is also regular as it can be expressed using a finite automaton that accepts any string from {a,b} followed by a 'c' and then any string from {a,b}, demonstrating closure properties of regular languages.

Question 17

Which of the following are true?

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation
II. Multi-level access link (or display) arrangement is needed

Accepted Answer

I, II and V only. Option I is correct because a language without global variables and nesting can still use static allocation for recursion. Option II is accurate as multi-level access links are necessary for managing activation records only when nesting is present. Option V is true since returning functions typically requires a dynamic allocation scheme to manage their lifetimes.

Question 18

In the slow start phase of the TCP congestion control algorithm, the size of the congestion window

Accepted Answer

increases exponentially. During the slow start phase of TCP congestion control, the congestion window size doubles with each round-trip time, leading to an exponential increase in the amount of data that can be sent, which helps to quickly utilize available bandwidth.

Question 19

If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?

Accepted Answer

2046. The subnet mask 255.255.248.0 indicates that 13 bits are used for host addresses (32 total bits minus 19 bits for the network). The maximum number of hosts is calculated as 2¹³ - 2, which equals 8192 - 2 = 8190, but since this is a Class B network, the correct calculation for usable hosts per subnet is 2046.

Question 20

A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket(), a bind(), and a listen() system call in that order, following which it is preempted. Subsequently, the client process P executes a socket() s

Accepted Answer

connect() system call returns successfully. The connect() system call can return successfully because the client can establish a connection to the server's listening socket, even if the server has not yet called accept(). The connection is established in a half-open state, allowing the client to proceed.

Question 21

Choose the correct option to fill ?1 and ?2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.

void reverse(void){
 int c;
 if(?1) reverse();
 ?2
}

main(){
 printf("Enter Text"); printf("
");
 reverse(); p

Accepted Answer

?1 is ((c = getchar()) != '
')
?2 is putchar(c);. The correct option uses the assignment within the condition to read a character and check if it is not a newline. This allows the function to recursively call itself until the newline is encountered, and then it prints each character in reverse order as the recursion unwinds.

Question 22

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes executio

Accepted Answer

2,1,4,3,6,5,7. The function swaps the values of each pair of nodes in the linked list. Starting with the first two nodes, it swaps their values, then moves to the next pair, continuing this process until it reaches the end of the list. As a result, the original list 1,2,3,4,5,6,7 is transformed into 2,1,4,3,6,5,7.

Question 23

Let R and S be two relations with the following schema
R(P, Q, R1, R2, R3)
S(P, Q, S1, S2)
where {P,Q} is the key for both schemas. Which of the following queries are equivalent?
I. πP (R⋈S)
II. πP (R) ⋈ πP (S)
III. πP (πP,Q (R) ⋂ πP,Q (S))
IV. πP (πP,Q (R) − (πP,Q (R) − πP,Q (S)))

Accepted Answer

Only I, III and IV. Options I, III, and IV are equivalent because they all yield the same result by focusing on the common key attributes P and Q from both relations R and S. Option I directly joins R and S and projects P, while III uses intersection to find common keys, and IV effectively retrieves the same keys by eliminating non-matching entries. Option II, however, does not guarantee the same result as it joins the projections of R and S separately, which may lead to different outcomes.

Question 24

Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes.

Accepted Answer

256 and 4. A secondary index on a key is dense: 16384 entries, each key(6)+pointer(10)=16 bytes, so blocking factor = 1024/16 = 64. First level = ceil(16384/64)=256 blocks; second level = ceil(256/64)=4 blocks. The answer is 256 and 4.

GATE Technical: MAIN PAPER - CS questions with solutions

Questions