PSC Assistant Professor Information Technology Model Questions and Answers

76. Let P be a singly linked list. Let Q be the pointer to an intermediate node X in the list. What is the worst case time complexity of the best known algorithm to delete the node X from the list?
(A) O(n)
(B) O(log2n)
(C) O(logn)
(D) O(1)
Answer: A

77. A problem in NP is NP complete if:
(A) Some problem in NP can be reduced to it in polynomial time
(B) The 3-SAT problem can be reduced to it in polynomial time
(C) It can be reduced to any other problem in NP in polynomial time
(D) It can be reduced to the 3SAT problem in polynomial time
Answer: C

78. The maximum number of edges in an acyclic undirected graph with n vertices is:
(A) n-1
(B) n+1
(C) n
(D) 2n-1
Answer: A

79. In a binary tree, the number of internal nodes of degree 1 is 5 and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is:
(A) 15
(B) 11
(C) 12
(D) 10
Answer: B

80. Which of the following sequences of array elements forms a heap?
(A) [23, 17, 14, 6, 13, 10, 1, 12, 7, 5] (B) [23, 17, 14, 6, 13, 10, 1, 5, 7, 12] (C) [23, 17, 14, 7, 13, 10, 1, 5, 6, 12] (D) [23, 17, 14, 7, 13, 10, 1, 12, 5, 7]Answer: C

81. The binary relation r = {(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4)} on the set A = {1, 2, 3, 4,} is:
(A) Reflexive, symmetric and transitive
(B) Neither reflexive, nor irreflexive but transitive
(C) Irreflexive and antisymmetric
(B) Irreflexive, symmetric and transitive
Answer: B

82. In a room containing 28 people, there are 18 people who speak English, 15 people who speak Hindi and 22 people who speak Kannada, 9 persons speak both English and Hindi, 11 persons speak both Hindi and Kannada where as 13 persons speak both Kannada and English. How many people speak all the three languages?
(A) 6
(B) 7
(C) 8
(B) 9
Answer: A

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

84. Which of the following statements is TRUE about the regular expression 01*0?
(A) It represents a finite set of finite strings
(B) It represents an infinite set of finite strings
(C) It represents an infinite set of infinite strings
(D) It represents a finite set of infinite strings
Answer: B

85. Let L be a context free language and M a regular language. Then the language L∩M is:
(A) Always regular
(B) Always a deterministic context free language
(C) Never regular
(D) Always a context free language
Answer: D

86. Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests: 4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7 if LRU replacement policy is used ,which cache block will have memory block 7?
(A) 4
(B) 5
(C) 6
(D) 7
Answer: D

87. Two shared resources R1 and R2 are used by processes P1 and P2. Each process has a certain priority for accessing each resource. Let Tij denote the priority of Pi for accessing Rj. A process Pi can snatch a resource Rk from process Pj, if Tik is greater than Tjk. Given the following:
I. T11>T21
II. T12>T22
III. T11<T21
IV. T12<T22
Which of the following conditions ensures that P1 and P2 can never deadlock?
(A) I and IV
(B) II and III
(C) I and II
(D) None of the above
Answer: C

88. Dijkstra’s banking algorithm in an OS, solves the problem of:
(A) Deadlock avoidance
(B) Deadlock recovery
(C) Mutual exclusion
(D) Context switching
Answer: A

89. In real-time OS, which of the following is the most suitable scheduling scheme?
(A) Round Roin
(B) First Come First Serve
(C) Preemptive
(D) Random Scheduling
Answer: C

90. A Linker:
(A) Is not necessary with variable partitions
(B) Must be run after the loader
(C) Creates a load module
(D) Is not needed with a good compiler
Answer: C

91. A firewall:
(A) Is a computer or router that sits between the trusted and untrusted
(B) It limits network access between the two security domains, maintains and logs all connections
(C) A firewall may need to allow http to pass
(D) All of these
Answer: D

92. 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 receivers public key
(B) Sender encrypts using his own public key
(C) Receiver decrypts using senders public key
(D) Receiver decrypts using his own public key
Answer: A

93. A host is connected to a department network which is part of a university network. The university network in turn, is part of the Internet. The largest network in which the Ethernet address of the host is unique is:
(A) The subnet to which the host belongs
(B) The department network
(C) The university network
(D) The internet
Answer: D

94. In a TCP/IP protocol suite, which one of the following is NOT part of the IP header?
(A) Fragment Offset
(B) Destination IP Address
(C) Source IP Address
(D) Destination port number
Answer: D

95. Count to infinity is a problem associated with:
(A) Link state routing protocol
(B) Distance vector routing protocol
(C) DNS while resolving host name
(D) TCP for congestion control
Answer: B

96. Which of the following statements is TRUE about CSMA/CD?
(A) IEEE 802.11 wireless LAN runs CSMA/CD protocol
(B) Ethernet is not based on CSMA/CD protocol
(C) CSMA/CD is not suitable for a high propagation delay network like satellite network
(D) There is no contention in a CSMA/CD network
Answer: C

97. HELO and PORT, respectively are commands from the protocols:
(A) FTP and HTTP
(B) TELNET and POP3
(C) HTTP and TELNET
(D) SMTP and FTP
Answer: D

98. A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that of:
(A) A combinational circuit
(B) A push down automaton with two stacks
(C) A finite automaton
(D) A push down automaton with one stack
Answer: B

99. In TCP, a unique sequence number is assigned to each:
(A) Byte
(B) Message
(C) Word
(D) Segment
Answer: B

100. What is XML?
(A) Superset of SGML, Extendable Markup Language
(B) Subset of SGML, Extensible Markup Language
(C) Like SGML, Extended Markup Language
(D) None of these
Answer: B