Computer Science Previous Year Questions (page 6)

Explanation

In a constraint satisfaction problem (e.g. the map colouring problem), constraints are expressed as arithmetic equations and inequalities that bind (restrict) the values of the variables. So option (a) is the proper choice.

Explanation

With the EX-OR operation, an odd number of 1's returns 1 and an even number of 1's returns 0. XOR gives 1 only when the inputs are different (A ⊕ B = A'B + AB'). Here 1 ⊕ 1 ⊕ 0 has two 1's, so it equals 0, not 1. Therefore the incorrect expression is (c) 1 ⊕ 1 ⊕ 0 = 1.

Explanation

F = x'y'z + x'yz + xy'z' + xyz' = x'z(y' + y) + xz'(y' + y) = x'z + xz'

Explanation

(AB' + AB'C + AC)(A'C' + B') = (AB'(1 + C) + AC)(A'C' + B') = (AB' + AC)(A'C' + B') = AA'B'C' + AB'B' + AA'CC' + AB'C = 0 + AB' + 0 + AB'C = AB'(1 + C) = AB'

Explanation

bit rate = no. of channels × Input bit rate = 4 × 100 kbps = 400 kbps

Explanation

Racing is problem of toggling more than once when the inputs are J = 1 and K = 1. The proper combination of propagation delay and edge triggering prevents the racing problem.

Explanation

Equivalence relations on a set are in bijection with partitions of the set. A 5-element set split into 3 classes has partition types (1 + 1 + 3) or (1 + 2 + 2). For the first type, choose the triple: ⁵C₃ = 10. For the second type, choose the singleton (5 ways) and then pair the remaining 4 elements (3 ways): 5 × 3 = 15. Total = 10 + 15 = 25.

Explanation

If R₁ and R₂ are reflexive relations on a set A, then the diagonal Δ = {(a, a) : a ∈ A} is contained in both R₁ and R₂. R₁ ∪ R₂ is reflexive because Δ ⊆ R₁ ⊆ R₁ ∪ R₂. R₁ ∩ R₂ is also reflexive, because Δ ⊆ R₁ ∧ Δ ⊆ R₂ ⇒ Δ ⊆ R₁ ∩ R₂.

Explanation

A clique is a maximal complete subgraph (every vertex connected to all other vertices in the subgraph). Such subgraphs are: (i) {b, c, e, f} (ii) {a, d, g} (iii) {a, b, g} (iv) {b, e, g} (v) {d, e, g}. There are 5 cliques.

Explanation

Instruction pipelining is a technique that implements a form of parallelism called instruction level parallelism with a single processor. It therefore allows faster CPU throughput than would otherwise be possible at a given clock rate.

Explanation

Application of stack(s) are: (i) Implementation of recursion. (ii) Evaluation of a postfix expression. (iii) Reverse a string. Job scheduling is commonly done via queue data structure.

Explanation

Since the given stack size is 5 and at most two elements are on the stack at any time, and no Pop is done on an empty stack, there is no overflow or underflow. The stack operations are performed smoothly.

Explanation

The number of ways to fully parenthesize an expression with n operators is the Catalan number C(n) = (1/(n + 1)) × ²ⁿCₙ. Here the number of operators is n = 4, so C(4) = (1/5) × ⁸C₄ = (1/5) × 8!/(4! 4!) = 70/5 = 14. Note: All operators work as nodes of a binary tree.

Explanation

In a full binary tree (each node has 0 or 2 children) with n nodes, the number of internal nodes is I = (n – 1)/2. When the tree is skewed (each internal node has one leaf child), every internal node adds one level, so the maximum height is also (n – 1)/2.

Explanation

If we delete the root node of a binary search tree, it can be replaced by its inorder successor or inorder predecessor. The inorder predecessor of 24 (largest node in the left subtree) is 16 and the inorder successor is 26. So, from the left subtree, 16 will be the new root.

Explanation

The number of spanning trees in a complete graph with n vertices = nⁿ⁻² = 4⁴⁻² = 16. A complete bipartite graph Kₘ,ₙ has mⁿ⁻¹ × nᵐ⁻¹ spanning trees = 2¹ × 2¹ = 4.

Explanation

Given i = 0, j = 1, k = –1, x = 0.5, y = 0.0. x * y < i + j || k = (((x * y) < (i + j)) || k) = (((0.5 * 0.0) < (0 + 1)) || –1) = ((0 < 1) || –1) = 1

Explanation

In 'C', int (*f( ))[ ]; declares f as a function returning a pointer to an array of integers.

Explanation

The function is recursive and starts with n = 100. It keeps adding the present value to f(n – 2) and stops at n = 0, where it returns 0. So it computes 100 + 98 + ... + 2, an arithmetic series with 50 terms, first term 100 and last term 2. Sum = (n/2)(a + l) = (50/2)(100 + 2) = 2550

Explanation

In a class hierarchy, when a method in a subclass has the name and type signatures as a method in its superclass, then the method in the subclass is said to over ride the method in the superclass.

Explanation

The member functions of a class which is given friend status by another class can access all private, protected and public members of the class granting friendship. Class friendship is neither reciprocal (commutative) nor transitive unless explicitly specified.

Explanation

Robustness is the ability of a computer system to cope with errors during execution and cope with erroneous input. Correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification.

Explanation

(i) A dynamic linker is the part of an operating system that loads and links the shared libraries needed by an executable when it is executed (at “run time”), by copying the context of libraries from present storage to RAM, and filling jump tables and relocating pointers. (ii) Static linker has reduction in overall program execution time than dynamic linker.

Explanation

Given reference string: 0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4. (i) FIFO with 3 page frames: faults occur at 0, 1, 2, 3, 0, 1, 4, 2, 3 (hits at the 2nd 0 and 1 after 4). Total page faults = 9. (ii) FIFO with 4 page frames: faults occur at 0, 1, 2, 3, 4, 0, 1, 2, 3, 4 (hits at 0 and 1 before 4 is loaded). Total page faults = 10. This is Belady's anomaly.

Explanation

Given I/O requests: 98, 37, 14, 124, 65, 67, head at 32. Using FCFS scheduling, total disk moves = (98 – 32) + (98 – 37) + (37 – 14) + (124 – 14) + (124 – 65) + (67 – 65) = 66 + 61 + 23 + 110 + 59 + 2 = 321

Explanation

The scheduling algorithm works as round robin with time quantum T. After a process has executed for T units, its waiting time becomes least (lowest priority), and its turn comes again only after every other process has had a chance for T units.

Explanation

Remaining need = Max need – Current allocation: P₁ = 5, P₂ = 5, P₃ = 3, P₄ = 2. Total allocated = 10, so available = 12 – 10 = 2. Satisfy P₄ (need 2), it releases 3 → available 4. Satisfy P₃ (need 3), releases 5 → available 7 (after P₃ completes). Then P₁ and P₂ can be satisfied similarly. Hence the safe sequence is P₄, P₃, P₁, P₂.

Explanation

• Strategic value of data mining is time stamping → correct • Information collection is an expensive process in building an expert system → correct • An expert system is a computer system that emulates the decision making ability of a human expert.

Explanation

The entity integrity constraint states that primary keys cannot be null. There must be a proper value in the primary key field. The basis of referential integrity is foreign keys. A foreign key in one table references a primary key in another table.

Explanation

The SQL null is the term used to represent a missing value. A null value in a table is a value in a field that appears to be blank. A field with a null value is a field with no value.

Explanation

Drop command remove all tuples of the relation as well as schema also. Delete command in SQL removes tuples from the relation but retain the schema of table in database.

Explanation

Attribute B has distinct values in all tuples, so {B} can be a candidate key, and {B, C} is then only a superkey (not minimal), because a candidate key is a minimal superkey. {A, D} and {C, D} have distinct values in all tuples, so both can be candidate keys. Hence only II could not be a candidate key.

Explanation

(i) Views help provide data independence, allow the schema to change without recompiling existing applications, and help with access control by letting users see only a particular subset of the data. (ii) A conceptual ER model may be used as the foundation for logical data models. (iii) Being unable to store information unless other unrelated information is stored is an insertion anomaly, not an update anomaly. (iv) SQL is not a procedural language. Only statements III and IV are false.

Explanation

Double precision floating point format occupies 8 bytes (64 bits) in computer memory: sign bit (1 bit), exponent (11 bits) and significand precision (53 bits, 52 explicitly stored).

Explanation

Since, each in mesh network total number of cables are required ⁿC₂ = ¹⁰C₂ = 45 Each device needs to be connected to 9 other devices. So, each device needs to have 9 ports.

Explanation

If the angle of incidence is equal to the critical angle, the light beam bends along the interface. When a beam of light travels through media of two different densities, if the angle of incidence is greater than the critical angle, reflection occurs.

Explanation

Each pair of users must have a separate secret key. If N people want to use this method, the number of secret keys needed is ᴺC₂ = N(N – 1)/2.

Explanation

Evolutionary Model is an iterative and incremental approach to software development. It is preferred for software development when requirements are not clear.

Explanation

The waterfall model is a sequential (non-iterative) process; it includes requirements, design, implementation, verification and maintenance. Risk analysis is used in the spiral model.

Explanation

(i) A replay attack (play back attack) is a form of network attack in which a valid data transmission is maliciously or fraudulently repeated or delayed. (ii) A masquerade attack is an attack that uses a fake identity. (iii) A passive attack is network attack in which a system is monitored and sometimes scanned for open ports and vulnerabilities. (iv) Denial of service attack, a type of attack on a network that is designed to bring the network to its knees by flooding it with useless traffic.

Explanation

(A) Line coding is the process of converting digital data into a digital signal – (iii). (B) Block coding provides redundancy to ensure synchronization and inherent error detection – (iv). (C) Scrambling provides synchronization without increasing the number of bits – (ii). (D) Pulse code modulation (PCM) is a technique to change an analog signal to digital data – (i).

Explanation

In write through method, data is written into the cache and the corresponding main memory location at the same time.

Explanation

The displacement addressing mode is similar to register indirect addressing mode, except that an offset is added to the contents of the register. The offset and register are specified in the instruction. Based Indexed Addressing: The operand’s offset is sum of the content of a base register BX or BP and an index register SI or DI. Based Indexed plus displacement addressing mode: In this mode of addressing the operand’s offset is given by offset=[BX or BP]+[SI or DI]+8 bit or 16 bit displacement. Indexed addressing mode: The operand’s offset is the sum of the content of an index register SI or DI and an 8 bit or 16 bit displacement. So, option (D) is correct.

Explanation

In a 16 × 16 grid, the worst case delay happens when a message travels between opposite corners (e.g. upper right to lower left). It passes through 2(N – 1) = 2(16 – 1) = 30 hops.

Explanation

In sequence (c), after visiting 912 (912 > 364) the search moves to the left subtree of 912, so every later node must be less than 912. 913 cannot appear after 912. So, the answer is (c).

Explanation

B is a MIN node: min(3, 12, 8) = 3, so A (MAX) gets α = 3. At C, the first leaf G = 2 gives C a value ≤ 2, which is less than α = 3. Whatever H and I produce, C cannot be chosen by A, so H and I are pruned. Option (b) is correct.

Explanation

Correct matching: Huffman codes – O(nlogn); Optimal polygon triangulation – θ(n³); Activity selection problem – θ(n); Quicksort – O(n²).

Explanation

Huffman code lengths: A (1/2) → 1 bit, B (1/4) → 2 bits, C (1/8) → 3 bits, D (1/8) → 3 bits. Average length = (1/2 × 1) + (1/4 × 2) + (1/8 × 3) + (1/8 × 3) = 14/8 = 1.75 bits per symbol.

Explanation

Properties of Max Heap: Must be complete binary tree. All levels are completely filled except possibly the last level. The last level is filled from Left to Right. Each parent node has a value greater than or equal to its children. Option (a) Not fulfill the property of Max Heap. Option (b) Not fulfill the property of Max Heap. Option (c) Fulfill the property of Max Heap. Option (d) Not fulfill the property of Max Heap. So, the correct option is (c). (xii) Divide and Conquer

Explanation

FORTRAN I, II & IV contain only static variables. All objects in Java are explicit heap dynamic variable & are destroyed by "Garbage Collector" Languages Such as APL, ALGOL 68, & LISP Use implicit heap dynamic variables. So, a-iii, b-i, c-iv, d-ii Hence, correct option is (c).