Midterm exam Data Structure

Abstraction

The process of hiding unnecessary details and showing only the essential features of an object or system.

In simple terms: You know what something does, but you don't need to know how it works internally.

Everyday Example:

🚗 Driving a Car

When you drive a car, you use:

• Steering wheel

• Accelerator

• Brake

You do not need to know how the engine, transmission, or fuel injection system works. You only use the controls.

Abstract Data Type (ADT)

A logical description of a data structure.

It defines:

• What operations can be performed

• Not how those operations are implemented

Think of it as a blueprint or set of rules.

Push

Add an Item

Pop

Remove the top item

Peek

View the top item

isEmpty

Check if the stack is empty

Stack

Follows the Last In, First Out (LIFO) principle

Imagine a stack of plates:

🍽 Plate 3 (Top)

🍽 Plate 2

🍽 Plate 1 (Bottom)

You can only:

• Put a plate on top

• Remove the top plate

Queue

Follows First In, First Out (FIFO) principle.

Example:

People waiting to buy movie tickets.

John → Maria → Alex

• John entered first.

• John will be served first.

Enqueue

Add to the rear

Dequeue

Remove from the front

Front

View the first person

Linear and Non-Linear

Two types of Data Structure

Linear

Elements are accessed in a sequential order but may be stored unsystematically.

Non-Linear

Elements are stored and accessed in a non-sequential order.

Linked List

Used for storing elements where each is a separate object.

Tree

Represents a hierarchical nature of a structure in a graphical form

Priority Queue

Used for retrieving and removing either the minimum or maximum element.

Heap

A partially sorted binary tree.

Set

Represents a collection of elements that do not have to be in order.

Map

A set of ordered pairs with elements known as key and value.

Graph

Consists of a set of points/nodes (vertices) and set of links (edges) which connects the pairs of vertices.

Algorithm

A clear, step-by-step procedure used to solve a problem or complete a task. Similar to a cooking recipe. A recipe provides instructions that must be followed in the correct order.

Everyday example: Making coffee

1. Prepare a cup.

2. Put coffee into the cup.

3. Add hot water.

4. Add sugar and milk.

5. Stir the coffee.

6. Serve.

Characteristics of a Good Algorithm

Finiteness, Definiteness, Input, Output, and Uniqueness or Effectiveness

Finiteness

The algorithm must stop after completing a limited number of steps.

Example:

1. Enter two numbers.

2. Add the numbers.

3. Display the result.

4. End. The algorithm has an ending.

Definiteness

Every instruction must be clear and understandable.

Clear instruction:

Add the first number and the second number.

Input

The information received by the algorithm before processing begins.

Example:

In a grading system, the inputs may be:

Student name: Ana

Quiz grade: 90

Exam grade: 85

An algorithm may have one ___, several ____, or sometimes no ____.

Output

The result produced by the algorithm.

Using the grades above:

Average: 87.5

The average is the ____.

Uniqueness or Effectiveness

Every step must produce an expected result based on the input or the result of a previous step.

Example:

Input: 10 and 5

Process: 10 + 5

Output: 15

The process should consistently produce the correct answer.

Elements of an Algorithm

Sequential Operations, Selection or Decision, Iteration, and Recursion

Sequential Operations

Are instructions performed one after another.

Example:

Calculating a rectangle’s area

1. Enter the length.

2. Enter the width.

3. Multiply the length by the width.

4. Display the area.

If:

Length = 5

Width = 4

Then:

Area = 5 × 4

Area = 20

Selection or Decision

Allows the algorithm to choose an action based on a condition. It normally uses an if statement.

Example: Passing or failing

If grade is 75 or higher

Display "Passed"

Otherwise

Display "Failed"

If the grade is 80, the output is: Passed

Iteration

Means repeating an instruction several times. It is also called a loop.

Example:

Display the numbers from 1 to 5:

1

2

3

4

5

The display instruction is repeated five times.

Recursion

Happens when a method calls itself to solve a smaller version of the same problem.

Algorithm Design Paradigms

A general approach used to solve a problem.

Brute Force Algorithm

Tries possible answers until it finds the correct one.

Divide and Conquer

Breaks a large problem into smaller problems. It usually follows three actions:

1. Divide the problem.

2. Solve each smaller problem.

3. Combine the answers.

Dynamic Programming

Saves previously calculated results so the computer does not need to calculate them again.

Greedy Algorithm

Chooses the option that provides the best immediate benefit.

Sorting Algorithm

Arranges data in a particular order.

Ascending order

The values are arranged from smallest to largest.

Original list: 5, 8, 1, 2, 20

Sorted list: 1, 2, 5, 8, 20

Descending order

The values are arranged from largest to smallest.

20, 8, 5, 2, 1

Alphabetical order

Names may be sorted from A to Z:

Cruz, Dela Rosa, Garcia, Reyes, Santos

Bubble Sort

Compares two neighboring values. If they are in the wrong order, the values exchange positions.

The biggest value slowly moves toward the end of the list, similar to a bubble rising to the surface.

Selection Sort

Finds the smallest value in the unsorted part of the array. It then places that value in the next correct position.

Insertion Sort

Takes one value at a time and inserts it into the correct position in the sorted part of the list. It is similar to arranging playing cards in your hand.

Searching Algorithms

• Is a basic, fundamental step in computing done via step-by-step method to locate a specific data among a collection of data.

• All ______ make use of a search key in order to complete the procedure, and they are expected to return a success or a failure status (in boolean true or false value).

• It is designed to check or retrieve an element from any data structure where it is being stored.

Linear Search

Or sequential 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.

Examines the elements one at a time.

Given: 12, 7, 20, 5, 9

Find 5.

Process:

1. Check 12 — not equal to 5.

2. Check 7 — not equal to 5.

3. Check 20 — not equal to 5.

4. Check 5 — found.

Binary Search

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. This can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first.

Jump 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.

Data Field

This contains the value of the element

Pointer field (link or reference)

This contains the address (random memory location) of the next node.

HEAD

The first node in the list is called ______.

NULL

The last node points to _____ since there are no more successive elements.

Singly Linked List

The basic linked list. Each node has data and an address field that contains a reference to the next node.

Doubly Linked List

Contains an extra pointer to connect to the previous node in the sequence. The left pointer contains the address of the preceding node called “predecessor.”

Circular Linked List

A linked list in which the last node’s right pointer contains the address of the first node.

Display

shows the elements in the list

Insert

adds an element into the list

Delete

removes a specific element or all the elements from the list

Search

finds a specific element in the list

Count

returns the number of elements in the list