# Data Structure Winter 2021 Paper Solution | 3130702

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

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

## Question: 1

(a) What is time complexity? Explain with an example.

Time complexity refers to the amount of time it takes for an algorithm to run and complete its task. It is used to measure the efficiency of an algorithm and is typically represented using big O notation.

An example of time complexity can be seen in the case of sorting algorithms. The bubble sort algorithm has a time complexity of O(n^2) because it compares and swaps elements in a list multiple times, resulting in a quadratic increase in the amount of time it takes to sort a larger list. On the other hand, the quicksort algorithm has a time complexity of O(n log n) as it can divide and conquer the list more efficiently, resulting in a linear increase in time with a logarithmic factor.

(b) Explain malloc and free functions in ‘C’. Also, discuss the advantages of
dynamic over static memory allocation.

(c) Explain the following: (i) priority queue (ii) primitive data structures (iii) non-primitive data structures (iv) linear data structures (v) nonlinear data structures (vi)
applications of stack (vii) sparse matrix

## Question: 2

(a) Write an algorithm for infix to postfix conversion.

Here is an algorithm for infix to postfix conversion:

``````Initialize an empty stack and an empty output string.

Iterate through each character in the infix expression:
a. If the character is an operand, add it to the output string.
b. If the character is an operator, check the following:
i. If the stack is empty or the character is an open parenthesis, push it onto the            stack.
ii. If the character is a closing parenthesis, pop operators from the stack and add them to the output string until an open parenthesis is encountered.
iii. If the character is an operator, pop operators from the stack and add them to the              output string until the stack is empty or the top operator on the stack has a lower precedence than the current operator. Then push the current operator onto the stack.

After iterating through the entire expression, pop any remaining operators from the stack and add them to the output string.

The output string now contains the postfix expression.``````

(b) Write an algorithm to evaluate postfix expression. Explain the working of the
algorithm using an appropriate example.

(c) Write a ‘C’ program to reverse a string using stack.

(c) Write an algorithm to (i) insert, and (ii) delete elements in a circular queue.

## Question: 3

(a) Write user defined ‘C’ function to insert a node at a specific location in singly

``````#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

void insertNode(struct Node** head, int data, int position) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;

if (position == 0) {
return;
}

for (int i = 0; i < position - 1; i++) {
temp = temp->next;
}

newNode->next = temp->next;
temp->next = newNode;
}
``````

(b) Write a user-defined ‘C’ function to delete a node from end in circular linked
list.

(c) Write a ‘C’ program to implement a queue using linked list.

## Question: 3

(a) Write a user-defined ‘C’ function to insert a node at the end in a circular linked list.

``````#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

void insertEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;

return;
}

temp = temp->next;
}
temp->next = newNode;
}
``````

(b) Write a user-defined ‘C’ function to delete a node from a specific location in

(c) Write a ‘C’ program to implement stack using a linked list.

## Question: 4

(a) Construct a binary tree from the traversals given below:
Inorder: D, B, A, E, G, C, H, F, I
Preorder: A, B, D, C, E, G, F, H, I

(b) Write a short on AVL tree.

AVL tree is a type of self-balancing binary search tree that maintains a balance factor for each node. The balance factor of a node is the difference between the heights of its left and right subtrees. AVL trees are named after their inventors, Adelson-Velsky and Landis.

The main feature of AVL tree is that it maintains the balance factor of each node such that it is always -1, 0, or 1. If the balance factor of a node is greater than 1 or less than -1, the tree is considered unbalanced and needs to be rebalanced. AVL trees are rebalanced by performing rotations on the nodes.

The rotations performed on AVL tree are:

• Left rotation: This is performed when a node has a balance factor of 2 and its right subtree has a balance factor of -1 or 0. In this case, the node is rotated to the left, and its right child becomes the new root of the subtree.
• Right rotation: This is performed when a node has a balance factor of -2 and its left subtree has a balance factor of 1 or 0. In this case, the node is rotated to the right, and its left child becomes the new root of the subtree.
• Left-right rotation: This is performed when a node has a balance factor of 2 and its right subtree has a balance factor of 1. In this case, the right child is rotated to the right, and then the node is rotated to the left.
• Right-left rotation: This is performed when a node has a balance factor of -2 and its left subtree has a balance factor of -1. In this case, the left child is rotated to the left, and then the node is rotated to the right.

The main advantage of AVL tree is that it ensures that the tree is balanced at all times, which allows for efficient operations such as insertion, deletion, and search. However, the AVL tree has a higher overhead compared to other data structures, as it requires additional space to store the balance factors for each node.

AVL trees are used in various applications such as compilers, databases, and computer networks. They are also commonly used as a benchmark to compare the performance of other self-balancing tree data structures.

(c) Explain the concept of B-tree with a suitable example and list its applications.

## Question: 4

(a) Construct a binary search tree from the following numbers.
38, 13, 51, 10, 12, 40, 84, 25, 89, 37, 66, 95

(b) Explain BFS and DFS.

(c) Explain B+ tree with example.

## Question: 5

(a) Explain Prim’s algorithm.

Prim’s algorithm is a greedy algorithm used to find the minimum spanning tree of a weighted undirected graph. The minimum spanning tree is a tree that spans all the vertices in the graph with the minimum total edge weight.

The algorithm starts with an arbitrary vertex and repeatedly adds the minimum weight edge that connects to an unvisited vertex until all vertices are visited.

Here are the steps to perform Prim’s algorithm:

1. Initialize a set of visited vertices and a set of unvisited vertices. Set the visited set to be empty and the unvisited set to contain all the vertices in the graph.
2. Choose an arbitrary vertex from the unvisited set and add it to the visited set.
3. For each edge connected to the chosen vertex, add the edge to a priority queue ordered by edge weight.
4. While the priority queue is not empty, do the following:
• Pop the minimum weight edge from the priority queue.
• If the edge connects a visited vertex to an unvisited vertex, add the unvisited vertex to the visited set and add the edge to the minimum spanning tree.
• If the edge connects two visited vertices, discard the edge.
5. When all vertices are visited, the minimum spanning tree is the set of edges in the tree.

Prim’s algorithm has a time complexity of O(E log V), where E is the number of edges and V is the number of vertices in the graph. It is an efficient algorithm for finding the minimum spanning tree of a graph and is often used in network design and optimization problems.

(b) Write a ‘C’ program for selection sort.

(c) List out different hash methods and explain any three.

## Question: 5

(a) Define terms with respect to file: fields, records, database

In the context of a file, the following terms are commonly used:

1. Fields: A field is a unit of data within a record that is designed to hold a specific piece of information. For example, in a file containing information about employees, each record might have fields for the employee’s name, address, age, and salary.
2. Records: A record is a collection of related data fields that are grouped together to represent a single entity or transaction. In our example, each record would contain all of the information about a single employee.
3. Database: A database is a collection of related data that is stored and organized in a way that enables efficient retrieval and manipulation of the data. In the context of files, a database typically consists of one or more files that are organized and managed together to provide a comprehensive view of the data. A database might contain multiple files, each representing a different type of data or set of records, and may include various tools for querying and analyzing the data.

(b) Compare sequential and binary search methods.

(c) Apply quick sort for the following data:
9, 7, 5, 11, 12, 2, 14, 3, 10, 6

###### 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.