Instructions:
- The marks are indicated in the right-hand margin.
- There are NINE questions in this paper.
- Attempt FIVE questions in all.
- Question No. 1 is compulsory.
Q.1 Choose the correct option/answer the following (Any seven question only):[2×7=14]
-
What is the time complexity of deleting a linked list?
- O(1)
- O(n)
- O(log n)
- O(n2)
-
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are
- 4 and 15 respectively
- 3 and 14 respectively
- 4 and 14 respectively
- 3 and 15 respectively
-
Which sorting algorithm is stable and works efficiently for small or nearly sorted datasets?
- Quick Sort
- Heap Sort
- Insertion Sort
- Selection Sort
-
In a BST, deletion of a node with two children uses
- Random node
- Inorder successor
- Any one of leaf nodes
- Root node
-
In a doubly linked list, what is the minimum pointer updates required to delete a node (not head/tail)
- 1
- 2
- 3
- 4
-
Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?
- Preorder and Inorder
- Inorder and Postorder
- Preorder and Postorder
- None of the above
-
The number of edges in a complete graph with 'n' vertices is?
- n(n+1)
- n2
- n(n − 1)/2
- 2n − 1
-
Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
- 1
- 2
- 3
- 4
-
Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is
- 80
- 0125
- 8000
- 25
-
Binary search
- is divide and conquer method
- can be implemented using recursive function
- is better than linear search in worst case
- all of these
Q.2 (a) Explain the role of time-space trade-off while choosing suitable data structure for a real-world application. Take suitable examples.[7]
(b) How Abstract Data Types achieve abstraction? Illustrate your answer with the help of Queue ADT, explaining both physical and abstracted views.[7]
Q.3 (a) Convert the following infix expression to equivalent postfix expression using stack. Also, evaluate the postfix expression using stack: 7 + 5 * 3^2/(9 − 2^2) + 6 * 4. Clearly mention the action taken and stack-state for each symbol scanned from input expression.[7]
(b) What is Circular queue? Write C functions for Q-insert and Q-delete operations on a circular queue.[7]
Q.4 (a) What is Binary Search Tree? Write a C function to insert a given node into BST.[7]
(b) Compare array-based lists and linked lists. Design an algorithm to reverse a singly linked list.[7]
Q.5 (a) Write a C program to implement stack operations using linked list. Analyse the implementation complexity also.[7]
(b) Write an algorithm to insert an element somewhere in the middle of a doubly linked list after given nth node.[7]
Q.6 (a) If the following sequence of numbers is to be sorted using quick sort, then show the iterations/passes of the sorting process: 42, 34, 75, 23, 21, 18, 90, 67, 78.[7]
(b) Write an algorithm for merge sort technique. Derive the best, average and worst complexity of your algorithm also.[7]
Q.7 (a) Explain the concept of hashing and its importance in data structures. Discuss different collision resolution techniques used in hashing.[7]
(b) How does an AVL-tree differ from binary search tree? Insert the following keys in the order given below to build an AVL-tree: 12, 11, 13, 10, 9, 15, 14, 18, 7, 6, 5, 4. Clearly mention different rotations used showing balance factor of each node.[7]
Q.8 (a) The level order traversal of a max heap is 50, 40, 30, 25, 16, 23, 20. What will be the level order traversal after inserting the elements 28, 43, 11 sequentially. Clearly indicate the heapify steps after each insertion.[7]
(b) Discuss various tree traversal schemes with suitable example. Write a recursive function for in-order tree traversal.[7]
Q.9 Write short note on any two of the following:[7×2=14]
- Asymptotic Notations
- BFS and DFS
- B-Tree
- Priority Queue
