Attempt __only five__ of the following questions. Each question carries equal marks.

__Question-1__**: True or false? If false, correct the statement.**

- Data encapsulation is the separation of the logical properties of data (and its organization) from its implementation ignoring inessential details.
- Both a queue and a stack are a FIFO data structure.
- Any appearance of a function name in its body indicates that the function is recursive.
- Compile-time errors are usually easier to detect and to correct than run-time errors.
- Data abstraction is the separation of the representation of data from the applications that use the data.
- The maximum number of nodes in a full binary tree where the leaf nodes are at level 6 is 64.
- Logical errors can usually be detected by the compiler.
- Recursive functions generally use “while” or “for” statements as their main control structure.
- Searching for a key in a binary search tree requires at most O (log N) comparisons.
- A linked list is a random-access structure.

__ __

__Question-2: __

- Queues are used in many ways by operating systems. Explain.
- FORTRAN uses column-major storage of 2D arrays. Give the general formula for accessing an element A[i,j] in a 2-D array stored in column-major order.
- Show what is written by the following code segment:

createStack(stack);createQueue(queue); for (count = 0; count < 100; ++count) if (count % 2 == 2) stack.Push(count); else queue.Enq(count); while (!(stack.IsEmpty()&& queue.IsEmpty())) cout << stack.Pop()<< “\t”<< queue.Deq() << end1;

__Question-3: __

- What is meant by the following terms:

Static variable, dynamic variable, base case, general (or recursive) case, run-time stack, binding time, stack underflow, queue overflow.

- Write a function called removeOdd that removes all odd numbers in a given queue without changing the order of remaining items in the queue.

__Question-4: __

- A 1-D array is defined as a structured data type made up of a finite, fixed-size collection of ordered homogeneous elements. Explain.
- In each plastic container of Pez candy, the colors are stored in random order. Your little brother likes only the red candies, so he takes out all the candies one by one, eats the red ones and keeps the others in order, so that he can return them to the container in the same order as before. Write a segment of code to simulate this process.

__Question-5: __

- Convert the following recursive functions into their iterative (non-recursive) versions:

**f(n){**

** if (n = 1) return (1)**

** else return (f(n-1) * 2)**

** }**

** **

**f(n){**

**if (n = 1) return (1)**

**else return (f(floor(n/2)) + 1) **

** }**

where **floor** () function represents rounding down function.

- Write two (recursive and non-recursive) procedures to print out a given linked list in reverse order. Briefly differentiate between your recursive and non-recursive implementations.

** **

__Question-6: __

- Explain why the static storage allocation in earlier versions of some programming languages (such as FORTRAN and COBOL) doesn’t support the implementation of recursive procedures.
- Some computers have fairly small ranges of allowable integers. One way to store a really large integer is to put each digit in a node of a linked list. The following list represents the real number 92587. Real numbers, of course, are allowed a much greater range than are integers, so the large integer can be converted into a variable of type Real. Write a function called MakeReal that inputs a pointer to a linked list of digits that represent a large integer, and returns the real-number equivalent of the number.

Best wishes…

Dr.-Ing. Samy Sadek