Karnataka PGCET 2017 Question Paper Computer Science and Engineering

POST GRADUATE COMMON ENTRANCE TEST-2017
DATE and TIME COURSE SUBJECT
ME/M.Tech/M.Arch/
01-07-2017 COMPUTER SCIENCE
courses offered by
2.30 p.m. to 4.30 p.m. ENGINEERING
VTU/UVCE/UBDTCE
MAXI1\1UM 11ARKS TOTAL DURATION MAXIMUM TIME FOR ANSWERING
100 150 Minutes 120 Minutes
MENTION YOUR PCCET NO. QUESTION BOOKLET DETAILS
VERSION CODE SERIAL NUMBER

C— 1 107139
1)0s :
1. Check whether the PGC7ET No. has been entered and shaded in the respective circles on the OMR answer sheet.
Ensure whether the circles corresponding to course and the specific branch have been shaded on the OMR
answer sheet.
This Question Booklet is issued to you by the invigilator after the 2" Bell i.e., after 2.25 p.m.
4. The Serial Number of this question booklet should be entered and the respective circles should also be shaded
completely on the OMR answer sheet.
5. The Version Code of this question booklet should be entered on the OMR answer sheet and the respective circles
should also be shaded completely on the OMR answer sheet.
6. Compulsorily sign at the bottom portion of the OMR answer sheet in the space provided.
DON 'Ts :
I. THE TIMING AND NIARKS PRINTED ON THE OMR ANSWER SHEET SHOULD NOT BE
DAMAGED / MUTILATED / SPOILED.
2. The 3' Bell rings at 2.30 p.m., till then;
• Do not remove the paper seal .1 polythene bag of this question booklet.
• Do not look inside this question booklet.
• Do not start answering on the OMR answer sheet.
IMPORTANT INSTRUCTIONS TO CAN IDATES
1. This question booklet contains 75 (items) questions and each question will have one statement and four answers.
(Four different options / responses.)
2. After the 3" Bell is rung at 2.30 p.m., remove the paper seal / polythene bag of this question booklet and check
that this booklet does not have any unprinted or torn or missing pages or items etc., if so, get it replaced by a
complete test booklet. Read each item and start answering on the OMR answer sheet.
3. During, the subsequent 120 minutes:
• Read each question (item) carefidly.
• Choose one correct answer from out of the tour available responses (options I choices) given under
each question item. In case you feel that there is more than one correct response, mark ate response
which you consider the best. In any case, choose only one response for each item.
• Completely darken / shade the relevant circle with a BLUE OR BLACK INK BALL POINT PEN
against the uestion number on the OMR answer sheet.
Correct Method of shading the circle on the OMR answer < sheet is as shown below t
G®00
4. Use the space provided on each page of the question booklet for Rough Work. Do not use the OMR answer sheet.
or the same.
After the last Bell is rung at 4.30 pm, stop marking on the OMR answer sheet and affix your left hand thumb
impression on the OMR answer sheet as per the instructions.
6. Handover the OMR ANSWER SHEET to the room invigilator as it is.
7. After separating the top sheet (KEA copy), the invigilator will return the bottom sheet replica (Candidate's copy)
to you to carry home for self-evaluation.
R. Preserve the replica of the OMR answer sheet for a minimum period of ONE year.
9. Only Non-programmable calculators are allowed.
Marks Distribution
PART-1 : 50 QUESTIONS CARRY ONE MARK EACH (1 TO 50)
PART-2 : 25 QUESTIONS CARRY TWO MARKS EACH (51 TO 75)

CSE-CI 111111111111E

COMPUTER SCIENCE & ENGINEERING
PART — 1
Each question carries one mark. (50 x 1 = 50)

4. The first-fit, best-fit and the worst-fit
1. Concurrent processes are processes
algorithm can be used for
that
(A) do not overlap in time (A) Contiguous allocation of
memory
(B) overlap in time
(B) Linked allocation of memory
(C) are extended by a processor at
the same time (C) Indexed allocation of memory

(D) Process generated from the same (0) Random allocation of memory
operating system

5. MS — DOS
2. Which of the following are real — time
(A) does not support multi-
systems ?
programming
(A) Railway reservation system
(B) supports multiprogramming to
(B) Aircraft control system some extent
(C) Payroll system (C) support multiprogramming fully
(D) Hotel reservation system (D) support mobile communication

3. Dirty bit is used to show the
6. In which of the thllowing scheduling
(A) page that is modified after being policies does context switching never
loaded into cache memory. take place ?
(B) page that is less frequently (A) Round Robin
accessed.
(B) First-come-First-served
(C) wrong page in the memory.
(C) Pre-emptive
(D) page with corrupted data.
(D) Time sharing

CSE 3 • C-11 •

7. Which page replacement algorithm 10. When an interrupt occurs, an operating
suffers from Belady's anomaly '? system

(A) FIFO replacement (A) ignores the interrupt

(B) Optimal replacement (B) always changes the state of the
interrupted process after
(C) LRU replacement
processing the interrupt.
(D) Stack algorithm
(C) always resumes execution of the
interrupted process after
processing the interrupt.
8. 'Aging' is
(D) may change the state of the
(A) keeping track of cache contents. interrupted process to "blocked
(B) keeping track of what pages are and schedule another process.
currently residing in the
memory.
11. A phone number in a database is an
(C) keeping track of how many times example of
a given page is referenced.
(A) Record
(D) Increasing the priority of jobs to
(B) Field
ensure termination in a finite
time. (C) Sort

(D) File

9. Memory protection is normally done
by the 12. The concept of locking can be used to
(A) user himself solve the problem of

(A) lost update
(B) processor and associated
hardware (B) scheduling

(C) compiler (C) memory management

(D) user program (D) deadlock

C-1 4 CSE

13. Given an attribute X, another attribute 16. Degree of relationship means
Y is dependent on it, if for a given X
(A) number of attributes of the
(A) There are many Y values relationship

(B) There is only one value of Y (B) number of entities participating
in relationship
(C) There is one or more Y values
(C) number of entities in the ER
(D) There is none or one Y values
model

(D) number of relationships in ER
14. Which normal form is considered model
adequate for relational database
design ?

(A) 2 NF 17. The topology with highest reliability is

(B) 3 NF (A) Bus topology

(C) 4 NF (B) Star topology

(D) BCNF (C) Ring topology

(D) Mesh topology

15. A relationship where weak entity is
one of the participating entities is
called as 18. The size of an ATM cell is

(A) Weak relationship • (A) 48 Bytes

(B) Binary relationship (B) 53 Bytes

(C) Identifying relationship (C) 52 Bytes

(D) Recursive relationship (D) 43 Bytes

CSI? 5 C-1

19. The address claSs meant for 23. The four lowest layers of the 7 —
multicasting is layered OSI reference model are
(A) Class C (A) Transport, Session, Presentation,
Application
(B) Class D
(B) Physical. Data-link, Network,
(C) Class E Transport

(D) Class B (C) Physical, Network, Transport,
Session
(D) Physical, Presentation, Transport,
20. Which company developed RP/IP Network
protocol for networking ?

(A) IBM 24. Which of the following is not a field in
the Ethernet Message Packet ?
(B) DEC
(A) Type
(C) NOVELL
(B) Data
(D) DARPA (C) Pin-code
(D) Address
21. Bridges function is
25. Which of the following ISO level is
(A) physical
more closely related to the physical
(B) network communications '?

(C) data — link (A) Application
(B) Session
(D) session
(C) Network
(D) Data-link
• 22. allows LAN users to share
computer programs and data.
26. What is ASP ?
(A) Communication Server
(A) This is a language.
(B) Proxy Server (B) This is a scripting language.
(C) Print Server (C) This is ,a package.
(D) File Server (D) This is a testing tool.

SpaCe For Rough Work

- .C-1 6 CSE

27. A box contains six red halls and four 30. The number of words that can be
green halls. Four balls are selected at formed out of the letters of the word,
random from the box. What is the COMMITTEE is :
probability that the two of the selected
(A)
balls will be red and two will be green '?

(A) 4/10 (B)

(B) 3/7
(C)
(C) 1/15
(D) 9!
(D) 4/7

31. The maximum number of edges in a
n-node undirected graph without self-
If n(A) = 115, n(B) = 326, n(A—B) = 47,
loops is
then n(A L.) B) is equal to
(A) n2
(A) 373
n(n 2 — 1)
(B)
(B) 165
(C) n—1
(C) 370
(n + 1)(n)
(D)
(D) 150

32. The best data structure to check
29. (P Q) n (R Q) is equivalent to whether an arithmetic expression has
balanced parentheses or not is a
(A) (P v Q) R

(B) (P v R) Q (A) Queue
(B) Stack
(C) (P R) Q
(C) Tree
(D) (P n Q) —> R
(D) List

CSC 7 .C-11

33. Which one of the following- algorithm 36. The best-case• analysis of the Quick
design technique used in finding all Sort
pairs of shortest distances in graph '?
(A) 0 (n(n — 1)/2)
(A) Dynamic programming
(B) 0(n2)
(B) Back tracking
(C) 0(n)
(C) Greedy
(D) 0(n log, n)
(D) Divide and Conquer

34. An m x n matrix A is said to be sparse 37. Level order transversal of a rooted tree
if can be done by stacking from the root
and performing
(A) many of its elements are non-
zero.
(A) Pre-order traversal

(B) many of its elements are zero.
(B) In-order traversal
(C) many of its elements are unit.
(C) Pre-order traversal
(D) many of its elements are
(D) Breadth first search
negative.

35. Which one is not Divide and Conquer 38. Which of the following are register ?
algorithm ?
(A) Accumulator
(A) Merge sort
(B) Buffer
(B) Quick sort
(C') Decoder
(C) Heap sort
(D) Encoder
(D) Binary search

C-1 8 CSE

39. Which of the following weights makes 42. Which of the thllowing does not have
the complement operation easier in 8 data lines ?
BCD thrm ?
(A) 8085
(A) 8 4 -- 2 — 1
(B) 8086
(B) Excess — 3
(C) 8088

(C) 2—4 —2—I (D) 2-SO

(D) 3 — 2 — I — ()

43. A multiplexer is also known as

40. The simplified form of the Boolean (A) Coder
function
(B) Decoder.
F = X'YZ + XY'Z' + XYZ + XYZ' is
(C) Data selector
(A) F = X'Z + X'Y
(D) Multi-vibrator
(B) F = YZ + XZ'

(C) F = YZ' + XY'
44. The seek time of a disk in 30 ms. It
(D) F = YZ + X'Y rotates at the rate of 30 rotations per
second. Each track has a capacity of
300 words. One access time is
41. A half adder is also known as approximately

(A) AND circuit (A) 47 ms

(B) NAND circuit (B) 50 ms

(C) NOR circuit (C) 60 ms

(D) EX-OR circuit (D) 62 ms

CSE 9 C-1

45. Flip-flop is a 48. A language L is accepted by a
Pushdown Automation if and only if
(A) Sequential circuit
it is

(B) Combinatorial circuit
(A) Context sensitive

(C) Parallel circuit
(B) Recursive

(D) Hamottanian circuit (C) Context free

(D) Right — Linear

46. Instructions in which all the operands
are stored in stack are called as
49. The lexical analyzer is in which phase
(A) Three address instructions of a complier '?

(B) Two address instructions (A) First

(C) One address instructions (B) Second

(D) Zero address instructions (C) Third

(D) Last

47. The word 'formal' in formal languages
means
50. Compiler can diagnose
(A) the symbols used have well-
defined meanings. (A) Grammatical errors only

(B) they are unnecessary, in reality. (B) Logical errors only

(C) Only the form of the strings of (C) Grammatical as well as Logical
symbols is significant. errors

(D) as the languages cannot be (D) Neither Grammatical nor Logical
termed as informal. errors

C-1 10 CSE

PART — 2
Each question carries two marks. (25 x 2 = 50)

51. The following program 54. Consider the following set of
main () processes with arrival times and the
CPU first times given in milliseconds :
float a = .5, b = .7; Process Arrival Time First time
if (b < .7) P1 0 5
if (a < .5) P2 1 3
printf ("TELO"); P3 1 3
else printf ("MILO"); P4 4 1
else printf ("RENO"); What is the average turn around tire
(A) MILO
for these processes with preempted
(B) TELO
shortest remounting five processing
(C) RENO
first algorithm is implemented ?
(D) PLO
(A) 5.50 •
(B) 5.75
52. What is f(L), if L is a language given
(C) 6.00
by 0 * (0 + 1) 1 * and. RO) = x,
f(1)=y*? (D) 6.25
(A) x*y*
55. Each process Pi, i = 1, 2, 3, .... 9 is
(B) xy*
(C) yx* coded as follows :
repeat P mutex
(D) x* xy
:critical section:
53. Consider a computer with 8 mega v ;mutex
bytes of main memory and a 128 K forever
cache. The cache block size is 4 K. It The code for P ao is identical except
uses a direct mapping scheme for a that it uses v ;mutex instead of
cache management. How many
P Imutex;, what is the largest number
different main memory blocks can-
of processes that can be inside the
map into a given physical cache
block ? critical section at any moment ?
(A) 2048 (A) 1
(B) 256 (B) 2
(C) 64 (C) 3
(D) 248 (D) 4

CSE 11 C-1

56. The seek time of a disk is 30 ins. It 58. Given the functional dependencies
rotates at the rate of 30 rotations per x w, y, y y z and z pg.
second. Each track has a capacity of Which of the following does not hold
300 words. The access time is good ?
approximately (A) Z

(A) 47 ms (B) W z

(C) x
(B) 50.ms
(D) 3. w

(C) 60 ms

59. The linker copies all library routines
(D) 62 ms
used in the program into the
executable image, this process is
referred tows
57. The relation schema. Student— (A) Assembling
pertbnnance (name, courseno, rollno,
(B) Dynamic linking
grade) has the following dependencies :
(C) Static linking
name, courseno grade, rollno, (D) Compiling
courseno oracle.

name —> rollno, rollno —* name. 60. Suppose that the Aloha Protocol is
used to share a 56 khps satellite
The highest normal form of their channel. Suppose that packets are
relation schema is 1000 bits long. What is the maximum
throughput of the system in packet
(A) 2 NF second ?
(A) 15
(B) 3 NF
(B) 10
(C) BCNF
(C) 12

(D) 4 NF (D) 14

C-1 12 CSE

61. A system is using NRZ-1 tO transfer 10 63. Suppose an ATM switch has 16 posts.
mbps data. What are the average each operating at SON ET OC-3
transmission rate 155 mbps. What is
signal rate and minimum bandwidth ?
the maximum possible throughput of
(A) 50 K band, 50 Khz the switch ?
(A) 2.48 Gbps
(B) 500 band, 500 Hz (B) 3.50 Gbps
(C) 2.01 Gbps
(C) 500 K band, 500 mHz
(D) 3.20 Gbps

(D) 500 K hand, 500 KHz
64. A small organization has a class C
address for 7 networks each with 24
hosts. What is an appropriate subnet
O. To detect a missing token, the monitor mask :
watches for a passing token in the ring (A) 255. /55. 155. 220
and maintains a timer equal to the (B) 255. /55. 158. 221
maximum possible token. rotation (C) 255.255. 255. 222

time. This interval equals (D) 255. 255. 255. 224

(A) NumStations x THT + Ring — 65. A binary relation R = 1(1, 1), (2, .1),
Latency (2, 2), (2, 3), (2, 4), (3, 1), (3, 2),
(3, 3), (3, 4)1. On the set A = 11, 2, 3,
(B) NumStations + THT * Ring — 41. is
Latency (A) Reflexive, Symmetric and
transitive
(C) NumStations x THT — Ring — (B) Neither reflexive nor irretlexive
Latency but transitive
(C) Irretlexive, symmetric and
(D) NumStations — THT * Ring — transitive
Latency (D) Irretlexive and antisymmetric

CSE 13 C-1

66. It is desired to find the no. of defective 69. The running time of an algorithm is
chips in a computer chip production represented by the following
unit. Obviously the probability of recurrence. relation :
findiniz, a detective chip does not
depend on whether the previous chip nn<3

was detective or not. The probability T(n) = T
n +cn otherwise
distribution is

(A) Binomial Which one of the following represents
the time complexity of the algorithm ?
(B) Normal

(C) Uniform (A) 0 (n)

(D) Triangular (B) 0 (n log n)

(C) 8 (n2)

67. IfU= 11,2,3,4, ....8,91, A:1,2,3,4k
(D) (0112 log n)
B = :2, 4, 6, 8: and C = :3, 4, 5, 61,
then (A L.) B) is
70. A circularly linked list is used to
(A) 15, 7, 9:
represent a queue. A single variable P
(B) 11,2,3,4,6,81 is used to access the queue. To which

(C) 1/, 4: node should P point, such that both the
operations of enqueue (insert) and
(D) 14);
dequeue (delete) can be .performed in
constant time ?

68. Which of the following proposition is
a tautology ?

(A) Rear mode
(A) (p v q) —) p

(B) p v (q p) (B) Front mode

(C) p v (p (C) Not possible with a single point

(D) P - (p --0 q) (D) Node next to front

Spire For Rough Work

C-1 14 CSC

71. Which of the following list of nodes 73. A four variable Boolean function is
corresponds to a post order traversal of given by F (w, x, y, z) = I (1, 2, 3, 4,
the binary tree in the figure shown ? 5, 6, 7, 8, 9, 10, II, 12, 13) + E d (0,
14, 15) the simplified term • of this
function is

(A)

(B) 0

(C)

(D) WXY + WXY
(A) DHEBIFJGCA
(B) ABDEHCFIGL
74. Postfix expression for (300 + 23) * (43
(C) DBEHIFLJGA
—21) / (84 + 7) is
(D) ABCDEFGHIJ
(A) 847 + 43 21 * 300 ,3 +

(B) 4321—*7 +/ 30023847
72. Consider the following graph :
(C) 300 + ')3 43 — * / 84 7

(D) 300 23 + 43 21 — * 84 7 + /

75. Using Quine — Mcclusky method, one
6
of the prime implicates of the function
Which one of the following is the
F(W, X, Y, Z) = /11-1 (7, 9, 12, 13, 14,
sequence of the edges added to the
15) + Id (4, I I) is
minimum spanning tree using
Kruskal's algorithm ? (A) WXY

(A) (b, e) (a, c) (e, (b, c) (f, g) (c, d)
(B) XY
(B) (b, e) (a, c) (e, (a, h) (d, t) (e, 0
(C) XYZ
(C) (b, e) (a, c) (c, (e, g) (g, t) (a, b)
(D) (b, e) (a, c) (c, 0 (d, e) (d, t) (d, b) (D) WYZ

CSE 15 C-1

C-1 16 CSE