Q. Explain how 2D array is stored in Array.

Data Indexing: Hashing is used in databases and  Only the largest size data member can be original.pop(); }
Ans: a two-dimensional array is essentially an array of information retrieval systems for quick access to stored directly accessed while using a union. while (!auxiliary.empty()) {
arrays. When stored in memory, a two-dimensional array data based on a hashed index.  It is used when you want to use less (same) original.push(auxiliary.top());
is typically represented as a contiguous block of memory. memory for different data members. auxiliary.pop();
EXAMPLE:  It allocates memory size to all its data } }
int arr[3][4] = { members to the size of its largest data int main() {
{1, 2, 3, 4}, member. stack<int> originalStack;
{5, 6, 7, 8}, Syntax stack<int> auxStack;
Example
{9, 10, 11, 12}, }; union [union name] { originalStack.push(1);
union employee {
Store like this Q. Explain stack by using linked list. type member_1;
string name;
originalStack.push(2);
Ans: Using a linked list to implement a stack involves type member_2; originalStack.push(3);
1 2 3 4 5 6 7 8 9 10 11 12 string department;
creating a structure where each node in the linked list type member_n; }; originalStack.push(4);
Q. What is priority queue int phone;
cout << "Original Stack: ";
holds the stack element and a pointer to the next element string email; };
Ans: A priority queue is an abstract data structure that
(or node) in the stack. This creates a Last-In-First-Out while (!originalStack.empty()) {
operates similar to a regular queue or stack but with a key
(LIFO) data structure, similar to how a stack operates. cout << originalStack.top() << " ";
difference: the order in which elements are removed Q. What do you understand by data structure originalStack.pop();
#include <iostream>
depends on their priority. In a priority queue, elements Ans: A data structure is a way of organizing and storing
struct Node { } cout << endl;
with higher priority are dequeued before elements with data in a computer so that it can be accessed and
int data; reverseStack(originalStack, auxStack);
lower priority, regardless of the order in which they were manipulated efficiently. It provides a means to manage
Node* next; }; cout << "Reversed Stack: ";
added. and organize data effectively to perform various
class Stack { while (!originalStack.empty()) {
This data structure is often implemented using various operations like insertion, deletion, searching, sorting, and
private: cout << originalStack.top() << " ";
approaches such as heaps, balanced binary search trees, more.
Node* head; originalStack.pop();
or arrays. The primary operations supported by a priority Key aspects:
public: } cout << endl; return 0; }
queue include: Organization: Data structures define the logical
Insertion: Adding an element to the priority queue. The
Stack() : head(nullptr) {}
relationship between data elements and how they are
Q. Describe the types of sparse matrix
bool isEmpty() { Ans: Sparse matrices are matrices that have a vast
element is added based on its priority. stored in memory.
return (head == nullptr); } majority of their elements as zero. They occur commonly
Deletion: Removing the element with the highest priority Operations: Each data structure supports specific
void push(int data) { in scientific and engineering applications where large
from the priority queue. operations that can be performed on the stored data, like
Node* node = new Node{data, head}; amounts of data are processed, but most of the data is
Peek/Access: Viewing the element with the highest traversal, insertion, deletion, searching, and sorting.
head = node; zero. There are several types of sparse matrices,
priority without removing it. Efficiency: Data structures are designed to optimize
std::cout << data << " pushed to stack\n"; } categorized based on their properties and storage
Update: Modifying the priority of an existing element in operations for efficiency in terms of time and space
int pop() { formats:
the priority queue. complexity. Different data structures have different
if (isEmpty()) { 1. Row-wise Linked List Representation:
Q. What is linked list std::cout << "Stack underflow\n";
performance characteristics for different operations.
In this representation, each row of the matrix is
Ans: A linked list is a fundamental data structure in Use Cases: Different data structures are suitable for
return -1; } represented as a linked list. Each node in the list contains
computer science used for storing and organizing a different scenarios.
Node* temp = head; the column index and the value of the non-zero element.
collection of elements. It consists of a sequence of nodes, head = head->next;
Q. Applications of stack 2. Column-wise Linked List Representation:
where each node contains data and a reference to the Ans: Stacks find various applications across different
int popped = temp->data; Similar to the row-wise representation, but here, each
next node in the sequence. The last node typically points domains due to their Last-In-First-Out (LIFO) nature. Here
delete temp; column of the matrix is represented as a linked list.
to a null reference, indicating the end of the list. are some common applications of stacks in data
return popped; } 3. Array of Structures (COO - Coordinate List):
The basic components of a linked list include: structures:
int peek() { In COO format, a list of tuples (row, column, value) is
Node: Each node in a linked list contains two parts: 1. Function Call and Recursion:
if (isEmpty()) { maintained, where each tuple represents a non-zero
Data: Holds the value or information. Stacks are used in programming languages to manage
std::cout << "Stack is empty\n"; element along with its row and column indices.
Pointer/Reference: Points to the next node in the function calls and their local variables. When a function is
return -1; } 4. Compressed Sparse Row (CSR)
sequence. called, its information (return address, parameters, etc.) is
return head->data; } }; In this format, three arrays are used: values array column
Head: The starting point or the reference to the first node pushed onto the call stack. As functions complete
int main() { indices and a row pointer array .
in the linked list. execution, they are popped off the stack.
Stack stack; 5. Compressed Sparse Column (CSC)
There are different types of linked lists: 2. Expression Evaluation:
stack.push(1); Similar to CSR, but it stores data column-wise. It uses
Singly Linked List: In this type, each node points only to Stacks are used in evaluating arithmetic expressions
stack.push(2); values, row indices, and column pointer arrays, where the
the next node in the sequence. Traversal in a singly linked (infix, postfix, or prefix notation) by converting them to
stack.push(3); column pointer array indicates the starting index in the
list is unidirectional. postfix or prefix and then evaluating using a stack-based
std::cout << "Top element of stack: " << stack.peek() values array for each column.
Doubly Linked List: Each node has pointers to both the algorithm.
<< "\n"; 6. Diagonal Storage:
next and previous nodes, allowing traversal in both 3. Undo Functionality in Text Editors:
std::cout << stack.pop() << " popped from stack\n"; For matrices with non-zero elements only along the main
forward and backward directions. The undo feature in text editors is often implemented
std::cout << stack.pop() << " popped from stack\n"; diagonal, storage can be optimized to store only the
Circular Linked List: In this type, the last node's pointer using a stack. Each action (typing, deleting, formatting) is
std::cout << "Top element of stack: " << stack.peek() diagonal elements.
points back to the first node, forming a circle. recorded as a command and pushed onto a stack. To
<< "\n"; 7. Triangular Storage:
Q. Explain B-tree. return 0; } undo, the editor pops the latest action from the stack.
For upper or lower triangular matrices (where elements
Ans: A B-tree is a self-balancing tree data structure 4. Browser History:
Q. Write a program of multidimensional array The backward and forward navigation history in web
above or below the main diagonal are zeros), storage can
designed to maintain sorted data and permit efficient be optimized to store only the non-zero triangular
Ans: #include <iostream>
search, insertion, and deletion operations. It is commonly browsers is maintained using a stack. As pages are
using namespace std; elements.
used in databases and file systems where large amounts visited, their URLs are pushed onto a stack. Going back in
const int ROWS = 3; 8. Block Sparse Format:
of data need to be stored, as it provides logarithmic time history pops URLs from the stack.
const int COLS = 4; Divides the matrix into smaller blocks and stores only the
complexity for most operations. 5. Parentheses Matching:
int main() { blocks that contain non-zero elements.
B-trees are often used in file systems, databases, and Stacks are used to check for balanced parentheses,
int multiArray[ROWS][COLS] = {
braces, and brackets in programming languages or syntax
Q. Explain D-Queue and Priority Queue
other applications that need to store and retrieve large {1, 2, 3, 4}, Ans: D-Queue
amounts of data quickly. They are also used in some parsing.
{5, 6, 7, 8}, D-Queue is a double-ended queue. It is a linear data
compilers to implement symbol tables. 6. Compiler Implementations:
{9, 10, 11, 12} structure that can be used to add or remove elements
The order of a B-tree is the maximum number of children Compilers use stacks to implement the parsing of
}; from both the front and the rear. It is implemented as a
that a node can have. The order of a B-tree must be at expressions and syntax by maintaining information about
cout << "Multidimensional Array:\n"; circular array. The basic operations of a D-Queue are:
least 3. nested structures and precedence.
for (int i = 0; i < ROWS; ++i) { Enqueue: Add an element to the front or the rear of
To insert a key into a B-tree, we start at the root node and 7. Backtracking Algorithms:
for (int j = 0; j < COLS; ++j) { queue.
search for the appropriate leaf node. If the leaf node has Backtracking algorithms, like depth-first search, often use
cout << multiArray[i][j] << " "; } Dequeue: Remove an element from the front or the rear of
enough space, we simply insert the key into the node. stacks to keep track of visited nodes or states to
cout << endl; } the queue.
Otherwise, we split the node into two nodes and insert the backtrack efficiently.
multiArray[1][2] = 20; Front: Get the element at the front of the queue.
key into the appropriate node. 8. Memory Management:
cout << "\nModified Multidimensional Array:\n"; Rear: Get the element at the rear of the queue.
To search for a key in a B-tree, we start at the root node Stacks play a role in managing memory in computer
for (int i = 0; i < ROWS; ++i) { IsEmpty: Check if the queue is empty.
and search for the leaf node that contains the key. If the systems. For example, the call stack in memory keeps
for (int j = 0; j < COLS; ++j) { IsFull: Check if the queue is full.
key is in the leaf node, we return it. Otherwise, we return track of function calls and their memory allocations.
cout << multiArray[i][j] << " "; } EXAMPLE
NULL. 9. Operating System Scheduling:
cout << endl; } #include <iostream>
To delete a key from a B-tree, we start at the root node Operating systems use stacks to store information about
return 0; } #include <deque>
and search for the leaf node that contains the key. If the processes, their states, and contexts for CPU scheduling.
leaf node has enough space, we simply delete the key
Q. Define structure and union with example. Q. Write the procedure to delete an element using namespace std;
Ans: STRUCTURE int main() {
from the node. Otherwise, we merge the node with its from an array deque<int> d;
sibling node and delete the key from the merged node. Structure (struct) is a user-defined data type in a
Ans: To delete an element from an array in most
programming language that stores different data types' d.push_back(1); // Insert element at the rear
Characteristics of a B-tree:- programming languages, you typically have to shift
values together. The struct keyword is used to define a d.push_front(2); // Insert element at the front
Balanced Tree: A B-tree is balanced, meaning all leaf elements after the deleted element to the left to fill the
structure data type in a program. The struct data type d.push_back(3);
nodes are at the same level, ensuring relatively uniform gap left by the deleted element.
stores one or more than one data element of different cout << "Deque elements after insertion: ";
access times for elements. #include <iostream>
kinds in a variable for (auto elem : d) {
Multiple Child Nodes: Each node in a B-tree can have using namespace std;
Advantages of Structure cout << elem << " "; }
more than two children (unlike binary trees). A node can void deleteElement(int arr[], int &n, int pos) {
 Structure stores more than one data type of cout << endl;
have multiple keys and pointers to child nodes. if (pos < 0 || pos >= n) {
the same object together. d.pop_back(); // Remove element from the rear
Sorted Data: Within a node, keys are stored in sorted cout << "Invalid position to delete.\n";
 It is helpful when you want to store data of d.pop_front(); // Remove element from the front
order, allowing for efficient search operations using return; }
different or similar data types such as cout << "Deque elements after deletion: ";
techniques like binary search. for (int i = pos; i < n - 1; ++i) {
name, address, phone, etc., of the same for (auto elem : d) {
Minimum and Maximum Keys: A B-tree node can have a arr[i] = arr[i + 1]; } }
object. cout << elem << " " }
variable number of keys within a specified range, defined int main() {
 It makes it very easy to maintain the entire cout << endl;
by minimum and maximum values known as the order of int arr[] = {1, 2, 3, 4, 5};
record as we represent complete records return 0; }
the B-tree. int size = 5;
Self-Balancing: Insertions and deletions in a B-tree may using a single name.
int position = 2; // Deleting element at index 2 (value 3)
Priority Queue
cause the tree to be unbalanced, but the B-tree has  The structure allows passing a whole set of Priority Queue is a queue in which elements are served
cout << "Original Array: ";
mechanisms to ensure it remains balanced after such records to any function with the help of a according to their priority. The elements in the priority
for (int i = 0; i < size; ++i) {
operations, single parameter. queue are arranged in such a way that the element with
cout << arr[i] << " ";
Q. What is Hashing  An array of structures can also be created the highest priority is at the front of the queue. The basic
} cout << endl;
to store multiple data of similar data types. operations of a priority queue are:
Ans: Hashing is a technique used in computer science to deleteElement(arr, size, position);
Syntax Enqueue: Add an element to the queue with a priority.
map data of arbitrary size to fixed-size values, typically Example cout << "Array after deletion: ";
struct [structure_name] Dequeue: Remove the element with the highest priority
for indexing and retrieval purposes. It involves applying a struct employee for (int i = 0; i < size; ++i) {
{ from the queue.
hash function that converts the input data (also called a { cout << arr[i] << " ";
type member_1; Peek: Get the element with the highest priority from the
"key") into a numerical value, known as the hash code or int id; } cout << endl;
type member_2; queue without removing it.
hash value. char name[50]; return 0; }
type member_n; }; IsEmpty: Check if the queue is empty.
Applications in various areas, including: string department; Q. Write a function to reverse a stack using Push IsFull: Check if the queue is full.
Hash Tables: Data structures that use hashing to string email; and Pop operation Priority queues are used in a variety of applications, such
efficiently store and retrieve key-value pairs. They provide }; Ans. To reverse a stack using only push and pop as job scheduling, network routing, and traffic
average-case constant-time lookup, insertion, and UNION operations, you can utilize another auxiliary stack. The management.
deletion operations. Union is a user-defined data type that is used to store the idea is to empty the original stack by popping its EXAMPLE
Cryptographic Hash Functions: Specialized hash functions different data type's values. However, in the union, one elements and pushing them onto the auxiliary stack. #include <iostream>
used in cryptography to produce fixed-size hash values member will occupy the memory at once. In other words, Then, refill the original stack in reversed order by popping #include <queue>
that are secure and irreversible. They are used in we can say that the size of the union is equal to the size elements from the auxiliary stack and pushing them back using namespace std;
password hashing, digital signatures, and data integrity of its largest data member size. Union offers an effective onto the original stack. int main() {
verification. way to use the same memory location several times by #include <iostream> priority_queue<int> pq;
Checksums: Hash functions used to verify data integrity each data member. The union keyword is used to define #include <stack> pq.push(5);
by producing a hash code (checksum) from data. Any and create a union data type. using namespace std; pq.push(1);
change in the data usually results in a different checksum, Advantages of Union void reverseStack(stack<int> &original, stack<int> pq.push(3);
indicating possible corruption.  Union takes less memory space as &auxiliary) { cout << "Priority Queue elements: ";
compared to the structure. while (!original.empty()) { while (!pq.empty()) {
auxiliary.push(original.top());
 cout << pq.top() << " "; // Display highest priority bubbleSort(arr, n); Merge sort is an efficient, general-purpose, and Traversal:
element cout << "Sorted array: "; comparison-based sorting algorithm. Most In-order traversal of a threaded binary tree utilizes
pq.pop(); // Remove highest priority for (int i = 0; i < n; ++i) { implementations produce a stable sort, which means that threads to visit nodes in ascending order efficiently.
element cout << arr[i] << " "; the relative order of equal elements is the same in the Searching:
} cout << endl; } cout << endl; input and output. Searching in a threaded binary tree follows the standard
return 0; } return 0; } Merge sort works by recursively dividing the unsorted list binary search tree properties.
Insertion Operations: Q. Make a binary search tree for giving data, 14, into two halves, sorting each half, and then merging the Insertion and Deletion:
Deque (Double-ended Queue): 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9, 14, 5 sorted halves back together. This process is repeated until Insertion and deletion operations in threaded binary trees
push_back: Insertion of an element at the rear of the the entire list is sorted. need to maintain threading while ensuring proper linkage
Ans: #include <iostream>
deque. The merge sort algorithm is relatively simple to of threads after modification.
using namespace std;
push_front: Insertion of an element at the front of the implement and understand, and it has a good average Considerations:
struct Node {
deque. and worst-case time complexity of O(n log n). This makes Complexity:
int data;
Priority Queue: it a good choice for sorting large lists. Implementing and maintaining threads in a threaded
Node* left;
Push: Insertion of an element into the priority queue Node* right; Q. Explain heap short and show step by step binary tree adds complexity to insertion, deletion, and
based on its priority. procedure to sort the data using heap sort tree manipulation operations.
Node(int val) : data(val), left(nullptr), right(nullptr) {}
Deletion Operations: Memory Overhead:
Deque (Double-ended Queue):
}; Node* insert(Node* root, int data) { technique. Additional pointers (threads) in each node increase
if (root == nullptr) { Ans: Heap sort is a comparison-based sorting algorithm
pop_back: Removal of an element from the rear of the memory usage compared to a regular binary tree.
return new Node(data); that builds a heap from the elements and repeatedly
deque. Trade-offs:
} if (data < root->data) { extracts the maximum (for max-heap) or minimum (for
pop_front: Removal of an element from the front of the The benefit of faster traversal via threads needs to be
root->left = insert(root->left, data); min-heap) element from the heap, resulting in a sorted
deque. balanced against increased complexity and memory
} else if (data > root->data) { array. Here's a step-by-step procedure to sort data using
EXAMPLE overhead.
root->right = insert(root->right, data); heap sort.
Deque (Double-ended Queue): } return root; Heap Sort Algorithm
Q. Describe hashing and various hashing
cpp techniques in detail.
} void inorderTraversal(Node* root) { To solve the problem follow the below idea:
Copy code d.pop_back(); // Remove from rear if (root == nullptr) { First convert the array into heap data structure using Ans: Hashing is a technique used in computer science to
#include <deque> d.pop_front(); // Remove from return; heapify, then one by one delete the root node of the Max- map data of arbitrary size to fixed-size values, typically
using namespace std; front } inorderTraversal(root->left); heap and replace it with the last node in the heap and used for indexing and accessing data in a data structure
int main() { return 0; } cout << root->data << " "; then heapify the root of the heap. Repeat this process called a hash table. It involves applying a hash function
deque<int> d; inorderTraversal(root->right); until size of heap is greater than 1. that converts input data (keys) into indices of an array,
d.push_back(1); // Insert at rear } int main() {  Build a heap from the given input array. allowing for faster retrieval of information based on the
d.push_front(2); // Insert at front int data[] = {14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17, 9,  Repeat the following steps until the heap key.
int rearElement = d.back(); // Access rear element 14, 5}; contains only one element: Hash Function:
Priority Queue: int size = sizeof(data) / sizeof(data[0]);  Swap the root element of the heap (which is Hash Function Properties:
Pop: Removal of the highest priority element from the Node* root = nullptr; the largest element) with the last element Deterministic: For a given input, the hash function should
priority queue. for (int i = 0; i < size; ++i) { of the heap. always produce the same output.
#include <queue> root = insert(root, data[i]);  Remove the last element of the heap (which Uniformity: Ideally, the hash function should distribute
using namespace std; } is now in the correct position). keys uniformly across the hash table to minimize
int main() { cout << "Inorder traversal of the constructed Binary  Heapify the remaining elements of the collisions.
priority_queue<int> pq; Search Tree:\n"; heap. Efficiency: Hash functions should be computationally
pq.push(5); // Push inorderTraversal(root);  The sorted array is obtained by reversing efficient.
int topPriority = pq.top(); // Access highest priority cout << endl; the order of the elements in the input array. Various Hashing Techniques:
element return 0; } Division Method:
pq.pop(); // Pop Uses the modulo operator to map keys directly to array
return 0; }
Q. Differentiate linear and Binary search with indices.
Q. Write a program to print a given singly linked list in the Q. Why double linked list is better than linked hash(key) = key % table_size
reverse order Example
Ans: Linear search is a method of searching for a
list? Multiplication Method:
Ans #include <iostream> Ans: A double linked list (DLL) offers certain advantages Involves multiplying the key by a constant (usually
using namespace std; particular value in a list. It works by checking each
over a singly linked list (SLL) due to its structure, allowing between 0 and 1) and extracting the fractional part.
struct Node { element of the list one by one until the desired value is
traversal in both directions (forward and backward). Here hash(key) = floor(table_size * (key * A % 1))
int data; found. If the value is not found, the search will return -1.
are some reasons why a double linked list might be Universal Hashing:
Node* next; Linear search:
considered better than a singly linked list in certain Utilizes a family of hash functions and selects one
Node(int val) : data(val), next(nullptr) {} Check the first element of the list.
scenarios: randomly at runtime to minimize collisions.
}; If the element is equal to 5, return the index of the
Advantages of Double Linked List: Provides better average-case performance by reducing
void insert(Node* &head, int val) { element.
Bidirectional Traversal: the likelihood of collisions for specific patterns of input
Node* newNode = new Node(val); If the element is not equal to 5, check the next element of
DLL allows traversal in both forward and backward data.
newNode->next = head; the list.
directions, unlike SLL, which only supports forward Hashing with Chaining (Separate Chaining):
head = newNode; } Repeat steps 2 and 3 until the desired value is found or
traversal. Handles collisions by storing multiple elements at each
void printReverse(Node* head) { the end of the list is reached.
This bidirectional traversal facilitates operations like index of the hash table using linked lists, arrays, or other
if (head == nullptr) { If the desired value is not found, return -1.
reverse traversal and easier manipulation of elements in data structures.
return; } EXAMPLE
both directions. Colliding elements are chained together at the same
printReverse(head->next); #include <iostream>
Deletion Efficiency: index.
cout << head->data << " "; using namespace std;
Deletion in DLL is more efficient than SLL in some cases, Open Addressing:
} int main() { int search(int array[], int n, int x)
especially when the node to be deleted is given. Resolves collisions by finding an alternative location
Node* head = nullptr; {
In a DLL, deletion can be performed without needing to within the hash table when a collision occurs.
for (int i = 5; i > 0; --i) { for (int i = 0; i < n; i++)
traverse the list from the beginning (as in SLL), as the Techniques include linear probing, quadratic probing, and
insert(head, i); if (array[i] == x)
node itself contains references to both the previous and double hashing.
} cout << "Original Linked List: "; return i;
next nodes. Perfect Hashing:
Node* temp = head; return -1;
Insertion at Both Ends: Achieves minimal collisions for a specific set of keys
while (temp != nullptr) { }
DLL allows efficient insertion at both the beginning and without chaining.
cout << temp->data << " "; Binary search:
end of the list. Requires more complex algorithms and may involve
temp = temp->next; Divide the list in half.
In SLL, inserting at the end requires traversal from the multiple levels of hashing.
} cout << endl; If the middle element of the list is equal to 5, return the
head to the end, which is less efficient than in DLL, where Q. Write algorithm ad its C syntax to insert an
cout << "Linked List in Reverse Order: "; index of the element.
the tail reference allows direct insertion at the end. element at the Kth position into the linear array
printReverse(head); If the middle element of the list is not equal to 5, search
Better for Reverse Operations:
cout << endl; the appropriate half of the list. Ans:
Operations like reversing the list or extracting elements
return 0; }: Repeat steps 2 and 3 until the desired value is found or Algorithm:
from the end become more efficient in DLL compared to
Q. Hashing Techniques the end of the list is reached. Check if the array is not full (there's enough space to
SLL due to the backward references.
If the desired value is not found, return -1. accommodate the new element).
Ans: Separate chaining: Considerations:
EXAMPLE Shift elements from index K to the right to create space
This is the most common hashing technique. It uses an Memory Overhead:
#include <iostream> for the new element.
array of linked lists to store the data. The hash function is DLL requires more memory per node due to the additional
using namespace std; Insert the new element at index K.
used to determine which linked list to store the data in. backward pointer, compared to SLL.
int binarySearch(int array[], int x, int low, int high) C Syntax:
Linear probing: This extra pointer might be considered wasteful in
{ #include <stdio.h>
This technique stores the data in an array. The hash scenarios where backward traversal or insertion at both
while (low <= high) { #define MAX_SIZE 100 // Define maximum array size
function is used to determine where to start searching for ends is not needed.
int mid = low + (high - low) / 2; void insertElement(int arr[], int size, int element, int k) {
the data. If the data is not found at the first location, the Complexity:
if (array[mid] == x) if (size >= MAX_SIZE) {
search continues at the next location, and so on. DLL involves more complex code compared to SLL due to
return mid; printf("Array is full. Cannot insert element.\n");
#include <iostream> handling backward references, potentially increasing the
if (array[mid] < x) return;
#include <unordered_map> chances of bugs or errors.
low = mid + 1; } if (k < 0 || k > size) {
using namespace std; Suitability:
else printf("Invalid position for insertion.\n");
int main() { The choice between SLL and DLL depends on the specific
high = mid - 1; return;
unordered_map<string, int> myMap; requirements of the application. If bidirectional traversal
} return -1; } } for (int i = size - 1; i >= k; i--) {
myMap["apple"] = 1; or efficient deletion at arbitrary nodes is a common
myMap["banana"] = 2; Q. What is sorting? Explain selection sort. operation, a DLL might be more suitable.
arr[i + 1] = arr[i]; // Shift elements to the right
Ans. Sorting in C++ is a technique that is implemented to }
myMap["cherry"] = 3; Q. What is Threaded Binary tree?
arrange the data in a specific order. Sorting is required to arr[k] = element; // Insert the new element at position k
cout << myMap["apple"] << endl; // prints 1 Ans: A threaded binary tree is a binary tree with additional
ensure that the data which we use is in a particular order } int main() {
cout << myMap["banana"] << endl; // prints 2 pointers (called threads) that link some nodes to their in-
so that we can easily retrieve the required piece of int arr[MAX_SIZE] = {1, 2, 3, 4, 5};
cout << myMap["cherry"] << endl; // prints 3 order successors or predecessors, enabling efficient
information from the pile of data. int size = 5; // Current size of the array
return 0; } traversal without the need for recursion or a stack. These
There are many algorithms available to sort. In general, int element = 10; // Element to be inserted
Q. Apply Bubble sort on DATA STRUCTURE threads act as shortcuts to navigate through the tree in a int position = 2; // Position at which the element should
Sorting in C++ are distinguished into two types:
Ans: Bubble sort is a simple sorting algorithm that specific order.
Internal Sorting: Internal sorting is used to sort data that be inserted
repeatedly steps through the list, compares adjacent Types of Threaded Binary Trees:
fits entirely in the main memory. printf("Original array: ");
elements, and swaps them if they are in the wrong order. Single Threaded Binary Tree:
External Sorting: External sorting is used to sort data that for (int i = 0; i < size; ++i) {
This process is repeated until the entire list is sorted. Each node contains only one additional pointer (either left
is too large to fit in the main memory and hence has to be printf("%d ", arr[i]);
When applying bubble sort to a data structure like an or right) that points to its in-order successor.
stored on disk. }
array or a linked list, the process remains the same. Nodes without a right child or left child point to their in-
Some of the most commonly used sorting algorithms are: printf("\n");
#include <iostream> order successor or predecessor, respectively.
Bubble sort, Selection sort, Insertion sort, Merge sort, insertElement(arr, size, element, position);
using namespace std; Double Threaded Binary Tree:
Quick sort, Heap sort, Counting sort, Radix sort. size++; // Increase the size of the array
void bubbleSort(int arr[], int n) { Each node contains both left and right additional pointers
Selection Sort Algorithm printf("Array after insertion: ");
for (int i = 0; i < n - 1; ++i) { that point to its in-order successor and predecessor,
Selection sort is a sorting algorithm that selects the for (int i = 0; i < size; ++i) {
bool swapped = false; respectively.
smallest element from an unsorted list in each iteration printf("%d ", arr[i]);
for (int j = 0; j < n - i - 1; ++j) { Nodes without a left child or right child point to their in-
and places that element at the beginning of the unsorted } printf("\n");
if (arr[j] > arr[j + 1]) { order predecessor or successor, respectively.
list. return 0;
swap(arr[j], arr[j + 1]); Advantages of Threaded Binary Trees:
#include <iostream> }
swapped = true; Efficient Traversal:
#include <algorithm> OUTPUT
} } In-order traversal can be performed without using
using namespace std; Original array: 1 2 3 4 5
if (!swapped) { recursion or a stack, reducing space complexity and
int main() { Array after insertion: 1 2 10 3 4 5
break; eliminating the need for function call overhead.
} } } int main() {
int arr[] = {5, 3, 2, 1, 4}; Q. What is circular Queue
Threads enable quick access to the next or previous node
int n = sizeof(arr) / sizeof(arr[0]); Ans: A circular queue (also known as a ring buffer) is a
int arr[] = {64, 25, 12, 22, 11}; in the in-order sequence.
sort(arr, arr + n); data structure that represents a queue in which the last
int n = sizeof(arr) / sizeof(arr[0]); Space Efficiency:
for (int i = 0; i < n; i++) { position is connected to the first position to form a circle
cout << "Original array: "; Threads eliminate the need for storing NULL pointers,
cout << arr[i] << " "; or loop. This arrangement overcomes the limitations of a
for (int i = 0; i < n; ++i) { reducing memory usage compared to traditional binary
} cout << endl; regular linear queue where new elements cannot be
cout << arr[i] << " "; trees.
return 0; } inserted after the queue becomes full and elements need
} cout << endl; Operations on Threaded Binary Trees:
to be shifted to accommodate new elements after
dequeue operations.
Characteristics of a Circular Queue:
Circular Structure:
The underlying array or linked list used to implement the
circular queue is treated as a circular data structure.
After reaching the end of the queue, the next insertion or
dequeue operation starts from the beginning of the
queue, utilizing the vacant spaces efficiently.
Front and Rear Pointers:
Front Pointer: Indicates the beginning or the first element
in the queue.
Rear Pointer: Indicates the end or the last element in the
queue.
Both pointers move circularly, and their positions wrap
around the array.
Operations:
Enqueue (Insertion): Adds elements to the rear end of the
circular queue.
Dequeue (Deletion): Removes elements from the front
end of the circular queue.
Overflow and Underflow Conditions: Special conditions
need to be handled when the circular queue is full
(overflow) or empty (underflow).
Advantages:

 Efficient utilization of memory space as it

overcomes the limitation of a linear queue.
 Provides a more efficient implementation
for scenarios where elements are frequently
added and removed.
 Implementation:
 Using Arrays: The circular queue can be
implemented using an array where the rear
and front pointers traverse the array in a
circular fashion.
 Using Linked Lists: Circular linked lists can
also be used to implement a circular queue,
with nodes forming a loop.
Implementation:
 Using Arrays: The circular queue can be
implemented using an array where the rear
and front pointers traverse the array in a
circular fashion.
 Using Linked Lists: Circular linked lists can
also be used to implement a circular queue,
with nodes forming a loop.