END TERM EXAMINATION |
|
| Second Semester[MCA] | June 2024 |
| Paper Code: MCA-102 | Subject : Data and File Structure |
| Time:3 Hour | Maximum Marks:60 |
| Note: Attempt all questions as directed. Internal Choice is indicated. | |
| Q1 Attempt any four of the following questions : (4*5=20) | |
| (a) Write a C Program/algorithm to implement two stacks using a single array. | |
| (b) Why Binary Search algorithm is more efficient than linear search? Depict your answer with a suitable example. Mention the time complexity level of two algorithms. | |
| (c) Write a routine to convert a singly linked list into a circular link list. How can you check whether the circular queue is empty or full? | |
| (d) What is a hash table? What are the properties of the hash function? Explain the midsquare hashing function. | |
| (e) Write a program in C to check whether a particular sub-string is present in a given string or not. If found print its location. | |
| (f) Evaluate the following postfix expression step by step using the algorithm A B C * / C D * + C B * -, where A=6, B=2, C=3, and D=4. | |
| (g) Elaborate M way search tree. Write the value of max children, min children, min keys, and max keys of a node if the order of the tree is 6. Compare B trees with B+ trees. | |
| (h) Given Prefix expression: A B L M K N P Q and infix expression: L B M A N K Q P. Draw the tree. | |
| (i) Show all the passes using quick sort for the following list 54, 26, 93, 17, 77, 31, 44, 55, 20 | |
| (j) Show the structure of the binary search tree after adding each of the following values in the order: 10,1, 3, 5, 15, 12, 16. What is the height of the created binary search tree? | |
| UNIT I | |
| Q2. a) How a linked list can be used to represent a polynomial 5x3 + 4x2+ 3x + 2. (5) | |
| b) Write a function in C to find the middle of a singly linked list. If the number of nodes is even, then there would be two middle nodes, so return the second middle node. (5) | |
| Or | |
| Q3. a) Formulate an algorithm that detects and removes a cycle in the linked list. (5) | |
| b) Given a linked list and two integers M and N. Write a function in C such that you retain M nodes then delete next N nodes, and continue the same till the end of the linked list. Eg Convert 1,2,3,4,5,6,7,8 if M=2 and N=2 (5) | |
| UNIT II | |
| Q4 (a) What do you know about B-trees? Write the steps to create a B-tree. Construct a B-tree of order 4 and insert the values 34, 45, 98, 1, 23, 41, 78, 100, 234, 122, 199, 10, 40. (5) | |
| (b) Discuss the properties and characteristics of a max-heap and a min-heap. Explain how heapify operations ensure that these properties are maintained during insertion and deletion operations. Provide examples illustrating the construction of both max-heaps from a given array of elements. (5) | |
| Or | |
| Q5. a) Write a function in C for heap sort using heap. (5) | |
| b) Compare AVL trees with Binary tree. Construct an AVL tree by inserting following elements one by one and count the total number of left and right rotations after inserting all the elements 16, 27, 9, 11, 36, 54, 81, 63, 72, 78. (5) | |
| UNIT-III | |
| Q6. a) Explain the concept of breadth-first search (BFS) in graph traversal. Develop an algorithm for BFS. (5) | |
| (b) Develop an algorithm for Warshall’s algorithm to compute the shortest distance between all pairs of vertices in a weighted directed graph. (5) | |
| or | |
| Q7. a) Compute the Minimum Spanning Tree and its cost for the following graph using Prim’s Algorithm. Indicate each step correctly. (5)
|
|
| Q7 (b) Explain the concept of topological sort for the following directed acyclic graph (DAG) (5)
|
|
| UNIT IV | |
| Q8. (a) Write a program in C that merges content of the two files into a third file. (5) | |
| (b) Explain the concept of polyphase merge and how it differs from conventional merge sort algorithms. (5) | |
| or | |
| Q9. a) Explain the sequential file access differs from indexed file access. (5) | |
| b) Consider inserting the keys 10, 22, 31, 4, 15, 28, 17, 59, 88 into a hash table with m=11 slots using open addressing with primary hash function h1(k)=k mod m. Illustrate the inserting of these keys using linear probing, using quadratic probing with c1=1 and c2=2 and using double hashing method with h2(k) = 1+ (k mod(m-1)). (5) | |
