Computer Science Previous Year Questions (page 10)

Explanation

A header file cannot be passed to a function in C++, while a constant, a structure and an array can be passed to a function.

Explanation

When you call an overloaded function, the compiler determines the most appropriate definition to use by comparing the arguments types you used to call the function with the parameter types specified in the definitions. The process of selecting the most appropriate overloaded function is called overload resolution.

Explanation

In a microprogrammed control unit, the next address generator (sequencer) supplies the address to the control address register (B), which addresses the control memory (C); the control word read from control memory supplies the next address information. So B is the control address register and C is the control memory.

Explanation

The '5' in 8085 indicates that it uses a single +5 V power supply (by using depletion-mode transistors), rather than the +5 V, –5 V and +12 V supplies needed by the 8080. Its clock speed is 3 MHz.

Explanation

LXI rp, data (load register pair immediate) loads a register pair with 2 bytes of immediate data. It is generally used to load SP or a memory pointer; the pairs used are H-L, D-E and B-C, where B, D, H hold the MSB and C, E, L hold the LSB.

Explanation

A binary tree of height h has at most 2ʰ leaves. Sorting n elements requires at least n! leaves, so n! ≤ 2ʰ, giving h ≥ lg(n!) ≥ (n/2) lg(n/2) = Ω(n lg n).

Explanation

Red-black trees are one of many search tree schemes that are 'balanced' in order to guarantee that basic dynamic-set operations take O(lg n) time in the worst case.

Explanation

Dijkstra's algorithm always chooses the closest vertex in V – S to add to the set S, where S is the set of vertices whose final shortest-path weights from the source are known. So it is a greedy algorithm.

Explanation

In transportation table: (i) An even number of atleast 4 cells must participate in closed loop and an occupied cell can be considered only once and not more. (ii) Closed loop may or may not be square or rectangle in shape. (iii) All cells in the loop that have a plus or minus sign, except the starting cell, must be occupied.

Explanation

(A) Strings with an even number of a's is regular, since a finite automaton can accept it. (B) Strings of a's whose length is prime, (C) palindromes over {a, b} and (D) strings of a's whose length is a perfect square are not regular: no finite automaton can accept them (provable with the pumping lemma).

Explanation

The book's solution: encapsulation allows us to focus on what something does without considering the complexities of how it works, and abstraction allows us to consider complex ideas while ignoring irrelevant details that would confuse us. Hence, as per the book, neither statement is correct.

Explanation

A class declared abstract cannot be instantiated; it must be extended and its methods implemented. It is designed only to act as a base class to be inherited by other classes. So both I and II are true.

Explanation

(A) is true by De Morgan's law: A ∩ B = (A' ∪ B')'. (B) is false: recursively enumerable languages are closed under union and intersection but not under complementation.

Explanation

CBSE(60) → CBSE(70) → CBSE(80) → CBSE(90) → CBSE(100). CBSE(100) returns 99; then CBSE(90) returns 98, CBSE(80) returns 97, CBSE(70) returns 96 and CBSE(60) returns 95. So the program prints 95.

Explanation

The loop copies all values of 'array' into p. After q = p, q refers to the same array object as p, so p[4] = 20 also makes q[4] = 20. 'array' itself is unchanged, so array[4] = 18. The output is 18 : 20.

Explanation

(i) MS-DOS was a single-user operating system. (ii) XENIX has always been multi-user. (iii) OS/2 does not provide a multi-user facility. The book's key is (d): (A), (B) and (C).

Explanation

Logical address space = number of pages × page size = 2⁶ × 2⁹ = 2¹⁵, so the logical address needs 15 bits. Physical address space = number of frames × page size = 2⁵ × 2⁹ = 2¹⁴, so the physical address needs 14 bits.

Explanation

Fair-share scheduling is a scheduling algorithm in which CPU usage is equally distributed among system users or groups, rather than equally among processes. The priority considers processor utilization by the individual process, by the user or group, and the weight assigned to the user or group, so (A), (B) and (C).

Explanation

User level threads – advantages: thread switching does not require kernel mode privileges; they can run on any OS; they are fast to create and manage. Disadvantages: in a typical OS most system calls are blocking, so if one user level thread executes a system call, all threads of that process are blocked; and a multithreaded application cannot take advantage of multiprocessing.

Explanation

'init' (PID 1) is not the first process in the system; it is the second, since the scheduler/swapper process (PID 0) is created first. So statement (c) is not correct.

Explanation

A synchronous interrupt is one whose source is in phase with the system clock, i.e. interrupts that depend on the system clock (example: a time service that uses the system clock).

Explanation

Virtual memory maps the virtual addresses used by a program into physical addresses. It provides more addressable memory, allows programs larger than physical memory to run, and allows easy swapping; it does not require more I/O. So 'More I/O is required' is incorrect.

Explanation

No single attribute determines all others. The closure {AB}⁺ = {A, B, C, D}, so AB is the only candidate key. 2NF requires non-prime attributes to be fully dependent on the key, but C depends on A alone and D on B alone (partial dependencies). So R is in 1NF but not in 2NF.

Explanation

The correlated subquery computes the average salary of the employee's own company (T.company_name = S.company_name). The query does not use max, so it does not select only the highest paid employee; it selects all employees who earn more than the average salary of their company.

Explanation

Super key: a set of attributes that uniquely identifies a tuple. Candidate key: a minimal super key (no proper subset is a super key). Primary key: the candidate key chosen to identify tuples. So Primary key ⊆ candidate key ⊆ super key.

Explanation

Regression testing verifies that previously developed and tested software still performs correctly after it is changed, so I is true. Equivalence partitioning is a black-box (not white-box) testing method, so II is false.

Explanation

Top-down testing proceeds from the main module to sub-modules; a sub-module not yet developed is simulated by a temporary program called a STUB. Bottom-up testing proceeds from sub-modules to the main module, using DRIVERS to simulate the main module. So only I is true.

Explanation

Vertical alignment of table contents is set by <td valign = 'top | middle | bottom | baseline'> Text here </td>. No option matches exactly; taking 'centre' as middle, option (b) matches.

Explanation

I is false: XML tags are case-sensitive. II is true: JavaScript identifiers are case-sensitive. III is false: CSS can be applied to any XML document. IV is false: a well-formed XML document does not need a DTD. (The book keys option (d).)

Explanation

A GKS segment is any object described by GKS commands and data that start with CREATE SEGMENT and terminate with CLOSE SEGMENT. Segments allow objects to be manipulated by simply referring to the segment number, so segments can be translated, rotated, panned and zoomed.

Explanation

Multilayer perceptron network and support vector machines are examples of supervised learning, while self organizing feature maps and Hopfield networks are examples of unsupervised learning.

Explanation

From α ⊃ β and α infer β is Modus Ponens (not Modus Tollens), and Modus Tollens infers ¬α from α ⊃ β and ¬β. R2 is not Modus Ponens either. So neither R1 nor R2 is correct.

Explanation

A planning graph consists of a sequence of levels that correspond to time steps in the plan; level 0 is the initial state. Each level contains a set of literals (all that could be true at that time step) and a set of actions (all whose preconditions could be satisfied at that step). It is used to obtain heuristic estimates, and a solution can be extracted using GRAPHPLAN.

Explanation

Game playing uses heuristic search, since brute-force computation over hundreds of thousands of positions is not practical.

Explanation

Deterministic and non-deterministic pushdown automata have different expressive power (NPDA accept all context-free languages, DPDA only deterministic CFLs). DFA and NFA are equivalent, and all the Turing machine variants are equivalent.

Explanation

Group the bits in threes from the right: 001 011 101 011. 001 = 1, 011 = 3, 101 = 5, 011 = 3. So (1011101011)₂ = (1353)₈.

Explanation

Convert both numbers to decimal, add, and convert back to base 4: (313)₄ = 3×4² + 1×4¹ + 3×4⁰ = 55; (322)₄ = 3×4² + 2×4¹ + 2×4⁰ = 58. 55 + 58 = 113, and 113 in base 4 is (1301)₄.

Explanation

Grouping the 1s: columns AB = 01 and 11 give B, the row CD = 11 together with the cell AB = 10, CD = 01 give CD and AD. SOP form = AD + CD + B = (A + C).D + B.

Explanation

In the Boolean product, multiplication is replaced by logical AND and addition by logical OR. Row i of A ⊙ B is the OR of the rows of B selected by the 1s in row i of A: row 1 = B1 = 1110, row 2 = B2 = 0110, row 3 = B1 ∨ B2 = 1110, row 4 = B3 = 1011. So option (a) is correct.

Explanation

P ↔ Q = P'Q' + PQ, so ¬(P ↔ Q) = P'Q + PQ', which is true exactly when P and Q differ. This is the same as P ↔ ¬Q (and ¬P ↔ Q).

Explanation

Proposition: ∃x H(x). Negation: ¬∃x H(x) ≡ ∀x ¬H(x).

Explanation

The clock repeats every 12 hours. 101 mod 12 = 5, so the time after 101 hours = 4 + 5 = 9 O'clock.

Explanation

The number of permutations of n objects with n₁, n₂, ..., nₖ identical objects of each type is n!/(n₁! n₂! ... nₖ!). BANANA has 6 letters with A three times, N twice and B once: 6!/(3! 2! 1!) = 60.

Explanation

cx = 0Ah = 10, so the loop body runs 10 times; loop decrements cx and stops when cx = 0h. ax starts at 0 and is decremented 10 times: 0 − 10 = FFF6h (16-bit two's complement). So ax = FFF6h and cx = 0h.

Explanation

After the rotate and shift instructions al = 00011110, and mul cl multiplies it by 2 (append a 0 bit at the LSB): ax = 0000000000111100 = 003CH. For mul, CF = 0 when the high byte of the result is 0 and CF = 1 otherwise; here the high byte is 0, so CF = 0. Hence ax = 003CH; CF = 0.

Explanation

Sequential part = 5% = 0.05, parallel part = 0.95. By Amdahl's law with an infinite number of processors, speed up S = 1 / (1 − 0.95) = 1 / 0.05 = 20.

Explanation

An in-order traversal of a binary search tree always gives the keys in ascending order, so the in-order sequence is 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20.

Explanation

Inserting 10, 1, 3, 5, 15, 12, 16: 10 is the root; 1 is its left child, 3 is the right child of 1 and 5 is the right child of 3; 15 is the right child of 10 with children 12 and 16. The longest root-to-leaf path is 10-1-3-5 with 3 edges, so the height is 3.

Explanation

Merge sort performs O(n log n) comparisons, and comparing two strings of length n takes O(n) time in the worst case. So the worst-case running time is O(n · n log n) = O(n² log n).

Explanation

In a binary heap stored in an array from index 1 to n, the children of index i are at 2i and 2i + 1, so the parent of the element at index i is at floor(i/2).