DSA MIDTERMS

DSA Midterms Lessons PUP

DATA

“raw facts”,  information, in a form of numbers, text, images, figures, or any other format, structure or unstructured.

STRUCTURE

something arranged in a definite pattern of organization

Data Structures

A specific way of organizing data in a specialized format on a computer so that the information can be organized, processed, stored, and retrieved quickly and effectively.

LINEAR

data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements. E.g. array, stack, queue, linked list, etc.

NON LINEAR

data elements are not placed sequentially or linearly. In this data structure, we can’t traverse all the elements in a single run only. E.g. data structures are trees and graphs, etc.

STATIC

Static data structure has a fixed memory size. It is easier to access the elements in a static data structure. An example of this data structure is an array.

DYNAMIC

in this data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code. Examples of this data structure are queue, stack, etc

HOMOGENOUS

this data structures consist of the same data element type, like element collections found in an array.

NON HOMOGENOUS

the data don’t have to be the same type, such as Linked List.

DATA TYPE

is a classification, or attribute of data which tells the compiler or interpreter how the programmer intends to use the data

Importance of Data Structures

EFFICIENCY, FLEXIBILITY, SCALABILITY

Arrays

is a collection of items of same data type stored at contiguous memory locations.

Array Index

In an array, elements are identified by their indexes. Array index starts from 0.

Array element

are items stored in an array and can be accessed by their index.

Array Length

is determined by the number of elements it can contain.

One dimensional array

You can imagine a 1d array as a row, where elements are stored one after another.

Two-dimensional array

Multidimensional arrays can be considered as an array of arrays or as a matrix consisting of rows and columns.

Three dimensional array

  A Multidimensional array    contains          three dimensions, so it can be considered an array of two-dimensional arrays.

Types of Array Operations

Traversal, Insertion, Deletion, Searching, Sorting

Linked List

is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers.

Node Structure

data & next pointer

Head and Tail

The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL or nullpointer, indicating the end of the list. This node is known as the tail node.

Types of Linked List

Singly linked list, Double Linked List, Circular Linked List

Single linked list

each node contains a reference to the next node in the sequence. Traversing a ____ linked list is done in a forward direction.

Double Linked List

each node contains references to both the next and previous nodes. This allows for traversal in both forward and backward directions, but it requires additional memory for the backward reference.

Circular Linked List

the last node points back to the head node, creating a circular structure. It can be either singly or doubly linked.

Types of Linked List Operations

Insertion, Deletion, Searching and Traversing

Insertion

Adding a new node to a linked list involves adjusting the pointers of the existing nodes to maintain the proper sequence. can be performed at the beginning, end, or any position within the list.

Deletion

Removing a node from a linked list requires adjusting the pointers of the neighboring nodes to bridge the gap left by the deleted node. can be performed at any position within the list.

Searching and Traversing

Searching for a specific value in a linked list involves traversing the list from the head node until the value is found or the end of the list is reached.

Stack

is a linear data structure that follows a particular order in which the operations are performed. ▪ The order may be LIFO (Last In First Out) or FILO(First In Last Out).

LIFO (Last In First Out)

implies that the element that is inserted last, comes out first.

FILO(First In Last Out)

implies that the element that is inserted first, comes out last

fixed size stack

has a fixed size and cannot grow or shrink dynamically. If the stack is full and an attempt is made to add an element to it, an overflow error occurs.

Dynamic Sized Stack

this stack can grow or shrink dynamically. When the stack is full, it automatically increases its size to accommodate the new element, and when the stack is empty, it decreases its size

Types of Stack Operations

push(), pop(), top(), isEmpty(), size()

push()

To insert an element into the stack.

pop()

To remove an element from the stack.

top()

Returns the top element of the stack.

isEmpty()

Returns true if stack is empty else false.

size()

Returns the size of stack.

Array-based implementation

the push operation is implemented by incrementing the index of the top element and storing the new element at that index

Linked list based implementation

the push operation is implemented by creating a new node with the new element and setting the next pointer of the current top node to the new node

QUEUES

is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.

Types of Queue

Input Restricted, Output Restricted, Circular Queue, Double Ended, Priority Queue

Input Restricted Queue

This is a simple queue. In this type of queue, the input can be taken from only one end but deletion can be done from any of the ends.

Output Restricted Queue

This is also a simple queue. In this type of queue, the input can be taken from both ends but deletion can be done from only one end.

Circular Queue

This is a special type of queue where the last position is connected back to the first position. Operations are performed in FIFO order.

Double Ended Queue (Dequeue)

In a ____________ the insertion and deletion operations, both can be performed from both ends.

Priority Queue

is a special queue where the elements are accessed based on the priority assigned to them.

Types of Queue Operations

Enqueue(), Dequeue(), Peek(), rear(), isFull(), isNull()

Enqueue()

Adds (or stores) an element to the end of the queue.

Dequeue()

Removal of elements from the queue.

Peek() or front()

Acquires the data element available at the front node of the queue without deleting it.

rear()

This operation returns the element at the rear end without removing it.

isFull()

Validates if the queue is full.

isNull()

Checks if the queue is empty.

Sequential allocation

A queue can be implemented using an array. It can organize a limited number of elements.

Linked list allocation

A queue can be implemented using a linked list. It can organize an unlimited number of elements.

Multi programming

When multiple programs are running in the main memory.

Network

a queue is used in devices such as a router or a switch. another application of a queue is a mail queue which is a directory that stores data and controls files for mail messages.

Job Scheduling

The computer has a task to execute a particular number of jobs that are scheduled to be executed one after another.

Shared resources

Queues are used as waiting lists for a single shared resource.

TREE

this data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search.

Parent Node

The node which is a predecessor of a node is called the _____ node of that node. {B} is the parent node of {D, E}.

Child Node

The node which is the immediate successor of a node is called the ____ node of that node. Examples

Root Node

The topmost node of a tree or the node which does not have any parent node is called the ______. {A} is the _________ of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.

Leaf Node or External Node

The nodes which do not have any child nodes are called ___ nodes. {K, L, M, N, O, P} are the leaf nodes of the tree.

Ancestor of a Node

Any predecessor nodes on the path of the root to that node are called ____ of that node. {A,B} are the ancestor nodes of the node {E}.

Descendant

Any successor node on the path from the leaf node to that node. {E,I} are the _____ of the node {B}.

Sibling

Children of the same parent node are called ___. {D,E} are called ___.

Level of a node

The count of edges on the path from the root node to that node. The root node has level 0.

Internal node

A node with at least one child is called _____ Node.

Neighbour of a Node

Parent or child nodes of that node are called _____ of that node.

Subtree

Any node of the tree along with its descendant

Types of Tree

BINARY, TERNARY, N-ary/Generic Generic

BINARY

In this tree, each node can have a maximum of two children linked to it.

TERNARY

is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”

N-ary/Generic

this tree are a collection of nodes where each node is a data structure that consists of records and a list of references to its children (duplicate references are not allowed).

Types of Tree Operations

Create, Insert, Search, Traversal

Create

Create a tree in the data structure.

Insert

 Inserts data in a tree.

Search

Searches specific data in a tree to check whether it is present or not.

Preorder Traversal

Traveling a tree in a pre order manner in the data structure.

In order Traversal

Traveling a tree in an in-order manner

Post order Traversal

Traveling a tree in a post-order manner.

GRAPH

is a non-linear data structure consisting of vertices and edges.

Components of Graph

VERTICES & EDGES

VERTICES

are the fundamental units of the graph. Sometimes, ______ are also known as vertex or nodes. Every node/vertex can be labeled or unlabeled.

EDGES

are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a directed graph.

Null Graph

A graph is known as a ___ graph if there are no edges in the graph.

Trivial Graph

Graph having only a single ____, it is also the smallest graph possible.

Undirected Graph

A graph in which edges do not have any direction. That is the nodes are unordered pairs in the definition of every edge.

Directed Graph

A graph in which edge has direction. That is the nodes are ordered pairs in the definition of every edge.

Connected Graph

The graph in which from one node we can visit any other node in the graph is known as a ____ graph.

Disconnected Graph

The graph in which at least one node is not reachable from a node

Regular Graph

The graph in which the degree of every vertex is equal to K is called K ____ graph.

Complete Graph

The graph in which from each node there is an edge to each other node.

Cycle Graph

The graph in which the graph is a cycle in itself, the degree of each vertex is 2.

Cyclic Graph

A graph containing at least one cycle is known as a ____ graph.