Data Structures — DU B. Voc – Web Designing Previous Year Question Papers

5. (a) Write a program/pseudo code to Merge k Sorted Arrays Using a Min-Heap. (8) (b) Given an array of integers num, find the maximum subarray sum. A subarray is a contiguous non-empty sequence of elements within the original array. (7) 6. (a) What do you mean by Dequeue? Given an array and an integer K, find the maximum for each and every contiguous subarray of size K. (7) Example: Input - arr[] = {1, 2, 3, 1, 4, 5}, K = 3 (b) Given an array of integers representing the heights of buildings, find the largest rectangle that can be formed by choosing two buildings and drawing a rectangle between them. (8) 7. (a) How do you handle overflow and underflow conditions in a Queue? Give example of each. (5) (b) How can a stack be used to check if a parenthesis expression is balanced? What is the time complexity of enqueue and dequeue operations in a Queue? (5) (c) Write an algorithm to serialize and deserialize a B tree. (5) 4. Parts of a questions should be attempted together. 1. (a) What are the operations in array ? Give example of each and Time Complexity. (3) (b) Write an algorithm for enqueue and dequeue operations in Queue? (3) (c) What is bubble Sort? write an example of bubble sort and time complexity of that. (3) (d) Given an array, write a program to find the maximum sum by adding the numbers alternatively? (3) Example: Input - 2 3 4 5 6 (e) Difference between min heap and max heap?(3) (f) Write an algorithm in which insertion should be in O(n) time and deletion should be in O(1) time, in stack using queue. (3) (g) What is the difference between circular linked list and double linked list. (3) (h) In how many ways Binary tree can be traversed? which Data Structure is used to traverse in Each way. (3) (i) Write three applications of Complete Binary Tree. (i) What are types of Stack Data Structure ? what are the limitations of Stack? (3) 2. (a) Demonstrate how to implement a complex recursive operation, like balancing an AVL tree or finding the lowest common ancestor in a binary search tree, while discussing the underlying recursive principles and time complexity? (10) (b) What are the key principles for designing an efficient and secure hash function, and how can I ensure uniform distribution of hash values while minimizing collisions? (5) 3. (a) Find the point in an array from where the array will go in ascending from descending order. (7) Example: Input - 8 7 6 5 12 14 16 (b) Convert given infix expression to Prefix and Postfix expression using Stack? (A+(B/C)*(D ^ E)-F) (8) 4. (a) Write a Program/Pseudo code to Flatten a Binary Tree to a Linked List (In-place) using: (10) (i) Iterative Approach (ii) Recursive Approach (b) Write an algorithm for implementing stack using linked list, Time complexity should be O(1). (5)