Module 1: Introduction to Data Structure
Module Wise Questions with solution
[Link] data structure with examples.
Ans:
A data structure is a specialized format for organizing, processing, retrieving and storing data.
There are several basic and advanced types of data structures, all designed to arrange data to suit
a specific purpose. Data structures make it easy for users to access and work with the data they
need. Most importantly, data structures frame the organization of information so that machines
and humans can better understand it. Typical base data types, such as integers or floating-point
values, that are available in most computer programming languages are generally insufficient to
capture the logical intent for data processing and use. Yet applications that ingest, manipulate
and produce information must understand how data should be organized to simplify processing.
Data structures bring together the data elements in a logical way and facilitate the effective use,
persistence and sharing of data. They provide a formal model that describes the way the data
elements are organized.
[Link] Linear and Non - Linear Data structure
Ans :
Sr no Linear Data Structure Non-Linear Data Structure
1 Data elements are arranged in a Data elements are arranged in a
sequential manner, each element hierarchical or interconnected manner,
connected to its next and/or previous forming branches and levels.
element.
2 Arrays, Linked Lists, Stacks, Queues Trees (Binary Tree, AVL Tree), Graphs
3 Sequential, from one element to the Can traverse in various directions or
next, in one pass (e.g., from the start to patterns (e.g., depth-first, breadth-first)
the end).
4 Linear memory usage, contiguous or Non-contiguous memory allocation, uses
sequential memory allocation. pointers to connect elements.
5 Simpler to implement and understand More complex due to hierarchical
due to their sequential nature. structures and relationships between
elements.
6 Used in simple applications where data Used in more complex applications
is processed in order (e.g., list of tasks, requiring hierarchical relationships (e.g.,
simple algorithms). organizational charts, route maps)
[Link] ADT With example.
Ans:
An Abstract Data Type (ADT) is a conceptual model that defines a set of operations and
behaviors for a data structure, without specifying how these operations are implemented or how
data is organized in memory. The definition of ADT only mentions what operations are to be
performed but not how these operations will be implemented. It does not specify how data will
be organized in memory and what algorithms will be used for implementing the operations. It is
called “abstract” because it provides an implementation-independent view.
The process of providing only the essentials and hiding the details is known as abstraction.
2. Stack ADT
The Stack ADT is a linear data structure that follows the LIFO (Last In, First Out) principle. It
allows elements to be added and removed only from one end, called the top of the stack.
In Stack ADT, the order of insertion and deletion should be according to the FILO or LIFO
Principle. Elements are inserted and removed from the same end, called the top of the stack. It
should also support the following operations:
● push(): Insert an element at one end of the stack called the top.
● pop(): Remove and return the element at the top of the stack, if it is not empty.
● peek(): Return the element at the top of the stack without removing it, if the stack is
not empty.
● size(): Return the number of elements in the stack.
● isEmpty(): Return true if the stack is empty; otherwise, return false.
● isFull(): Return true if the stack is full; otherwise, return false.
3. Queue ADT
The Queue ADT is a linear data structure that follows the FIFO (First In, First Out) principle. It
allows elements to be inserted at one end (rear) and removed from the other end (front).
The Queue ADT follows a design similar to the Stack ADT, but the order of insertion and
deletion changes to FIFO. Elements are inserted at one end (called the rear) and removed from
the other end (called the front). It should support the following operations:
● enqueue(): Insert an element at the end of the queue.
● dequeue(): Remove and return the first element of the queue, if the queue is not
empty.
● peek(): Return the element of the queue without removing it, if the queue is not
empty.
● size(): Return the number of elements in the queue.
● isEmpty(): Return true if the queue is empty; otherwise, return false.
4. Classify the Types of Data Structures.
Answer:
Data structures can be classified into Linear and Nonlinear types. These classifications help in
selecting the most appropriate structure based on the type of problem being solved.
Linear Data Structures: In these structures, the data elements are arranged sequentially, and
each element is connected to the next (and sometimes the previous) element.
Examples:
Arrays: A collection of elements stored in contiguous memory locations. Accessing an element
is fast (constant time), but resizing the array or inserting/deleting elements can be slow.
Linked Lists: A sequence of elements, where each element (node) points to the next one. It
allows efficient insertion and deletion but has slower access times compared to arrays.
Stacks: A collection of elements that follows the Last In, First Out (LIFO) principle.
Operations like push and pop occur at one end (top).
Queues: A collection of elements that follows the First In, First Out (FIFO) principle.
Operations like enqueue and dequeue happen at opposite ends.
Nonlinear Data Structures: These structures store data in a way where elements are not stored
sequentially. Each element can have more than one relation to other elements, forming a
hierarchy or network.
Examples:Trees: A hierarchical structure where each node has a value and a list of children
(e.g., binary trees, AVL trees).
Graphs: A collection of nodes (vertices) connected by edges. Graphs can be directed or
undirected and are useful for modeling networks like social media connections or road maps.
5. Differentiate Between Static and Dynamic Data Structures?
Answer:
Sr no Static Data Structure Dynamic Data Structure
1 Fixed size, determined at compile-time. Variable size, determined at runtime.
2 Memory is allocated at compile-time (fixed Memory is allocated at compile-time
allocation). (fixed allocation).
3 Inflexible, cannot change size during Flexible, can grow or shrink as
execution. required during execution.
4 Array, Static Linked List Linked List, Stack, Queue, Binary
Tree
5 More efficient in terms of memory usage if More memory-intensive due to
the size is known in advance. overhead of dynamic memory
allocation.
6 Easier to implement and manage. More complex, involves dynamic
memory management and pointers.
7 Faster access and less memory overhead Slower access times due to pointers
(since memory is contiguous). and extra memory management.
8 Manual memory management is not Automatic or explicit memory
required. management (e.g., using pointers).
6. Discuss Operations Performed on Data Structures?
Answer:
Operations on data structures are critical in performing tasks such as searching, sorting, insertion,
and deletion of data. The basic operations are:
● Insertion: This operation adds a new element to the data structure. For example, in a
linked list, a node can be inserted at the beginning, end, or at a specific position.
● Deletion: This operation removes an element from the data structure. For instance, in a
stack, the operation pop removes the top element, while in a queue, dequeue removes the
front element.
● Searching: The process of finding an element within the data structure. In arrays, a linear
or binary search can be performed, whereas, in linked lists, a traversal is needed to search
for an element.
● Traversal: This refers to visiting each element of the data structure in a systematic way,
like accessing each node in a linked list or visiting each node in a tree.
[Link] the Music Player system. Find out which appropriate data structure will be
used to maintain the playlist of the music player system.
Ans : For managing a playlist in a music player system, a queue is the more appropriate data
structure
Order of Playback: A queue processes elements in the same order they were added, which is
essential for a music playlist where songs need to be played in sequence.
● Enqueue: New songs are added to the end of the playlist (queue).
● Dequeue: The song at the front of the queue is played, and once finished, it is removed
from the playlist
Example:
● If the songs "A", "B", and "C" are added to the playlist in that order, they will be
played as A → B → C, following the FIFO order.
Benefits:
● Songs can be played in the order they were added.
● Easy to add songs to the end of the playlist.
● Easy to remove the currently playing song when it finishes
[Link] are developing a student course registration system for a university. Students can
enroll in courses they want to take for the upcoming semester. To manage this process,
Find out an appropriate linear data structure.
Ans : For a student course registration system where students enroll in courses for the
upcoming semester, a queue is the more appropriate linear data structure
Queue (First In, First Out - FIFO):
● Order of Enrollment: A queue operates on the First In, First Out (FIFO) principle,
which means that the first student to request enrollment in a course gets processed first.
This is essential for a registration system where fairness and processing order are
important.
○ Enqueue: When a student registers for a course, they are added to the end of the
queue.
○ Dequeue: When it's time to confirm enrollment, the student at the front of the
queue (the first to register) gets processed first.
Example:
If Student A registers for a course, followed by Student B and Student C, the queue will ensure
that Student A's enrollment is processed first, then Student B's, and finally Student C's.
Q.8. Discuss insertion in an array (at given position/ before or after given element) with
diagram.
Ans : Insertion in an array (Kindly refer the given link)
Q.9. Discuss delete given element from an array (or delete from given position) with
diagram.
Ans : Deletion in array (Kindly refer the given link)
Q.10. Insertion/ deletion operation is difficult in an array. Justify with a diagram.
Ans : Inserting/appending an element at the end of the array takes O(1) time. We have seen this
in the strengths(fast appends).
If we want to insert something into an array, first, we have to make space by "scooting over"
everything starting at the index we're inserting into, as shown in the image. In the worst case,
we're inserting into the 0th index in the array (prepending),
Inserting an element at the 2nd index and moving the rest of the element right shift each once.
The resultant array becomes – { A, B, C, D, E }.
In the next lessons, you will learn more about insertion and shifting algorithms, with clear
explanations, code snippets, and sketches to understand why these inserts are expensive at the
start and middle.
Deleting an element at the end of the array takes O(1) time, which is the best case. In computer
science, we only care about the worse case scenarios when working on algorithms. But, when we
remove an element from the middle or start of the array, we have to fill the gap by scooting over
all the elements after it. This will be O(n) if we consider a case of deleting an element from the
0th index.
Deleting an element at the 3rd index and filling the gap by left-shifting the rest of the elements;
the resultant array becomes – { A, B, C, D, E }.
Q.11. Illustrate searching operation on array with example
Ans :.
1. Linear Search:
Concept:
Linear search iterates through each element of the array sequentially until the target element is
found or the end of the array is reached.
It works on both sorted and unsorted arrays.
Example:
Array: [20, 10, 50, 30, 40]
Target: 30
Process:
Start at the first element (index 0).
Compare the element with the target.
If they match, the search is successful.
If they don't match, move to the next element.
Repeat steps 2-4 until the target is found or the end of the array is reached.
Diagram:
Array: [20, 10, 50, 30, 40]
^
Compare 20 with 30 (No match)
Array: [20, 10, 50, 30, 40]
^
Compare 10 with 30 (No match)
Array: [20, 10, 50, 30, 40]
^
Compare 50 with 30 (No match)
Array: [20, 10, 50, 30, 40]
Compare 50 with 30 (No match)
Array: [20, 10, 50, 30, 40]
^
Compare 30 with 30 (Match! Found at index 3)
Q.12. Illustrate traversal operation on array with example.
Ans :
Array traversal means visiting each element of an array, one by one, in a specific order. It's like
taking a walk along the row of boxes we talked about earlier, looking inside each one.
Example:
● Let's use an array of numbers: [10, 20, 30, 40, 50]
How Traversal Works:
1. Start at the beginning: We begin at the first element (index 0).
2. Visit each element: We look at the value in the current element.
3. Move to the next element: We move to the next index (index 1, then index 2, and so on).
4. Repeat: We repeat steps 2 and 3 until we reach the end of the array.
Visual Representation:
Array:
[ 10 ] [ 20 ] [ 30 ] [ 40 ] [ 50 ]
0 1 2 3 4 (Indexes)
Traversal Steps:
Visit 10:
[ 10 ] -> [ 20 ] [ 30 ] [ 40 ] [ 50 ]
^
Visit 20:
[ 10 ] -> [ 20 ] -> [ 30 ] [ 40 ] [ 50 ]
^
Visit 30:
[ 10 ] [ 20 ] -> [ 30 ] -> [ 40 ] [ 50 ]
^
Visit 40:
[ 10 ] [ 20 ] [ 30 ] -> [ 40 ] -> [ 50 ]
^
Visit 50:
[ 10 ] [ 20 ] [ 30 ] [ 40 ] -> [ 50 ]
^
What We Do During Traversal:
While we're "walking" through the array, we can do many things with each element:Print it to
the [Link] it to a sum.
● Compare it to another value.
● Modify it.
● Any other operation that you need to do with each value in the array.