BE Computer Engineering (IOE, TU) Data Structure and Algorithm (IOE, CT 552) Question Paper 2078

(a) Define a stack and list its basic operations (PUSH, POP, PEEK) along with the overflow and underflow conditions. Write an algorithm to implement these operations using a one-dimensional array. (6)

(b) Convert the following infix expression into its equivalent postfix expression using a stack, showing the stack and output at each step:

A + ( B * C - ( D / E ^ F ) * G ) * H

Then explain how the resulting postfix expression is evaluated using a stack. (6)

(a) Define a Binary Search Tree (BST). Starting from an empty tree, insert the following keys one by one and draw the resulting BST: 45, 30, 60, 25, 40, 55, 70, 35. (5)

(b) Write the inorder, preorder and postorder traversal sequences of the BST obtained in part (a). (3)

(c) From the BST in part (a), delete node 30 and then node 60. Draw the tree after each deletion and clearly explain the rule you applied for deleting a node that has two children. (4)

(a) Differentiate between the adjacency matrix and adjacency list representations of a graph, commenting on their space requirements. (4)

(b) Write the algorithms for Depth First Search (DFS) and Breadth First Search (BFS) traversal of a graph, mentioning the auxiliary data structure each one uses. (4)

(c) For the graph given below, show the order in which vertices are visited using both DFS and BFS, starting from vertex A. Assume adjacent vertices are visited in alphabetical order.

A - B,  A - C
B - D,  B - E
C - F
E - F,  E - G

(4)

(a) Write the algorithm for Quick Sort and explain the working of the partition step with the role of the pivot element. (6)

(b) Sort the following list in ascending order using Quick Sort, choosing the first element as the pivot, and show the array after each partitioning pass:

38, 27, 43, 3, 9, 82, 10

(4)

(c) Derive the best-case and worst-case time complexity of Quick Sort and state when the worst case occurs. (2)

(a) Differentiate between a singly linked list and a doubly linked list with neat diagrams. (3)

(b) Write an algorithm to insert a new node at the beginning and to delete a node from the end of a singly linked list. (5)

(a) What is a circular queue? Explain how it overcomes the limitation of a linear queue implemented using an array. (4)

(b) For a circular queue of size 5, show the contents of the array, FRONT and REAR after the following sequence of operations: enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50), enqueue(60). (4)

(a) Define recursion and explain the difference between a recursive and an iterative solution with respect to memory usage. (3)

(b) Write a recursive function to solve the Tower of Hanoi problem for n disks and determine the total number of moves required for n = 4 disks. (5)

(a) Define a hash function and explain what is meant by a collision in hashing. (3)

(b) Insert the keys 23, 43, 13, 27, 33 into a hash table of size 10 using the hash function h(k) = k mod 10, resolving collisions by linear probing. Show the final table. (5)

(a) Write the algorithm for binary search and state the precondition that the input must satisfy. (4)

(b) Trace binary search to locate the key 23 in the sorted array [4, 8, 15, 16, 23, 42, 50], showing the values of low, high and mid at each step, and derive its time complexity. (4)

(a) Define Big-O, Big-Omega (Ω) and Big-Theta (Θ) asymptotic notations. (4)

(b) Determine the time complexity of the following code fragment in terms of Big-O notation and justify your answer:

for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j = j * 2) {
        printf("%d", i + j);
    }
}

(4)

(a) Define a heap and differentiate between a max-heap and a min-heap. (3)

(b) Build a max-heap from the following list of elements by successive insertion and draw the final heap, then show the array after performing one delete-max operation:

12, 19, 16, 1, 4, 7

(5)