## UGC Net Computer Science Paper II Dec 12 Page 2 (Solved)

11. In compiler design ‘reducing the strength’ refers to
(A) reducing the range of values of input variables.
(B) code optimization using cheaper machine instructions.
(C) reducing efficiency of program.
(D) None of the above
Explanation :I

n compiler design , strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array addressing.

Most of a program's execution time is typically spent in a small section of code (called a hot spot), and that code is often inside a loop that is executed over and over.

A compiler uses methods to identify loops and recognize the characteristics of register values within those loops.

12. In which addressing mode, the effective address of the operand is generated by adding a constant value to the contents of register ?
(A) Absolute
(B) Indirect
(C) Immediate
(D) Index

Explanation : The address of the operand is obtained by adding to the contents of the general register (called index register) a constant value. The number of the index register and the constant value are included in the instruction code. Index Mode is used to access an array whose elements are in successive memory locations. The content of the instruction code, represents the starting address of the array and the value of the index register, and the index value of the current element. By increment or decremented index register different element of the array can be accessed.

13. Which of the following is true ?
(A) A relation in BCNF is always in 3NF.
(B) A relation in 3NF is always in BCNF.
(C) BCNF and 3NF are same.
(D) A relation in BCNF is not in 3NF.
Explanation :When a relation has more than one candidate key, anomalies may result even though the relation is in 3NF.

• 3NF does not deal satisfactorily with the case of a relation with overlapping candidate keys
• i.e. composite candidate keys with at least one attribute in common.
• BCNF is based on the concept of a determinant.
• A determinant is any attribute (simple or composite) on which some other attribute is fully functionally dependent.
• A relation is in BCNF is, and only if, every determinant is a candidate key.

14. Given memory partitions of 100 K,500 K, 200 K, 300 K and 600 K (in order) and processes of 212 K, 417 K, 112 K, and 426 K (in order), using the first-fit algorithm, in which partition
would the process requiring 426 K be placed ?
(A) 500 K
(B) 200 K
(C) 300 K
(D) 600 K
Explanation :In the first fit approach is to allocate the first free partition or hole large enough which can accommodate the process. It finishes after finding the first suitable free partition.

15. What is the size of the Unicode character in Windows Operating System ?

(A) 8-Bits
(B) 16-Bits
(C) 32-Bits
(D) 64-Bits
Explanation : Unicode is a worldwide character-encoding standard. The system uses Unicode exclusively for character and string manipulation.

Typically, a Windows application should use UTF-16 internally, converting only as part of a "thin layer" over the interface that must use another format. This technique defends against loss and corruption of data. Each code page supports different characters, but none of them supports the full spectrum of characters provided by Unicode. Most of the code pages support different subsets, differently encoded. The code pages for UTF-8 and UTF-7 are an exception, since they support the complete Unicode character set, and conversion between these encodings and UTF-16 is lossless.

16. In which tree, for every node the height of its left subtree and right subtree differ almost by one ?
(A) Binary search tree
(B) AVL tree
(D) Complete Binary Tree
Explanation : AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.

The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1(not greater than one).

17. The design issue of Datalink Layer in OSI Reference Model is
(A) Framing
(B) Representation of bits
(C) Synchronization of bits
(D) Connection control
Explanation :

## Framing

The DLL translates the physical layer's raw bit stream into discrete units (messages) called frames. How can the receiver detect frame boundaries? That is, how can the receiver recognize the start and end of a frame?
Length Count:
Make the first field in the frame's header be the length of the frame. That way the receiver knows how big the current frame is and can determine where the next frame ends.Disadvantage: Receiver loses synchronization when bits become garbled. If the bits in the count become corrupted during transmission, the receiver will think that the frame contains fewer (or more) bits than it actually does. Although checksum will detect the incorrect frames, the receiver will have difficulty resynchronizing to the start of a new frame. This technique is not used anymore, since better techniques are available.
Bit Stuffing:
Use reserved bit patterns to indicate the start and end of a frame. For instance, use the 4-bit sequence of 0111 to delimit consecutive frames. A frame consists of everything between two delimiters.Problem: What happens if the reserved delimiter happens to appear in the frame itself? If we don't remove it from the data, the receiver will think that the incoming frame is actually two smaller frames!
Solution: Use bit stuffing. Within the frame, replace every occurrence of two consecutive 1's with 110. E.g., append a zero bit after each pair of 1's in the data. This prevents 3 consecutive 1's from ever appearing in the frame.
Likewise, the receiver converts two consecutive 1's followed by a 0 into two 1's, but recognizes the 0111 sequence as the end of the frame.
Example: The frame ``1011101'' would be transmitted over the physical layer as ``0111101101010111''.
Note: When using bit stuffing, locating the start/end of a frame is easy, even when frames are damaged. The receiver simply scans arriving data for the reserved patterns. Moreover, the receiver will resynchronize quickly with the sender as to where frames begin and end, even when bits in the frame get garbled.
The main disadvantage with bit stuffing is the insertion of additional bits into the data stream, wasting bandwidth. How much expansion? The precise amount depends on the frequency in which the reserved patterns appear as user data.
Character stuffing:
Same idea as bit-stuffing, but operates on bytes instead of bits.Use reserved characters to indicate the start and end of a frame. For instance, use the two-character sequence DLE STX (Data-Link Escape, Start of TeXt) to signal the beginning of a frame, and the sequence DLE ETX (End of TeXt) to flag the frame's end.
Problem: What happens if the two-character sequence DLE ETX happens to appear in the frame itself?
Solution: Use character stuffing; within the frame, replace every occurrence of DLE with the two-character sequence DLE DLE. The receiver reverses the processes, replacing every occurrence of DLE DLE with a single DLE.
Example: If the frame contained ``A B DLE D E DLE'', the characters transmitted over the channel would be ``DLE STX A B DLE DLE D E DLE DLE DLE ETX''.
Disadvantage: character is the smallest unit that can be operated on; not all architectures are byte oriented.
Encoding Violations:
Send an signal that doesn't conform to any legal bit representation. In Manchester encoding, for instance, 1-bits are represented by a high-low sequence, and 0-bits by low-high sequences. The start/end of a frame could be represented by the signal low-low or high-high.The advantage of encoding violations is that no extra bandwidth is required as in bit-stuffing. The IEEE 802.4 standard uses this approach.
Finally, some systems use a combination of these techniques. IEEE 802.3, for instance, has both a length field and special frame start and frame end patterns.

18. Given the following expressions of a grammar
E → E * F / F + E / F
F  → F – F / id
Which of the following is true ?
(A) * has higher precedence than +
(B) – has higher precedence than *
(C) + and – have same precedence
(D) + has higher precedence than *
Explanation :Operator at lower  level in tree has higher precedence than operator at upper levels

- has higher precedence than  +and *

+  and * have equal precedence

19. The maturity levels used to measure a process are
(A) Initial, Repeatable, Defined,Managed, Optimized.
(B) Primary, Secondary, Defined,Managed, Optimized.
(C) Initial, Stating, Defined,Managed, Optimized.
(D) None of the above
Explanation :There are five levels defined along the continuum of the model and, according to the SEI: "Predictability, effectiveness, and control of an organization's software processes are believed to improve as the organization moves up these five levels. While not rigorous, the empirical evidence to date supports this belief".

1. Initial (chaotic, ad hoc, individual heroics) - the starting point for use of a new or undocumented repeat process.
2. Repeatable - the process is at least documented sufficiently such that repeating the same steps may be attempted.
3. Defined - the process is defined/confirmed as a standard business process.
4. Managed - the process is quantitatively managed in accordance with agreed-upon metrics.
5. Optimizing - process management includes deliberate process optimization/improvement.

20. The problem of indefinite blockage of low-priority jobs in general priority scheduling algorithm can be solved using :
(A) Parity bit
(B) Aging
(C) Compaction
(D) Timer