DS GTU Paper Solution Winter 2020 | 3130702

Here, We provide Data Structure GTU Paper Solution Winter 2020 . Read the Full DS GTU paper solution given below.

Data Structure GTU Old Paper Winter 2020 [Marks : 56] : Click Here 

(a) Compare array and linked list.

Arrays and linked lists are two common data structures used in programming. Here are some key differences between the two:

  1. Memory allocation: In an array, memory is allocated in contiguous blocks, while in a linked list, memory can be allocated anywhere and is not necessarily contiguous.
  2. Size flexibility: Arrays have a fixed size, meaning that once an array is created, its size cannot be changed. In contrast, linked lists can grow or shrink in size dynamically, as new nodes are added or removed.
  3. Access time: Accessing an element in an array is faster than accessing an element in a linked list because the array’s memory is contiguous, and its elements can be accessed directly with an index. In contrast, accessing an element in a linked list requires traversing the list from the beginning to the desired element.
  4. Insertion and deletion: Inserting or deleting an element in an array requires shifting all the elements to the right or left of the inserted or deleted element. In contrast, inserting or deleting an element in a linked list only requires modifying a few pointers.
  5. Memory usage: Arrays require a fixed amount of memory, while linked lists require additional memory for pointers.
  6. Sequential processing: Arrays are better suited for sequential processing, such as sorting or searching, while linked lists are better suited for applications that require frequent insertions or deletions, such as a queue or a stack.

In summary, arrays and linked lists have their own strengths and weaknesses, and which one to use depends on the specific requirements of the problem being solved.

(b) Compare primitive and non primitive data types data structures.

(c) Write an algorithm to perform insert and delete operations on simple queue.

(a) Search the number 50 from the given data using binary search technique. Illustrate the searching process. 10, 14, 20, 39, 41, 45, 49, 50, 60

  • Low = 0, High = 8
  • search_ele = 50
  • Mid_ele_idx = (low + high)/2
  • = (0+8)/2
  • = 4

Is 41 = 50? No

The list now is 45 49 50 60

  • Low =5, high= 8
  • Mid_ele_idx = (low + high) /2
  • = (5+8)/2
  • = 6

Is 49 = 50? No

The list now is 50 60

  • Low = 7, high = 8
  • Mid_ele_idx = (low + high)/2
  • = (7+8)/2
  • = 7

Is 50 = 50 ? yes

location = 7

Output: The search element 50 is found at location 7.

(b) Apply merge sort algorithm to the following elements. 20, 10, 5, 15, 25, 30, 50, 35

 (c) Write a ‘C’ program for bubble sort.

(a) What is stack? Why do we use multiple stacks?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. In a stack, elements are added and removed from the top of the stack only.

Stacks are widely used in programming and computer science, as they provide an efficient way to store and retrieve data. Some common applications of stacks include expression evaluation, backtracking, and recursion.

Multiple stacks can be used in situations where different types of data need to be stored separately. For example, in a web browser, multiple stacks may be used to keep track of the pages visited in different tabs or windows. In a multi-threaded program, each thread may have its own stack to store its local variables and function calls.

Another use of multiple stacks is in implementing specific data structures, such as a double-ended queue (deque), which requires two stacks to support insertion and deletion at both ends.

In some cases, multiple stacks may also be used to improve the performance of certain algorithms. For example, in a parallel computing system, multiple stacks may be used to distribute the load across different processors, allowing the program to run faster.

In summary, multiple stacks are used to organize and separate different types of data, implement specific data structures, and improve the performance of certain algorithms.

(b) Convert the following infix expressions to their prefix and postfix equivalents.
1. A*B+C/D

2. (A*B)+(C/D)-(D+E)

(c) What is priority queue? Discuss its applications and implementation details.

(a)  Evaluate following Expression using stack 53+62/*35*+

Input: str = “53+62/*35*+
Output: 39
Explanation: 

  • Scan 5, it’s a number, so push it to stack. Stack contains ‘5’ 
  • Scan 3, again a number, push it to stack, stack now contains ‘5 3’ (from bottom to top) 
  • Scan +, it’s an operator, pop two operands from stack, apply the + operator on operands, we get 5+3 which results in 8. We push the result 8 to stack. The stack now becomes ‘8’. 
  • Scan6, again a number, push it to stack, stack now contains ‘8 6’ .
  • Scan2, again a number, push it to stack, stack now contains ‘8 6 2’ .
  • Scan /, it’s an operator, pop two operands from stack, apply the / operator on operands, we get 6/2 which results in 3. We push the result 3 to stack. The stack now becomes ‘8 3’. 
  • Scan *, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 8*3 which results in 24. We push the result 24 to the stack. The stack now becomes ‘24’. 
  • Scan 3, again a number, push it to stack, stack now contains ‘24 3’
  • Scan 5, it’s a number, so push it to stack. Stack contains ’24 3 5’ 
  • Scan *, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 3*5 which results in 15. We push the result 15 to the stack. The stack now becomes ’24 15’. 
  • Scan +, it’s an operator, pop two operands from stack, apply the + operator on operands, we get 24+15 which results in 39. We push the result 39 to stack. The stack now becomes ‘39’. 
  • There are no more elements to scan, we return the top element from the stack (which is the only element left in a stack).

(b)  Design an algorithm to perform insert operation in circular queue.

(c) Design an algorithm to merge two linked list.

(a) Define: 1. Acyclic graph 2. Leaf node 3. Complete binary tree

1. Acyclic graph :

A graph is called an acyclic graph if zero cycles are present, and an acyclic graph is the complete opposite of a cyclic graph.

2. Leaf node :

The node of the tree, which doesn’t have any child node, is called a leaf node. A leaf node is the bottom-most node of the tree. There can be any number of leaf nodes present in a general tree. Leaf nodes can also be called external nodes.

3. Complete binary tree :

A binary tree is said to be a complete binary tree when all the levels are completely filled except the last level, which is filled from the left.

(b) For following expressions, construct the corresponding binary tree
1. A+B/C*D-E

(c) How are graphs represented inside a computer’s memory? Which method do you prefer and why?

(a) Define: 1. Connected graph 2. Threaded tree 3. Degree of node

  1. Connected graph: A connected graph is a graph in which there is a path between every pair of vertices. In other words, there are no disconnected components in the graph. A graph can be disconnected if there are one or more vertices that are not reachable from any other vertex.
  2. Threaded tree: A threaded tree is a binary tree in which all the null pointers are replaced with references to other nodes in the tree, called threads. There are two types of threads: left threads and right threads. A left thread of a node is a reference to the in-order predecessor of the node, while a right thread is a reference to the in-order successor of the node. Threaded trees can be used to traverse the tree in in-order without using a stack or recursion.
  3. Degree of node: The degree of a node in a graph is the number of edges incident to the node. For a directed graph, there are two types of degrees: in-degree and out-degree. The in-degree of a node is the number of edges that point to the node, while the out-degree is the number of edges that start from the node. In a undirected graph, the degree of a node is the sum of the in-degree and out-degree, since the edges are bidirectional. The degree of a node is a useful measure of the connectivity of the node in the graph.

(b) Differentiate between depth first search and breadth first search.

(c) Design an algorithm to insert a given value in the binary search tree. 

(a) Explain basic file operations

Basic file operations refer to the actions that can be performed on files in a computer’s file system. Here are some of the most common file operations:

  1. Creating a file: This operation involves creating a new file in the file system with a specified name and location. In most programming languages, this can be done using a built-in function or class that provides access to the file system.
  2. Opening a file: This operation involves opening an existing file in the file system for reading, writing, or both. In most programming languages, this can be done using a built-in function or class that provides access to the file system. When opening a file, the file handle or file descriptor is returned, which can be used to read or write data to the file.
  3. Reading from a file: This operation involves reading data from an open file into a buffer or variable. This can be done using a built-in function or method that provides access to the file handle or file descriptor.
  4. Writing to a file: This operation involves writing data to an open file. This can be done using a built-in function or method that provides access to the file handle or file descriptor.
  5. Closing a file: This operation involves closing an open file when it is no longer needed. This is an important operation to ensure that the data in the file is saved properly and that system resources are released.
  6. Deleting a file: This operation involves removing an existing file from the file system. In most programming languages, this can be done using a built-in function or class that provides access to the file system.

These are some of the basic file operations that can be performed on files in a computer’s file system. Proper handling of file operations is important to ensure that the data is saved and accessed correctly, and that system resources are used efficiently.

(b) List out applications of hashing.

(c) What is file organization? Briefly summarize different file organizations.

(a) Give a brief note on indexing

Indexing in data structures is a technique used to optimize the search and retrieval of data from large collections of data. An index is a data structure that contains a mapping of the values in a dataset to their locations in memory or on disk. Indexing enables fast access to data based on a search key or a range of keys.

There are different types of indexing techniques, including:

  1. Sequential indexing: This technique uses a sequential list of keys to locate the data items in memory or on disk. This is the simplest form of indexing, but it can be slow for large datasets.
  2. Binary search indexing: This technique uses a sorted list of keys and a binary search algorithm to locate the data items in memory or on disk. This is faster than sequential indexing, but it requires that the keys be sorted.
  3. B-tree indexing: This technique uses a balanced tree structure to store the keys and data items. This enables fast access to data items based on a range of keys, and it is commonly used in databases.
  4. Hash indexing: This technique uses a hash function to map the keys to the locations of the data items in memory or on disk. This is the fastest form of indexing, but it can be sensitive to collisions in the hash function.

Indexing is a powerful technique that can significantly improve the performance of data access and retrieval operations. However, it requires additional memory and processing overhead to maintain the index structure. The choice of indexing technique depends on the size and complexity of the dataset, the access patterns, and the performance requirements of the application.

(b) Build a chained hash table of 10 memory locations. Insert the keys 131, 3, 4, 21, 61, 24, 7, 97, 8, 9 in hash table using chaining. Use h(k) = k mod m. (m=10)

(c) Consider the hash table of size 10. Using quadratic probing, insert the keys 72, 27, 36, 24, 63, 81, and 101 into hash table. Take c1=1 and c2=3.

Read More : DS GTU Paper Solution Winter 2021
Read More : DBMS GTU Paper Solution Winter 2020

“Do you have the answer to any of the questions provided on our website? If so, please let us know by providing the question number and your answer in the space provided below. We appreciate your contributions to helping other students succeed.