Introduction to Data Structures and Algorithms
FIFO Behavior
Enqueue and dequeue are two basic operations that can be applied on a queue.
Tree Data Structure
A tree is a multilevel data structure that represents a hierarchical relationship between a finite set of individual elements called nodes.
Graph Data Structure
A graph is a non-linear data structure that consists of a set of nodes (or vertices) and a set of edges (or arcs), with each edge going from one node to another. Each edge in the graph depicts a relationship between a pair of nodes.
Key Operations on Data Structures
Traversing, searching, insertion, deletion, sorting, merging, copying, and concatenation are key operations performed on a data structure.
Algorithm Definition
An algorithm is a sequence of steps or instructions required to solve a given problem.
Space Complexity of an Algorithm
The analysis of an algorithm based on how much memory it needs to solve a particular problem is called the space complexity of an algorithm.
Asymptotic Complexity
A measure of the time complexity of an algorithm where we disregard certain terms of a function to express the efficiency of the algorithm is called asymptotic complexity.
Algorithm Efficiency
For a given input, the efficiency of an algorithm’s complexity is measured for the average case, best case, and worst case.
Question-Answers
Q1. List various non-linear data structures. (PTU, May 2004)
Ans. Some non-linear data structures are graphs, trees, and multilinked structures like sparse matrices.
Q2. What is the difference between data structure and data types? (PTU, May 2004)
Ans. The differences between data structure and data types are as follows:
| Data Structure | Data Types |
|---|---|
| A data structure is a logical or mathematical model of a particular organization of data. e.g., STACK, QUEUE, LINKED LIST, etc. | A data type is a term that refers to the kind of data that a variable may hold in a programming language. e.g., Integer, float, character, etc. |
Q3. What are non-linear data structures? Give examples. (PTU, Dec. 2006; May 2007, 2004)
OR
What do you mean by non-linear data structure? Give examples. (PTU, May 2011; Dec. 2008)
Ans. Non-linear data structures can express more complex relationships than physical adjacency. Examples of these data structures are trees and graphs.