2021

1. Define Data Structure?

• Data structure is the arrangement of data in a computer memory/storage.

2. Briefly explain the importance of using data structures in programming.

• Efficiency: Enable efficient processing and storage of large amounts of data.

Different structures are suited for different types of applications, which can
greatly affect the performance of an application.

• Data Management: Help in managing and organizing data in a structured way,

making data manipulation and retrieval more effective.

• Problem Solving: Allow programmers to tackle complex problems by providing a

means to handle data in a more logical and manageable way.

• Resource Optimization: Enhance the use of resources like memory and

processing power, as data can be stored and accessed optimally.

• Code Maintenance: Lead to cleaner, more maintainable code due to the

abstraction they provide.

3. Assume that you have designed an algorithm to do a specific task in your final
project. Briefly explain how you can evaluate the efficiency of your algorithm.

• Time Complexity: Analyze how the running time increases with the size of the
input. This is often done using Big O notation.

• Space Complexity: Determine how much memory the algorithm uses in relation
to the input size.

• Benchmark Testing: Run the algorithm with various inputs to measure actual
running time and resource usage.

• Theoretical Analysis: Use mathematical analysis to predict the performance

under different conditions.

• Comparative Analysis: Compare with other algorithms solving the same problem
in terms of speed, memory usage, and scalability.
4. Write a Java function that calculate and returns the sum of all the even numbers of
a given array.

public int sumOfEvenNumbers(int[] array)

{
int sum = 0;
for (int i = 0; i < array.length; i++)
{
if (array[i] % 2 == 0)
{
sum += array[i];
}
}
return sum;
}

5. Write a Java program that finds the maximum and minimum elements in the
following array.
78 65 12 48 23 96 77 18 29 54

public void findMaxMin(int[] array)

{
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++)
{
if (array[i] > max)
{
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
System.out.println("Max: " + max);
System.out.println("Min: " + min);
}

6. What is an abstract data type?

ADT is a specification of a mathematical set of data and the set of operations that
can be performed on the data. Ex: Stack, Queue, LinkedList, Tree
7. State whether the following data structures is leaner or nonlinear.

a) Array - Linear
b) Stack - Linear
c) Queue Linear
d) Graph-Non-Linear

8. Compare and contrast arrays and linked lists data structures, highlighting their
advantages and disadvantages

Arrays:
Advantages:
• Direct Access: Allows direct access to elements using indices.
• Memory Efficient: More memory efficient as it does not require extra storage for
references.
• Better Cache Performance: Due to contiguous memory allocation, they have
better cache locality.

Disadvantages:
• Fixed Size: The size of the array is fixed and needs to be known beforehand.
• Inefficient Insertions/Deletions: Inserting or deleting elements is costly because it
may require shifting elements.

Linked Lists:
Advantages:
• Dynamic Size: Can grow or shrink in size dynamically.
• Efficient Insertions/Deletions: More efficient insertions and deletions, as they
involve only updating references.

Disadvantages:
• No Direct Access: Cannot directly access elements; need to traverse from the
beginning.
• More Memory: Requires extra memory for storing pointers to next (and
previous for doubly linked lists) elements.
• Poor Cache Performance: Due to non-contiguous memory allocation, they have
poorer cache performance.
9. Declare a Java structure to store an integer and a String.

public class Data

{
int number;
String text;

public Data(int number, String text)

{
this.number = number;
this.text = text;
}
}

10. Implement a Java function to insert a node at the beginning of a linked list.
public class Node
{
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
public class LinkedList
{
Node head;
public void insertAtBeginning(int data)
{
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
 }}
11. Differentiate Stack and Queue data structures.

Stack:

• LIFO Principle: Last-In-First-Out. The last element added is the first one to be
removed.
• Operations: Main operations are push (to add an item) and pop (to remove an
item). Additional operations include peek (to view the top element without
removing it) and isEmpty (to check if the stack is empty).
• Usage: Used in scenarios like function call stacks, undo mechanisms in software,
and for algorithms involving backtracking.

Queue:

• FIFO Principle: First-In-First-Out. The first element added is the first one to be
removed.
• Operations: Main operations are enqueue (to add an item to the rear) and
dequeue (to remove an item from the front). Additional operations include front
(to view the first element) and isEmpty/isFull (to check the status of the queue).
• Usage: Used in scenarios like managing requests on a single shared resource (like
a printer), handling call center operations, and in breadth-first search
algorithms.

12. Graphically represent the static and dynamic implementations of Stack?

Static Implementation: This is where the size of the stack is fixed at the time of
creation. If the stack is full and you try to push an element, it will result in a stack
overflow.

Static Implementation (Using Array):

| | <- Top
|5 |
|3 |
|2 |
|1 |
‾‾‾
Here, the stack is implemented using a fixed-size array. The Top pointer points to
the current top of the stack.
 Dynamic Implementation: This is where the size of the stack can grow and shrink as
needed. If the stack is full and you try to push an element, the stack will
automatically resize to make room for the new element.

Dynamic Implementation (Using Linked List):

Top -> | 5 | -> | 3 | -> | 2 | -> | 1 | -> NULL

In this implementation, the stack grows and shrinks dynamically with each push and
pop operation, using a linked list.

13. Define Tree data structure.

• A tree is a data structure that emulates a hierarchical tree structure with a set of
linked nodes.

14. Define the term 'sorting 'giving at least one example.

• Sorting is the process of arranging or ordering a collection of items in a specific

way. For example, if we have a list of numbers, we can sort them in ascending or
descending order.
• Consider a list of numbers: [3, 1, 4, 2]. Sorting this list in ascending order results
in [1, 2, 3, 4].

15. Consider the following data set.

Data Set: 94, 40, 62, 2, 18

a. Sort above data set using selection sort.

Selection Sort works by repeatedly finding the minimum element from the
unsorted part and putting it at the beginning.
First Pass:
Find minimum (2), swap with the first element: [2, 40, 62, 94, 18]
Second Pass:
Find minimum (18), swap with the second element: [2, 18, 62, 94, 40]
Third Pass:
Find minimum (40), swap with the third element: [2, 18, 40, 94, 62]
Fourth Pass:
Find minimum (62), swap with the fourth element: [2, 18, 40, 62, 94]

Sorted DataSet: [2, 18, 40, 62, 94]

 b. Sort the above data set using bubble sort.
Bubble Sort repeatedly steps through the list, compares adjacent elements,
and swaps them if they are in the wrong order.

First Pass:

Compare all adjacent elements and swap if needed.

After first pass, the largest element (94) is bubbled to the end: [40, 62, 2, 18,
94]
Second Pass:

Repeat for the rest, largest (62) to the end: [40, 2, 18, 62, 94]
Third Pass:

Repeat, (40) moves to its correct position: [2, 18, 40, 62, 94]
Fourth Pass:

Sorted DataSet: [2, 18, 40, 62, 94]

16. Write down the pseudo codes to implement a linear search algorithm.

Public int srg (a[] , n, t)

For i=0 to n-1
if(a[i] = t)
return i;
next 1
return -1;

17. Write a Java function to implement a linear search in an integer array.

public static int linearSearch(int[] array, int target)

{
for (int i = 0; i < array.length; i++)
{
if (array[i] == target)
{
return i;
}
}
return -1;
}