Data Structure and Algorithms

This is the question set Data Structure and Algorithms Fall old 2017, which was taken by Pokhara University.

Pokhara University – Data Structure and Algorithms Fall 2017 old

Level:  Bachelor 
Semester: Fall
Year: 2017
Program: BCIS
Full Marks: 100
Course: Data Structure and Algorithms (old)
Pass Marks: 45

Time:  3hrs.

Candidates are required to give their answers in their own words as far as practicable.
The figures in the margin indicate full marks.
Attempt all the questions.

    1. a) What do you mean by data structure? Explain Built-in data structures and user-defined data structures. (7)
        b) What do you mean by expression tree? Convert the infix expression (A + B) / (C $ D) / E * F - G to the postfix expression using stack.  (8)

    2. a) Why Stack is called LIFO data structure? Write an algorithm for basic operations on a stack. (7)
    b) What do you mean by Height Balanced Tree? Create height balanced tree from the following data: (8)
         40, 50, 60, 70, 65, 55, 57, 56, 54, 30 and show the deletion of root.

    3. a) Create a B-tree of order 5 from the following data: (7)
             10, 20, 30,5,40,50,60,50, 8, 6, 70, 80, 65, 50
    b) Define Hash function and load factor. For the input {41, 46, 59, 36, 45, 55, 0, 81, 14, 15}, show the resulting Hash table using linear probing and separate chaining for hash function H(x) = Xmod10. (8)

    4. a) What do you mean by priority queues? Create mi- heap for the data: 20, 18, 21, 28, 9, 26, 9 and 8.   (7)
        b) Create a binomial queue from the following data. (8)
            40, 50, 60, 35, 40, 30, 30, 40, 40, 30, 20 

    5. a) Explain Quick sort with its algorithm one suitable example. (7)
         b) Sort the data {35, 25, 57, 24, 48, 41, 77, 39, 62, and 80} in ascending order using the insertion sort algorithm. (8)

    6. a) Explain the various methods of graph representation techniques.    (7)
        b) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum spanning tree and summarizes the key differences between them. (8)

    7. Write short notes on any two:  (2×5)
         a) Algorithm Analysis
         b) Greedy Algorithm
         c) Topological sort