0% found this document useful (0 votes)
20 views17 pages

prev year soln

Uploaded by

rahulrizz875
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
20 views17 pages

prev year soln

Uploaded by

rahulrizz875
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 17

MODULE 1

1.a

Data structure is a representation of the logical relationships existing between individual elements of
data. A data structure is a way of organizing all data items that considers not only the elements
stored but also their relationship to each other.

The logical or mathematical model of a particular organization of data is called a data structure.

The commonly used operations on data structures are as follows,

Create: The Create operation results in reserving memory for the program elements. The creation of
data structures may take place either during compile time or during run time

Destroy: The Destroy operation destroys the memory space allocated for the specified data
structure.

3. Selection: The Selection operation deals with accessing a particular data within a data structure.

4. Updating: The Update operation updates or modifies the data in the data structure.

5. Searching: The Searching operation finds the presence of the desired data item in the list of data
items.

6. Sorting: Sorting is the process of arranging all the data items in the data structure in a particular
order, say for example, either in ascending order or in descending order.

7. Merging: Merging is a process of combing the data items of two different sorted list into a single
list.
1.b

2.a

• This is an ordered-list in which insertions(called push) and deletions(called pop) are made at one
end called the top

• Since last element inserted into a stack is first element removed, a stack is also known as a LIFO
list(Last In First Out).

When an element is inserted in a stack, the concept is called push, and when an element is removed
from the stack, the concept is called pop.

Trying to pop out an empty stack is called underflow and trying to push an element in a full stack is
called overflow.
#include <stdio.h>
#include <stdlib.h>

#define MAX 5 // Maximum size of the stack

int stack[MAX]; // Stack array


int top = -1; // Initialize top of the stack

// Function to push an element onto the stack


void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow! Cannot push %d\n", value);
} else {
top++;
stack[top] = value;
printf("%d pushed onto stack\n", value);
}
}

// Function to pop an element from the stack


void pop() {
if (top == -1) {
printf("Stack Underflow! No elements to pop\n");
} else {
printf("%d popped from stack\n", stack[top]);
top--;
}
}

// Function to display the stack elements


void display() {
if (top == -1) {
printf("Stack is empty\n");
} else {
printf("Stack elements: ");
for (int i = top; i >= 0; i--) {
printf("%d ", stack[i]);
}
printf("\n");
}
}

// Main function
int main() {
int choice, value;

while (1) {
printf("\nStack Operations Menu:\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter the value to push: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice! Please choose between 1-4.\n");
}
}

return 0;
}

3.a

When item enters and deleted from the queue, the queue gradually shifts to the right as shown in
figure.

In this above situation, when we try to insert another item, which shows that the queue is full . This
means that the rear index equals to MAX_QUEUE_SIZE -1. But even if the space is available at the
front end, rear insertion cannot be done.
IMPLEMENTATION OF CIRCULAR QUEUE

When the array is viewed as a circle, each array position has a next and a previous position. The
position next to MAX-QUEUE-SIZE -1 is 0, and the position that precedes 0 is MAX-QUEUE-SIZE -1.

When the queue rear is at MAX_QUEUE_SIZE-1, the next element is inserted at position 0.

In circular queue, the variables front and rear are moved from their current position to the next
position in clockwise direction. This may be done using code

if (rear = = MAX_QUEUE_SIZE-1)
rear = 0;
else rear++;

3.b
MULTIPLE STACKS AND QUEUES

In multiple stacks, we examine only sequential mappings of stacks into an array. The array is one
dimensional which is memory[MEMORY_SIZE]. Assume n stacks are needed, and then divide the
available memory into n segments. The array is divided in proportion if the expected sizes of the
various stacks are known. Otherwise, divide the memory into equal segments.

Assume that i refers to the stack number of one of the n stacks. To establish this stack, create indices
for both the bottom and top positions of this stack. boundary[i] points to the position immediately to
the left of the bottom element of stack i, top[i] points to the top element. Stack i is empty iff
boundary[i]=top[i].

The declarations are:


#define MEMORY_SIZE 100 /* size of memory */
#define MAX_STACKS 10 /* max number of stacks plus 1 */
element memory[MEMORY_SIZE]; /* global memory declaration */
int top [MAX_STACKS];
int boundary [MAX_STACKS] ;
int n; /*number of stacks entered by the user */

3.c

DEFINITION
“A queue is an ordered list in which insertions (additions, pushes) and deletions (removals and
pops) take place at different ends.”
The end at which new elements are added is called the rear, and that from which old elements are
deleted is called the front.

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. To implement a
queue using dynamic arrays, the size of the queue can grow or shrink as required, overcoming the
limitations of fixed-size arrays.
Operations

1. Enqueue (Insertion)

• Check Capacity:
If the queue is full (size == capacity), double the size of the array by reallocating memory.

• Insert Element:
Place the new element at the position rear + 1, and update the rear pointer.

• Adjust Circular Behavior:


Use modulo arithmetic to handle wrap-around at the end of the array:
rear = (rear + 1) % capacity.

2. Dequeue (Removal)

• Check for Underflow:


If the queue is empty (size == 0), return an error.

• Remove Element:
Increment the front pointer and adjust using modulo:
front = (front + 1) % capacity.

• Shrink the Array (Optional):


If the queue size becomes very small, reduce the capacity to optimize space.

3. Display

• Print elements from front to rear using modulo arithmetic to ensure wrap-around.

4.a

DEFINITION

A linked list, or one-way list, is a linear collection of data elements, called nodes, where the linear
order is given by means of pointers. That is, each node is divided into two parts:

• The first part contains the information of the element, and

• The second part, called the link field or nextpointer field, contains the address of the next
node in the list.

6.a

Array representation:

A tree can be represented using an array, which is called sequential representation.

The nodes are numbered from 1 to n, and one dimensional array can be used to store the nodes.

Position 0 of this array is left empty and the node numbered i is mapped to position i of the array.
For complete binary tree the array representation is ideal, as no space is wasted.

For the skewed tree less than half the array is utilized.

Linked representation:

The problems in array representation are:

It is good for complete binary trees, but more memory is wasted for skewed and many other binary
trees.

The insertion and deletion of nodes from the middle of a tree require the movement of many nodes
to reflect the change in level number of these nodes.

These problems can be easily overcome by linked representation

Each node has three fields,

LeftChild - which contains the address of left subtree

RightChild - which contains the address of right subtree.

Data - which contains the actual information


7.a
7.b

What is a Selection Tree?

A Selection Tree is a specialized complete binary tree used in sorting and merging applications. It is
often used to find the smallest element among multiple sorted sequences efficiently.

1. Tournament Tree:
A type of selection tree that determines the smallest element by comparing elements
pairwise in a binary tree structure.

2. Loser Tree:
A variant of the selection tree that keeps track of the second-best element at each
comparison step.

#include <stdio.h>
#include <limits.h>

#define K 3 // Number of sorted arrays


#define N 5 // Number of elements in each array

typedef struct {
int value, arrayIndex, elementIndex;
} Node;

// Build initial selection tree


void buildTree(Node tree[], int arrays[K][N]) {
for (int i = 0; i < K; i++)
tree[i] = (Node){arrays[i][0], i, 1};
}

// Update tree and print smallest element


void updateTree(Node tree[], int arrays[K][N]) {
int minIdx = 0;

for (int i = 1; i < K; i++)


if (tree[i].value < tree[minIdx].value)
minIdx = i;

printf("%d ", tree[minIdx].value);


tree[minIdx].value = (tree[minIdx].elementIndex < N)
? arrays[minIdx][tree[minIdx].elementIndex++]
: INT_MAX;
}

void mergeSortedArrays(int arrays[K][N]) {


Node tree[K];
buildTree(tree, arrays);

printf("Merged array: ");


for (int i = 0; i < K * N; i++)
updateTree(tree, arrays);
printf("\n");
}

int main() {
int arrays[K][N] = {
{1, 4, 7, 10, 13},
{2, 5, 8, 11, 14},
{3, 6, 9, 12, 15}
};

mergeSortedArrays(arrays);
return 0;
}
7.c

8.b

Weighted Graph:
A weighted graph assigns a weight (numeric value) to each edge. The weights can represent
distances, costs, or other factors depending on the application.

Example:
Vertices V={A,B,C}V = \{A, B, C\}V={A,B,C}
Weighted edges:

• A→BA \rightarrow BA→B (weight 4)


• B→CB \rightarrow CB→C (weight 3)
• C→AC \rightarrow AC→A (weight 5)
Self-Loop:
A self-loop is an edge that connects a vertex to itself. In other words, the edge starts and ends at the
same vertex.

Example:
Vertex AAA has a self-loop: (A,A)(A, A)(A,A)

Parallel Edges:
Parallel edges are two or more edges that connect the same pair of vertices but may have
different directions or weights in a weighted or directed graph.

Example:
Vertices V={A,B}V = \{A, B\}V={A,B}
Edges: (A,B)(A, B)(A,B) and (A,B)(A, B)(A,B) with different weights (e.g., 2 and 5)

8.c

Elementary graph operations are fundamental operations that can be performed on graphs in
graph theory. These operations allow us to modify, analyze, or traverse graphs. Below are the
key elementary graph operations:

1. Adding a Vertex:
o This operation adds a new vertex (or node) to the graph.
o The vertex may or may not be connected to any other vertices initially.
2. Removing a Vertex:
o This operation removes a vertex from the graph.
o If the vertex is connected to any edges, those edges are also removed.
3. Adding an Edge:
o This operation adds a new edge (or connection) between two existing vertices.
o The edge can either be directed (pointing from one vertex to another) or
undirected (connecting two vertices without direction).
4. Removing an Edge:
o This operation removes an edge between two vertices, disconnecting them.
o For a directed graph, this means the specific direction of the edge is
eliminated.
5. Degree of a Vertex:
o The degree of a vertex is the number of edges connected to it.
o In a directed graph, the in-degree (number of incoming edges) and out-degree
(number of outgoing edges) are considered separately.
6. Checking for an Edge:
o This operation checks whether an edge exists between two given vertices.
o It is typically used in graph traversal or pathfinding algorithms.
7. Graph Traversal:
o Depth-First Search (DFS): Explores as far as possible along each branch
before backtracking.
o Breadth-First Search (BFS): Explores all neighbors of a vertex before
moving to the next level neighbors.
o These operations help in exploring and searching through a graph.
8. Graph Transpose (for Directed Graphs):
o This operation reverses the direction of all edges in a directed graph.
o The transpose of a graph is useful in certain algorithms like finding strongly
connected components.
9. Graph Complement:
o The complement of a graph contains the same set of vertices, but its edges are
the complement of the original graph. That is, if there is an edge between two
vertices in the original graph, there will not be one in the complement, and
vice versa.
10. Checking Connectivity:

• This operation checks whether all vertices in the graph are connected in a single
component.
• In an undirected graph, this means there is a path between any pair of vertices.

9.a

when two or more keys map to the same memory location, a collision Figure 5.18 shows a
hash table in which each key from the set K is mapped to locations generated by using a hash
function. Note that keys k2 and k6 point to the same memory location. This is known as
collision.

The two most popular methods of resolving collisions are: Collision Resolution by Linear
Probing (open addressing) and Quadratic Probing
10.a
10.b

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference
between heights of left and right subtrees for any node cannot be more than one.

Node* insert(Node* node, int key) {


if (node == nullptr) return(newNode(key));
if (key < node->key) node->left = insert(node->left, key);
else if (key > node->key) node->right = insert(node->right, key);
else return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key) return rightRotate(node);
if (balance < -1 && key > node->right->key) return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}

You might also like