STEP TOWARDS SUCCESS bu es AKASH’S - Guru Gobind Singh Indra Prastha University Series Fe m4 ts =" SOLVED PAPERS [PREVIOUS YEARS SOLVED QUESTION PAPERS] [B.Tech] THIRD SEMESTER Data Structure (CIC-209) Rs.81.00/-Indian Knowledge System* Discrete Mathematics Digital Logic and Computer Design Data Structures Object-Oriented Programming using C++ Computational Methods Lab ECC-263 | Digital Logic and Coraputer Design Lab CIC-255 [Data Structures Lab CIC-257 | Object-Oriented Programming using C++ Lab *NUES: All examinations to be conducted by the concerned teacher as specified in the detailed syllabus of the paper. @ALL RIGHTS RESERVED WITH THE PUBLISHERS (All rights resolved, no part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior written permission of the publisher. Any violation thereof shall lead to legal recourse’ without any further notice.) Published by: AKASH BOOKS 4278/2, Ansari Road, Darya Ganj, New Delhi-110002 Ph, : 0-9818257423, 9971086337 Note :As publishers, we a re committed to serve the student community with the best of our resources. We take every care to eliminate errors during the course of editing printing of books. Therefore, we state that authors, publishers and sellers should not be held responsible for any mistake that might have crept in advertently. Printed at : DelhiSYLLABUS (ACADEMIC SESSION 2014-15) DATA STRUCTURES: INSTRUCTIONS TO PAPER SETTERS Maximum Marks: 75 1, Question No. 1 should be compulsory and cover the entire syllabus. This question should have objective or short answer type questions. It should be of 25 marks. 2. Apart from Question No. 1, the rest of the paper shall consist of four units as per the syllabus. Every unit should have two questions. However, the student may be asked to attempt only 1'question from each unit. Each question should be 12.5 marks. UNIT-I Introduction to programm ing methodologies and design of algorithms. Abstract Data Type, array, array organization, sparse array. Stacks and Stack ADT, Stack Manipulation, Prefix, infix and postfix expressions, theig interconversion and. expression evaluation. Queues and Queue ADT, Queue manipulation. General Lists and List ADT, List manipulations, Single, double and circular lists. [11,72] [No. of hrs. 12] - : UNIT-IL Trees, Properties of Trees, Binary trees, Binary Tree traversal, Tree manipulation algorithms, Expreession trees and their usage, binary search trees, AVL Trees, Heaps and their implementation. [11,72] No. of hrs. 12] UNIT-II Multiway trees, B-Trees, 2-3 trees, 2-3-4 trees, B* and B+ Trees. Graphs, Graph representation, Graph traversal. . — (T1,T2) (No. of hrs. 12] : UNIT-IV Sorting concept, order, stability, Selection sorts (straight, heap), insertion sort (Straight Insertion, Shell sort), Exchange Sort (Bubble, quicksort), Merge sort (only 2 way merge sort). Searching ~ List search, sequential search, binary search, hashing concepts, ha: (Dirgst, subtraction, modulo-division, midsquare, folding, pseudorandom hashing), collision - resolution (by open addressing: linear probe, quadratic probe, ‘pseudorandom collision resolution, linked list collision resolution), Bucket hashing. 171,12] (No. of hrs. 12] ing methodsNEW TOPICS ADDED FROM ACADEMIC SESSION 2022-23 THIRD SEMESTER [B.TECH] 5 DATA STRUCTURE (CIC-209) Q.1. What is the Time - Space Trade Off in Algorithm & also explain its type. Ans, Time-Space Trade-Off in Algorithms A trade off is a situation where one thing increases and another thing decreases. It is a way to solve a problem in: « Either in less time and by using more space, or * In very little space by spending a long amount of time. The best Algorithm is that which helps to solve a problem that requires less space in memory and also takes less time to generate the output. But in general, it is not always possible to achieve both of these conditions at the same time. The most common condition is an algorithm using a lookup table. This means that the answers to some * questions for every possible value can be written down. One way of solving this problem is to write down the entire lookup table, which will let you find answers very quickly but will use a lot of space. Another way is to calculate the answers without writing down anything, which uses very little space, but might take a long time. Therefore, the more time-efficient algorithms you have, that would be less space-efficient. ‘Types of Space-Time Trade-off (a) Compressed or Uncompressed data: A space-time trade-off can be applied : to the problem of data storage. If data stored is uncompressed, it takes more space but less time: But if the data is stored compressed, it takes less space but more time to run the decompression algorithm. There are many instances where it is possible to directly work with compressed data. In that case of compressed bitmap indices, where it is faster to work with compression than without compression. (b) Re-Rendering or Stored images: In this case, storing only the source and rendering it as an image would take more space but less time i.e., storing an image in the cache is faster than re-rendering but requires more space in memory. (c) Smaller code or Loop Unrolling: Smaller code occupies less space in memory butitrequires high computation time that is required for jumping back to the beginning of the loop at the end of each iteration. Loop unrolling can optimize execution speed at the cost of increased binary size. It occupies more space in memory but requires less computation time. (d) Lookup tables or Recalculation: In a lookup table, an implementation can. include the entire table which reduces computing time but increases the amount of memory needed. It can recalculate i.e., compute table entries as needed, increasing computing time but reducing memory requirements. Q.2. What is algorithm and why analysis of it is important? ‘Ans. In the analysis of the algorithm, it.generally focused on CPU (time) usage, Memory usage, Disk usage, and Network usage. All are important, but the most concern is about the CPU time. Be carefill to differentiate between: * Performance: How much time/memory/disk/ete. is used when a program is run.* g-2021 Third Somestor, Data Structure - ‘This depends on the machine, compiler, etc. as well as the code we write. * Complexity: How do the resource requirements of a program or algorithm scale, ie, what happens as the size of the problem being solved by the code gets larger. Note: Complexity affects performance but not vice-versa. Algorithm Analysis: Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a Specific computational problem. Analysis of algorithms is the determination of the amount of time and space resources required to execute it. Why Analysis of Algorithms is important? * To predict the behavior of an algorithm without implementing it on a specific computer. * It is much more convenient to have simple measures for the efficiency of an algorithm than to implement the algorithm and test the efficiency every time a certain Parameter in the underlying computer system changes. * Itis impossible to predict the exact behavior of an algorithm. There are too many influencing factors. * The analysis is thus only an approximation; it is not perfect, * More importantly, by analyzing different algorithms, we can compare them to determine the best one for our purpose. Q.3. Explain the different types of Algorithm analysis? Ans. Types of Algorithm Analysis are as follows: (a) Best case: Define the input for which algorithm takes less time or minimum time. In the best case calculate the lower bound of an algorithm. Example: In the linear search when search data is present at the first location of large data then the best case occurs. (b) Worst Case: Define the input for which algorithm takes along time or maximum time. In the worst calculate the upper bound of an algorithm. Example: In the linear search when search data is not present at all then the worst case occurs. (c) Average case: In the average case take all random inputs and calculate the computation time for all inputs. And then we divide it by the total number of inputs. Average case = all random case time / total no of case Q.4, What is the Asymptotic Analysis of Algorithms? Explain the Different types of Asymptotic Notations? Ans. Asymptotic Analysis - Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst ease scenario of an algorithm. * Asymptotic analysis is input bound i.., if there's no input to the algorithm, it is conclided to work in a constant time. Other than the “input” all other factors are considered constant.LP. University Techl-Akash Books 2021-8 Asymptotic analysis refers to computiny mathernatiealuofts ef computation For ase Genuine te of any operation in computed as f{n) and may be for another operation it is computed as etn) ‘This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small. Usually, the time required by an algorithm falls under three types - * Best Case ~ Minimum time required for program execution. * Average Case — Average time required for program execution. * Worst Case ~ Maximum time required for program execution. Asymptotic Notations Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm. * O Notation + QNotation © @ Notation Big Oh Notation, O : The notation O(n) is the formal way to express the upper bound of an algorithm's running time. It measures the worst case time complexity or the longest amount of time an algorithm can possibly take to complete. Ban For example, for a function fin) Offtn)) = { g(n) : there exists ¢ > 0 and n, such that fla) < c.g(n) for alln>n,.} Omega Notation, © : The notation (n) is the formal way to express the lower pound of en algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.4-2021 ‘Third Somoster, Data Structure For example, for a function fin) Q((n)) = { gin): there exists ¢ > 0 and n, such that g(n) < cf{n) for all n > n,. } Theta Notation, + The notation @(n) is the formal way to express both the I-wer bound and the upper bound of an algorithm's running time. Itis represented as follows O¢fin)) = { g(a) if and only if g(n) = O(n) and gn) = O¢fin) for all n > ny, } Common Asymptotic Notations : Following is a list of some common asymptotic notations — logarithmic quadratic cubic exponential4-2021 ‘Third Somoster, Data Structure For example, for a function fin) Q(f(n)) = { gin): there exists ¢ > 0 and n, such that g(n) < c-f{n) for all n > n,. } Theta Notation, : The notation 8(n) is the formal way to express both the I-wer ‘bound and the upper bound of an algorithm's running time. Itis represented as follows 0(f(n)) = { g(n) if and only if g(n) = O(f(n)) and. g(n) = O(f(n)) for all n > ny.) Common Asymptotic Notations : Following is a list of some common asymptotic notations - logarithmic quadratic cubic exponentialLP. Univorsity-{B/Tech|-Akash Books 2021-5 Q.5. What is tho Sparse Matrix? Explai A int ropresentation of Sparso Matrix. Seen ee Arey Ans. A matrix is a two-dimensional data object made of m rows and n columns, therefore having total m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix. Why to use Sparse Matrix instead of simple matrix ? * Storage: There are lesser non-zero elements than zeros and thus lesser memory can be used to store only those elements. * Computing time: Computing time can be saved by logically designing a data structure traversing only non-zero elements.. Example: 00304 00570 00000 02600 Representing a sparse matrix by a 2D array leads to wastage of lots of memory fas zeroes in the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements, we only store non-zero elements. This means storing non-zero elements with triples- (Row, Column, value). Sparse Matrix Representations can be done in many ways following are two common representations: 1.Array representation _—_2, Linked list representation Method 1: Using Arrays: 2D array is used to represent a sparse matrix in which there are three rows named as * Row: Index of row, where non-zero element is located © Column: Index of coluron, where non-zero element is located * Value: Value of the non zero element located at index — (row, column) oo03s04 Row [ololr{alsfs DOD 0 => Cotumn |2]4|2/3]il2 ooo000 value |3|4/5/7|2[6 02600 Method 2: Using Linked Lists : In linked list, each node has four fields. These four fields are defined as: © Row: Index of row, where non-zero element is located © Column: Index of column, where non-zero element is located « Value: Value of the non zero element located at index (row,column) * Next node: Address of the next nodealata Third Somestor, Data Structure cons a oosto 0 qz-_e +] ae => fale 1 dl] 02600 3} 4/4] 3} al 6) ‘NULL x Sravoruns [OW Q.6. What is a Dis ‘Ans. Two sets are called dig) . a disjoint sets if they don’t have ‘any element in common, the intersection of sets is a null set. A data stricture that stores non overlapping or digjoint subset of elements ie called disjoint set data structure. The disjoint set. ‘data structure supports following operations; * Adding new sets to the disjoint set, . * Merging disjoint sets toa single disjoint set using Union operation. * Finding representative of a disjoint set using Find operation. * Check if two sets are disjoint or not. Consider a situation with a number of persons and the following tasks to be performed on them: ~ Add a new friendship relation, i.e. a person x becomes the friend of another person y ie adding new element toa set. * Find whether individual x is a friend of individual y (direct or indirect friend) A tnion-find algorithm is an algorithm that Performs two useful operations on such a data structure: * Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset. * Union: Join two subsets into a single subset. Here first we have to check if the two subsets belong to same set. If no, th 1en We cannot perform union. Q.7. What is the Polynomial? Ans. A polynomial p(x) is the expression in variable x which is in the form (ax* + bx + .... + jx+ 1), where a, b,c ...., k fall in the category of real numbers and ‘w’ is non negative integer, which is called the degree of polynomial. An essential characteristic of the polynomial is that each expression consists of two parts: * one is the coefficient * other is the exponent Example: 10x? + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value, Points to keep in Mind while working with Polynomials: * The sign of each coefficient and exponent is stored within the coefficient and the exponent itself * Additional terms having equal exponent is possible one y _* The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent Q8. How to represent a Polynomial? term in the polynomialLP. University-{B.Tech]-Akash Books 2021-7 ‘Ans. Polynomial can be represented in the various ways. These are: « By the use of arrays * By the use of Linked List Representation of Polynomials Using Arrays ‘There may arise some situation where you need to evaluate mi i : situation w any polynomial expressions and perform basic arithmetic operations like addition and subtraction with those numbers. For this, you will have to get a way to represent those polynomials. The simple way is to represent a polynomial with degree ‘n’ and store the coefficient of n+1 terms of the polynomial in the array. So every array element will consist of two values: * Coefficient and + Exponent Polynomial representation using Linked List ___ The linked list can be used to represent a polynomial of any degree. Simply the information field is changed according to the number of variables used in the polynomial. Ifa single variable is used in the polynomial the information field of the node contains two parts: one for coefficient of variable and the other for degree of variable. Let us consider an example to represent a polynomial using linked list as follows: Polynomial: 3x 4x?+ 22-9 Linked List: ROOT s[3s]|—+ 42 ala (spo X In the above linked list, the external pointer ‘ROOT point to the first node of the linked list, The first node of the linked list contains the information about the variable with the highest degree. The first node points to the next node with next lowest degree of the variable. Representation of a polynomial using the linked list is beneficial when the Ms operations on the polynomial like addition and subtractions are performed, The resulting elynomial ean also be traversed very easily to display the polynomial. ROOT L__.[s[s 2 aya 0X ROOT2 |___.fs[s [2 ne 3] oD] ‘The above two linked lists represent the polynomials, 3x°- 4x + 2x - 9 and 5x2 232 + 6x + 3 respectively. If both the polynomials are added then the resulting linked will be: ROOT EISELE +|8 | {-s]o [x] st pointer ROOT gives the representation for polynomial, ‘The linked lis 8x3 6x? + 8x — 6.8-2021 Third Semester, Data Structure UNIT -I Q.1. Refer to Q.1 (a) of First Term Examination 2014 (Pg. No. 1-2014) Q2. Refer to Q.1 (b) of First’ ‘Term Examination 2014 (Pg. No. 1-2014) Q8. Refer to Q.1 (c) of First ‘Term Examination 2014 (Pg. No. 2-2014) Q.4. Refer to Q.1 (4) (j),(i) of First Term QB. Refer to Q.2 (a), (b), (c) of First Term Examination 2014 (Pg. No. 3-2014) Q6. Refer to Q.3 (a), (b), (c) of First Term Examination 2014 (Pg. No. 4-2014) Q.7. Refer to Q.4 (a), (b) of First Term Examination 2014 (Pg. No. 7-2014) -Q8. Refer to Q.1 (b) of End Term Examination 2014 (Pg. No. 18-2014) 9. Refer to Q.2 of End Term Examination 2014 (Pg, No. 19-2014) Q.10. Refer to Q.1 (d), (e), (0, (h) of First: ‘Term Examination 2015 (Pg. No. 11-2015) Q.IL. Refer to Q.2 (b) of First Term Examination 2015 (Pg. No. 6-2015) Q.12. Refer to Q.3 (a), (b) of First Term Examination 2015 (Pg. No. 7-2015) Q.13, Refer to Q.4 (a), (b), (c) of First ‘Term Examination 2015 (Pg. No. 8-2015) Q.14, Refer to Q.1 (e) of End Term Examination 2015 (Pg. No. 18-2015) Q.15. Refer to Q.2 (a), (b) of End Term Examination 2015 (Pg. No. 18-2015) Q.16. Refer to Q.1 (c) of End Term Examination 2015 (Pg. No. 30-2015) QUT, Refer to Q.1 (a), (b), (o) of First Term Examination 2016 (Pg. No. 1.2016) Q.18, Refer to Q.2 (a), () of First Term Examination 2016 (Pg. No. 2-2016) Q.19. Refer to Q.$ (a), (b) of First Term Examination 2016 (Pg. No. 3-2016) Examination 2014 (Pg. No. 2-2014) of First Term Examination 2017 (Pg. No. 1-2017) Q.24. Refer to Q.1(c), Q25. Refer to Q.2 (a), (b) of First Term Examination 2017 (Pg, No. 3-2017) Q.26. Refer to Q.3 (a) of First Term Examination 2017 (Pg. No. 3-2017) (b), (¢) of End Term Examination 2017 (Pg. No. 11-2017) End Term Examination 2017 (Pg. No. 16-2017) Q.29. Refer to Q.3 of End Term Examination 2017 (Pg. No. 17-2017) Q.30. Refer to Q.1 (a), (b), (©), (@) of First Term Examination 2018 (Pg. No. 1-2018) Q.31. Refer to Q.2 (a), (b) of First Term Examination 2018 (Pg. No, 2-2018) Q.82. Refer to Q.3 (a) of First Term Exarhination 2018 (Pg. No. 3-2018) Q.33. Refer to Q.1 (b), (0. (0), (0, g) of End Term Examination 2018 (Pg.No.9,10, 11-2018) Q.34. Refer to Q.2 (a), (b) of End Term Examination 2018 (Pg. No, 12-2018) Q.85. Refer to Q.3 (a), (b) of End Term Examination 2018 (Pg. No. 18-2018) 36. Refer to-Q.4 (a) of End Term Examination 2018 (Pg, No. 15-2018)LP. University-[B.Tech]-Akash Books 2021-9 UNIT - It Q.1. Refer to Q.1 (e) of First Term Examination 2014 (Pg. No. 3-2014) Q.2. Refer to Q.1 (a) of End Term Examination 2014 (Pg. No. 18-2014) Q.3. Refer to Q.4 (a), (b) of End Term Examination 2014 (Pg. No. 19-2014) Q.4. Refer to,Q.5 of End Term Examination 2014 (Pg. No. 21-2014) Q.5. Refer to Q.7 of End Term Examination 2014 (Pg. No. 22-2014) Q.6. Refer to Q.1 (a), (b), (c) of First Term Examination 2015 (Pg. No. 1-2015) Q.7. Refer to Q.1 (g) of First Term Examination 2015 (Pg. No. 2-2015) Q.8, Refer to Q.2 (a) of First Term Examination 2015 (Pg. No. 2-2015) Q.9. Refer to Q.1 (a), (b) of Second Term Examination 2015 (Pg. No. 10-2015) Q.10. Refer to Q.2 (a) of Second Term Examination 2015 (Pg: No. 11-2015) Q.11. Refer to Q.1 (b) of End Term Examination 2015 (Pg. No. 16-2015) Q.12. Refer to Q.3 of End Term Examination 2015 (Pg. No. 23-2015) Q.13, Refer to Q.5 of End Term Examination 2015 (Pg. No. 26-2015) Q.14, Refer to Q.8 (b) of End Term Examination 2015 (Pg. No. 30-2015) Q.165. Refer to Q.1 (4), (e) of First Term Examination 2016 (Pg. No. 1-2016) Q.16, Refer to Q.4 (a), (b) of First Term Examination 2016 (Pg. No. 4-2016) Q.17. Refer to Q.1 (c) of End Term Examination 2016 (Pg. No. 11-2016) Q.18. Refer to Q.4 of End Term Examination 2016 (Pg. No. 18-2016) Q.19. Refer to Q.5 of End Term Examination 2016 (Pg. No. 19-2016) Q.20. Refer to Q.6 of End Term Examination 2016 (Pg. No. 25-2016) Q.21. Refer to Q.1 (b), (e) of First Term Examination 2017 (Pg. No. 1, 2-2017) Q.22. Refer to Q.3 (b) of First Term Examination 2017 (Pg. No. 4-2017) Q.23. Refer to Q.4 (a), (b) of First Term Examination 2017 (Pg. No. 7-2017) Q.24. Refer to Q.1 (€), (0, @), (), @ of End Term Examination 2017 (Pg, No, 12, 13,14,15-2017) Q.25. Refer to Q.4 of End Term Examination 2017 (Pg. No. 17-2017) Q.26. Refer to Q.5 of End Term Examination 2017 (Pg. No. 23-2017) Q.27. Refer to Q.6 of End Term Examination 2017 (Pg. No. 25-2017) Q.28. Refer to Q.1 (c) of First Term Examination 2018 (Pg. No. 2-2018) Q.29. Refer to Q.8 (b) of First Term Examination 2018 (Pg. No. 4-2018) Q.30. Refer to Q.4 (a), (b) of First Term Examination 2018 (Pg. No. 6-2018) Q.31. Refer to Q.1 (d) of End Term Examination 2018 (Pg. No. 10-2018) Q.32. Refer to Q.1 (i), G) of End Term Examination 2018 (Pg, No. 11, 12-2018) Q.33. Refer to Q.4 (b) of End ‘Term Examination 2018 (Pg. Nv, 15-2018) 2.34, Refer to Q.5 (a), () of End Term Examination 2018 (Pg, No. 19-2018) Q.35, Refer to Q.7 (b) of End Term Bxamination 2018 (Pg. No. 24-2018)10-2021 ‘Third Semester, Data Structure UNIT - II QL Refer to Q.1 (c), (A), (e) of End Term Examination 2014 (Pg. No. 18-2014) Q2. Refer to Q.3 (a), (b) of End Term Examination 2014 (Pg. No. 19-2014) Q8, Refer to Q.6 of End ‘Term Examination 2014 (Pg. No: 21-2014) Q4, Refer to Q.8 of End Term Examination 2014 (Pg. No. 24-2014) Q.5. Refer to Q.1 (A), (e) of Second Term Examination 2015 (Pg. No. 10-2016) Q.6. Refer to Q.3 (a), (b) of Second Term Examination 2015 (Pg. No. 13-2015) Q.7. Refer to Q.4 (a), (b) of Second Term Examination 2015 (Pg. Ne. 14-2015) QS. Refer to Q.1 (c) of End Term Examination 2015 (Pg. No. 17-2015) Q.9. Refer to Q.4 of End Term Examination 2015 (Pg. No. 24-2015) Q.10. Refer to Q.7 (a), (b), (c) of End Term Examination 2015 (Pg. No. 29-2015) QL Refer to Q.8 (a) of End Term Examination 2018 (Pg. No, 30-2015) Qu12. Refer to Q.1 (a) of End Term Examination 2016 (Pg. No. 10-2016) Q13. Refer to Q.3 (b) of End Term Examination 2016 (Pg. No. 17-2016) Q.14, Refer to Q.7 (b) of End Term Examination 2016 (Pg. No. 30-2016) Q5. Refer to Q.8 (a) of End Term Examination 2016 (Pg. No. 30-2016) Q.16, Refer to Q.1 (e) of E ind Term Examination 2017 (Pg. No. 12-2017) Q.17. Refer to Q.8 of End Term Examination 2017 (Pg. No. 29-2017) Q.18. Refer to Q.9 of End Term Examination 2017 (Pg. No. 81-2017) Q.19, Refer to Q.1 (a) of End ‘Term Examination 2018 (Pg. No. 9-2018) Q.20. Refer to Q.8 (a), (1 b) of End Torm Examination 2018 (Pg. No, 26-2018) Q.21. Refer to Q.9 (a), (b) of End Term Examination 2018 (Pg. No. 30-2018)LP. University-{B:Tech}-Akash Books 2021-11 UNIT - Iv Q.1. Refer to Q.1 (c) of Second Term Examination 2015 (Pg. No. 10-2015) Q.2. Refer to Q.2 (b) of Second Term Examination 2015 (Pg. No, 13-2015) Qs. Refer to Q.1 (a), (@) of End Term Examination 2015 (Pg. No. 16-2015) Q.4. Refer to Q.6 of End Term Examination 2015 (Pg. No. 26-2015) Q.5. Refer to Q.1 (b) of End Term Examination 2016 (Pg. No. 10-2016) Q.6. Refer to Q.1(d) of End Term Examination 2016 (Pg. No. 14-2016) QZ. Refer to Q.7 (a) of End Term Examination 2016 (Pg. No. 28-2016) Q8, Refer to Q.7 of End Term Examination 2017 (Pg. No. 26-2017) Q.9, Refer to Q.1 (e) of End Term Examination 2018 (Pg. No. 10-2018) Q.10. Refer to Q.1 (h) of End Term Examination 2018 (Pg. No. 11-2018) Q.11. Refer to Q.6 (a), (b) of End Term Examination 2018 (Pg. No. 21-2018) Q.12. Refer to Q.7 (a) of End Term Examination 2018 (Pg. No. 22-2018)FIRST TERM EXAMINATION THIRD SEMESTER (B.TECH) [ETCS-209] DATA STRUCTURES—SEPT. 2014 Time: 1.30 hrs. MM. : 30 Note: Attempt any three questions in total including Question No, 1 which is compulsory, Q.1.(@) Define a Double ended queue? What are its type? Ans. A deque is a list in which the element can be inserted or deleted at either end. Ttis also known as a head-tail linked list, because elements can be added to or removed from either the front (head) or back (tail) end. —Consider the deque shown in fig. 29 [s7[45 [54] 63 O12 Left=8 4 5 6 Right=7 8 9 42. [86 63 [27 [18 Right-0 1 2 Left=3 4 5°6 Lef=7 8 9 Double-ended queues Basically, there are two variants of double-ended queue. (1) Input Restricted deque: In this dequeue, insertions can be done at one of the dequeue, while deletion can be done from both ends. (2) Output Restricted deque: In this dequeue, deletions can be done only at one of the dequeue, while insertion can be done on both ends. Q.1.(6) What are linear list? What are it types? An, A linear list is a non-sequential collection of data items called nodes. These nodes in principle are structures containing fields, each node ina linked list has basically two field. (1) Data field (2) Link field. ‘The data field contains an actual value to be stored and processed. And the link field contain the address of the next data item in the linked list, START| INFO} INFO| X Single linked list Nodes Lal prev] INFO [next 2 Prev info | next [ef Prev | into ay Doubly linked list2-2014 ‘Third Semester, Data Structures ‘Types of linked list (1) Singly linked Itt (2) Doubly linked Jist (8) Circular linked list (4) Circular doubly linked list Q.1.(c) Reverse a linked list without using the pointer? Ans. To reverse a linear linked list, three pointer fields are used. These are tpt, ptr, ept which hold the address of the previous node, current node and next node. To begin with the address of the first node, which is held in pointer variable FIRST, is assigned to PTR and typt is assigned value NULL. ° on athe Algorithm: Step 1 Step 2 Step 3 Repeat step 4 while PTR! = NULL, Step 4 (a) CPT = LINK (PTR) (b) LINK (PTR) ='TPT (©) TPT = PTR (@) PTR = CPT Step 5 STOP. : Q.1.(—)@) Convert the following in fix expression into a postfix using a stack. {a+ (b-c)}* ((d-e)(S +g-h) Ans. Symbol Scanned |’ ° Stack Express (Postfix), 1. { { a 2. a { a 3. + (+ a 4. oe b4¢ ab 5. b ime ab 6. a He abe iB ( Ge abe— 8. ) (+ abe — 9. ) abe—+ 10. 2 : abe-+ i. ( * abe — + al ( #(( abe-+ 13. a *( abo-+d 1 4: _ *C abe- +d. = e a abe-+de 7 ) + abe - + de — 36. ) a 4 ( * abe-+de- 18. : ul abe-+de-f ue : We abe—+de-f 29. * oe thee deteLP, University-(B.Tech)-Akash Books * 2014-3 22, - "IG abe-+de-3g 23. h UG abe - + de -fgh 24, ) yt abe-+de-fgh-+ , 25. } = abe ~ + de - fgh-+/* Q.1.(d) (i) If you are usin; ig C language to implement the heterogenous linked list, what pointer type will 1 you use? Ans. We use the void pointer to implement the heterogeneous linked list. The heterogenous linked list contain different data types in its nodes and we need a link, Pointer, to connect them. Since we can't use ordinary pointer for this, we use the void Pointer. Void pointer is a generic pointer type, and capable of storing pointer to any type. Q.1,(e) What are threaded binary Trees? How are threads different from Pointers? And how we can determine the next node to which a thread points? Ans. Ina linked representation of any binary tree, field LEFT and RIGHT will contain null entries. This space may be more efficiently used by réplacing the null entriés by special pointers called threads. Which points to the nodes higher in the trees. Such trees are called Threaded Tree. Difference between threads and pointer: Threads in a binary tree must be distinguished from normal pointer. In a graphical representation of a threaded. binary tree, threads are shown by dotted lines. In a computer memory, an extra field called tag or flag is used to distinguish a thread from a normal pointer. ‘Tree can be threaded using one way threading or two way threading. Ina one way threading, a thread will appear in the right field of the node and will point to the Successor node in the in order traversal of tree; and in two way threading of tree a thread will also appear in the left field of a node and will point to the preceding node in the in order traversal of tree. half of the entries in the pointer Q.2.(a) Write an algorithm or pseudo code to extract characters from a given string from a given position for n characters and store it another string which is initialized atrun time. Ans. # include #define SIZE 100. void print_str (char $ [); void read_str (char S{]); main () ( : char str [SIZE]; dot read_str (Str); : print_str (Str); ) while (Str [0]); ) void read_str (char * S) { inti; char c; for (i = 0; (c= get char ())!="\n';i +4) Sli)=c; Sli) = NULL;4-2014 1 ‘Void print_str (char*S) ‘Third Semester, Data Structures =0;S[iki++) putchar (S{i); putchar (‘\n); ! Q.2.(6) What is Abstract Data type and its i af ee) F typ its implementation through data Ans. Abstract Data Type: Abstract dat ih which specifies the logieal and mathematical node ofthe ela type. canned ‘To implement a fraction data type: ‘Type day strict { int numerator, denomination; fraction; } main () { fraction f f. numerator = 1; £. denomination Application | <—use the ADT i [Specification] «—define the ADT implementation} Implement ADT ‘When we use abstract data type, our program divide into two: ‘The Application: The part that use Abstract data type. The Implementation: The part that implement the Abstract data type. Q.2.(c) How will you check the validity of an expression containing nested parenthesis? ‘Ans. To check the validity of an expression containing nested parenthesis we use the stack. Stack works fine for this. The steps are: (1) Maintain a stack of characters. (2) Whenever you find opening braces ‘(, ,, or {’ push it on the stack. (3) Whenever you find closing traces‘, '?, ‘Y check if top of stack is corresponding opening bracket, if yes then pop the stack, else break the loop and return false. (4) Repeat step 2-3 until end of the string. Q.3.(a) Write a pseudo code/algorithm for (@ insertion at the end of a circular linked list. (éi) Deletion of a node with a given data in a doubly linked list. Ans. _ FIRST 10 18 30 5 PTR cPTLP. University-(B,Tech)-Akash-Books Repeat CPT = Link (CPT) till link (CPT) # FIRST ie, LINK (CPT) = PTR . LINK (PTR) = FIRST 2014-5 FIRST CPT PTR [fo Jolie Lufas Lf 30 5 At the end 1. IfAvail = NULL then linked list is overflow and STOP. 2, PTR < AVAIL, AVAIL < LINK (AVAIL) Read INFO (PTR) . CPT « FIRST . Repeat step 5 while LINK (CPT)! = FIRST CPT <— LINK (CPT) . LINK (CPT) — PTR LINK (PTR) <— FIRST . STOP. (i) If a specific node is given. - if FIRST = NULL then write UNDERFLOW and STOP. . Read DATA as information of node to be deleted. . PTR < FIRST Repeat step (5) while INFO.(PTR) = DATA PTR « RPT (PTR) . CPT <— LPT (PTR) TPT < RPT (PTR) RPT (CPT) — TPT LPT (TPT) — CPT 7. RPT (PTR) < AVAIL AVAIL — PTR 8. STOP. Q.3.(6) How can we use linked list tg store a sparse matrix? . Ans. The most advantage of linked list-is manageability of memory and it is very important for large programs which are used to process a lot of data, To represent a sparse matrix we use a linked list for each row and each column, So its needs two pointers : Next in this row and next in this column. Struct node { node * next (01; node * next row; int row; int col; int value; exnaaae Parone a Class matrix {cans ‘Thitd Semestor, Data Structures ’ # include Struct node \ {int data; struct node * next; hi Void remove Duplicates (Struct node * head) { . Struct node * current Struct nodé* next — next; if Current return; While (Current > next { N current — > next — > data) if (Currnet > 7 dats { next — next = current — > next — > next; free (current _ next); } else { current = current ~ > next; ) ) } void Push (Struct node ** head — ref, int new-data) “( : ? Struct node * new_node = (Struct node*) malloc (size-of (Struct node); new_node — > next = (*tiead-ref); (*head-ref) = new-node; } Void printlist (Struct node * node) , { While (node! = NULL) { printf ("/d", node — > data); node = node — > next;LP. University-(B.Tech)-Akash Books 2014-7 1 int main () { . struct node * head = NULL; \ Push (& head, 20); ‘ Push (& head, 13); Push (& head, 13); Push (& head, 11); : Push (& head, 11); Push (& head, 11); Print f(“/n linked list before duplicate removal”); print List (head); remove Duplicates (head); printf (“In linked list after duplicate Removal); printlist (head); getchar (); ) é Q-4.(@) Consider a float array APR (2:8,- 4:1), 6:10) whose base address is 200. Find the address of APR (5, - 1,8] M Ans. APR (2 : 8,4: 1), 6: 10) length of three dimensional of APR are 4=8—241=7 L)=1-(-4)+1=6 Ly=10-641=5 Accordingly APR contains L, 10 elements. Suppose the programming language store APR in memory in row major order, and Base (APR) = 200 w =4 words per memory cell. The effective indices of the subscripts ar E,=5-2=3 E,=-1-(4)=3 By 7 For row major order, we have: EL, E\L, +E, (BL, +E,) Ly (ByL,+E,)Ly+E, = 105 +2 = 107 Add (APR [5,~1, 8] = 200 + 4 (107) = 200 + 428 = 628. Q.4.(0) Consider a circular queue with fixed 5 position. Find the value of Front & REAR when following operations are performed i) A,B,C, inserted. (ii) Ais deleted. (ii) D&E are inserted. (iv) B & C deleted. (v) F inserted. (vi) D deleted. (vit) G & Hinserted. Ans. (i) A,B, C, inserted. no Circular queue Ala|c t of FRONT REAR8-2014 ‘Third Semester, Data Structures (i) Ais deleted all c FRONT REAR (iii) D & E are inserted. Bic D E \t nowt nea (iv) B & C deleted. { D E fal FRONT REAR (0) Finserted F DIE 1 2 ean Front (vi) Dis deleted. F E fan. FRONT (vii) G & Hinserted. FI] G]H E REAR FRONTEND TERM EXAMINATION THIRD SEMESTER (B.TECH) [ETCS-209] DATA STRUCTURES—JAN. 2015 Time : 8.00 hrs, - Note: Attemptany five questions including Q.No. 1 which is ¢ompulsory. Q.1. Differentiate between (a) B+ & B- tree (B) Stack and queue (c) Merge Sort and Quick sort (@ Sequential search and binary search (@) Direct Hasing and Digit extraction hasting. Ans. (a) Difference between B* and B- tree. Original B-tree had Record pointers in all of the index nodes; B* tree only in leaf nodes. Given’a xey K and the two node pointers L and R around it > all key K and the two node pointer L and R around it (1) all key values pointed to by L are < K. (2) All key values pointed to by R are > = K. > B+ tree data pages are linked together to form a sequential file. Q.1.(6) Stack and queue. Stack Queue (1) Stack is a heap of elements placed (1) Queue is a set of elements one after one over the other. the other (2) Stack Mechanism is last in First Out (2) queue mechanism is First in First (IFO). out (FIFO) (8) Both insertion arid deletion éecur at | (3) Insertion and deletion occur at two the same end. different ends, (4) If there is no value at the top, stack (4) if front = rear queue is said to is empty. empty. : tena () It has subtype such as queue, Papa circular queue, double ended queue, priority queue. Q.L.(c) Merge Sort and Quick sort. Ans. (1) In worst case, Merge sort still maintain a complexity of o (n log n) while quick sort becomes 0 (n°). (2) In quick sort there is pivot selection but there is no pivot selection in merge sort. The array are partitioned equally which continues recursively and finally its merged. (3) Merge sort is not an in place sorting while quick sort is (without regard to the internal stack space that taken by each recursive algorith). Q.1.(@) Difference between sequential search & binary search. Binary search Sequential search (1) Search all, (1) Search one after other. (2) Data should be in sorted, (2) Data can be in any order. (3) Only 1 when condition is used, (3) Any no. of when condition, (4) Only‘='relational operator used. | (4) Any relational operator (5) Access is faster. (5) Access is slow.LP. University-(B,Toch)-Akash Books 2014-19 Q.14e) Direct Hashing and Digit extraction Hashing. Sol. Diroct Hashing: In direct Hashing, the key is the d ; any slgsrithm manipulation. The file must thorefore contain arosord fo vey posnble toy Although situation suitable for direct Hashing are limited. Ttcan he very power me because it generates that there are no synonyms or collision. 'y powerful Digit Extraction Hashing: Using the digit extraction hasti ‘ei extracted from the key and used as the address. for e.g. 6 digit Muinber tohegh to throes adroes, Wo could sole the fire thirdand fourth dgitandvethem atthe ress. x 125870 —> 158) Q.2. Use a Stack to evaluate the following arithmeti i changing stack of the stack of the stack in iebalax forme” ae am ee XYZ “* AB/C +- for X=1,Y=5,Z=2,P=8,A=15,B=3,C=8 Ans. Substitute the value : 152 * * 153/8 += 2 3 . 5 5 | [25 15]..[ 15] 5 5 | [43 1 1 1 25} [25] [25] [25] Las} Las} Liz 1 5 2 a 7 15 3 1 8 + = Q.3.(a) Discuss any two hash function using suitable example? ‘Ans. Hash Function: Hash function is a function which, when applied to the key, produced an integer which can be used as an address in a hash table. Hash Function: (1) Division Method: In the division method for creating hash function, we map a key k into'one of m slots by taking the remainder of k divided by m. : Hk) = Kmod mor h(k)=K mod m +1 for e.g. if the hash table has size m = 12 and the key is k = 100 then h (k) = 4 since it require only a single division operation, hashing by divisionis quite fast. (2) Mid Square Method: In mid square method, we square the key, after getting the number, we take some digit from the middle of that number as an address. Let us take some 4 digit number as a key. : 1337 —SSPSetE 5 1787569 now take 3rd and 4th digit from each number and that will be the hash address of these keys. (Q.3.(b) Which sorting algorithm is easily adaptable to singly linked lists? Explain your answer. Sol. The simple insertion sort is simply adaptable to sit method in which there is an array link of pointers, one for Initially ink (i) =i + 1 for 0 <= i 10, 11, 15, 24, 30, 32, 34, 45, 50, 66, 68, 72, 90. Preorder: (1) Visit the root. (2) Traverse the left subtree of root. (8) Traverse the right subtree of root. — 45, 32, 15, 11, 10, 24, 30, 34, 90, 68, 66, 50, 72 Postorder: 1. Traverse the Left Subtree of root. 2, Traverse the right subtree of root. 8. Visit the root. 10, 11, 30, 24, 15, 34, 32, 50, 66, 72, 68, 90, 45. , 5. For the following sequence determine the binary heap obtained when the keys are inserted one by one in order given into an initially empty heap 16, 14, 10, 8, 7, 9, 3, 2, 4,1 Ans. Binary Heap: The Binary heap data structure is an array that can be viewed asa complete binary tree. Each node of the binary tree corresponds to an element of the carry. The array is completely filled on all levels except possibly lowest. . es represent heap in level order, going from left to right. The array corresponding to e heap. 12 3°45 678 910 A [ae [14 [10 [8 [7] 973] 2/4] Ifan array a contain key value of nodes in a hheap length [A] is the total number of elements. 1 heap-size [A] = length [A] = number of elements ‘The root of the tree A[1) and given indexi ofa node the indices of its parent, left child and right child can be computed. Parent (i) return floor (i/2) Left (i) return 2i Right (i) - X 9 10 return 2i+1 ‘The index of 16 is 1.'To find the index otter, (2) (4) G) child we calculate 1x 2=2. : This takes us correctly to 14. Binary-Heap Q.6. Sort the following numbers using exchange sort and Merge Sort. Illustrate the intermediate steps as well. 100, 300, 95, 60, 900, 800 ‘Ans. Exchange Sort: Exchange sort attempt to improve the ordering by comparing the elements in pairs and exchanging them if they are not in sorted order. This operation is repeated till the table is sorted. The following method compare adjacent elements and is known as Bubble Sort. First Pass 100 no swapping 100 100 100 100 100 200 95 (swapped) 95 95 95 95 95 300 60 (swapped) 60 60 60 60 60 300 10 (swap) 10 | 10 to 10 10 300 300 (No swap) 300 900 900 900 900 900 800 (swap) 800 800 800 800 800 90022-2014 Third Semester, Data Structures nd Pass ‘95 (swap.) 95 ly 95 95 96 60 (Swap) 60 60 60 60 100 10 (swap) 10 10 10 10 100 100 (No swap) 100 100 300 300 300 300 (No swap) 300 800. 800 800 800 £800 (No swap) 900 900 300 900 900 4" Puss 60 10 10 60 95 95 100. 100 No further swaps possible. This is sorted array. 300 300 1 800 800 900 900 _ Merge Sort: Merge sort is a sorting technique that divides the array into subarray of size 2 and merge adjacent pairs we than have approximately n/2 array of size 2. This Process is repeated until there is only.one array remaining of size n. 100, 300, 95, 60, 10, 900, 800 Pass 1: 100 [300] [60] 95] [10] 900] [800] Pass 2: Merge each pair of pairs to obtain the list of elements. 60 | 96 | 100 | 300 10 | 800 | 900 Pass 8: Merge the two subarray into one array. 10 | 60 | 95 [100 | 300 | 800 | 900 Q.7. Define the following tree: (a) AVL Ans. AVL tree is a binary search tree that has an additional balance condition. This balance condition must be easy to maintain.and ensure that the depth of the tree is O (log N). Definition (1) An empty binary tree B is an AVL tree. (2) If B is the non-empty binary tree with B, and By are its left and right subtree then Bis an AVL tree if and only if! (a) B, and By are AVL (6) Ih, —hgl's1 Where h, and hy are the heights of B, and B, sub-tree. Balance Factor: To implement a AVL tree, each node must contain a balance factor. BF = Height of left sub-tree — Height of Right sub-tree. (6) 2-3-4 tree. Ans, In Computer Science, a 2-3-4 tree (also called 2-4 tree) is a self balancing data structure that is commonly used to implement dictionaries. The numbers means a tree where every node with children (internal node) has either two, three or four child nodes. + a 2-node has one data clement, and its internal node has two child nodes. + a B-node has two data element, and its internal has three child nodes. + a 4-node has 3 data element and its internal has 4-child nodes, : (oo r Pgl pa ao 2-node ‘3-node ‘4-nodeLP. Univorsity-(B,Tvch)-Akash Books 2-3-4 tree are B-tree of order 4 like B-tree i ii Scien ane ree in general they can search, insert or * One property of 2-3-4 tree is all external enod are at th + 2-9-4 tree are isometry of Red-black tree. oo () Complete tree is Ans. complete binary tree of depth d is the strictly binary tree all of whose leaves 2014-23 Root level O level 2 level 3 If a binary tree contain m nodes at level I, it contain at most 2m nodes at level I+ 1, since a binary tree can contain almost one node at level O, it can contain almost ol node at level I. ‘Thus the total Number of node in a complete binary tree of depth d equals the sum of the number of nodes at each level between o and d i.e. Number of nodes at level 0 is 2°= 1 Number of nodes at level 1 is 2’ = 1 Number of nodes at level d is 24 => 24. ‘The total nuniber of node is a complete binary tree is 4 2t42%..42% = (d) Expression tree. ‘Ans. Algebric expression such as a/b+(c—de qd) have an inherent tree structure for example following figure is a representation of the expression in equation (1). This kind of tree is called expression tree. * Terminals node of an expression tree are the variable or constants. * The non-Terminals of the expression tree are the operators. * Parenthesis does not appear in the tree. : * The common algebric operators are either unary or binary.24-2014 Third Semester, Data Structures Q8. Write short notes on any two of the following: (a) Bucket Hasing Ans. Closed hashing stores all records directly in the hash table. Each record with the key value value Ky, has a home position that-is h (K,). The slot computed by hash function, When a record is inserted, the bucket to which it is mapped has available space to store the record. If the bucket does not have enough space, however it indicates an error condition called ‘Bucket Overflow’. Bucket overflow occur done to following reasons. Insufficient Buckets: The number of bucket which we denote by nb, must be sen such that nb > nr/fr. Where nr denote total number of record. fr denote the record that fit in the bucket. Skewness: If the selection of a bucket, of others, the bucket is said to be skewed a * Bucket methods are good for implementing hash table stored on disk, because the bucket size can be set to the size of a disk block. (®) Collision Resolution. chor during insertion is more frequent than that 8 against. being symmetrical. Ans. Suppose we want to add a new record R with the key K to our file F, but suppose ‘the memory location address H(/) is already occupied. This situation is called collision. (1) Collision resolution by open addressing. (2) Collision resolution by separate chaining. Open Addressing: In this, all elements are stored in the hash table itself. That is each table entry contains either an element of the dynamic set or NIL. Advantage: The advantage of open addressing is that it avoids pointers together. Instead of following pointers, we compute the sequence of slot to be examined. The extra memory freed by not storing pointers provides the hash table with a large number of slots for the same amount of memory. Hashing with Changing: This method maintain a chain of elements which has the same hash address, We can take the hash table as an array of pointers. Size of hash. table can be number of records. Here each pointer will point to one linked list and the elements which have the same hash address will be maintained in the linked list, We can maintained the linked list in sorted order and each elements of linked list will contain the whole record with key. Advantage: The main advanta; perfect collision resolution. * Here hash table contain only pointer which point to linked list-containing records. Disadvantage: The main disadvantage is also wastage of memory space. In case where records are very small or contains only key. (c) Complexity of program. ‘Ans. The complexity of an algorithm is a function fin) which measure the time and for space used by an algorithm in terms of input size n. The choice of particular algorithm depends on following performance analysis and measurements. (1) Space complexity: Analysis of space complexity of an algorithm or program is the amount of memory it needs to run to complete. ‘The space needed by the program consist of following components. (A) Instruction space (2) Data space (3) Environment stack space. (2) Time complexity: Time complexity of an algorithm is the amount of time it needs to run to completion. ‘The exact time will depend on the implementation of the algorithm programming language, optimising the capability of the compiler used, the CPU speed, other hardware and 0 on, * To measure the time complexity accurately, we have to count all sorts of operations performed in an algorithm. * The time complexity also depend on the amount of data input to a«, algorithm. ge of this hashing is saving of memory space andHA@OLK SETHE FIRST TERM EXAMINATION [SEPT.-2015] THIRD SEMESTER [B. TECH] DATA STRUCTURE [ETCS-209] Time: 1% Hrs. MM :30 Note: Attempt Q.No.1 which is compulsory any two more questions . Q.1. (a) How the resulting BST will look if the input is already sorted in non- decreasing order. aw __ Ans. Ifall nodes are already sorted in non deereasing order then all nodes are inserted into the right side of a binary search tree, for example > nodes are 1, 2,3, 4,5 the BST will look like fm Q.1. (b) Cdnistruct Binary tree T from following sequence. 2) ° PREORDER:ABDGCEHIF INORDER:D GBAHEICF Ans. PREORDER:ABDGCEHIF INORDER:DGBAHEICF (AY 8). D @ =_ © @a® © Q.1. (c) Number of nodes in complete tree is 1000000. Find its depth. (1) ‘Ans. The depth of complete binary tree is log(n) where fo. of nodes is n. So the depth of complete binary tree which has the 1000000 nodes is. Jog (1000000) = 6 : Q.1. (d) Write algorithm/progranrto perform POP operation on stack using singly linked list.22-2015 Third Semester, Data Structure Ans. Void pop (c) { Struct node * ptr; If (top = = NULL) { printf ("Underflow") return; } ptr = top; top = ptr — link; free (ptr); ) Q.1. (e) What is the difference between. ground header linked list and circular header linked list? qq) Q.1. () What is the condition that a circular queue is full if the queue is implemented using arrays? a) Ans. If ((front = = 0) && (rear == Max — 1)|| (front that means queue is overflow or full, Q1, @ Binary tree withN nodes has exactly sususss Null branches a Ans. Binary tree with N nodes has exactly n + 1 null branches. Q.1. (h) What is Time Space Trade off? Q2. (a) Why height balancing tree is required? Create 4, 2, b, ¥, 6, x, di, w, €, v, f. (8) Ans. The first balanced binary search tree or height balancing tree was the AVL tree with has an additional balancing condition. The simplest idea is to require that the Jeft and right subtrees have the same height, so height balancing tree is required. AVL tree of nodes~a, z, b, % 6%, d,w,e, v, f. Creation of AVL ‘Tree AVL tree of following. Nodes: a, z, b, »,¢, x, d, w,¢, v, fInsert a Insert z Insert z ‘There is Balance factor of a is -2 so after R-L rotation the tree is. Insert y Insert ¢ LP. University-[B.Tech.)-Akash Books oe @ 1 2) 0. @ 2 2) +4 ©} 0 ®o 2015-34-2015 ‘Third Semester, Data Structure Insert x ‘There is the Balance factor of b is ~2 So after L-R rotation the tree is— Insert d Insert wLP. University-{B.Tech.]-Akash Books 2015-5 ‘After Insertion of w the Balance factor is unbalanced i rotation the tree is— inced so after applying the L-R Or Insert e After Insertion of node e the tree is unbalanced so after applying the L-L rotation the tree is— 1 Insert v6-2015, ‘Third Scmester, Data Structure After Insert the node v the tree is unbalanced so after apply the RR rotating tree is Insert f After Insert the node f the tree is unbalanced so after apply the R-L rotation the final tree is— Q.2, (b) Write a procedure/program to reverse a singly linked. without using any more memory? @) Ans. Reverse a singly linked list, . Step 1 PTR = FIRST Step 2'TPT = NULL Step 3 Repeat step 4 while PTR! = NULL Step 4 (a) CPT = LINk (PTR)LP. University-{B/Tech, Akash Books (0) LINK (PTR) = TPT () IPT = PTR (d) PTR= CPT! Step 6 Stop. Q.3. (a) Consider the following: in fix expression and convert into reverse polish notation using stack. (6) Ans. (A +(B*C(D/E4F)*G)*H) 2015-7 Character Stack Reverse polish Notatic Scanned Postfix Notation c A A + G A ( HC A B (+0 AB - ores AB ¢ (+ ABC a (+(- ABC* ( (+(-C ABC D (4 (= ABC*D / (4(-U ABC*D E (+4(-U ABC * DE A (CUA ABC * DE F (4 (-U4 ABC * DEF ) (H(- ABC * DEF * (ct ABC * DEF 4/ G (+(-* ABC * DEF */G ) G+ ABC * DEF */G*— * G+* ABC * DEF */G* - H Gt ABC * DEF 4/G* — ) = ABC * DEF4/G*-H*+ Reverse polish notation Q.3. (6) What is an algorithm/program for inserting and deleting a node at a given location in circular linked list. ) Ans. Inserting a node at given location. Step 1. If AVAIL = NULL then write overflow and stop Step 2. Read DATAas information of node after which insertion will be made. Step 3. PTR = AVAIL AVAIL = LINK (AVAIL) Read Info (PTR) Step4. CPT = FIRST Step 6. Repeat Step 6 while Info (CPT) 1=DATA8-2015 Third Semester, Data Structure Step 6. CPT = LINK (CPT) Step 7. LINK (PTR) = LINK (CPT) LINK (CPT) + PTR Step 8° Stop. Deletion of node at given Location. Step 1. "If FIRST = NULL then write underflow and stop. Step 2. _ Read'DATAas information of node to be deleted. Step 3. PTR = FIRST Step 4. Repeat step 5 while info (PTR) # DATA. Step 5. CPT=PTR PTR = LINK (PTR) Step 6. LINK (CPT) = LINK (PTR) Step 7. LINK (PTR) = AVAIL AVAIL = PTR Step 8. Stop. _.. QA. (a) Suppose: multidimensional arrays A and B are declared as A(-2: a and B (1:8, -5:5,-10:5) stored in column major order. @ Find the Jength of each dimensions ofAand B, ii) The number of elements inA and B. (iii) Consider the clements BG, 3, 3) in B. ES, and the address of the element assuming words per memory location. 222) (2.5) qa) Find the effective indices E1, E2, Base(b) = 400 and there are w=4 (2.5) Ans. (i) The length of a dimension is obtained by: Length = upper bound — Lower bound + 1 Hence the length Li of the dimensions of Aare: Ll =2-(-2)+1=5andL2=22-241=21 Li ~141=8,12=5-(-5)+1411,135-(10) +1216 ) Accordingly A has 5*21 = 105 elements and B has 8*11*16 = 1408 elements. (ii) The effective index Ei is obtained fr and LB is the lower bound. Hence El = 3-1= 2, E2=3~-(-5)=E3=3-(-10)=13 Considering B is stored in column-major order, the address of B [3,3,3] will be calculated as. ESL2 = 13*11 = 143, E2L2 + B2 = 143 +8 = 151 (ESL2 + B2) Li = 151*8 = 1208, (ESL2 + £2) L1 + E1 = 1208 +2 = 1210 ‘Therfore address of B [3,3,3] = 400 + 4(1210) = 400 + 4840 = 5240. Q.4 (6) What is Garbage Collections? Ans, Gabage Collection: Garbage collection (GC) is a dynamic approach to automatic memory management and heap allocation that Processes and identifies dead memory block and reallocates storage for reuse. The primary purpose of garbage collection is to reduce taemory leaks, ‘om Ei = ki-LB, where ki is the given indexLP. University-[B.Tech.]-Akash Books "2015-9, Qa. (e) Write algorithm/program for insertion operation on queue using Singly linked list. : Ans. void insert () { struct node * ptr; ptr = (struct node *) malloc (size of (struct node)); int item; . prinf ("Input the element for Inserting’ scanf ("/d", and item); ptr — info = item; ptr > Link = NULL; If (front = = NULL) front = Ptr; else rear —> link = ptr; rear = ptr; }SECOND TERM EXAMINATION [NOV.-2015] THIRD SEMESTER [B. TECH] DATA STRUCTURE [ETCS-209] ‘Time: 1% Hrs, MM:39 Note: Attempt Q.No.1 which is compulsory any two more questions . ' Q.1. (a) Difference between B- tree and B+ tree? @ Ans, Original B-tree had record pointers in all of the index nodes; B+ tree only ir leaf nodes. Given a key K and the two node pointers L and R around it. ~ All key K and the two node pointer L and R around it 1. All key valués pointed to by Lare < K. 2. All key values pointed to by Rand > = K. — B+ tree data pages are linked together to form a sequential file. Q.1. 6) Construct 3-way search tree for the following list of keys. List: 20, 35, 40, 10, 15, 25, 80, 45 Ans. List: 20, 85, 40, 10, 15, 25, 30, 45 8 way Search tree. 20 | 35 25 | 30 ¥ Q.1. (c) Consider the following specification of a graph. VG) = (1, 2, 3, 4, 5} and E(G) = ((1, 2), (1, 3), (8, 3), (8, 4), (4, 1), (4, 5), (5,2 Draw its adjacency matrix. Ans. V(G) = (1, 2, 3, 4, 5) E(G) = ((1, 2), (1, 3), @, 3), , 4), 4, D, (4,5), (5, 20) Adjacency Matrix Representation. “rests Tjori00 2}00000 3}00110 4j10001 5/0 1000 Q.1. (d) Compare the complexities in average case and worst case of th following sorting: Merge sort, Heap sort; Quick sort, Selection sortLP. University-(B.Tech.}-Akash Books 2015-11 Ans. ee Bost Average Worst Guick Sort NlogN NiogN ig Merge Sort NlogN NlogN Nog Heap Sort NlogN N log N log Selection Sort w w N Q.1. (e) What is pseudorandom hashing method? Ans. Pscudorandom Hashing Acommon random-number generator is shown below. y= axte ‘To use the pseudorandom-number generator as a hasing method, we set x to the key, multiply it by the coefficient a, and then add the constant c. The result is then divided by the list size, with the remainder being the hashed address. Example: Y = ((17 x 122267) modulo 307 Y = (2061539 +7) modulo 307 Y = 2061546 Y= 41 Q.2. (a) Construct B-TREE of order 5 by inserting the following elements. 8,14, 7, 1, 8, 5, 11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25 and 19, And also delete values 6, 23, 3 from above constructed tree, Ans. B-Tree of order 5: : Elements: 3, 14,7, 1, 8,5, 11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, 19 Insert 3 3 Insert.14 3 | 14 Insert 7 ei7 in Insert 1 1) 3]7 414 7 Insert 8 1,3 8 | 14 Here node was already full 50 after insert 8, it is splitted into 2 node and 7 is the median key, 7 Insert 5 4 3] 5 8 | 1412-2015 Third Semester, Data Structure Insert 11 and 17 1) 3|5 8 | 11 {14 | 17 7 | 43 Insert 12 i} 3]5 aii 14 | 17 Here node was already full so after insert 13, It is splitted into 2 nodes and 13 is the median key. Insert 6, 23, 12, 20° 7 [43 1[3[s[6 8 [2 4417 [20] 23 Insert 26 7 [13] 20 i[s|[s[e a iufi2 14[17] [a3] 26 Here node was already full, so it is splitted into 2 nodes and 20 is the median key. Insert 4 4 [7] 13]20] 1[3] (5J6 e[ufi2] [sp] [oapas Here node was already full so after Insert 4, It is splitted into 2 nodes and dis the median key. Insert 16, 18, 24, 25 4 [7] 13] 20 173} (se) Ce [1 [42] [14]t6 [17] 78] [23] 2] as [26 Insert 19 13 4[7 Lz [20 +13} [s[e} [elu] [s]ie] Gels] [es] 2s[es [eeLP. Univorsity-(Btveh,|-Akash Booka ; Hore nodo was already full so after Insert 19 it in aplittod, into 2 nodes. 17 is tho 1, 0 es. 17isthe =“ median key 80 it will go into parent node, Hore perent node ia a iti splitted in 2 nodes and 13 is the median key and it will becorse ees 2015-13, the new root, After delete the node 6 8 ar 8: 17 | 20 173) (s]7) (nie ia[i6] [rafts] [23] 2a] 2s]as After delete the node 23 13 as 17 [20 113) (517) fe 14|16] [rafts 24] 25[ 26 After delete the node 3 8 [13 [17 [20 114[517] [riz] Dafss] [eli 24 [25 [26 Q.2. (6) Write algorithm/program of depth first search for traversal of graph? Ans. Step 1: Set status = 1 (ready State) for each node in G. Step 2 : Push the starting node on the stack and set its status = 2 (writing state). Step’ : Repeat steps 4 and 5 until stack is empty. Step 4: Pop the top Node N. Process it and set its status = 3 (processed state). Step 5: ‘Push on to the stack all the neighbour of N that are in the ready state (whose status = 1) and set their. status = 2 (waiting state). Step 6 : Exit. Q.3. (a) Suppose the table T has 11 memeory locations T (1), T(2},...TI11] and suppose the File F consist of 8 records A, B, C, D, E, X, ¥, ZRecord: A, B, C, D, E,X; Y, Z and its hash address U(W): 4, 8, 2, 11, 4, 11, 5, 1 resp. How file F will appear in memory when 8 records arc entered into table T in above order using, linear probing and quadratic probing collision resolution. technique? Find average successful search probes (S) and average unsuccessful search probes (S) and average unsuccessful search probes (U) also for both? Oy Ans. Reord A, B CG, BF B X& Y% & Hk) 4 8 % UW 4 WW 5 2 Suppose the 8 records are entered into the table T in above order using the liner probing and Quadratic probing collision resolution technique then the file F will appear in memory as follows. : Mabie xX C; Address: 1, 214-2015 Third Semester, Data Structure i i ldress H(t) =5, the record is not». Although Y is the only record with hash ad 5, the a toT [5I, since T (8) has already been filled by E because of a previous collisio, an Similarly Z does not appear in T (1). I ‘The average no. S of probes for a successful search follows: 1414+14+14+24+24+243 8 s 13 = +216 8 The average no. U of probes for’an unsuccessful search follows. T+O+5+44342414 2414148 ees = ns ‘The first sum adds the no. of probes to find each of he 8 records, and the second sum adds the no. of probes to find as empty location for cach of the 11 locations, 8. (©) Difference between internal sorting and external sorting? Sort the following elements using shell sort: 11, 88, 22, 77, 33, 66, 44, 55, (148) Ans. Internal sorting: Which deals with sortin, main memory. Example: Bubble, selection ete. sortin, External sorting: Which deals with sorting t Sorting is applied when data can not be stored in th organization, Shell sort: 11, 88, 22, 77, 33, 66, 44, 55 Input to pass 1 with distance = ig the data stored in computer's ig. 11 | 88 | 22 | 77 | 33 | 66 Output of pass 1 is input to pass 2 and distance = 1 att) 220) |e22)|663|.o93 (ars (aa leas Output of pass 2 is 11 | 22 | 33 | 441 55] 66 | 77 | 28 Q-4. (a) Consider a company with 68 employee. Each has been assigned a4 digit employee number which has been assigned a 4 digit employee naber which is used as the primary key in the company’s employce file. Suppose L (se! of memory addresses of the location) consist of 100 two digit addvesses 00,01,02- ~-09. Then apply the division method using prime no. closest to 99, mid square method and folding method to find out 2-digit hash address for cach. of the following employee no. 9614, 5882, 1825, (a2 aiLP. University-[B,Tech.|~Akash Books 2015-15 ‘Ans. () Division Method: Choose a prime no. M close to 99, such as M = 11 (9614) = 11, H (6882) = 62 H (1825) = 79 oo ‘That is dividing 9614 by 97 gives a remainder 11. dividing 5882 by 97 give 62 and so on, In the case that the memory address begin with 01 rather then one choose that the function H(k) = k (mod M) + 1 to obtain: , H (9614) = 11 + 1 = 12, H (5882) = 62 + 1 = 63 H (1825) = 79 +1 =80 (ii) Midsquare Method: K 9614 5882 1825 B 92428996 34597924 3330625 HG) 28 97 06 Observe 4" and 5“ digit are choosen for Hash address. (ii) Folding Method: Choping the keys K into 1, 2, 1 digits and add them. So the address will be: H(9614)=9+61+4=74 H (5882) = 5 +88 +2=95 H (1826) = 148245 ~ 88 QA. (6) Write algorithm/program of anyone sorting technique which is used when input elements are small? Difference between comparison based sorting and non-comparison based sorting? (3+1) Ans. When Input elements are small then many sorting techniques may be used such as, bubble, sort, insertion sort, selection sort ete. Algorithm of Selection Sort L.n=length [Al 2.Forj=1ton-1 3. smallest =/ 4.fori=j+1ton 5. IfAli] 2. #include 20-2015 - ‘Third Semester, Data Structure 8. struct node 4d 5. int data; 6. struct node *next; Ty 8. void push(struct node** top, int data); 9. int pop(struct node** top); 10, struct queue u.{ 12, ‘struct node *stack 1; 18. struct node *stack2; 14.); 16. void enqueue(struct queue *q,, int x) 16. { 17. push(&q->stackl, x); 18.) i 19. void dequeue(struct queue *q) 20. { “21, intx; 22. if (q->stackl == NULL && q->stack2 == NULL) { 23. —_printf(“queue is empty”); 24, return; 25. ) - 26. If (q->stack2 == NULL) { 27. while (q->stack1 != NULL) ( 28. x = pop(&q->stack1); 29. push(&q->stack2, x); a. 31.) 82. x= pop(&q->stack2); 83. . printf(“%d\n",, x); 34.) 35. void push(strict node** top, int aa 36. ( iz 87. struct node* newnode = (struct node*) malloc(sizeof{struct node)); 38. if(newnode == NULL) { 39, Printf(“Stack overflow \n");LP. University-{B.Tech.}-Akash Books 40. return; a} 42, newnode->data = data; 43, newnode-Snext = (*top); 44, (top) = newnode; 45.) BN 46. int pop(struct node** top) 4nd . i 48, int buff; . 49, struct node *t; 80. if(*top == NULL) { 51. _printf{“Stack underflow \n"); 32, return: 53.) \ 54. else (~~ - wh 55. t= *top; 56. buff = t->data; 2015-21 ‘eT. *top = t->next; 58. free(t); ” 59, return buff; 60. } . 61.) 62, void display(struct node *top 1 struct node *top2) 63. ( 64, while (top1 != NULL) [ 65. printft“%ed\n", top1->data); 66. _top1 = top1->next; 67.) : 68. while (top2 [= NULL) { 69. _printf("%d\n", top2->data); 70. _top2 = top2->next; m0) 72.) 78. int main () 74,{ 75. struct queue 76. intf=0, a; 71. charch- Yi 4q = (struct queue*)malloc(sizeof (struct queue));22-2015 ‘Third Semester, Data Structure 78. 79. 80. 81. 82, 83. 84, 85, 86, 87. 88. 89. 90. 91, 92, 93. 94. 95. 96. 97. 98. 99. qe>stackl = NULL; q->stack2 = NULL; while (ch=s‘y’ | Ich=='Y){ printf (“enter ur choice\n1.add to queue\n2. remove from queue\n3.display\n4.exit\n seanfl“%od”., &f); switch(f) ( -case 1: printf (“enter the element to be added to queue\n”); scanf(“%d”, &a); enquetie(q, a); break; case 2: dequeue(q); break; : case 3: display(q->stack1, q->stack2); break; : case 4: exit(1); break; ° default : printf (“invalid\n"); break; } Algorithm for enqueue operation if queue is full return overflow endif rear «rear +1 queue [rear] — data return trun end procedure Algorithm for dequeue operation if queue is empty return underflow endif data = queueffront] front « front +1 return trun end procedureLP. University-{B.Tech.}-Akash Books 2015-23 3. Draw Tree with following information: preorder: G, B, Q, A, C, K, F, P, D, E, R, H eel Inorder: QB, K, C, F, A, G, P, E, D, H, R Find Postorder of the above Tree. Ans. Preorder: G,B, Q, A, C, K, F, PD, E, R, H Inorder: Q, B, KC, F,A,G, PB, B,D, H, R Root node is G Q,B,K,C, FA BE Inorder, 9 ———> © PEDHR, Left subtree Right subtree S Q,B,K,C, FA P,E,D,H.R “ Now in preorden next node is B. + 80 Ss © RED 2 KGRA In inorder Q is left node and right subtree is K, CFA. ‘A and in inorder left subtree of Ais K, C, F, so the next ‘Now next node in preorder is parent is A. GS 8 PEDHR Q A, K CF Now in preorder the next nude is C50 the parent node is C and In inorder the left node of C is K and right node of Cis F. So S \ B) PEDHR24-2015 Third Semoster, Data Structure Now in preorder the next nodo is P go tho P will bo the parent node and Node, E,D,HR are the right side node in inorder, Now next node in preorder is D so the D will be the parent node and In inorder left node of D is E and Right subtree of D is H, R node so Now in preorder the next node is R so R will be the parcent node and In inorder His the left side node of R. So the final tree is Post order of aboye tree is— Q,K,F,A,B, E,H,R, D,P,G QA. Define Bubble sort and Quick sort with example. Which one is better if data set is small? (12.5) Ans, Bubble sort: Bubble sort isa simple sorting algorithm. This sorting algorithm is comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order, This algorithm is not suitable for large data sets as its average and worst case comploxity are of O(n!) whore n are no of items.LP, University-{B.Tech. Akash Books 2015-25 Initial stage-List is unsorted. We are going to sort this in ASCENDING order using bubble sort Cs I 4 3 2 7 Tat Pass ofthe first Forloop. ——SSSSSC*Y ‘J=0, ali]=5, al +1] = 4 (Second for loop starts working) 5 4 3 2 7 Here Kaien ‘compared. Thair positions are then interchanged. Second for loop gets iterated. Now J = 1 alj|=S and af + 1] =3 4 5 3 z 7 Now j=2 af] = Sand al + 1 4 3 5 2 7 Now j=3 afj] =5 and a[j+1]=1 \e . * * —— Largest element of the list is moved to last position after first pass. a Ls z i 5 After the first pass of first For loop. See the largest element of the list is moved to last position. . a —s z 7 = After the second pass. See the second largest element is moved to second last position. . 3 2 4 4 I 5 ] After the third pass, See the third largest element moved to.. 2z 7 3 a a ] \After the fourth pass. The list gets sorted in ascending order. [at z Zz Ts So an array of 5 elements gets sorted in 5 passes. So the number of passes required to sort an array of ‘n’ elements using Bubble sort is =» Quick Sort: Quick sort is @ highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays, A large array is partitioned into two arrays one of which holds values smaller than specified value say pivot based on which the partition is made and another array holds values greater than pivot value.“a 7 26-2015 ‘Third Semester, Data Structure ‘The quick sort partitions an array and then calls itself recursively twice to sort the resulting two subarray. This algorithm is quite efficient for large sized data sets an it, average and worst case complexity are of O(nlogn) where n are no. of items. Partitioning is illustrated on the above example. 1. The first action is to get the pivot out of the way - swap it with the last element 5, 3, 25, 6, 10, 17, 1, 2, 18,8 : 2. We want larger elements to go to the right and smaller elements to go to the left. ‘Two “fingers” are used to scan the elements from left to right and from right to left: (5, 3, 25, 6, 10, 17, 1, 2, 18, 8] a A i j * While dis to the left of j, we move i right, skipping all the elements less than the Pivot. If an element is found greater then the pivot, i stops * While j is to the right of i, we move left, skipping all the elements greater than the pivot. Ifan element is found less then the pivot, j stops * When both i andj have stopped, the elements are swapped. * When i and j have crossed, no swap is performed, scanning stops, and the element Pointed to by i is swapped with the pivot . In the example the first swapping will be between 25 and 2, the second between 10 and 1, 8. Restore the pivot. After restoring the pivot we obtain the following partitioning into three groups: 15,3, 2, 6, 11 [8] (10, 25, 18, 17] : STEP 3. Recursively quicksort the left and the right parts. Quick sort is better for small data elements because its average case complexity is Of logn). Q.5. Suppose you have an AVL Node class that stores integers: (12.5) Public class AVLNode { Public int item; public AVLNode left; Public AVLNode right; Public AVLNode (int i, AVLNode 1, AVLNode r) item = ijleft = 1; right = 7; 3}: Write a complete method that takes a height h, and returns a reference to the roof of an AVL tree of height h that contains the minimum number of nodes. ‘The integers stored in the nodes (the item instance variables) should satisfy the binary search tree property, and they should all be distinct (but they do not have to be consecutive). You can define helper methods and/or classes if you wish. Ans. (Data Missing) Q6. Write Algorithm for Prims Algorith; . SI ing a Wille gorithm. Show how to generate MST usi (12.6) Prim’s algorithm is a greedy algorithm that finds 8 onnected weighted undirected graph. ’ Ans, Prim’s Algorithm: minimum spanning tree for acLP, Univeraity-{B,Tech,}-Akash Itfinds a subset of tho edges that forms a tree that 5 total woight ofall the edges in the troe is minimized. Books 2015-27. icluden every vertex, where the ‘This algorithm is directly based on the MSI minimum spanning tree) property roperty, Example Asimple weighted graph. Minimum-cost spanning tree Prim’s Algorithm MST-PRIM(G, w, r) for each u VIG] do keylu] <0 fu] NIL koyir] <0 QeVIG) while Q #2 dou « EXTRACT-MIN(Q) for each v Adj{tt) do ify Q and w(u, v) last->next * The code for processing a circular list is often simpler than the code for processing 2 non-circular list-mainly because you don't have to constantly check if the next node is defined-it is always defined.FIRST TERM EXAMINATION [SEPT. 2016] THIRD SEMESTER [B.TECH] DATA STRUCTURE [ETCS-209] Time: 1.90 hrs. : MM. :30 Note: Attempt any three questions including Q.no. 1 which is compulsory, Q.1. (a) What are two main factors for measuring the performance of algorithm? Explain in brief. (2) Ans. Space and Time complexities are the parameters by which we can analyze the performance of a program or algorithm. Space Complexity: It is the amount of memory it needed to run to completion. It has a fixed pact that includes space for the cock, space for simple variable and fixed size component variables, constants etc. and a variable part that includes the space needed by component variable whose size is dependent on the particular problem instance being solved and the stack space. ‘Time Complexity: It is the amount of computer time needs to run to completion. It is the sum of the compile time & the run time, The compile time does not depend on the instance characteristics major concern is the run time of a program. Q.1. (b) What do you mean by garbage collection? (2) Ans, Garbage Collection: Garbage collection (GC) is a dynamic approach to automatic memory management and heap allocation that processes and identifies dead memory block and reallocates storage for reuse. The primary purpose of garbage collection is to reduce memory leaks. : Q.1. (c) Define time-space trade off? @, Ans. Time-Space tradeoff: Is a way of solving a problem calculation in less time by using more space (or memory), or by solving a problem in very little space by spending along time. Most computers have a large amount of space, but not infinite space. Also, most people are willing to wait a little while for a big calculation, but not forever. So if your problem is taking a long time but not much memory, a space-time tradeoff would letyou use more memory and solve the problem more quickly or it could be solved very quickly but requires more memory than you have, you can try to spend more time solving the problem in the limited memory. Q.1, (d) How the resulting binary search tree will look like if the input is already sorted in non-decreasing order. (2) Ans, If all nodes are already sorted in non decreasing order then all nodes are inserted into the right side of a binary search tree, for example > nodes are 1,2, 3,4, 5 a the BST will look like >