Midterm Exam(Data Structures)
It is a process of hiding the internal details of an application from the outer world.
Abstraction
refers to hiding the original data entity via a data structure that can internally work through the hidden data entities
Data Abstraction
This allows developers to work with abstract processes, using hidden processes
internally to achieve desired functionality
Process Abstraction
It is elements are accessed in a
sequential order but may be stored
unsystematically.
Linear
It is Elements are stored
and accessed in a non-sequential
order
Non-Linear
is a logical description of how data is viewed as well as the operations that are allowed
without regard to how they will be implemented.
ADT
It is used for storing elements where each is a separate object
Linked list
It is an ordered list in which insertion and deletion are done at one (1) end
Stack
It is an ordered list in which insertion and deletion are done at seperate ends
Queue
It represents a hierarchical nature of a structure in a graphical form.
Tree
It is a partially sorted binary tree.
Heap
It represents a collection of elements that do not have to be in order.
Set
It is a set of ordered pairs with elements known as key and value
Map
It consists of a set of points/nodes (vertices) and set of links (edges) which
connects the pairs of vertices
Graph
It is a step-by-step set of instructions to be executed in sequence for solving a
problem
Algorithims
It is an algorithm must be terminated after a specified number of steps
Finiteness
each instruction has to be clear and unambiguous
Definiteness
It is an algorithm that should have zero or more well defined data given before an algorithm begins.
Input
It is an algorithm that must have one (1) or more results with specified relation with input
Output
it is the result of each step depends on the input and/or the result of the
previous step
Uniqueness
This is the most basic and simplest type of algorithm.
BFA
Brute Force Algorithm
the idea is to solve the problem in two sections, the first section
divides the problem into subproblems of the same type
Devide and Conquer Algorithms
DCA
the idea is to store the previously calculated result to avoid calculating it again and again
Dynamic Programming
The solution is built part by part. The decision to choose the next part is done on
the basis that it gives an immediate benefit.
Greedy Algorithm
It is used to arrange elements of an array /list in a specific order.
Sorting Algorithm
sorting is done in passes or iteration. Thus at the end of each iteration, the heaviest element is placed
at its proper place in the list. In other words, the largest element in the list bubbles up
Bubbles Sort
the technique first selects the smallest element in the array and swaps
it with the first element in the array
Selection Sort
It compares each element with all its previous elements and put or insert the element in
its proper position.
Inserstion Sort
It is a basic, fundamental step in computing done via step-by-step method to locate a
specific data among a collection of data.
Searching Algorithm
It equential search is a method for finding an element within a list. This
type of searching algorithms sequentially checks each element of the list until a match is
found or the whole list has been searched.
Linear search
It is used to find the position of a specific value contained in a sorted array.
The critical part of this strategy is that the list must be in order
Binary Search
The fundamental idea behind this searching technique is to search fewer
number of elements compared to linear search algorithm. This can be done by skipping
some fixed number of array elements or jumping ahead by fixed number of steps in
every iteration
Jump search
It contains the value of the element
Data field
This contains the address (random memory
location) of the next node
Pointer field
It is the basic linked list. Each node has data and an address field that
contains a reference to the next node.
Singly Linked list
It contains an extra pointer to connect to the previous node in the
sequence. The left pointer
Doubly Linked list
is a linked list in which the last node’s right pointer contains the address
of the first node
Circular Linked list
it is special format for storing and organizing data
Data Structure
Add an element to the top of a stack
Push
Remove an element from the top of a stack
Pop
Check if the stack is empty
IsEmpty
Check if the stack is full
isFull
Get the value of the top element without removing it
Peek