BE Computer Engineering (Pokhara University) Data Structure and Algorithms (PU, CMP 160) Question Paper 2078

(a) Define a stack and a queue as abstract data types, clearly stating the operations and the access policy (LIFO vs FIFO) of each. (b) Write an algorithm to convert an infix expression to its equivalent postfix form using a stack, and trace your algorithm on the expression A + B * (C - D) / E. (c) Explain how a circular queue overcomes the limitation of a simple linear queue implemented in an array, and write the conditions used to detect a full and an empty circular queue.

(a) Construct a Binary Search Tree (BST) by inserting the following keys in the given order: 45, 15, 79, 90, 10, 55, 12, 20, 50. Show the tree after each insertion. (b) Write the inorder, preorder and postorder traversal sequences of the resulting tree. (c) Describe, with the help of diagrams, the procedure to delete a node that has two children from a BST, and apply it to delete the node 45 from the tree you constructed.

(a) Differentiate between the adjacency matrix and adjacency list representations of a graph, comparing their space and time requirements. (b) Explain the Breadth First Search (BFS) and Depth First Search (DFS) traversal techniques, mentioning the auxiliary data structure used by each. (c) Apply Dijkstra's algorithm to find the shortest path from source vertex A to all other vertices in a weighted graph of your choice (at least 5 vertices), showing the contents of the distance and visited sets at each step.

(a) Explain the working principle of Quick Sort with a suitable example, clearly describing the partitioning step. (b) Sort the array [38, 27, 43, 3, 9, 82, 10] using Merge Sort and show every level of division and merging. (c) Derive the best-case, average-case and worst-case time complexities of Quick Sort and explain under what input condition the worst case occurs.

Write a recursive function to compute the n-th Fibonacci number. Draw the recursion tree for fib(5), and explain why this recursive approach has exponential time complexity. Suggest one technique to improve its efficiency.

Write an algorithm to reverse a singly linked list in place (without using extra nodes), and explain its time and space complexity. List two advantages of a doubly linked list over a singly linked list.

What is a hash collision? Insert the keys 12, 22, 32, 42, 52 into a hash table of size 10 using the hash function h(k) = k mod 10, resolving collisions using (a) linear probing and (b) separate chaining. Show the resulting table in each case.

Define Big-O, Big-Omega and Big-Theta notations. Arrange the following functions in increasing order of growth rate: n!, n log n, 2^n, n^2, log n, n. Justify the placement of n log n relative to n^2.

Write the algorithm for binary search on a sorted array and trace it to search for the key 23 in the array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Explain why binary search cannot be applied directly to a singly linked list.

What is an AVL tree? Insert the keys 30, 20, 10 into an empty AVL tree and show the rotation required to keep it balanced, naming the type of rotation performed. State the balance factor condition that every node of an AVL tree must satisfy.

Differentiate between a stack and a queue with respect to insertion and deletion, and give one real-world application of each. Also explain how two stacks can be used to implement a queue.