Question 1

Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?

Accepted Answer

G2 = (V,E2) where E2 = {(u,v) | (v,u) ∈ E}. G2 represents the transpose of the original graph G, where the direction of all edges is reversed. This operation preserves the strongly connected components, as the reachability between vertices remains intact in both directions.

Question 2

Consider the following program in C language:

#include <stdio.h>

main()
{
 int i;
 int *pi = &i;
 scanf("%d", pi);
 printf("%d
", i+5);
}

Which one of the following statements is TRUE?

Accepted Answer

On execution, the value printed is 5 more than the integer value entered.. The program correctly reads an integer value into the variable 'i' using a pointer, and then it prints the value of 'i' increased by 5, which means the output is indeed 5 more than the integer value entered by the user.

Question 3

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Accepted Answer

Θ(n²). When a graph is represented as an adjacency matrix, checking for the existence of edges requires examining each entry in the n x n matrix. This results in a time complexity of Θ(n²) for Depth First Search, as every vertex and its potential connections must be considered.

Question 4

Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?

Accepted Answer

t1 > t2. For [1 2 3 4 5] (sorted, first-element pivot) comparisons are 4+3+2+1=10. For [4 1 5 3 2], pivot 4 makes 4 comparisons, then [1 3 2] makes 2+1=3 and [5] makes 0, total 7. So t1=10 > t2=7, i.e. t1 > t2.

Question 5

Which one of the following is TRUE ?

Accepted Answer

The language L = {w | w has 3k + 1 b's for some k ∈ N with Σ = {a, b}} is regular.. This language can be recognized by a finite automaton because it only requires counting the number of 'b's modulo 3, which is a finite condition. Regular languages can be defined by such finite counting, making this language regular.

Question 6

Match the following:
1) Waterfall model
2) Evolutionary model
3) Component-based software engineering
4) Spiral development

a) Specifications can be developed incrementally
b) Requirements compromises are inevitable
c) Explicit recognition of risk
d) Inflexible partitioning of the project

Accepted Answer

1-d, 2-a, 3-b, 4-c. The Waterfall model is characterized by its rigid structure, dividing the project into distinct stages, hence option 1-d. The Evolutionary model allows for incremental development of specifications, matching option 2-a. Component-based software engineering often involves trade-offs and compromises in requirements, aligning with option 3-b. Lastly, the Spiral development model incorporates risk assessment as a core element, corresponding to option 4-c.

Question 7

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the re

Accepted Answer

3. Starting at 100 with SSTF, the service order by nearest-seek is 100, then 105, then 110, then 90 (distance 20, closer than 135 at 25). Thus cylinder 90 is the 4th serviced, i.e. after servicing 3 requests, so the answer is 3.

Question 8

Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies {{E, F} → {G}, {F} → {I, J}, {E, H} → {K, L}, {K} → {M}, {L} → {N}} on R. What is the key for R?

Accepted Answer

{E, F, H}. The correct option {E, F, H} is a key for relation R because it can determine all other attributes in the relation through the given functional dependencies. Specifically, {E, F} can derive {G, I, J}, and adding {H} allows us to derive {K, L}, which in turn can derive {M} and {N}, thus covering all attributes.

Question 9

Given the following statements:
S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL.
S2: Given the table R (a, b, c) where a and b together form the primary key, the following is a valid table definition.
CREATE TABLE S
 a INTEGER,
 d INTEGER,
 e IN

Accepted Answer

Both S1 and S2 are FALSE.. S1 is false because while a foreign key can enforce referential integrity, it cannot always be replaced by a check constraint, which has different limitations. S2 is also false because the primary key defined on column 'd' does not include 'a' or 'b', which are necessary for proper referencing to the primary key of table R.

Question 10

Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links.

[S1] The computational overhead in link state protocols is higher than in distance vector protocols.
[S2] A distance vector protocol (

Accepted Answer

S1 and S3 are true, but S2 is false.. Link state protocols require more computational resources because they maintain a complete view of the network topology, leading to higher overhead compared to distance vector protocols, which only share information with neighbors. Additionally, link state protocols can quickly adapt to changes in the network, resulting in faster convergence after topology changes. However, distance vector protocols can indeed avoid persistent loops with techniques like split horizon, which is not a limitation of link state protocols.

Question 11

Which of the following are used to generate a message digest by the network security protocols?
(P) RSA
(Q) SHA-1
(R) DES
(S) MD5

Accepted Answer

Q and S only. SHA-1 and MD5 are cryptographic hash functions specifically designed to produce message digests, which are used to ensure data integrity. RSA and DES, on the other hand, are encryption algorithms and do not generate message digests.

Question 12

Identify the correct order in which the following actions take place in an interaction between a web browser and a web server.
1. The web browser requests a webpage using HTTP.
2. The web browser establishes a TCP connection with the web server.
3. The web server sends the requested webpag

Accepted Answer

4,2,1,3. The correct order begins with the web browser resolving the domain name through DNS, which is necessary to find the server's IP address. Next, it establishes a TCP connection to ensure reliable communication. After the connection is established, the browser sends an HTTP request for the webpage, and finally, the server responds by sending the requested webpage back to the browser.

Question 13

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

Accepted Answer

r2(x); w2(x); r3(x); r1(x); w1(x). The correct option is conflict serializable because it can be transformed into a serial schedule without violating the order of conflicting operations. In this case, the writes and reads are arranged such that the dependencies between transactions do not create cycles, allowing for a consistent execution order.

Question 14

Let L be a language and L̄ be its complement. Which one of the following is NOT a viable possibility?

Accepted Answer

Both L and L̄ are r.e. but not recursive.. Option C is not viable because if both L and its complement L are recursively enumerable but not recursive, it would imply that neither can be decided, leading to a contradiction with the properties of recursive languages.

Question 15

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

Accepted Answer

(A). If a polynomial time algorithm exists for the largest clique problem, which is NP-complete, it implies that all problems in NP can also be solved in polynomial time, thus making P equal to NP. This situation is accurately represented in option (A), where NP-complete problems are a subset of P.

Question 16

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

Accepted Answer

3, 0, and 1. The maximum chain length is 3 because the keys 5, 15, and 33 all hash to the same slot, creating the longest chain. The minimum chain length is 0 since some slots remain empty after all insertions. The average chain length is 1, calculated by dividing the total number of keys by the number of non-empty slots.

Question 17

Consider the following C function in which size is the number of elements in the array E:

int MyX(int *E, unsigned int size)
{
 int Y = 0;
 int Z;
 int i, j, k;

for(i = 0; i < size; i++)
 Y = Y + E[i];

for(i = 0; i < size; i++)
 for(j = i; j < size; j++)
 {
 Z = 0;
 for(k = i; k <= j;

Accepted Answer

maximum possible sum of elements in any sub-array of array E.. The function calculates the maximum sum of all possible contiguous sub-arrays by iterating through each possible sub-array and comparing their sums to find the highest one, which is stored in Y.

Question 18

Consider the following pseudo code. What is the total number of multiplications to be performed?

D = 2
for i = 1 to n do
 for j = i to n do
 for k = j + 1 to n do
 D = D * 3

Accepted Answer

One-sixth of the product of the 3 consecutive integers.. The correct option is right because the nested loops iterate in such a way that the total number of multiplications corresponds to the combination of choosing 3 distinct integers from a set of n, which mathematically is represented as n(n-1)(n-2)/6, equating to one-sixth of the product of three consecutive integers.

Question 19

An access sequence of cache block addresses is of length N and contains unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of

Accepted Answer

1/N. The miss ratio is determined by the proportion of unique accesses to the total number of accesses. Since there are N unique block addresses and each access is unique, the miss ratio simplifies to 1/N, indicating that each access results in a cache miss until the cache can accommodate the accessed blocks.

Question 20

An ordered n-tuple (d₁, d₂,..., dₙ) with d₁ ≥ d₂ ≥... ≥ dₙ is called graphic if there exists a simple undirected graph with n vertices having degrees d₁, d₂,..., dₙ respectively. Which of the following 6-tuples is NOT graphic?

Accepted Answer

(3, 3, 3, 1, 0, 0). The 6-tuple (3, 3, 3, 1, 0, 0) is not graphic because the sum of the degrees (10) is odd, which violates the Handshaking Lemma that states the sum of the degrees of a graph must be even, as each edge contributes two to the total degree count.

Question 21

Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE ?

Accepted Answer

(~(p ↔ q) ∧ r) ∨ (p ∧ q ∧ ~r). The correct option is true because it captures the scenario where exactly two of the variables are true: it allows for the case where p and q are true while r is false, and also the case where p and r are true while q is false, ensuring that only two variables are true at any time.

Question 22

Consider the following minterm expression for F:
F(P,Q,R,S) = Σ 0, 2, 5, 7, 8, 10, 13, 15
The minterms 2, 7, 8 and 13 are ‘do not care’ terms. The minimal sum-of-products form for F is

Accepted Answer

Q̅ S̅ + Q S. The correct option, Q̅ S̅ + Q S, represents a simplified form of the function F by combining the relevant minterms while utilizing the 'do not care' conditions to eliminate unnecessary terms, thus achieving minimal representation.

Question 23

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.

f (x, y, a, b)
{
 if (x is 1) y = a;
 else y = b;
}

Which one of the following digital logic blocks is the most suitable for implementing this fun

Accepted Answer

Multiplexor. The function described selects between two inputs, a and b, based on the value of x, which is characteristic of a multiplexor. A multiplexor routes one of its multiple inputs to the output depending on the control signal, making it the most suitable choice for this logic function.

Question 24

Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency.

P1: Four-stage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with

Accepted Answer

P3. Peak clock period is set by the slowest stage: P1=2ns, P2=1.5ns, P3=1ns, P4=1.1ns. P3 has the smallest maximum stage latency (1ns), giving the highest peak clock frequency (1 GHz).

Question 25

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Accepted Answer

O(n²). Choosing the central element as the pivot in quicksort can lead to unbalanced partitions, especially if the array is already sorted or nearly sorted, resulting in a worst-case scenario where the algorithm behaves like selection sort, thus having a time complexity of O(n²).

Question 26

Let Σ be a finite non-empty alphabet and let 2^Σ* be the power set of Σ*. Which one of the following is TRUE ?

Accepted Answer

2^Σ* is uncountable and Σ* is countable. The set Σ* consists of all finite strings over a finite alphabet Σ, making it countable since it can be listed. However, the power set 2^Σ*, which includes all possible subsets of Σ*, is uncountable, as it has a greater cardinality than Σ* itself.

Question 27

One of the purposes of using intermediate code in compilers is to

Accepted Answer

increase the chances of reusing the machine-independent code optimizer in other compilers.. Using intermediate code allows for a separation between the front-end and back-end of the compiler, enabling the machine-independent code optimizer to be reused across different compilers, thus enhancing efficiency and reducing development time.

Question 28

Which of the following statements are CORRECT?
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.
2) Automatic garbage collection is essential to implement recursion.
3) Dynamic allocation of activation records is essential to implement recursi

Accepted Answer

1 and 3 only. Static allocation of data areas does indeed hinder recursion because it limits the ability to create new activation records for each recursive call. Additionally, dynamic allocation of activation records is crucial for recursion, as it allows each call to maintain its own state without overwriting previous calls.

Question 29

In the context of modular software design, which one of the following combinations is desirable?

Accepted Answer

High cohesion and low coupling. High cohesion within a module means that its components are closely related and work together effectively, while low coupling between modules indicates that they are independent and can function without relying heavily on each other. This combination enhances maintainability, scalability, and reusability in software design.

Question 30

What is the optimized version of the relation algebra expression πA1(πA2(σF1(σF2(r)))), where A1, A2 are sets of attributes in r with A1 ⊆ A2 and F1, F2 are Boolean expressions based on the attributes in r?

Accepted Answer

πA1(σ(F1∧F2)(r)). The correct option is optimized because it first applies the selection of both conditions F1 and F2 together, which reduces the dataset before projecting only the attributes in A1. This minimizes the amount of data processed in the projection step, making the operation more efficient.

Question 31

A prime attribute of a relation scheme R is an attribute that appears

Accepted Answer

in some candidate key of R.. A prime attribute is defined as an attribute that is part of at least one candidate key, which means it plays a crucial role in uniquely identifying tuples within the relation.

Question 32

In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

Accepted Answer

Data Link Layer and Bit synchronization. The Data Link Layer primarily focuses on node-to-node data transfer and error detection, while bit synchronization is more closely associated with the Physical Layer, which handles the transmission of raw bit streams over a physical medium.

Question 33

A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

Accepted Answer

0111110101. The correct option is right because in bit-stuffing, a '0' is inserted after every sequence of five consecutive '1's to prevent confusion with the delimiter. The output string 01111100101 contains a stuffed '0' after the five '1's, indicating that the original input string must have been 0111110101.

Question 34

Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP v4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D?
(i) TTL (ii) Checks

Accepted Answer

(i), (ii) and (iii). All three fields can change during the transmission of an IP datagram. The Time to Live (TTL) decreases as the packet traverses routers, the Checksum is recalculated at each hop to ensure data integrity, and the Fragment Offset may change if the datagram is fragmented during transmission.

Question 35

An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address 131.23.151.76. The router’s routing table has the following entries:
Prefix — Output Interface Identifier
131.16.0.0 /12 — 3
131.28.0.0 /14 — 5
131.19.0.0 /16 — 2
131.22.0.0 /15 — 1
The identifie

Accepted Answer

1. 131.23 in binary is 10000011.00010111. The /15 entry 131.22.0.0 masks to 10000011.0001011x, and 131.23 (...0001011 1) matches it, so it qualifies; the /12 entry also matches but /15 is longer. Among the four entries only /12 and /15 match, and longest-prefix routing chooses /15, giving output interface 1 (index 3).

Question 36

An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fields in the header of the third IP fragment generated by the router for this packet are

Accepted Answer

MF bit: 0; Datagram Length: 1444; Offset: 370. Payload = 4404 - 20 = 4384 bytes, split into 1480 + 1480 + 1424. The third fragment carries 1424 data bytes, total length 1424 + 20 = 1444, byte offset 2960 so fragment offset 2960/8 = 370, and MF = 0 since it is last. That is option (A), not the stored option.

Question 37

Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation.

employee (empId, empName, empAge)
dependent (depId, eId

Accepted Answer

all of his/her dependents.. The query subtracts the empIds of employees who have at least one dependent younger than or equal to them from the set of all empIds, resulting in only those employees whose age is greater than that of all their dependents.

Question 38

Consider the decision problem 2CNFSAT defined as follows:
{ Φ | Φ is a satisfiable propositional formula in CNF with at most two literals per clause }
For example, Φ = (x1 ∨ x2) ∧ (x1 ∨ x̄3) ∧ (x2 ∨ x4) is a Boolean formula and it is in 2CNFSAT.
The decision problem 2CNFSAT is

Accepted Answer

solvable in polynomial time by reduction to directed graph reachability.. The correct option is right because 2CNFSAT can be transformed into a directed graph problem where the satisfiability of the formula corresponds to finding a path in the graph, allowing it to be solved efficiently in polynomial time.

Question 39

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

Accepted Answer

(97 × 97 × 97)/100³. The correct option calculates the probability that each of the first three slots remains unfilled after three insertions, assuming uniform hashing. Since there are 100 slots and 97 of them are available for each insertion, the probability for each of the three slots to remain unfilled is (97/100), leading to (97 × 97 × 97)/100³.

Question 40

Consider the pseudocode given below. The function DoSomething() takes an argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

typedef struct treeNode* treeptr;

struct treeNode
{
 treep

Accepted Answer

number of leaf nodes in the tree.. The function counts leaf nodes by checking if a node has no children (leftMostChild is NULL) and returns 1 for each leaf. It recursively processes the leftmost child and right sibling, ensuring all leaf nodes are counted.

Question 41

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

int ProcessArray(int *listA, int x, int n)
{
 int i, j, k;
 i = 0;
 j = n-1;
 do {
 k = (i+j)/2;
 if (x <= listA[k])
 j = k-1;
 if (listA[k] <= x)
 i = k+1;
 }while (i <=

Accepted Answer

It is an implementation of binary search.. The function uses a divide-and-conquer approach to efficiently search for the element x within the sorted array listA, which is characteristic of binary search. It repeatedly narrows down the search range by comparing x with the middle element until it either finds x or determines that it is not present.

Question 42

Consider the set of all functions f: {0,1,..., 2014} → {0,1,..., 2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements:
P. For each such function it must be the case that for every i, f(i) = i.
Q. For each such function it must be the case that for some i, f(

Accepted Answer

Only Q and R are true. Statement Q is true because if f(f(i)) = i, then there must be at least one value i for which f(i) equals i, indicating a fixed point. Statement R is also true since the function must map every element in the domain to an element in the codomain, ensuring that it is onto. However, statement P is false because it is possible for f(i) to be different from i while still satisfying f(f(i)) = i.

Question 43

If G is a forest with n vertices and k connected components, how many edges does G have?

Accepted Answer

n − k. In a forest, which is a collection of trees, the number of edges is always one less than the number of vertices in each connected component. Therefore, for k components, the total number of edges is n (the total number of vertices) minus k (the number of components), resulting in n - k.

Question 44

The CORRECT formula for the sentence, "not all rainy days are cold" is

Accepted Answer

∃d (Rainy(d) ∧ ~Cold(d)). The correct option indicates that there exists at least one day that is rainy and not cold, which accurately reflects the meaning of the original sentence that not all rainy days are cold.

Question 45

Consider the following relational schema:
employee(empId, empName, empDept)
customer(custId, custName, salesRepId, rating)

salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following quer

Accepted Answer

Names of all the employees with all their customers having a 'GOOD' rating.. The query checks for employees who do not have any customers with a rating other than 'GOOD'. Therefore, it returns the names of employees whose customers all have a 'GOOD' rating.

GATE Technical: COMPUTER – CS questions with solutions

Questions