PU CET PG 2018 Question Paper M.E. _Computer Science _ Engg._

M.E.(Computer Science & Engg.)
1. What does the following function do for a given Linked List with first node as head?
void fun1(struct node* head)
{
if(head == NULL)
return;

fun1(head->next);
printf("%d ", head->data);
}

A) Prints all nodes of linked lists
B) Prints all nodes of linked list in reverse order
C) Prints alternate nodes of Linked List
D) Prints alternate nodes in reverse order

2. Which of the following sorting algorithms can be used to sort a random linked list with
minimum time complexity?
A) Insertion Sort B) Quick Sort C) Heap Sort D) Merge Sort

3. In the worst case, the number of comparisons needed to search a singly linked list of
length n for a given element is:
A) log 2 n B) n/2 C) log 2 n – 1 D) n

4. Suppose we are sorting an array of eight integers using heapsort, and we have just
finished some heapify (either maxheapify or minheapify) operations. The array now
looks like this: 16 14 15 10 12 27 28. How many heapify operations have been performed
on root of heap?
A) 1 B) 2 C) 3 D) 5

5. B+ trees are preferred to binary trees in databases because:
A) Disk capacities are greater than memory capacities.
B) Disk access is much slower than memory access.
C) Disk data transfer rates are much less than memory data transfer rates.
D) Disks are more reliable than memory.

6. A B+ -tree index is to be built on the Name attribute of the relation STUDENT. Assume
that all student names are of length 8 bytes, disk block are size 512 bytes, and index
pointers are of size 4 bytes. Given this scenario, what would be the best choice of the
degree (i.e. the number of pointers per node) of the B+ -tree?
A) 16 B) 42 C) 43 D) 44

7. Consider an undirected random graph of eight vertices. The probability that there is an
edge between a pair of vertices is 1/2. What is the expected number of unordered cycles
of length three?
A) 1/8 B) 1 C) 7 D) 8

8. A RAM chip has a capacity of 1024 words of 8 bits each (1K × 8). The number of 2 × 4
decoders with enable line needed to construct a 16K × 16 RAM from 1K × 8 RAM is:
A) 4 B) 5 C) 6 D) 7

9. Which of the following is true:
A) The AVL trees are more balanced compared to Red Black Trees, but they may
cause more rotations during insertion and deletion.
B) Heights of AVL and Red-Black trees are generally same, but AVL Trees may
cause more rotations during insertion and deletion.
C) Red Black trees are more balanced compared to AVL Trees, but may cause more
rotations during insertion and deletion.
D) Heights of AVL and Red-Black trees are generally same, but Red Black rees may
cause more rotations during insertion and deletion.

10. In a complete k-ary tree, every internal node has exactly k children or no child. The
number of leaves in such a tree with n internal nodes is:
A) nk B) (n – 1) k+ 1 C) n( k – 1) + 1 D) n(k – 1)

11. Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can
be multiplied is several ways with different number of total scalar multiplications. For
example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of
multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the
total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5
and t = 80, then the number of scalar multiplications needed is:
A) 248000 B) 44000 C) 19000 D) 25000

12. Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x
5, respectively. The minimum number of scalar multiplications required to find the
product A1A2A3A4 using the basic matrix multiplication method is:
A) 1500 B) 2000 C) 500 D) 100

13. Which of the following algorithms is NOT a divide & conquer algorithm by nature?
A) Euclidean algorithm to compute the greatest common divisor
B) Heap Sort
C) Cooley-Tukey fast Fourier transform
D) Quick Sort

14. What is time complexity of fun()?
intfun(intn)
{
intcount = 0;
for(inti = n; i>
0; i /= 2)
for(intj = 0; j
<i; j++)
count += 1;
returncount;
}
A) O(n^2) B) O(nLogn) C) O(n) D) O(nLognLogn)

15. 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
A) T(n) <= 2T(n/5) + n B) T(n) <= T(n/5) + T(4n/5) + n
C) T(n) <= 2T(4n/5) + n D) T(n) <= 2T(n/2) + n

16. The recurrence equation
T(1) = 1
T(n) = 2T(n - 1) + n, n ≥ 2
evaluates to:
A) 2n + 1- n – 2 B) 2n - n
C) 2n + 1 - 2n – 2 D) 2n - n

17. Consider the following function
double f(double x){
if (abs(x*x - 3) < 0.01) return x;
else return f(x/2 + 1.5/x);
}
Give a value q (to 2 decimals) such that f(q) will return q:_____.
A) 1.73 B) 2.24 C) 4.22 D) 3.42

18. In a certain operating system, deadlock prevention is attempted using the following
scheme. Each process is assigned a unique timestamp, and is restarted with the same
timestamp if killed. Let Ph be the process holding a resource R, Pr be a process requesting
for the same resource R, and T(Ph) and T(Pr) be their timestamps respectively. The
decision to wait or preempt one of the processes is based on the following algorithm.
if T(Pr) < T(Ph)

then kill Pr

else wait

Which one of the following is TRUE?
A) The scheme is deadlock-free, but not starvation-free
B) The scheme is not deadlock-free, but starvation-free
C) The scheme is neither deadlock-free nor starvation-free
D) The scheme is both deadlock-free and starvation-free

19. Consider a paging hardware with a TLB. Assume that the entire page table and all the
pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80
milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective
memory access time (in milliseconds) is _________.
A) 120 B) 122 C) 124 D) 118

20. In which one of the following page replacement policies, Belady’s anomaly may occur?
A) FIFO B) Optimal C) LRU D) MRU

21. In which one of the following page replacement algorithms it is possible for the page
fault rate to increase even when the number of allocated frames increases?
A) LRU (Least Recently Used)
B) OPT (Optimal Page Replacement)
C) MRU (Most Recently Used)
D) FIFO (First In First Out)

22. Consider a non-negative counting semaphore S. The operation P(S) decrements S, and
V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are
issued in some order. The largest initial value of S for which at least one P(S) operation
will remain blocked is ________.
A) 7 B) 8 C) 9 D) 10

23. An operating system uses Shortest Remaining Time first (SRT) process scheduling
algorithm. Consider the arrival times and execution times for the following processes:
Process Execution time Arrival time
P1 20 0
P2 25 15
P3 10 30
P4 15 45
What is the total waiting time for process P2?
A) 5 B) 15 C) 40 D) 55

24. Assume every process requires 3 seconds of service time in a system with single
processor. If new processes are arriving at the rate of 10 processes per minute, then
estimate the fraction of time CPU is busy in system?

A) 20% B) 30% C) 50% D) 60%

25. A system contains three programs and each requires three tape units for its operation. The
minimum number of tape units which the system must have such that deadlocks never
arise is _________.
A) 6 B) 7 C) 8 D) 9

26. A system shares 9 tape drives. The current allocation and maximum requirement of tape
drives for 4 processes are shown below:
Process Maximum need Current allocation

P1 9 3

P2 6 1

P3 5 3

P4 10 0

Which of the following best describes the current state of the system?
A) Safe, Deadlocked B) Safe, Not Deadlocked
C) Not Safe, Deadlocked D) Not Safe, Not Deadlocked

27. What is the min and max number of tables required to convert an ER diagram with 2
entities and 1 relationship between them with partial participation constraints of both
entities?
A) Min 1 and max 2 B) Min 1 and max 3
C) Min 2 and max 3 D) Min 2 and max 2

28. Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.
T1: r1(X); r1(Z); w1(X); w1(Z)
T2: r2(Y); r2(Z); w2(Z)
T3: r3(Y); r3(X); w3(Y)
S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z);
w3(Y); w2(Z); r1(Z); w1(X); w1(Z)
S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z);
r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?
A) Only S1 is conflict-serializable.
B) Only S2 is conflict-serializable.
C) Both S1 and S2 are conflict-serializable.
D) Neither S1 nor S2 is conflict-serializable.

29. ACID properties of a transactions are:
A) Atomicity, consistency, isolation, database
B) Atomicity, consistency, isolation, durability
C) Atomicity, consistency, integrity, durability
D) Atomicity, consistency, integrity, database

30. Database table by name Loan_Records is given below.
Borrower Bank_Manager Loan_Amount
Ramesh Sunderajan 10000.00
Suresh Ramgopal 5000.00
Mahesh Sunderajan 7000.00
What is the output of the following SQL query?

SELECT Count(*)
FROM ( (SELECT Borrower, Bank_Manager
FROM Loan_Records) AS S
NATURAL JOIN (SELECT Bank_Manager,
Loan_Amount
FROM Loan_Records) AS T );

A) 3 B) 9 C) 5 D) 6

31. Consider the following relational schema:
Suppliers(sid:integer, sname:string, city:string, street:string)
Parts(pid:integer, pname:string, color:string)
Catalog(sid:integer, pid:integer, cost:real)

Assume that, in the suppliers relation above, each supplier and each street within a city
has a unique name, and (sname, city) forms a candidate key. No other functional
dependencies are implied other than those implied by primary and candidate keys. Which
one of the following is TRUE about the above schema?
A) The schema is in BCNF
B) The schema is in 3NF but not in BCNF
C) The schema is in 2NF but not in 3NF
D) The schema is not in 2NF

32. Which one of the following is a top-down parser?
A) Recursive descent parser B) Operator precedence parser
C) An LR(k) parser D) An LALR(k) parser

33. Which grammar rules violate the requirement of the operator grammar? A, B, C are
variables and a, b, c are terminals
1) A → BC
2) A → CcBb
3) A → BaC

4) A → ε

A) 1 only B) 1 and 2 only C) 1 and 3 only D) 1 and 4 only

34. A linker reads four modules whose lengths are 200, 800, 600 and 500 words respectively.
If they are loaded in that order, what are the relocation constants?
A) 0, 200, 500, 600 B) 0, 200, 1000, 1600
C) 200, 500, 600, 800 D) 200, 700, 1300, 2100

35. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming
signal is 46.4 ms. The minimum frame size is:
A) 94 B) 416 C) 464 D) 512

36. How many 8-bit characters can be transmitted per second over a 9600 baud serial
communication link using asynchronous mode of transmission with one start bit, eight
data bits, two stop bits, and one parity bit?
A) 600 B) 800 C) 876 D) 1200

37. 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 identifier of the output interface on which this packet will be forwarded is ______.
A) 1 B) 2 C) 3 D) 5

38. IPv6 does not support which of the following addressing modes?
A) Unicast addressing B) Multicast addressing
C) Broadcast addressing D) Anycast addressing

39. Which of the following is not true about User Datagram Protocol in transport layer?
A) Works well in unidirectional communication, suitable for broadcast information.
B) It does three way handshake before sending datagrams
C) It provides datagrams, suitable for modeling other protocols such as in IP
tunneling or Remote Procedure Call and the Network File System
D) The lack of retransmission delays makes it suitable for real-time applications

40. Host X has IP address 192.168.1.97 and is connected through two routers R1 and R2 to
another host Y with IP address 192.168.1.80. Router R1 has IP addresses 192.168.1.135
and 192.168.1.110. R2 has IP addresses 192.168.1.67 and 192.168.1.155. The netmask
used in the network is 255.255.255.224.
Which IP address should X configure its gateway as?
A) 192.168.1.67 B) 192.168.1.110

C) 192.168.1.135 D) 192.168.1.155

41. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences
of (110)’s as (011)’s}.

Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences
of (000)’s as (111)’s}.
Which one of the following is TRUE?
A) L1 is regular but not L2 B) L2 is regular but not L1
C) Both L2 and L1 are regular D) Neither L1 nor L2 are regular

42. Which one of the following regular expressions is NOT equivalent to the regular
expression (a + b + c) *?
A) (a* + b* + c*)* B) (a*b*c*)*
C) ((ab)* + c*)* D) (a*b* + c*)*

43. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
A) 1, 2 and 3 B) 2, 3 and 4
C) 1, 2 and 4 D) 1, 3 and 4

44. S ->aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b}
is the set of:
A) All palindromes
B) All odd length palindromes
C) Strings that begin and end with the same symbol
D) All even length palindromes

45. Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume
that there is no cycle-time overhead of pipelining. When an application is executing on
this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if
25% of the instructions incur 2 pipeline stall cycles is:
A) 4 B) 8 C) 6 D) 7

46. Which of the following systems is a most likely candidate example of a pipe and filter
architecture?
A) Expert system B) DB repository
C) Aircraft flight controller D) Signal processing

47. In a computer system, four files of size 11050 bytes, 4990 bytes, 5170 bytes and 12640
bytes need to be stored. For storing these files on disk, we can use either 100 byte disk
blocks or 200 byte disk blocks (but can't mix block sizes). For each block used to store a

file, 4 bytes of bookkeeping information also needs to be stored on the disk. Thus, the
total space used to store a file is the sum of the space taken to store the file and the space
taken to store the book keeping information for the blocks allocated for storing the file. A
disk block can store either bookkeeping information for a file or data from a file, but not
both. What is the total space required for storing the files using 100 byte disk blocks and
200 byte disk blocks respectively?
A) 35400 and 35800 bytes B) 35800 and 35400 bytes
C) 35600 and 35400 bytes D) 35400 and 35600 bytes

48. Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a
connected graph, then the number of bounded faces in any embedding of G on the plane
is equal to
A) 3 B) 4 C) 5 D) 6

49. G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G
and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be:
A) Regular B) Complete C) Hamiltonian D) Euler

50. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly
once is _______.
A) 80 B) 8 C) 20 D) 210

51. Which one of the following in NOT necessarily a property of a Group?
A) Commutativity
B) Associativity
C) Existence of inverse for every element
D) Existence of identity

52. The product of the non-zero eigenvalues of the matrix

10001
01110
01110
01110
10001

is ______

A) 4 B) 5 C) 6 D) 7

53. Let A, B, C, D be n × n matrices, each with non-zero determinant. If ABCD = 1, then B-1
is:
A) D-1C-1A-1 B) CDA
C) ADC D) Does not necessarily exist

54. An orthogonal matrix A has eigen values 1, 2 and 4. What is the trace of the matrix AT?
A) 7/4 B) 1/7 C) 7 D) 4/7

55. Find the Integral value of f(x) = x * sinx within the limits 0, π.
A) π B) 2π C) π/2 D) 0

56. Which one of the following Boolean expressions is NOT a tautology?
A) ((a → b) ∧ (b → c)) → (a → c) B) (a ↔ c) →( ¬b → (a ∧ c))
C) (a ∧ b ∧ c) → (c ∨ a) D) a → (b → a)

57. 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
function?
A) Full adder B) Priority encoder
C) Multiplexer D) Flip-flop

58. The hexadecimal representation of 6578 is
A) 1AF B) D78 C) D71 D) 32F

59. 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
A) P and R only B) Q and R only
C) Q and S only D) R and S only

60. A sender is employing public key cryptography to send a secret message to a receiver.
Which one of the following statements is TRUE?
A) Sender encrypts using receiver’s public key
B) Sender encrypts using his own public key
C) Receiver decrypts using sender’s public key
D) Receiver decrypts using his own public key

61. An attacker sits between customer and Banker, and captures the information from
thecustomer and retransmits to the banker by altering the information. This attack is
called as ______.
A) Masquerade Attack B) Replay Attack
C) Passive Attack D) Denial of Service Attack

62. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g,
respectively. The postorder traversal of the binary tree is:
A) debfgca B) edbgfca
C) edbfgca D) defgbca

63. To evaluate an expression without any embedded function calls:
A) One stack is enough
B) Two stacks are needed
C) As many stacks as the height of the expression tree are needed
D) A Turing machine is needed in the general case

64. A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn
from the bag, its colour recorded and it is put back in the bag. This process is repeated 3
times. The probability that no two of the marbles drawn have the same colour is
A) 1/36 B) 1/6 C) ¼ D) 1/3

65. Four fair six-sided dice are rolled. The probability that the sum being 22 is X/1296. The
value of X is ________
A) 7 B) 8 C) 9 D) 10

66. What does the following program print?
#include
void f(int *p, int *q)
{
p = q;
*p = 2;
}
inti = 0, j = 1;
intmain()
{
f(&i, &j);
printf("%d %d \n", i, j);
getchar();
return 0;
}

A) 22 B) 21 C) 01 D) 02

67. A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred
byte-wise. Let the interrupt overhead be 4 msec. The byte transfer time between the
device interface register and CPU or memory is negligible. What is the minimum
performance gain of operating the device under interrupt mode over operating it under
program controlled mode?
A) 15 B) 25 C) 35 D) 45

68. Which one of the following is NOT performed during compilation?

A) Dynamic memory allocation B) Type checking
C) Symbol table management D) Inline expansion

69. Which of the following is an example of a spooled device?
A) a line printer used to print the output of a number of jobs
B) a terminal used to enter input data to a running program
C) a secondary storage device in a virtual memory system
D) a graphic display device

70. Which of the following requires a device driver?
A) Register B) Cache C) Main memory D) Disk

71. Which of the following protocol is used for transferring electronic mail messages from
one machine to another?
A) TELNET B) FTP C) SNMP D) SMTP

72. Which one of the following is not a client server application?
A) Internet chat B) Web browsing
C) E-mail D) Ping

73. SATA is the abbreviation of
A) Serial Advanced Technology Attachment
B) Serial Advanced Technology Architecture
C) Serial Advanced Technology Adapter
D) Serial Advanced Technology Array

74. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in
linear time, the data structure to be used is:
A) Queue B) Stack C) Heap D) B-Tree

75. If L and L' are recursively enumerable, then L is
A) Regular B) Context-free
C) Context-sensitive D) Recursive

x-x-x