Data Structures — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

1. State whether the following statements are True or False. a. The time complexity of linear search is always O(log n), because it checks elements one by one. b. If an array is already sorted in ascending order, then binary search will always take O(1) time to find any element. c. The in order traversal of every binary tree always gives the nodes in sorted order. d. For a graph represented using an adjacency matrix, checking whether an edge exists between two given vertices takes O(1) time. e. In a linked list, elements must be stored in contiguous memory locations and each node must contain information to locate the next relevant node. f. In a sparse matrix 3-tuple representation, the first row stores only the first non-zero element of the original matrix. 2.(a) Write the algorithms to insert a node at the beginning (head) of the following types of linked lists. 1. Doubly linked list 2. Circular linked list Also mention one application of each type. 2.(b) What is a sparse matrix? Represent the following matrix using as a Sparse Array: Write the algorithm to calculate the transpos-=[98e of a Sparse Array. 3. Consider the following graphs and 3(a). Perform depth first traversal for the graph starting from node 1 and depict the step-wise states of the stack and visited array. 3(b). Perform breadth first traversal for the graph starting from node 1 and depict the step-wise states of the queue and visited array. 4.(a) Given the following in order and preorder traversals of a binary tree, determine post-order traversal of a binary tree: Inorder Traversal: d b e a f c g Pre-order Traversal: a b d e c f g 4.(b) Define height, depth, and level of a node in a binary tree. For the following binary tree, write the order of nodes visited in preorder, postorder, and level-ordered traversals. 5.(a) Explain the working of insertion sort using the following array: Show the list after each major pass. Also justify why the worst-case time complexity of insertion sort is O(n2). 5.(b) Write the algorithms to the following operations. a. b. c. push an element onto a Stack enqueue an element onto a Queue delete a node by value from a Linked List 6.(a) Define a heap and explain the difference between a max heap and a min heap. Convert the following array into a max heap conceptually and show the final heap structure: 6.(b) Apply binary search to find 35 in the following sorted array. Depict each step of the searching algorithm.