Data Structure Using 'C' Winter 2019 Exam Paper PDF

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) Winter – 19 EXAMINATION Subject Name: Data Structure Using ‘C’ Model Ans...

MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) Winter – 19 EXAMINATION Subject Name: Data Structure Using ‘C’ Model Answer Subject Code: 22317 Important Instructions to examiners: 1) The answers should be examined by key words and not as word-to-word as given in the model answer scheme. 2) The model answer and the answer written by candidate may vary but the examiner may try to assess the understanding level of the candidate. 3) The language errors such as grammatical, spelling errors should not be given more Importance (Not applicable for subject English and Communication Skills. 4) While assessing figures, examiner may give credit for principal components indicated in the figure. The figures drawn by candidate and model answer may vary. The examiner may give credit for any equivalent figure drawn. 5) Credits may be given step wise for numerical problems. In some cases, the assumed constant values may vary and there may be some difference in the candidate’s answers and model answer. 6) In case of some questions credit may be given by judgement on part of examiner of relevant answer based on candidate’s understanding. 7) For programming language papers, credit may be given to any other program based on equivalent concept. Q. Sub Answer Marking No. Q. Scheme N. 1. Attempt any Five of the following: 10M a Write any four operations that can be performed on data structure. 2M Ans 1. Data structure operations (Non Primitive) 2 M for any 4 2. Inserting: Adding a new data in the data structure is referred as Operation insertion. 3. Deleting: Removing a data from the data structure is referred as deletion. 4. Sorting: Arranging the data in some logical order (ascending or descending, numerically or alphabetically). 5. Searching: Finding the location of data within the data structure which satisfy the searching condition. 6. Traversing: Accessing each data exactly once in the data structure so that each data item is traversed or visited. 7. Merging: Combining the data of two different sorted files into a single sorted file. 8. Copying: Copying the contents of one data structure to another. 9. Concatenation: Combining the data from two or more data structure. OR 1|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) Data structure operations (Primitive) 1. Creation: To create new Data Structure 2. Destroy: To delete Data Structure 3. Selection: To access (select) data from the data structure 4. Updating: To edit or change the data within the data structure. b Define the term overflow and underflow with respect to stack. 2M Ans Stack overflow: When a stack is full and push operation is performed to 1 M for stack insert a new element, stack is said to be in overflow state. overflow and 1M for stack underflow Stack underflow: When there is no element in a stack (stack empty) and pop operation is called then stack is said to underflow state. c Define the following term w.r.t. tree: (i) In-degree (ii) out-degree. 2M Ans In -degree: Number of edges coming towards node is in-degree of node. 1 M for each correct For e.g. : In degree of node B is 1 definition Out -degree: Number of edges going out from node is out -degree of node. For e.g. Out Degree of is node D is 2 2|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) d Evaluate the following arithmetic expression P written in postfix 2M notation: P : 4, 2, ^, 3, *,3,-,8,4 ,/,+ Ans 2 M for correct Sr. Symbol STACK answer No. Scanner 1 4 4 2 2 4, 2 3 ^ 16 4 3 16, 3 5 * 48 6 3 48,3 7 - 45 8 8 45,8 9 4 45,8,4 10 / 45,2 11 + 47 3|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) e Describe directed and undirected graph. 2M Ans Direct Graph: 1M for each A directed graph is defined as the set of ordered pair of vertices and edges definition where each connected edge has assigned a direction. with diagram Undirected Graph : An undirected graph G is a graph in which each edge e is not assigned a direction. A B D C f Give classification of data structure. 2M Ans 2 M for diagram g Define queue. State any two applications where queue is used. 2M Ans A Queue is an ordered collection of items. It has two ends, front and rear. 1M for Front end is used to delete element from queue. Rear end is used to insert an definition, 1M element in queue. Queue has two ends; the element entered first in the queue for is removed first from the queue. So it is called as FIFO list. applications (any two) 4|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) APPLICATIONS OF QUEUES 1. Round Robin Technique for processor scheduling is implemented using queues. 2. All types of customer service (like railway ticket reservation) center software’s are designed using queues to store customer's information. 3. Printer server routines are designed using queues. A number of users share a printer using printer server (a dedicated computer to which a printer is connected), the printer server then spools all the jobs from all the users, to the server’s hard disk in a queue. From here jobs are printed one-by-one according to their number in the queue. 2. Attempt any Three of the following: 12M a Sort the given number in ascending order using Radix sort: 4M 348, 14, 641, 3851, 74. Ans Pass 1: 4 M for correct 0 1 2 3 4 5 6 7 8 9 answer 0348 0348 0014 0014 0641 0641 3851 3851 0074 0074 0641,3851,0014,0074,0348 Pass 2: 0 1 2 3 4 5 6 7 8 9 0641 0641 3851 3851 0014 0014 0074 0074 0348 0348 5|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) 0014,0641,0348,3851,0074 Pass 3: 0 1 2 3 4 5 6 7 8 9 0014 0014 0641 0641 0348 0348 3851 3851 0074 0074 0014,0074,0348,0641,3851 Pass 4: 0 1 2 3 4 5 6 7 8 9 0014 0014 0074 0074 0348 0348 0641 0641 3851 3851 Sorted Elements are: 14, 74, 348, 641, 3851 b Write an algorithm to insert a new node at the beginning and end of the 4M singly linked list. Ans 1. Algorithm for inserting a node at the beginning 2M for Algorithm for Insert first(start, item) inserting a node at the 1. [check the overflow] beginning if Ptr=NULL then print ‘Overflow’ 2M for exit Algorithm for Inserting A else Node at the End Ptr=(node *) malloc (size of (node)) //create new node from memory and assign its address to ptr 6|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) End if 2. set Ptr->num = item 3. set Ptr->next=start 4. set start=Ptr 2. Algorithm for Inserting A Node at the End insert last (start, item) 1. [check for overflow] If Ptr=NULL, then print ‘Overflow’ exit else Ptr=(node * ) malloc (sizeof (node)); end if 2. set Ptr->info=item 3. set Ptr->next=NULL 4. if start=NULL and if then set start=P 5. set loc=start 6. repeat step 7 until loc->next != NULL 7. set loc=loc->next 8. set loc->next=P c Explain the concept of circular Queue along with its need. 4M Ans  Circular queue are the queues implemented in circular form rather 3 M for than in a straight line. explanation  Circular queues overcome the problem of unutilized space in linear and & 1M for queue implemented as an array. need  The main disadvantage of linear queue using array is that when 7|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) elements are deleted from the queue, new elements cannot be added in their place in the queue, i.e. the position cannot be reused. After rear reaches the last position, i.e. MAX-1 in order to reuse the vacant positions, we can bring rear back to the 0th position, if it is empty, and continue incrementing rear in same manner as earlier.  Thus rear will have to be incremented circularly. For deletion, front will also have to be incremented circularly.  Rear can be incremented circularly by the following code. If ((rear == MAX-1) and (front !=0) Rear =0; Else Rear= rear +1; Example: Assuming that the queue contains three elements.  Now we insert an element F at the beginning by bringing rear to the first position in the queue. this can be represented circularly as shown. Need of Circular Queue:  Circular queues overcome the problem of unutilized space in linear queue implemented as an array.  The element can be stored efficiently in an array so as to wrap around so that the end of queue is followed by front of the queue. d Draw a binary search tree for the given number. 50, 33, 44, 22, 77, 35, 4M 60, 40. Ans 4 M for correct answer 8|28  MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION (Autonomous) (ISO/IEC - 27001 - 2013 Certified) 3. Attempt any Three of the following: 12M a Explain time and space complexity with an example. 4M Ans Time Complexity: Time complexity of program or algorithm is amount of 2M for Time computer time that it needs to run to completion. To measure time Complexity complexity of an algorithm we concentrate on developing only frequency and count for key statements. 2M for space complexity Example: #include void main () { int i, n, sum, x; sum=0; printf(“\n Enter no of data to be added”); scanf(“% d”, &n); for(i=0 ; i