OCET M.Tech CSE paper

Can you give me question paper for Punjab University Common Entrance Test M tech CSE examination soon ?

[Arvind Kumar]

Here I am giving you question paper for Punjab University Common Entrance Test M tech CSE examination.
1. Which of the following approach is used by the Merge sort algorithm ?
(A) Divide and conquer (B) Backtracking
(C) Heuristic Search (D) Greedy approach
2. In a set of n elements, for a relation to be reflexive, how many number of relations should
be there ?
(A) 2n2 (B) 2n(n–1)
(C) 2(n)(n+1)/2 (D) 2n–3n(n–1)/2
3. Preprocessing is a phase of translation, which occurs :
(A) After Compilation and Linking (B) After Compilation but before linking
(C) Dynamically at Runtime only (D) Before Compilation
4. What will be the output of the following program ?
void main ()
{ int i, j;
i = 12;
j = ++i + i++;
printf (“\n % d % d”, i, j);
}
(A) 13 26 (B) 14 28
(C) 14 26 (D) 13 28
5. If integer needs two bytes of storage, then maximum value of an unsigned integer is :
(A) 216 – 1 (B) 215 – 1
(C) 216 + 1 (D) 2*216 – 1
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
7. Which of the following algorithms has running time O(n2) in the worst case but O(nlogn)
on average ?
(A) Bubble Sort (B) Tornament 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)
M. E. (Computer Science and Engineering)/A
M. E. (Computer Science and Engineering)/OEC-22656-A <3> [Turn over
M. E. (Computer Science and Engineering)/OEC-22656-A <4>
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) 0 0
M. E. (Computer Science and Engineering)/OEC-22656-A <5> [Turn over
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 subgraph of its union with any other graph
(B) The intersection of two graphs is not necessarily a subgraph of both of them
(C) A spanning subgraph of a graph G is a subgraph 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 an 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 and
initializations 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
M. E. (Computer Science and Engineering)/OEC-22656-A <6>
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 a line size of 128
words. The 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
M. E. (Computer Science and Engineering)/OEC-22656-A <7> [Turn over
30. Consider a grammar with the following productions :
I. S →a a b | b a c | aB
II. S →aS | b
III. S →abb | ab
IV. S a →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 permfile using the following command >chmod 2666 permfile, 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, Behaviour
(D) ER Diagram, DFD, Class Diagram
M. E. (Computer Science and Engineering)/OEC-22656-A <8>
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 single 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
M. E. (Computer Science and Engineering)/OEC-22656-A <9> [Turn over
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 the 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 increase 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 and Wait
(C) Preemption (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
M. E. (Computer Science and Engineering)/OEC-22656-A <10>
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
M. E. (Computer Science and Engineering)/OEC-22656-A <11> [Turn over
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. The deviation 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 is FALSE ?
(A) Any relation with two attributes is in BCNF
(B) A relation in which every key has only one attribute is in 2 NF
(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 {l,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 network
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
M. E. (Computer Science and Engineering)/OEC-22656-A <12>
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 Modeling 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 by 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