- What is Data Structure?
Ans. A Data structure is the basic concept of any programming language. It is the way of organizing and manipulating data so that it can be used effectively. Data Structures also define how data and the relationship amongst different data are represented. It helps programmers in determining how efficiently different functions or algorithms can be applied. Data structures are used in almost every program or software system that has been developed.
- What are the different types of Data Structures?
Ans. There are two types of data structures:
- Linear Data Structure
In a linear data structure, the data elements are arranged sequentially. The elements are stored in a non-hierarchical way such that each element is connected to its previous and the next element, except the first and last element. They are easy to implement as computer memory is also arranged linearly.
Example: Arrays, Stacks, Queue, Linked List.
- Non-Linear Data Structure
In a non-linear data structure, the elements of data structure do not form a sequence. They are connected hierarchically. Each element can have multiple paths to connect to other elements in a non-linear arrangement. Non-linear data structures support multi-level storage. They are not easy to implement but are more efficient in utilizing computer memory compared to the linear data structure.
Example: Trees, Graphs, Tables
- Name some applications of Data Structures.
Ans. Some of the popular applications of Data Structures include:
- Artificial intelligence
- Blockchain
- Compiler design
- Database Management
- Graphics
- Machine learning
- Numerical Analysis
- Operating System
- Simulation
- Statistical Analysis Package
- How do linear data structures differ from non-linear data structures?
Ans. The differences between linear data structures and non-linear data structures are:
Linear Data Structures | Non-Linear Data Structures |
Data elements are connected sequentially or linearly (non-hierarchical). | Data elements are connected in a non-linear or hierarchical manner. |
All data elements are arranged at a single level. | Data elements are arranged in multiple levels. |
Each data element is connected to the previous and next items. | Each element is attached to many other elements. |
Easy to implement. | Difficult to implement. |
Requires a single run to traverse each data element. | Traversing data elements in one go is not possible. It requires multiple runs to be traversed. |
Memory utilization is not efficient. | Memory is utilized efficiently. |
The time complexity increases with the increase in the input size. | The time complexity remains the same with the increase in the input size. |
Mostly used for developing the software. | Used in image processing and Artificial Intelligence |
Example: Arrays, linked list, stack, queue | Example: Graphs, Trees |
- What are the different types of Trees in data structures?
Ans. The following are the different types of Trees in data structures:
Tree Type | Description |
General Tree | No restriction is imposed on the number of nodes that a node can have. A node can have either 0 or infinite numbers of nodes. The topmost node is called a root node while the child node of the parent node is called a subtree. |
Binary Tree | In this, every node can have at most 2 child nodes, left and right. |
Binary Search Tree | It is a binary tree extension with some optional restrictions. The value of the left subtree should be less than the value of that node. The value of the rightsubtree should be greater than the value of that node. |
AVL Tree | It is a self-balancing binary search tree. |
Red-black Tree | Self-balancing binary search tree, where each node has a color(red or black). |
N-ary Tree | In this, the maximum number of children that a node can have is limited to N. |
- Explain the difference between file structure and storage structure?
Ans. The main difference between file structure and storage structure is the memory area that is being accessed.
In a File Structure, a user writes the data in a file and saves that file in auxiliary or secondary memory. The file is stored in a hard disk or external device like Pen Drive. The data will remain intact till it is deleted manually by the user.
In a Storage Structure, data is stored in the main memory of the computer that is RAM. The data is deleted once the function that uses this data gets completed.
- Explain some operations that can be performed on a data structure.
Ans. The following are some of the operations that can be performed on a data structure:
Operation | Description |
Insertion | Add a new element |
Deletion | Delete an existing element |
Searching | Find the location of an existing element |
Sorting | Arrange elements in ascending or descending order (numerical data) or dictionary order (alphanumeric data) |
Traversal | Access each element exactly once for processing |
Merging | Combine the data elements of two sorted files into a single file in the sorted form |
- List the advantages of a Linked List over an Array?
Ans. The following are the advantages of a Linked List over an Array:
- Dynamic data structure:
The Linked list is dynamically stored in the main memory. It grows as per the program demand. On the other hand, an array is statically stored in the main memory. The size of linked lists is not fixed, they can expand and shrink during run time.
- Ease of performing operations:
The linked list takes less time while performing operations like insertion, deletion, etc. while an array takes more time.
- Efficient memory utilization:
Memory utilization is efficient in a linked list as the memory can be allocated or deallocated at the run time. Memory utilization is inefficient in the array.
- Linked lists are considered linear or non-linear data structures?
Ans. A linked list can be considered either linear or non-linear data structure. It depends on the application that they are used for. A linked list is considered non-linear if it is used for data storage. It is considered as a linear data structure if it is used for access strategies.
- How are the elements of a 2D array are stored in the memory?
Ans. Row-Major Order and Column-Major Order are the two methods used to store elements of a 2D array in the memory:
Row-Major Order:
In this method, all the rows of the 2D array are stored in the memory contiguously. The 1st row of the array will be stored completely first. It will be followed by the 2nd column of the array and so on till the last row of the array.
Column-Major Order:
In this method, all the columns of the 2D array are stored in the memory contiguously. The 1st column of the array will be stored completely first. It will be followed by the 2nd column of the array and so on till the last column of the array.
- List some applications of stack data structures.
Ans. Some of the common applications of a stack data structure are:
- Expression evaluation
- Backtracking
- Syntax parsing
- Parenthesis checking
- String reversal
- Memory management
- Write the code in C to create a node in the singly linked list.
Ans. Below is the code in C to create a node in the singly linked list
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node));