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

M.E.(Computer Science & Engg.)

1. Which one of the following is true?
A) R ∩ S = (R ∪S) − [(R − S) ∪(S − R)]
B) R ∪S = (R ∩ S) − [(R − S) ∪(S − R)]
C) R ∩ S = (R ∪S) − [(R − S) ∩ (S − R)]
D) R ∩ S = (R ∪S) ∪(R − S)

The time complexity of computing the transitive closure of a binary relation on a set of n
2.
elements is known to be
A) O(nlogn)
B) O(n3/2)
C) O(n3)
D) O(n)

3. The power set of the set {ϕ} is
A) {ϕ}
B) { ϕ, { ϕ }}
C) {0}
D) {0, ϕ, { ϕ }}

4. Cyclometric complexity of a flow graph G with n vertices and e edges is
A) V(G)= e+n-2
B) V(G)= e-n+2
C) V(G)= e+n+2
D) V(G)= e-n-2

5. A relation R in {1,2,3,4,5,6} is given by {(1,2),(2,3),(3,4),(4,4),(4,5)}. This relation is:
A) Reflexive
B) Symmetric
C) Transitive
D) Not reflexive, not symmetric and not transitive

6. a<<1 is equivalent to:
A) Multiplying a by 2
B) Dividing a by 2
C) Adding 2 to a
D) Subtracting 2 to a

Which of the following algorithms has running time O(n2) in the worst case but O(nlogn) on
7.
average?
A) Bubble Sort
B) Tournament Sort
C) Merge Sort
D) Quick Sort

8. The upper bound on T(n)=3T(n/2) +n is
A) O(nlgn)
B) O(nlg3)
C) O(n2)
D) O(nlgn+n)

9. Which one of the following statements is false?
A) Optimal binary search tree construction can be performed efficiently using dynamic
programming
B) Breadth- first search cannot be used to find converted components of a graph
C) Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely
constructed
D) Depth-first search can be used to find connected components of a graph

10. An error detecting code in which code is the remainder resulting from dividing the bits to be
checked by a predetermined binary number, is known as
A) Cyclic redundancy check
B) Checksum
C) Error detecting code
D) Error rate

11. Which address is the loopback address?
A) 0.0.0.1
B) 127.0.0.0
C) 127.0.0.1
D) 255.255.255.255

12. As a frame travels through a routed network the MAC address will always
A) Change to reflect the current source and destination
B) The source address will remain the same but the destination address will change
C) The source address will change and the destination address will change.
D) Nothing changes

13. Which two of the following four regular expressions are equivalent? ( ε is the empty string).
(i) (00) * (ε + 0)
(ii) (00)*
(iii) 0*
(iv) 0 (00)*
A) (i) and (ii)
B) (ii) and (iii)
C) (i) and (iii)
D) (iii) and (iv)

14. What will be the output of the following Program
main (){
Int a=10,b,c;

b=!a;
c=~a;
printf(“%d %d”, b,c);
}
A) 10 -10
B) 0 -11
C) -10 -10
D) 00

15. Suppose that the set A contains 5 elements and the set B contains 2 elements. How many
different functions f : A → B can one define?
A) 10
B) 25
C) 16
D) 32

16. Which of the following is false
A) A graph is a sub-graph of its union with any other graph.
B) The intersection of two graphs is not necessarily a sub-graph of both of them.
C) A spanning sub-graph of a graph G is a sub-graph that contains all the vertices of G.
D) Hamilton path is a path that includes all the vertices of a graph.

17. A full binary tree with n leaves contains:
A) n nodes
B) log2 n nodes
C) 2n – 1 nodes
D) 2n nodes

18. Which of the following is a hash function?
A) Shortest distance
B) Mid square
C) Folding
D) Extraction

19. If A ⊕ B = C, then
A) A ⊕ C=B
B) B ⊕ C=A
C) A ⊕ B ⊕ C=0
D) All of the above

20. How many pulses are needed to change the contents of a 8 bit up-counter from 10101100
to 00100111?
A) 134
B) 133
C) 124
D) 123

21. The correct way to de-allocate dynamically created one dimensional array arr is
A) free(arr)
B) free(arr[0])
C) free(*arr)
D) realloc(arr)

22. Given the declaration statement, int* p[2][3][4]; which of the following definitions of q is valid?
A) Int* (*q)[3][4]=p;
B) Int* (*q)[2][3][4]=p;
C) Int ****q=p;
D) Int *q[2][3][4]=(*)p;

23. The 8085 microprocessor responds to the presence of an interrupt
A) as soon as the TRAP pin becomes ‘high’
B) by checking the TRAP pin for ’ high’ status at the end of each instruction fetch
C) by checking the TRAP pin for ‘high’ status at the end of the execution of each instruction
D) by checking the TRAP pin for ‘high’ status at regular intervals

24. Consider a weighted complete graph G on the vertex set {v1,...,vn} such that the weight of the
edge (vi,vj) is 2|i - j|. The weight of a minimum spanning tree of G is:
A) n-1
B) 2n-2
C) nc2
D) n2

25. The maximum number of binary trees that can be formed with three unlabeled nodes is:
A) 1
B) 4
C) 5
D) 3

26. Let G be the non-planar graph with the minimum possible number of edges. Then G has
A) 9 edges and 5 vertices
B) 9 edges and 6 vertices
C) 10 edges and 5 vertices
D) 10 edges and 6 vertices

27. Suppose a processor does not have any stack pointer register. Which of the following statements
is true?
A) It cannot have subroutine call instruction
B) In can have subroutine call instruction, but no nested subroutine calls
C) Nested subroutine calls are possible, but interrupts are not
D) All sequences of subroutine calls and also interrupts are possible

28. A certain pipelined RISC machine has 8 general-purpose registers R0, R1, . . . , R7 and supports
the following operations.
ADD Rs1, Rs2, Rd Add Rs1 to Rs2 and put the sum in Rd
MUL Rs1, Rs2, Rd Multiply Rs1 by Rs2 and put the product in Rd
An operation normally takes one cycle; however, an operation takes two cycles if it produces a
result required by the immediately following operation in an operation sequence. Consider the
expression AB+ ABC+ BC, where variables A, B, C are located in registers R0, R1, R2. If the
contents of these three registers must not be modified, what is the minimum number of clock
cycles required for an operation sequence that computes the value of AB+ ABC+ BC ?
A) 5
B) 6
C) 7
D) 8

29. Consider a 2-way set associative cache consisting of 128 lines with line size of 128 words. CPU
generates a 20-bit address of a word in main memory. The number of bits in the TAG, LINE and
WORD fields are respectively:
A) 9,6,5
B) 7,7,6
C) 6,6,8
D) 7,6,7

30. Consider a grammar with the following productions
I. S → a α b│ b α c │ α B
II. S → α S│ b
III. S → α bb│ ab
IV. S α → bdb│ b
The above grammar is
A) Context free
B) Regular
C) Context sensitive
D) LR (k)

31. Context free languages are closed under
A) Union, Kleene Closure, Complement, Reversal
B) Union, Kleene Closure, Concatenation, Reversal
C) Union, Kleene Closure, Reversal, Intersection
D) Complement, Kleene Closure, Union, Concatenation

32. For the settings of pfile using the following command
>chmod 2666 pfile, Which of the following is not true
A) The file has the SUID bit set
B) Mandatory locking has been enabled
C) The file is not executable by any user
D) The associated group has read and write permissions

33. Purpose of a start bit in RS 232 serial communication protocol is
A) to synchronise receiver for receiving every byte
B) to synchronise receiver for receiving a sequence of bytes
C) a parity bit
D) to synchronise receiver for receiving the last byte

34. Analysis models depict software in which three representations?
A) Architecture, Interface, Component
B) Cost, Risk, Schedule
C) Information, Function, Behavior
D) ER Diagram, DFD, Class Diagram

35. Identify error in following SQL:
SELECT RollNo , Sum(Marks)
FROM Student_table
GROUP BY RollNo
HAVING Student_name=‘Rahul’;
A) Syntax Error
B) SUM() is not an aggregate function
C) HAVING cannot be used with GROUP BY
D) The Having condition has to be based on some column that appears in the select list

36. Which of the following is not a type of DMA
A) Block Transfer DMA
B) Cycle stealing DMA
C) Interleaved DMA
D) Phase shifted DMA

37. For a pipelined CPU with s ingle ALU, consider the following situations
1. The j+1st instruction uses the result of the jth instruction as an operand.
2. The execution of conditional jump instruction
3. The jth and j+1st instruction requires ALU at the same time.
A) 1 and 2 only
B) 2 and 3 only
C) 3 Only
D) All of the three

38. In a public key cryptographic system, a sender has encrypted a message with the recipient’s
public key. What key does the recipient use to decipher the message?
A) Recipient’s public key
B) Recipient’s private key
C) Sender’s public key
D) Sender’s private key

39. The address sequence generated by tracing particular program executing in a pure demand
paging system with 100 records (addresses) per page with 1 free main memory frame is recorded

as follows. What is the number of page faults?
0100,0200,0430,0499,0510,0530,0560,0120,0220,0240,0260,0320,0370
A) 13
B) 8
C) 7
D) 10

40. Which of the following statements is false?
A) Every NFA can be converted to an equivalent DFA
B) Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing
machine
C) Every regular language is also a context-free language
D) Every subset of a recursively enumerable set is recursive

41. 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

42. The contents of accumulator after the execution of following instruction will be
MVI A, A7H
ORA A
RLC
A) CFH
B) 4FH
C) 4EH
D) CEH

43. Which of the following statements is false?
A) Virtual memory implements translation of a program’s address space into physical memory
address space
B) Virtual memory allows each program to exceed the size of the primary memory
C) Virtual memory increases the degree of multiprogramming
D) Virtual memory reduces the context switching overhead

44. Which of the following is not a necessary condition for a deadlock to occur?
A) Mutual Exclusion
B) Hold & Wait
C) Pre-emption
D) Circular wait

45. Banker’s algorithm for resource allocation deals with
A) Deadlock prevention

B) Deadlock avoidance
C) Deadlock recovery
D) Mutual exclusion

46. A computer has a 24-bit virtual address space and 512 byte pages. A page table entry takes 2 –
bytes. A multilevel page table is used because each page table must be contained with a page.
How many levels are required?
A) 2
B) 3
C) 4
D) 5

47. For all the delayed branch instructions, irrespective of whether the condition evaluates to true or
false.
A) The instruction following the conditional branch instruction in memory is executed.
B) The first instruction in fall through path is executed.
C) The first instruction in taken path is executed.
D) The branch takes longer to execute than any other instruction.

48. The primary key on table STUDENT is the RollNO column. Which of the following statements
will not use the associated index on RollNO?
A) select * from STUDENT where nvl (RollNO, '00000') = '12';
B) select * from STUDENT where RollNO = '12';
C) select RollNO, LASTNAME from STUDENT where RollNO = '12';
D) select 1 from STUDENT where RollNO = '12';

49. Your unmask value is set to 022 and you create a file. Which set of permissions are associated
with this file?
A) rw -rw - rw -
B) rwxr- -r --
C) rw-r- -r--
D) rwxrwxrwx

50. Which of the following IP address is not in range of IP address spanned by CIDR address
192.168.10.0/20
A) 192.168.12.0
B) 192.168.11.0
C) 192.168.16.0
D) 192.168.15.0

51. What can be the maximum size of stage -1 boot program at the beginning of a hard disk,
assuming a 4 bytes bootstrap magic bit pattern, 64 bytes of for partition table and 512 bytes of
sector size.
A) 448 bytes
B) 508 bytes

C) 444 bytes
D) 512 bytes

52. An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
A) The SLR(1) parser for G has S-R conflicts
B) The LR(1) parser for G has S-R conflicts
C) The LR(0) parser for G has S-R conflicts
D) The LALR(1) parser for G has reduce-reduce conflicts

53. Consider a machine with 128 MB physical memory and a 24-bit logical address space. If the
page size is 2KB, what is the size of the page table?
A) 16 KB
B) 8 KB
C) 2 KB
D) 24 KB

54. What are the port numbers used by FTP for File Transfer and Control connection respectively
A) 21,20
B) 20,21
C) 20,25
D) 21,22

55. Which of the following statement(s) is (are) true
(i) In a tree, there is only one unique path connected any two nodes
(ii) If G is a tree with p vertices and q edges then q=p-1
A) Only (i)
B) Only (ii)
C) Both (i) and (ii)
D) None is true

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

57. Which of the following statements are true?
1. Every left recursive grammar can be converted into the right recursive grammar and vice
versa
2. All ε -productions can be removed from the context free grammar by suitable
transformations

3. The language generated by the context free grammar all of whose productions are of
form X w or X wY (where w is string of terminals and Y is non terminal), is
always regular.
4. Derivation trees of strings generated by a context free grammar in Chomsky Normal
form are always binary trees
A) All are true
B) 2, ,3, and 4 only
C) 1, 3, 4 only
D) 1,2, and 4 only

58. Testing of software in actual environment with actual data is called
A) Alpha Testing
B) Beta Testing
C) Gamma testing
D) Real Testing

59. To provide more subnets, a class B address is assigned the subnet mask of 255.255.248.0. How
many hosts are possible per subnet?
A) 2048
B) 2046
C) 2044
D) 4096

60. What is the sequence of execution of constructor in following derivations, if object of Class D is
instantiated
Class A: public B, virtual C
{};
Class D: Public A
{};
A) C, B, A, D
B) A, B, C, D
C) D, A, B, C
D) D, B, C, A

61. In a demand –paged memory system, it takes 200 ns to satisfy a memory request if the page is in
memory. If the page is not in memory, the request takes 7ms if a free frame is available or the
page to be swapped out has not been modified. It takes 15ms if the page to be swapped out has
been modified. What is the effective access time if the page fault rate is 5% and 60% of the time
the page to be replaced has been modified.
A) 715.34 µs
B) 590.19µs
C) 780.01 µs
D) 800.12 µs
62. Which one of the following statements if FALSE?
A) Any relation with two attributes is in BCNF
B) A relation in which every key has only one attribute is in 2NF

C) A prime attribute can be transitively dependent on a key in a 3 NF relation.
D) A prime attribute can be transitively dependent on a key in a BCNF relation.

63. Which command in UNIX shell displays the file and directory names that begin with characters
a,b, or c and that end with number 1
A) ls –d abc*1
B) ls [a-c*1]
C) ls –ld [abc]*1
D) ls {1,b,c} /* 1

64. For a function of three variables, how many robust and worst test cases are to be generated
A) 13, 15
B) 13, 125
C) 18, 125
D) 18, 32

65. Which of the following is not associated with the DHCP relay agents?
A) It is BOOTP relay agent
B) It direct DHCPDISCOVER packets to DHCP server
C) It is used to find the DHCP server on other networks
D) It is used when multiple DHCP servers are present on the netework.

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

67. Suppose you are developing a software product in organic application mode. Estimated size of
product is 10,0000 lines of code. The nominal effort using COCOMO
A) Should be more than 24 but less than 30 Person months
B) Should be more than 30 but less than 36 Person months
C) Should be more than 36 Person months
D) Should be less than 24 Person months

68. What will be the length and volume of a program using Halstead’s measure if number of unique
operators and operands are 8 each and total count of operators and operands are 20,15
respectively.
A) 48, 140
B) 46, 150
C) 40, 150
D) 48,150

69. In Unified Modelling Language, - sign in class diagram represents

A) Constructor
B) Positive attributes
C) Public visibility
D) Private Visibility

70. Your current working directory is the /mount/drive_1/first directory. Which command string put
you into the /mount/drive_2/second directory?
A) cd ../second
B) cd /drive_2/second
C) cd ../ .. /drive_2/second
D) cd ../ ../second

71. Which of the following statement is not true?
A) Virtual functions should not be static and must be a member of a class
B) Virtual functions may be declared as friend of another class
C) Constructors cannot be declared as virtual but destructors can be declared as virtual.
D) Virtual functions cannot return value when defined in public or protected section.

72. Which of the characteristic is common to traps, subroutine calls and supervisor calls but different
in interrupts?
A) Interrupts calls are synchronous and others are asynchronous
B) Interrupts calls are asynchronous and others are synchronous
C) Only Interrupt calls are caused due to hardware errors
D) Only Interrupt calls change the execution mode to kernel mode.

73. Which of the following instruction can only be executed in the Kernel mode?
A) Write the program counter
B) Read the time-of- day clock.
C) Subroutine Calls
D) Change Memory Management Registers

74. Consider a hash table with hash function (4x +3)mod 5 with starting value 0 and no linear
probing. What should be contents of hash table after inserting following values 2,5,7,9. Note that
“_” represents blank space.
A) _2759
B) _2_59
C) _7_5_9
D) 72_59

75. Which one of the following uses UDP as the transport protocol?
A) HTTP
B) Telnet
C) DNS
D) SMTP
x-x-x