Full Marks: 60
Pass Marks: 24
Time: 3 hours

Attempt any two questions: (2 x 10 = 20)

1. Write a menu program to demonstrate the simulation of stack operations in array implementation.
2. State relative merits and demerits of contiguous list and Linked list. Explain the steps involved in inserting and deleting a mode in singly linked list.
3. A binary tree T has 12 nodes. The in-order and pre-order traversals of T yield the following sequence of nodes:
   • In-order : VPNAQRSOKBTM
   • Pre-order : SPVQNARTOKBM

Construct the Binary tree T showing each step. Explain, how you can arrive at solution in brief?

Attempt any eight questions: (8 x 5 = 40)

4. Consider the function:

   void transfer (int n, char from, char to, char temp){
        if (n > 0){
            transfer ( n – 1, from, temp, to);
            printif ( "In Move Disk % d from % C to % C" n, from, to);
            transfer ( n – 1, temp, to, from);
        }
    }

   Trace the output with the function Cell transfer(3,'R','L','C');
5. “To write an efficient program, we should know about data structures.” Explain the above statement.
6. Write C function to display all the items in a circular queue in array implementation. Write assumptions, you need.
7. Explain Divide and Conquer algorithm taking reference to Merge Sort.
8. Trace Binary Search algorithm for the data: 21, 36, 56, 79, 101, 123, 142, 203. And Search for the values 123 and 153.
9. Differentiate between tree and graph. What are spanning forest and spanning tree. Explain MST (Minimum cost Spanning Tree) problem.
10. A file contains 100 symbols in which following character with their probability of occurrence. Build a Huff man tree according to Greedy Strategy.
    
11. Explain the use of Big O notation in analyzing algorithms. Compare sorting time efficiencies of Quick-Sort and Merge-Sort.
12. Explain CLL, DLL, DCLL (Circular, Doubly, Doubly Circular Linked List).
13. Write Short notes on (any two):
    • a. Hash function
    • b. External Sorting
    • c. ADT.