HPSC Polytechnic Lecturer 2022: Lecturer (Technical Education) Screening Test, Computer Engineering (Advt. No. 11/2021)
Text of page 1
DO NOT OPEN THE SEAL UNTIL INSTRUCTED TO DO SO
Question Booklet No.
QUESTION BOOKLET
COMPUTER ENGINEERING
Booklet Series
A
Roll No.
(Enter your Roll number in the above space)
Time Allowed : 2 Hours Maximum Marks : 100
INSTRUCTIONS FOR CANDIDATES
1. IMMEDIATELY AFTER THE COMMENCEMENT OF THE EXAMINATION, YOU SHOULD CHECK THAT
THIS QUESTION BOOKLET DOES NOT HAVE ANY UNPRINTED OR TORN OR MISSING PAGES OR
QUESTIONS ETC. IF SO, GET IT REPLACED BY A COMPLETE QUESTION BOOKLET.
2. Please note that it is the candidate’s responsibility to encode and fill in the Roll Number and
Question Booklet Series Code A, B, C or D carefully and without any omission or discrepancy at
the appropriate places in the OMR Answer Sheet. Any omission/discrepancy will render the
OMR Answer Sheet liable for rejection.
3. This Question Booklet contains 100 questions. Each question is printed in English only. Each
question comprises four responses (answers). You will select the response which you want to
mark on the OMR Answer Sheet. In case you feel that there is more than one correct response,
mark the response which you consider the best. In any case, choose ONLY ONE response for
each question.
4. You have to mark all your responses ONLY on the separate OMR Answer Sheet provided. See
Instructions at the backside of the OMR Answer Sheet.
5. All questions carry equal marks.
6. Before you proceed to mark in the OMR Answer Sheet the response to various questions in the
Question Booklet, you have to fill in some particulars in the OMR Answer Sheet as per
instructions mentioned on the OMR Answer Sheet.
7. After you have completed filling in all your responses on the OMR Answer Sheet and the
examination has concluded, you should hand over to the Invigilator only the OMR Answer
Sheet. You are permitted to take away with you the Question Booklet, along with candidate’s
copy of OMR Answer Sheet.
8. Sheets for rough work are appended in the Question Booklet at the end.
9. Penalty for wrong answers :
THERE WILL BE PENALTY FOR WRONG ANSWERS MARKED BY A CANDIDATE AS UNDER.
(i) There are four alternatives for the answer to every question. For each question for which
a wrong answer has been given by the candidate, 0.25 mark assigned to that question will
be deducted as penalty.
(ii) If a candidate gives more than one answer, it will be treated as a wrong answer even if one
of the given answers happens to be correct and there will be same penalty as above to that
question.
(iii) If a question is left blank, i.e., no answer is given by the candidate, there will be no penalty
for that question.
DO NOT OPEN THE SEAL UNTIL INSTRUCTED TO DO SO
Computer Engineering /5- A
Text of page 2
1. The binary equivalent of (1011·011)10 5. In a k-way set associative cache,
is equal to the cache is divided into v sets,
[A] 11·375 each of which consists of k lines.
The lines of a set are placed in
[B] 10·123
sequence one after another. The
[C] 11·175 lines in set s are sequenced before
[D] 9·234 the lines in set (s+1). The main
memory blocks are numbered from
2. The following switching functions 0 onwards. The main memory
are to be implemented using a block numbered j must be mapped
decoder : to any one of the cache lines from
f1 = m (1, 2, 4, 8, 10, 14), f2 = m (2,
[A] ( j mod v)* k to ( j mod v) * k+(k–1)
5, 9, 11), f3 = m (2, 4, 5, 6, 7).
The minimum configuration of the [B] ( j mod v) to ( j mod v) + (k–1)
decoder will be
[C] ( j mod k) to ( j mod k) + (v–1)
[A] 2 to 4 line
[B] 3 to 8 line [D] ( j mod k) * v to ( j mod k) * v + (v–1)
[C] 4 to 16 line
6. The main virtue for using single
[D] 5 to 32 line Bus structure is
3. The parallel outputs of a counter [A] fast data transfers
circuit represent the
[B] cost effective connectivity and
[A] parallel data word
speed
[B] clock frequency
[C] counter modulus [C] cost effective connectivity and
ease of attaching peripheral
[D] clock count devices
4. The figure shows a digital circuit [D] cheaper in price
constructed using negative edge
triggered J-K flip flops. Assume a 7. Consider three different processors
starting state of Q2Q1Q0=000. P1, P2, P3 executing the same
This state Q2Q1Q0=000 will repeat instruction set. P1 has a 3 GHz
after _____ number of cycles of the clock rate and a CPI of 1·5. P2 has
clock CLK. a 2·5 GHz clock rate and a CPI of
1·0. P3 has a 4 GHz clock rate and
a CPI of 2·2. If each processor
executes a program in 10 seconds,
find the number of instructions
executed by the processors.
[A] 18*10^3, 13*10^2, 17*10^5
[A] 4
[B] 8 [B] 20*10^9, 25*10^9, 18·18*10^9
[C] 16 [C] 18*10^4, 25*10^1, 20*10^3
[D] 6
[D] 3*10^1, 15*10^2, 2·5*10^3
Computer Engineering/5- A 2
Text of page 3
8. A 50 kbps device is connected to a 11. The post-order traversal of a binary
processor. The interrupt overhead is tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The in-
50 sec. The minimum performance order traversal of the same tree is
achieved when interrupt is initiated 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of
and data transferred is used instead a tree is the length of the longest
of programmed I/O is path from the root to any leaf. The
[A] 2·4 height of the binary tree above is
[B] 0·4 [A] 3
[C] 3 [B] 5
[D] 3·5 [C] 4
[D] 2
9. What will be the output printed by
the following C program? 12. N items are stored in a sorted
void main() doubly linked list. For a delete
operation, a pointer is provided to
{
the record to be deleted. For a
int x=1, i, y=2; decrease-key operation, a pointer
for (i=0; i<5; i++) is provided to the record on
{ which the operation is to be
x<<1; performed. An algorithm performs
the following operations on
y=x+i;
the list in this order: (N)delete,
} O(logN)insert, O(logN)find and
printf(‘‘%d, %d’’, x,y); (N)decrease-key. What is the
} time complexity of all these
[A] 1, 5 operations put together?
[B] 32, 5 [A] O(log 2N)
[C] 1, 72 [B] O(N)
[D] 32, 72 [C] O(N2)
[D] (N2logN)
10. Suppose, a circular queue of capacity
(n–1) elements is implemented with 13. What is the maximum number of
an array of n elements. Assume edges in a bipartite graph having
that the insertion and deletion 10 vertices?
operations are carried out using [A] 24
REAR and FRONT as array index [B] 21
variables respectively. Initially, [C] 25
REAR = FRONT = 0. The conditions [D] 16
to detect queue full and queue
empty are 14. If the array A contains the items
[A] full:(REAR+1) mod n ==FRONT 10, 4, 7, 23, 67, 12 and 5 in that
empty:REAR ==FRONT order, what will be the resultant
array A after third pass of
[B] full:(REAR+1) mod n==FRONT
insertion sort?
empty:(FRONT+1) mod n==REAR
[A] 67, 12, 10, 5, 4, 7, 23
[C] full:REAR==FRONT
[B] 4, 7, 10, 23, 67, 12, 5
empty:(REAR+1) mod n==FRONT
[C] 4, 5, 7, 67, 10, 12, 23
[D] full:(FRONT+1) mod n==REAR
empty:REAR==FRONT [D] 10, 7, 4, 67, 23, 12, 5
Computer Engineering /5- A 3 [ P.T.O.
Text of page 4
15. Which one of the following hash 19. An array of 25 distinct elements is
functions on integers will to be sorted using quicksort.
distribute keys most uniformly Assume that the pivot element is
over 10 buckets numbered 0 to 9 chosen uniformly at random. The
for i ranging from 0 to 2020? probability that the pivot element
[A] h(i)=i2 mod 10 gets placed in the worst possible
location in the first round of
[B] h(i)=i3 mod 10
partitioning (rounded off to 2
[C] h(i)=(11*i2) mod 10 decimal places) is
[D] h(i)=(12*i) mod 10 [A] 0·5
[B] 0·7
16. What happens when a top-down
approach of dynamic programming [C] 0·9
is applied to any problem? [D] 0·08
[A] It increases both the time
complexity and the space 20. Which of the following CFG’s
complexity cannot be simulated by an FSM?
[B] It increases the space [A] SSa|b
complexity and decreases the [B] SaSb|ab
time complexity [C] SabX, XcY, Yd|aX
[C] It increases the time [D] SSb|a
complexity and decreases the
space complexity 21. What is the pumping length of
[D] It decreases both the time string of length x?
complexity and the space [A] x+1
complexity
[B] x
17. Let G be a complete undirected [C] x–1
graph on 4 vertices, having 6 edges [D] x2
with weights being 1, 2, 3, 4, 5 and
6. The maximum possible weight 22. Consider the languages L1= and
that a minimum weight spanning L2={a}. Which of the following
tree of G can have is represents L1 L2* U L1* ?
[A] 5 [A] {}
[B] 8 [B] {}
[C] 7 [C] {}
[D] 20 [D] {}
18. The Floyd-Warshall algorithm for 23. Access time of the symbol table
all-pair shortest paths computation will be logarithmic, if it is
is based on implemented by
[A] Greedy paradigm [A] Linear list
[B] Divide-and-Conquer paradigm [B] Search Tree
[C] Dynamic Programming paradigm [C] Hash Table
[D] Heuristics [D] Self-organization list
Computer Engineering/5- A 4
Text of page 5
24. Which one of the following is a 28. How are system calls invoked?
top-down parser?
[A] By a privileged instruction
[A] Recursive descent parser
[B] Operator precedence parser [B] With an indirect jump
[C] An LR(k) parser [C] Through a software interrupt
[D] An LALR(k) parser [D] Through polling
25. Whenever a procedure is
executed, its activation record is 29. The time required to create a new
stored on the stack, also known as thread in an existing process is
[A] Access Stack [A] greater than the time required
[B] Control Stack to create a new process
[C] Formal Stack [B] less than the time required to
[D] Return Stack create a new process
[C] equal to the time required to
26. Consider the following translation
create a new process
scheme :
SER [D] double the time required to
create a new process
R*E{print(‘‘*’’);}R|
EF+E{print(“+”);}|F 30. Consider the following snapshot of
F(S)|id{print(id.value);} a system running n concurrent
Here id is a token that represents processes. Process i is holding Xi
an integer and id.value represents instances of a resource R, 1 i n.
the corresponding integer value. Assume that all instances of R are
For an input ‘2 * 3 + 4’, this currently in use. Further, for all i,
translation scheme prints process i can place a request for at
most Yi additional instances of R
[A] 2 * 3 + 4
while holding the Xi instances it
[B] 2 * + 3 4 already has. Of the n processes,
[C] 2 3 * 4 + there are exactly two processes p
[D] 2 3 4 + * and q such that Yp = Yq = 0.
Which one of the following
27. What is the maximum number of conditions guarantees that no
reduce moves that can be taken by other process apart from p and q
a bottom-up parser for a grammar can complete execution?
with no epsilon-production and
unit-production (i.e., of type A [A] Xp+Xq<Min{Yk|1 k n, kp, kq}
and Aa) to parse a string with n
tokens? [B] Xp+Xq<Max{Yk|1 k n, kp, kq}
[A] n/2 [C] Min(Xp,Xq) Min{Yk|1kn, kp,
[B] n-1 kq}
[C] 2n-1 [D] M i n ( X p , X q ) M a x { Y k | 1 kn ,
[D] 2n kp, kq}
Computer Engineering /5- A 5 [ P.T.O.
Text of page 6
31. Consider three concurrent processes 34. An ER model of a database consists
P1, P2 and P3 as shown below, of entity types A and B. These are
which access a shared variable D connected by a relationship R
that has been initialized to 100 : which does not have its own
P1::D=D+20 P2::D=D+50 P3::D=D+10 attribute. Under which one of the
The processes are executed on a following conditions can the
uniprocessor system running a relational table for R be merged
time-shared operating system. If the with that of A?
minimum and maximum possible [A] Relationship R is one-to-many
values of D after the three processes and the participation of A in R
have completed execution are X and is total
Y respectively, then the value of
[B] Relationship R is one-to-many
Y–X is
and the participation of A in R
[A] 110
is partial
[B] 20
[C] Relationship R is many-to-one
[C] 80
and the participation of A in R
[D] 10
is total
32. If we preempt a resource from a
[D] Relationship R is many-to-one
process, the process cannot and the participation of A in R
continue with its normal execution is partial
and it must be
[A] aborted 35. Consider a database table T
[B] rolled back containing two columns X and Y
[C] terminated each of type integer. After the
[D] queued creation of the table, one record
(X=1, Y=1) is inserted in the table.
33. Consider the following four
Let MX and MY denote the
processes with arrival times (in
respective maximum values of X
milliseconds) and their lengths of
and Y among all records in the
CPU bursts (in milliseconds) as
table at any point in time. Using
shown below :
MX and MY, new records are
Process P1 P2 P3 P4 inserted in the table 128 times
with X and Y values being MX+1,
Arrival time 0 1 3 4
2*MY+1 respectively. It may be
CPU burst time 3 1 3 Z noted that each time after the
insertion, values of MX and MY
These processes are run on a
change. What will be the output of
single processor using preemptive
the following SQL query after the
Shortest Remaining Time First
steps mentioned above are carried
scheduling algorithm. If the
out?
average waiting time of the
processes is 1 millisecond, then SELECT Y FROM T WHERE X=7
the value of Z is [A] 127
[A] 3
[B] 255
[B] 2
[C] 5 [C] 129
[D] 7 [D] 257
Computer Engineering/5- A 6
Text of page 7
36. The employee information in a 38. A link has a transmission speed of
company is stored in the relation 106 bits/sec. It uses data packets of
size 1000 bytes each. Assume that
Employee (name, sex, salary,
the acknowledgement has negligible
deptName)
transmission delay and that its
Consider the following SQL query propagation delay is the same as the
data propagation delay. Also assume
select deptName
that the processing delays at the
from Employee nodes are negligible. The efficiency
of the stop-and-wait protocol in this
where sex = ‘M’ setup is exactly 25%. The value of
group by deptName the one-way propagation delay
(in milliseconds) is
having avg (salary) > (select avg [A] 10
(salary) from Employee) [B] 24
It returns the names of the [C] 12
department in which [D] 05
39. Determine the maximum length of
[A] the average salary is more
the cable (in km) for transmitting
than the average salary in the
data at a rate of 500 Mbps in an
company
Ethernet LAN with frames of size
[B] the average salary of male 10000 bits. Assume the signal speed
employees is more than the in the cable to be 200000 km/s.
average salary of all male [A] 1
employees in the company [B] 2
[C] 2·5
[C] the average salary of male
[D] 5
employees is more than the
average salary of employees in 40. Consider a source computer(S)
the same department transmitting a file of size 106 bits to
a destination computer(D)over a
[D] the average salary of male network of two routers (R1 and R2)
employees is more than the and three links (L1, L2 and L3).
average salary in the company L1connects S to R1; L2 connects R1
to R2; and L3 connects R2 to D. Let
each link be of length 100 km.
37. How many 8-bit characters can be Assume signals travel over each
transmitted per second over a link at a speed of 108 meters per
9600 baud serial communication second. Assume that the link
link using asynchronous mode of bandwidth on each link is 1 Mbps.
transmission with one start bit, Let the file be broken down into
eight data bits, two stop bits and 1000 packets each of size 1000 bits.
one parity bit? Find the total sum of transmission
and propagation delays in
[A] 600
transmitting the file from S to D.
[B] 800 [A] 1005 ms
[B] 1010 ms
[C] 876
[C] 3000 ms
[D] 120 [D] 3003 ms
Computer Engineering /5- A 7 [ P.T.O.
Text of page 8
41. Consider an IP packet with a 46. The SIMD is an organization which
length of 4500 bytes that includes [A] contains a lot of processing
a 20-byte IPv4 header and a units under the common
40-byte TCP header. The packet is control unit supervision
forwarded to an IPv4 router that [B] is capable of processing many
supports a Maximum Transmission programs at one time
Unit (MTU) of 600 bytes. Assume [C] contains an individual computer
that the length of the IP header in having control unit, processing
all the outgoing fragments of this unit and a memory unit
packet is 20 bytes. Assume that [D] All of the above
the fragmentation offset value 47. The rotational latency required in
stored in the first fragment is 0. reading a block of data from a disk
The fragmentation offset value to memory along with seek time
stored in the third fragment is and transfer time is
[A] 144 [A] the total time required for the
[B] 255 platter to rotate the right
[C] 102 sector under the head
[D] 124 [B] the total time required for
42. In the IPv4 addressing format, the read and write head to move in
number of networks allowed under the correct position over the
Class C addresses is appropriate track
[A] 2^14 [C] the total time required for the
platter to complete its full
[B] 2^7
rotation
[C] 2^21
[D] None of the above
[D] 2^24
48. Which among the following bits is
43. Let Z = [aij] which is given by used when the cache location is
abij = (i–j)3. Z is denoted by updated?
[A] symmetric matrix [A] Flag bit
[B] anti-symmetric matrix [B] Reference bit
[C] Update bit
[C] identity matrix
[D] Dirty bit
[D] None of the above
49. When a subroutine is called, the
44. What is the mean value (mv) in a address of the instruction
Poisson Distribution, such that ‘t’ following the CALL instructions is
is the number of trials and ‘s’ is stored in/on the
the probability of success? [A] Stack
[A] mv = ts [B] Accumulator
[B] mv = (ts)2 [C] Program Counter (PC)
[C] mv = ts(1–s) [D] Stack pointer
[D] mv = s 50. For a given priority queue, what is
the time complexity to insert a
45. Which among the following logic
node based on some position?
gates are known as universal gates?
[A] O(nlogn)
[A] XOR, NAND, OR
[B] OR, NOT, XOR [B] O(logn)
[C] NOR, NAND, XNOR [C] O(n2)
[D] NOR, NAND [D] O(n)
Computer Engineering/5- A 8
Text of page 9
51. Convert the infix expression to 56. What is the total number of states
postfix expression that are required to automate the
‘‘a+(b*c(d/e^f )*g)*h)’’ given expression i.e. {a,b}*{aba}{a,b}*
using finite automata?
[A] ab*cdef/^*g-h+
[A] 4
[B] abcdef^/*g*h*+
[B] 3
[C] abcd*^ed/g*-h*+
[C] 5
[D] abc*de^fg/*-*h+
[D] 6
52. Dijkstra’s algorithm follows
[A] Greedy algorithm 57. Find the non-context free
[B] Branch and bound language among the following.
[C] Back tracking [A] L = {R|{0,1}*}
[D] Dynamic programming [B] L = {p^nq^n|n0}
53. Given an alphabet , a regular [C] L = {|{0,1}*}
language is a language which is [D] L = {p^nq^mr^ms^n|n, m0}
not obtained from the basic
languages by using which of the 58. The Bottom-up parsing method is
following operations? also called
[A] Union [A] Predictive parsing
[B] Concatenation [B] Shift reduce parsing
[C] Kleene* [C] Recursive descent parsing
[D] All of the above [D] None of the above
54. Lang1 = {x|x does not contain the
string ‘pg’} 59. Which FSA concept is used in the
compiler?
Lang2 = {x|x contains the string
‘pg’} [A] Code optimization
Given = {p, g}, what is the [B] Code generation
difference of the minimum number [C] Lexical analysis
of states that is required to form [D] Parser
Lang1 and Lang2?
[A] 0 60. Find out the most powerful parsers.
[B] 1 [A] SLR
[C] 2 [B] LALR
[D] Not determined [C] Canonical LR
55. Given an expression L(G)={w in [D] Operator-precedence
T*|S*w}, find out the total number
of incorrect notations or symbols, 61. Given a string of tokens; which of
such that changing them would the following is the method of
make the expression correct. finding a parse?
[A] 0 Error [A] Analysing
[B] 1 Error [B] Recognizing
[C] 2 Errors [C] Parsing
[D] Invalid Expression [D] Tokenizing
Computer Engineering /5- A 9 [ P.T.O.
Text of page 10
62. Which among the following is used 67. Select one statement which
to group the characters into contains error.
tokens? [A] select* from stock where
[A] Parser stockid = 10008
[B] Code generator [B] select stockid from stock
[C] Lexical analyser where stockid = 10003
[D] None of the above [C] select stockid from stock
[D] select stockid where
63. In the translation process,
stockid = 10005 and
compiler always reports the Lastname = ‘johnson’
existence of which of the
following? 68. Choose the correct expression from
[A] Objects the following for maximum children
[B] Classes of a B-tree having order m.
[C] Errors [A] m/2
[D] Text [B] m –1
[C] m
64. What is the exact location of
[D] m+1
operating system in the memory?
[A] Either low or high memory 69. It is stated that every time an
(depending on the location of attribute X is appeared, the same
interrupt vector) value of Y is matched and a
[B] In the low memory different value of Z is matched.
Thus, it is clear that
[C] In the high memory
[A] XY
[D] None of the above
[B] XZ
65. The technique of copying a process [C] X(Y,Z)
from main memory to secondary
[D] (Y,Z)X
memory based on requirement is
called 70. Which of the following is the
[A] Demand paging characteristic of distributed
[B] Paging database?
[C] Threads [A] It is a single logical database
[D] Segmentation which is limited to only one
location
66. Find out the reference to the [B] It is a loose collection of file
associative memory. which is limited to only one
[A] The data address is generated location
by the CPU [C] It is a loose collection of file
[B] The data address of the data is that is spread to multiple
supplied by the users locations and is
[C] The data itself is used as an interconnected by a network
address and there is no need [D] A single logical database that
for an address is spread to multiple locations
[D] The data are accessed and is interconnected by a
sequentially network
Computer Engineering/5- A 10
Text of page 11
71. Identify the device from the 75. If a processor clock is rated as
following options that usually links 1250 million cycles per second,
two homogeneous packed then its clock period is
broadcast local networks. [A] 1·9*10^–10 sec
[B] 1·6*10^–9 sec
[A] A Hub [C] 1·25*10^–10 sec
[D] 8*10^–10 sec
[B] A Router
76. A program consists of four major
[C] A Bridge types of instructions. The
instructions mix and the CPI for
[D] A Gateway each instruction type are given in
the following table. If the clock
72. Find the transmission rate of frequency of the processor is
circuit of the TDM where a link 400 MHz, what is the average CPI
transmits 4000 frames per second of the processor?
and each slot has 8 bits
Instruction Type CPI Instruction Mix
respectively. TDM is
Arithmetic and Logic 1 60%
[A] 32 kbps Load/Store with cache
2 18%
[B] 500 bps hit
Branch 4 12%
[C] 500kbps Memory reference with
8 10%
[D] 32 bps cache miss
[A] 3·75
73. There is a point where secure [B] 2·24
internal network and untrusted [C] 1·87
external network meet and a [D] 1·54
firewall is installed at this point. 77. A hypothetical control unit
This is known as supports 5 groups of mutually
exclusive control signals. The
[A] Chokepoint number of bits that can be saved
[B] Meeting point using vertical approach compared
to horizontal is
[C] Firewall point Groups G1 G2 G3 G4 G5
[D] Securepoint #control signals 1 5 7 15 8
[A] 22
74. Choose the correct expression [B] 36
from the following for the length of [C] 14
UDP datagram. [D] 4
78. A device has been used in cycle
[A] UDP length = IP length – IP stealing mode of DMA. A word of
header’s length 4 bytes can be transferred when it
is available. The memory cycle
[B] UDP length = UDP length –
time is 40 ms and CPU is idle for
UDP header’s length
10% of its time. What is the data
[C] UDP length = IP length + IP transfer rate of the device?
header’s length [A] 1011 bits/sec
[B] 11.11 B/sec
[D] UDP length = UDP length + [C] 12.33 B/sec
UDP header’s length [D] 2048 B/sec
Computer Engineering /5- A 11 [ P.T.O.
Text of page 12
79. Consider the following C program. 81. What is the output of the BFS
traversal of the graph below?
struct listnode
{
int data;
struct listnode *next;
}
void fun (struct listnode *head);
{
if(head= = NULL || head next ==
[A] A F D B C E
NULL) return;
[B] C B A F D
struct listnode *tmp = head
[C] A B D C F
next;
[D] F D C B A
head next = tmp next;
free (tmp); 82. Let A be an array of 31 numbers
fun (head next); consisting of a sequence of 0’s
followed by a sequence of 1’s. The
}
problem is to find the smallest
What is the functionality of the index i such that A[i] is 1 by
above function? probing the minimum number of
[A] It reverses the linked list locations in A. The worst-case
[B] It deletes the linked list number of probes performed by an
optimal algorithm is
[C] Alternate nodes will be
deleted [A] 8
[D] It reverses the linked list and [B] 4
deletes alternate nodes [C] 5
[D] 10
80. Five items P, Q, R, S and T are
pushed onto a stack one after 83. There are n unsorted arrays :
another starting from P. The stack A1, A2, ..., An. (Assume that n is odd)
is popped four times and the Each of A1, A2, ..., An contains n
popped elements are inserted into distinct elements. There are no
a queue. The two elements are common elements between any
deleted from the queue and two arrays. The worst-case time
pushed back onto the stack. Again complexity of computing the
one element is popped from the median of the medians of A1, A2,
stack. The popped item is ..., An is
[A] P [A] O(n)
[B] R [B] O(nlogn)
[C] Q [C] O(n2)
[D] S
[D] O(n2/logn)
Computer Engineering/5- A 12
Text of page 13
84. If L is a regular language over 87. Assuming P NP, which of the
= {a,b}, which one of the following following is true?
languages is not regular? [A] NP–complete = NP
[A] L·LR{xy|x L,yR L} [B] NP–complete P =
[C] NP–hard = NP
[B] Suffix(L) = {y *| x *such
[D] P = NP–complete
that xy L}
88. A lexical analyzer uses the
[C] Prefix(L) = {x *| y *such
following patterns to recognize
that xy L}
three tokens T1, T2 and T3 over the
[D] {wwR|w L} alphabet {a, b, c}.
T1:a?(b|c)*a
85. The context-free grammar T2:b?(a|c)*b
S A111|S1, A A0|00 is T3:c?(b|a)*c
equivalent to
Note that ‘x?’ means 0 or 1
[A] {0n1m|n=2,m=3} occurrence of the symbol x. Note
also that the analyzer outputs the
[B] {0n1m|n=1,m=5} token that matches the longest
possible prefix. If the string
[C] {0n1m|n should be greater than bbaacabc is processed by the
two and m should be greater analyzer, which one of the
than four} following is the sequence of tokens
it outputs?
[D] {0n1m|n should be less than
four and m should be less than [A] T1T2T3
three} [B] T1T1T3
[C] T2T1T3
86. Following context-free grammar [D] T3T3
S aB|bA 89. Consider the CFG with {S,A,B} as
the non-terminal alphabet, {a,b} as
A b|aS|bAA the terminal alphabet, S as the
start symbol and the following set
B b|bS|aBB
of production rules :
generates strings of terminals that S bA S aB
have Aa Bb
[A] equal number of a’s and b’s A aS B bS
S bAA B aBB
[B] odd number of a’s and odd
Which of the following strings is
number of b’s
generated by the grammar?
[C] even number of a’s and even [A] aaaabb
number of b’s [B] aabbbb
[D] odd number of a’s and even [C] aabbab
number of a’s [D] Abbba
Computer Engineering /5- A 13 [ P.T.O.
Text of page 14
90. Which of the following derivations 93. In which one of the following
does a top-down parser use while page replacement algorithms, it
parsing an input string? The input is possible for the page fault rate
is assumed to be scanned in left to to increase even when the
right order. number of allocated frames
increases?
[A] Leftmost derivation
[B] Leftmost derivation traced out [A] LRU (Least Recently Used)
in reverse
[C] Rightmost derivation [B] OPT (Optimal Page
Replacement)
[D] Rightmost derivation traced
out in reverse
[C] MRU (Most Recently Used)
91. Restricting the child process to a [D] FIFO (First In First Out)
subset of the parent’s resources
prevents any process from
[A] overloading the system by 94. Consider two relations R1(A,B)
using a lot of secondary storage with the tuples (1,5), (3,7) and
[B] underloading the system by R2(A,C) = (1,7), (4,9). Assume that
very less CPU utilization R(A,B,C) is the full natural outer
join of R1 and R2. Consider the
[C] overloading the system by
following tuples of the form (A,B,C):
creating a lot of sub-processes
[D] crashing the system by a = (1,5, null), b = (1,null,7),
utilizing multiple resources c = (3,null,9), d = (4,7,null), e = (1,5,7),
f = (3,7,null), g = (4,null,9).
92. A computer system has 6 tape
drives, with ‘n’ processes Which one of the following
competing for them. Each process statements is correct?
may need 3 tape drives. The
maximum value of ‘n’ for which the
system is guaranteed to be [A] R contains a, b, e, f, g but not
deadlock free is c, d
[A] 2
[B] R contains all of a, b, c, d, e, f, g
[B] 3
[C] R contains e, f, g but not a, b
[C] 4
[D] 1 [D] R contains e but not f, g
Computer Engineering/5- A 14
Text of page 15
95. Consider the relation X(P, Q, R, S, 98. Two-phase protocol in database
T, U) with the following set of management system is
functional dependencies
[A] a concurrency mechanism
F={ that is deadlock free
{P, R} {S, T}; [B] a recovery protocol used for
restoring a database after a
{P, S, U} {Q, R} crash
} [C] any update to the system log
done in 2 phases
Which of the following is the trivial
functional dependency in F+, [D] not effective in database
+
where F is closure of F?
99. A channel has a bit rate of 4 kbps
[A] {P, R} {S, T} and one-way propagation delay of
20 ms. The channel uses stop and
[B] {P, R} {R, T} wait protocol. The transmission
time of the acknowledgement
[C] {P, S} {S}
frame is negligible. To get a
[D] {P, S, U} {Q} channel efficiency of at least 50%,
the minimum frame size should be
[A] 80 bytes
96. A clustering index is defined on
the fields which are of the type [B] 80 bits
[C] 160 bytes
[A] non-key and ordering
[D] 160 bits
[B] non-key and non-ordering
[C] key and ordering 100. If a browser sends a request to
remote server to access a web page,
[D] key and non-ordering then which among the following is
the correct sequence to send the
packet over the network from a
97. In a file with 1 million records and host? (Assume that the host has
with an order of the tree being just restarted)
100, find out the maximum
[A] HTTP GET request, DNS query,
number of nodes to be accessed if
TCP SYN
B+ tree index is used.
[B] DNS query, HTTP GET request,
[A] 5 TCP SYN
[B] 4 [C] DNS query, TCP SYN, HTTP
GET request
[C] 3
[D] TCP SYN, DNS query, HTTP
[D] 10 GET request
Computer Engineering /5- A 15 [ P.T.O.
Text of page 16
SPACE FOR ROUGH WORK
Computer Engineering/5- A 16 LLL22/5—732×4
Text of page 1
Final Answer Key - Computer Engineering
Held on 11.06.2022
Series 'A'
Q.No. Ans Q.No. Ans Q.No. Ans Q.No. Ans
1 A 26 D 51 B 76 B
2 C 27 B 52 A 77 A
3 D 28 C 53 D 78 B
4 D 29 B 54 A 79 C
5 A 30 A 55 A 80 D
6 C 31 C 56 A 81 C
7 B 32 B 57 B 82 C
8 B 33 B 58 B 83 C
9 A 34 C 59 C 84 D
10 A 35 A 60 C 85 A
11 C 36 D 61 C 86 X
12 C 37 B 62 C 87 B
13 C 38 C 63 C 88 D
14 B 39 B 64 A 89 C
15 B 40 A 65 A 90 A
16 B 41 A 66 C 91 C
17 C 42 C 67 D 92 A
18 C 43 B 68 C 93 D
19 D 44 A 69 A 94 C
20 B 45 D 70 D 95 C
21 A 46 A 71 C 96 A
22 D 47 C 72 A 97 B
23 B 48 D 73 A 98 X
24 A 49 A 74 A 99 D
25 B 50 D 75 D 100 C
Text of page 2
Final Answer Key - Computer Engineering
Held on 11.06.2022
Series 'B'
Q No. Ans Q No. Ans Q No. Ans Q No. Ans
1 C 26 C 51 C 76 A
2 C 27 B 52 B 77 B
3 C 28 B 53 B 78 B
4 D 29 A 54 C 79 C
5 A 30 A 55 A 80 C
6 X 31 C 56 D 81 C
7 B 32 C 57 B 82 C
8 D 33 C 58 C 83 C
9 C 34 B 59 B 84 A
10 A 35 B 60 A 85 A
11 C 36 B 61 A 86 C
12 A 37 C 62 C 87 D
13 D 38 C 63 B 88 C
14 C 39 D 64 A 89 A
15 C 40 B 65 D 90 D
16 A 41 A 66 A 91 C
17 B 42 D 67 C 92 A
18 X 43 B 68 D 93 A
19 D 44 A 69 A 94 A
20 C 45 B 70 D 95 D
21 A 46 D 71 B 96 B
22 C 47 B 72 A 97 A
23 D 48 C 73 D 98 B
24 D 49 B 74 A 99 C
25 A 50 A 75 A 100 D
Text of page 3
Final Answer Key - Computer Engineering
Held on 11.06.2022
Series 'C'
Q No. Ans Q No. Ans Q No. Ans Q No. Ans
1 A 26 C 51 A 76 A
2 C 27 A 52 B 77 D
3 D 28 A 53 X 78 B
4 A 29 A 54 D 79 A
5 D 30 D 55 C 80 B
6 B 31 B 56 A 81 D
7 A 32 A 57 C 82 B
8 D 33 B 58 D 83 C
9 A 34 C 59 D 84 B
10 A 35 D 60 A 85 A
11 A 36 C 61 C 86 C
12 B 37 C 62 B 87 B
13 B 38 C 63 B 88 B
14 C 39 D 64 A 89 C
15 C 40 A 65 A 90 A
16 C 41 X 66 C 91 D
17 C 42 B 67 C 92 B
18 C 43 D 68 C 93 C
19 A 44 C 69 B 94 B
20 A 45 A 70 B 95 A
21 C 46 C 71 B 96 A
22 D 47 A 72 C 97 C
23 C 48 D 73 C 98 B
24 A 49 C 74 D 99 A
25 D 50 C 75 B 100 D
Text of page 4
Final Answer Key - Computer Engineering
Held on 11.06.2022
Series 'D'
Q No. Ans Q No. Ans Q No. Ans Q No. Ans
1 A 26 A 51 A 76 D
2 B 27 D 52 D 77 C
3 D 28 B 53 B 78 A
4 B 29 A 54 A 79 C
5 C 30 D 55 B 80 D
6 B 31 A 56 C 81 D
7 A 32 A 57 D 82 A
8 C 33 A 58 C 83 C
9 B 34 B 59 C 84 B
10 B 35 B 60 C 85 B
11 C 36 C 61 D 86 A
12 A 37 C 62 A 87 A
13 D 38 C 63 X 88 C
14 B 39 C 64 B 89 C
15 C 40 C 65 D 90 C
16 B 41 A 66 C 91 B
17 A 42 A 67 A 92 B
18 A 43 C 68 C 93 B
19 C 44 D 69 A 94 C
20 B 45 C 70 D 95 C
21 A 46 A 71 C 96 D
22 D 47 D 72 C 97 B
23 A 48 C 73 A 98 A
24 C 49 A 74 B 99 D
25 D 50 A 75 X 100 BPage 1 of 16
Source: Haryana Public Service Commission. Question paper published by Haryana Public Service Commission.