Correct Answer: To organize data efficiently
Explanation: Data structures in programming are used to efficiently organize and manage data, facilitating operations like insertion, deletion, and searching.
Correct Answer: Stack
Explanation: A stack data structure follows the Last-In-First-Out (LIFO) principle where the last element added is the first one to be removed.
Correct Answer: Linked List
Explanation: A linked list allows elements to be accessed in both forward and backward directions, but its access time is generally slower compared to arrays due to pointer traversal.
Correct Answer: Constant time complexity for all operations
Explanation: Hash tables provide constant time complexity (O(1)) for insert, delete, and search operations under favorable conditions, making them efficient for many applications.
Correct Answer: Tree
Explanation: A tree data structure is used to represent hierarchical relationships between elements, with a root node at the top and child nodes branching out.
Correct Answer: A data structure with first-in-first-out (FIFO) access
Explanation: A queue data structure follows the FIFO principle where the element added first is the one removed first.
Correct Answer: Stack
Explanation: A stack data structure is ideal for implementing recursion due to its Last-In-First-Out (LIFO) nature, which matches the recursive function call mechanism.
Correct Answer: Each element pointing to the previous and next elements
Explanation: In a doubly linked list, each element contains pointers to both the previous and next elements, enabling bidirectional traversal.
Correct Answer: Binary Heap
Explanation: A binary heap is a specialized tree-based data structure that allows efficient insertion and extraction of the highest (or lowest) priority element.
Correct Answer: Elements having arbitrary relationships between them
Explanation: A graph data structure consists of nodes (vertices) and edges that represent arbitrary relationships between pairs of nodes.
Correct Answer: Each element pointing to the next element only
Explanation: In a singly linked list, each element (node) contains a data field and a pointer to the next node in the sequence.
Correct Answer: Both the next and previous nodes
Explanation: Doubly linked lists have nodes that contain pointers to both the next and previous nodes, allowing bidirectional traversal.
Correct Answer: Its last node points back to the head node
Explanation: A circular linked list connects the last node back to the head node, forming a circular loop.
Correct Answer: Insertion at the beginning
Explanation: Insertion at the beginning of a singly linked list is more efficient (O(1)) compared to a doubly linked list (O(1)) due to the lack of a previous pointer.
Correct Answer: O(n)
Explanation: Inserting a node at the end of a singly linked list requires traversing the entire list to reach the last node, resulting in O(n) time complexity.
Correct Answer: Doubly linked list
Explanation: Doubly linked lists allow traversal from both the head to tail and from tail to head with equal efficiency.
Correct Answer: Support for dynamic memory allocation
Explanation: Circular linked lists support dynamic memory allocation and are useful in applications where continuous access to elements is needed.
Correct Answer: Doubly linked list
Explanation: Doubly linked lists allow efficient insertions and deletions at both the head and tail ends due to bidirectional traversal capability.
Correct Answer: Deletion of the head node
Explanation: Deleting the head node in a circular linked list requires special handling to adjust pointers and maintain the circular structure.
Correct Answer: Doubly linked list
Explanation: Doubly linked lists are ideal for implementing an LRU cache as they allow constant time complexity for insertion, deletion, and moving nodes to the front based on recent usage.
struct Node {
int data;
struct Node *next;
};
Correct Answer: Singly linked list
Explanation: The given struct definition represents a singly linked list node with a data field and a pointer to the next node.
struct Node *insertAtBeginning(struct Node *head, int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head;
return newNode;
}
Correct Answer: Insertion at the beginning
Explanation: The function `insertAtBeginning` inserts a new node with the given value at the beginning of a singly linked list.
void deleteNode(struct Node **head_ref, int key) {
struct Node *temp = *head_ref, *prev;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) return;
prev->next = temp->next;
free(temp);
}
Correct Answer: Deletion of a node by key
Explanation: The function `deleteNode` deletes a node from a singly linked list based on the given key value.
void insertAtEnd(struct Node **head_ref, int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
struct Node *last = *head_ref;
newNode->data = value;
newNode->next = NULL;
if (*head_ref == NULL) {
newNode->prev = NULL;
*head_ref = newNode;
return;
}
while (last->next != NULL)
last = last->next;
last->next = newNode;
newNode->prev = last;
}
Correct Answer: Insertion at the end
Explanation: The function `insertAtEnd` inserts a new node with the given value at the end of a doubly linked list.
struct Node {
int data;
struct Node *next;
};
struct Node *createCircularLinkedList(int arr[], int n) {
if (n == 0) return NULL;
struct Node *head = (struct Node *)malloc(sizeof(struct Node));
head->data = arr[0];
head->next = head;
struct Node *current = head;
for (int i = 1; i < n; ++i) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = arr[i];
newNode->next = head;
current->next = newNode;
current = newNode;
}
return head;
}
Correct Answer: Circular linked list
Explanation: The function `createCircularLinkedList` creates a circular linked list where the last node points back to the head node.
void traverseAndPrint(struct Node *head) {
struct Node *temp = head;
if (head != NULL) {
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("Head");
}
}
Correct Answer: Traversal and printing of a circular linked list
Explanation: The function `traverseAndPrint` traverses and prints the elements of a circular linked list starting from the head node.
void deleteHeadNode(struct Node **head_ref) {
if (*head_ref == NULL) return;
struct Node *temp = *head_ref;
struct Node *current = *head_ref;
while (current->next != *head_ref)
current = current->next;
if (current == *head_ref) {
*head_ref = NULL;
} else {
current->next = temp->next;
*head_ref = temp->next;
}
free(temp);
}
Correct Answer: Deletion of the head node
Explanation: The function `deleteHeadNode` deletes the head node of a circular linked list and adjusts pointers accordingly.
struct Node *reverseLinkedList(struct Node *head) {
struct Node *prev = NULL;
struct Node *current = head;
struct Node *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
Correct Answer: Reversing a singly linked list
Explanation: The function `reverseLinkedList` reverses the given singly linked list by changing the direction of pointers.
void deleteLastNode(struct Node **head_ref) {
if (*head_ref == NULL) return;
struct Node *temp = *head_ref;
while (temp->next != NULL)
temp = temp->next;
if (temp->prev != NULL)
temp->prev->next = NULL;
else
*head_ref = NULL;
free(temp);
}
Correct Answer: Deletion at the end
Explanation: The function `deleteLastNode` deletes the last node of a doubly linked list by adjusting pointers and freeing memory.
int hasCycle(struct Node *head) {
struct Node *slow = head;
struct Node *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return 1; // Cycle detected
}
return 0; // No cycle found
}
Correct Answer: Whether it contains a cycle
Explanation: The function `hasCycle` determines whether the given singly linked list contains a cycle by using a slow and fast pointer approach.
Correct Answer: Last-In-First-Out (LIFO) access
Explanation: A stack data structure follows the Last-In-First-Out (LIFO) principle, where the last element added is the first one to be removed.
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
void push(int value) {
if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}
Correct Answer: Push operation
Explanation: The function `push` pushes (inserts) an element onto the top of the stack implemented using an array.
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
Correct Answer: Pop operation
Explanation: The function `pop` removes and returns the element from the top of the stack implemented using an array.
int isEmpty() {
return (top < 0);
}
Correct Answer: Whether it is empty
Explanation: The function `isEmpty` checks if the stack implemented using an array is empty by evaluating the top index.
int peek() {
if (top < 0) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}
Correct Answer: Peek operation
Explanation: The function `peek` returns the element from the top of the stack implemented using an array without removing it.
Correct Answer: Array
Explanation: Arrays are commonly used to implement stacks due to their simplicity and efficient access time for push and pop operations.
struct Node {
int data;
struct Node *next;
};
Correct Answer: No modification needed
Explanation: The given struct definition is already suitable for nodes in a linked list to implement a stack using a singly linked list.
struct Node {
int data;
struct Node *next;
};
struct Node *top = NULL;
void push(int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = top;
top = newNode;
}
Correct Answer: Push operation
Explanation: The function `push` inserts a new node with the given value onto the top of the stack implemented using a linked list.
Correct Answer: O(1)
Explanation: The pop operation in a stack implemented using a singly linked list has a time complexity of O(1) because it only involves adjusting pointers.
int isEmpty() {
return (top == NULL);
}
Correct Answer: Whether it is empty
Explanation: The function `isEmpty` checks if the stack implemented using a linked list is empty by evaluating the `top` pointer.
int peek() {
if (top == NULL) {
printf("Stack is empty\n");
return -1;
}
return top->data;
}
Correct Answer: Peek operation
Explanation: The function `peek` returns the data value of the top node in a stack implemented using a linked list without removing it.
int pop() {
if (top == NULL) {
printf("Stack Underflow\n");
return -1;
}
struct Node *temp = top;
int data = temp->data;
top = top->next;
free(temp);
return data;
}
Correct Answer: Pop operation
Explanation: The function `pop` removes and returns the top element from a stack implemented using a linked list.
Correct Answer: Deque
Explanation: A deque (double-ended queue) is suitable for implementing a stack that requires efficient insertion and deletion at both ends.
#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;
void push(int value) {
if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
int peek() {
if (top < 0) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}
int isEmpty() {
return (top < 0);
}
Correct Answer: Implementation of a stack using an array
Explanation: The function snippet demonstrates the implementation of a stack data structure using an array in C.
Correct Answer: Push operation
Explanation: Push operation in a stack implemented using an array is more efficient (O(1)) compared to a stack implemented using a linked list (O(1)) due to direct access.
Correct Answer: Limited size
Explanation: Arrays used to implement stacks have a fixed size, leading to potential overflow if the stack size exceeds the predefined maximum size.
Correct Answer: Dynamic size
Explanation: Linked lists used to implement stacks allow dynamic memory allocation, enabling the stack to grow or shrink as needed.
int isFull() {
return (top >= MAX_SIZE - 1);
}
Correct Answer: Whether it is full
Explanation: The function `isFull` checks if the stack implemented using an array has reached its maximum capacity.
#define MAX_SIZE 50
int stack[MAX_SIZE];
int top = -1;
void push(int value) {
if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = value;
}
Correct Answer: Push operation
Explanation: The function `push` inserts an element onto the top of the stack implemented using an array with a fixed size.
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
Correct Answer: Pop operation
Explanation: The function `pop` removes and returns the top element from a stack implemented using an array.
Correct Answer: First-In-First-Out (FIFO) access
Explanation: A queue data structure follows the First-In-First-Out (FIFO) principle, where the first element added is the first one to be removed.
#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if (rear >= MAX_SIZE - 1) {
printf("Queue Overflow\n");
return;
}
if (front == -1)
front = 0;
queue[++rear] = value;
}
Correct Answer: Enqueue operation
Explanation: The function `enqueue` inserts an element into the rear of the queue implemented using an array.
int dequeue() {
if (front == -1 || front > rear) {
printf("Queue Underflow\n");
return -1;
}
return queue[front++];
}
Correct Answer: Dequeue operation
Explanation: The function `dequeue` removes and returns the front element from the queue implemented using an array.
Correct Answer: Deque
Explanation: A deque (double-ended queue) is suitable for implementing a queue that requires efficient insertion and deletion at both ends.
int isEmpty() {
return (front == -1 || front > rear);
}
Correct Answer: Whether it is empty
Explanation: The function `isEmpty` checks if the queue implemented using an array is empty by evaluating the `front` and `rear` indices.
Correct Answer: Enqueue operation
Explanation: Enqueue operation in a queue implemented using an array is more efficient (O(1)) compared to a queue implemented using a linked list (O(1)) due to direct access.
Correct Answer: Limited size
Explanation: Arrays used to implement queues have a fixed size, leading to potential overflow if the queue size exceeds the predefined maximum size.
Correct Answer: Dynamic size
Explanation: Linked lists used to implement queues allow dynamic memory allocation, enabling the queue to grow or shrink as needed.
struct Node {
int data;
struct Node *next;
};
struct Node *front = NULL;
struct Node *rear = NULL;
void enqueue(int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (rear == NULL) {
front = newNode;
} else {
rear->next = newNode;
}
rear = newNode;
}
Correct Answer: Implementation of a queue using a linked list
Explanation: The function snippet demonstrates the implementation of a queue data structure using a singly linked list in C.
int dequeue() {
if (front == NULL) {
printf("Queue Underflow\n");
return -1;
}
struct Node *temp = front;
int data = temp->data;
front = front->next;
if (front == NULL)
rear = NULL;
free(temp);
return data;
}
Correct Answer: Dequeue operation
Explanation: The function `dequeue` removes and returns the front element from a queue implemented using a linked list.
int peek() {
if (front == NULL) {
printf("Queue is empty\n");
return -1;
}
return front->data;
}
Correct Answer: Peek operation
Explanation: The function `peek` returns the data value of the front node in a queue implemented using a linked list without removing it.
int isEmpty() {
return (front == NULL);
}
Correct Answer: Whether it is empty
Explanation: The function `isEmpty` checks if the queue implemented using a linked list is empty by evaluating the `front` pointer.
Correct Answer: Deque
Explanation: A deque (double-ended queue) is suitable for implementing a queue that requires efficient insertion at one end (rear) and deletion at the other end (front).
int isFull() {
return 0; // Linked list-based queues do not have a fixed size limit
}
Correct Answer: Whether it is full
Explanation: This function always returns 0 because queues implemented using linked lists do not have a fixed size limit like arrays.
Correct Answer: Enqueue operation
Explanation: Enqueue operation in a queue implemented using a linked list is more efficient (O(1)) compared to a queue implemented using an array (O(1)) due to direct pointer manipulation.
Correct Answer: Inefficient insertion
Explanation: Insertion in a queue implemented using a linked list requires traversal to the rear end, which can be inefficient compared to arrays for large queues.
Correct Answer: Faster access time
Explanation: Access time (enqueue and dequeue operations) in a queue implemented using an array is typically faster than in a linked list due to direct indexing.
#define MAX_SIZE 50
int queue[MAX_SIZE];
int front = -1, rear = -1;
void enqueue(int value) {
if ((rear + 1) % MAX_SIZE == front) {
printf("Queue Overflow\n");
return;
}
if (front == -1)
front = 0;
rear = (rear + 1) % MAX_SIZE;
queue[rear] = value;
}
int dequeue() {
if (front == -1) {
printf("Queue Underflow\n");
return -1;
}
int data = queue[front];
if (front == rear)
front = rear = -1;
else
front = (front + 1) % MAX_SIZE;
return data;
}
Correct Answer: Implementation of a circular queue using an array
Explanation: The function snippet demonstrates the implementation of a circular queue data structure using an array in C.
int peek() {
if (front == -1) {
printf("Queue is empty\n");
return -1;
}
return queue[front];
}
Correct Answer: Peek operation
Explanation: The function `peek` returns the data value of the front element in a circular queue implemented using an array without removing it.
int isEmpty() {
return (front == -1);
}
Correct Answer: Whether it is empty
Explanation: The function `isEmpty` checks if the circular queue implemented using an array is empty by evaluating the `front` index.
Correct Answer: Two children per node
Explanation: A binary tree is a hierarchical data structure where each node has at most two children.
Correct Answer: Inorder traversal
Explanation: Inorder traversal visits the left subtree, then the root node, and finally the right subtree in a binary tree.
struct Node {
int data;
struct Node *left;
struct Node *right;
};
Correct Answer: Definition of a binary tree node
Explanation: This C struct defines a node structure for a binary tree, where each node contains integer data and pointers to left and right child nodes.
struct Node *createNode(int value) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
Correct Answer: Initialization operation
Explanation: The function `createNode` initializes and returns a new node with the given integer value for a binary tree.
Correct Answer: Preorder traversal
Explanation: Preorder traversal visits the root node first, then the left subtree, and finally the right subtree in a binary tree.
struct Node *insert(struct Node *root, int value) {
if (root == NULL)
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
}
Correct Answer: Insertion operation
Explanation: The function `insert` recursively inserts a value into a binary search tree (BST) maintaining its properties.
Correct Answer: Postorder traversal
Explanation: Postorder traversal visits the left subtree, then the right subtree, and finally the root node in a binary tree.
Correct Answer: Efficient insertion and deletion
Explanation: BSTs provide efficient O(log n) time complexity for insertion, deletion, and search operations, making them advantageous over arrays and linked lists for sorted data.
struct Node *search(struct Node *root, int key) {
if (root == NULL || root->data == key)
return root;
if (key < root->data)
return search(root->left, key);
return search(root->right, key);
}
Correct Answer: Search operation
Explanation: The function `search` recursively searches for a key value in a binary search tree (BST) and returns the node if found, or NULL if not found.
Correct Answer: Level order traversal
Explanation: Level order traversal visits nodes level by level from left to right in a binary tree, starting from the root.
Correct Answer: Postorder traversal
Explanation: Postorder traversal of a binary expression tree visits the left subtree, right subtree, and then the root, which is suitable for generating a postfix expression.
struct Node *minValueNode(struct Node *node) {
struct Node *current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}
Correct Answer: Minimum value search
Explanation: The function `minValueNode` finds and returns the node with the minimum value in a binary search tree (BST).
Correct Answer: Search
Explanation: Search operation in a binary search tree (BST) has an average time complexity of O(log n), whereas in a binary tree, it can range up to O(n) depending on the tree structure.
struct Node *deleteNode(struct Node *root, int key) {
if (root == NULL) return root;
if (key < root->data)
root->left = deleteNode(root->left, key);
else if (key > root->data)
root->right = deleteNode(root->right, key);
else {
if (root->left == NULL) {
struct Node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node *temp = root->left;
free(root);
return temp;
}
struct Node *temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
Correct Answer: Deletion operation
Explanation: The function `deleteNode` recursively deletes a node with the given key from a binary search tree (BST) while maintaining its properties.
Correct Answer: Inorder traversal
Explanation: Inorder traversal of a binary search tree (BST) produces a sorted list of elements in ascending order.
Correct Answer: Insertion
Explanation: Insertion in an unbalanced binary search tree (BST) can lead to worst-case time complexity of O(n), whereas balanced BSTs maintain O(log n) complexity for all operations.
int countNodes(struct Node *root) {
if (root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
Correct Answer: Counting operation
Explanation: The function `countNodes` recursively counts and returns the number of nodes in a binary tree.
Correct Answer: Reverse inorder traversal
Explanation: Reverse inorder traversal visits the root node first, then the right subtree, and finally the left subtree in a binary tree.
Correct Answer: BST property
Explanation: The BST property ensures the ordering of nodes in a binary search tree, facilitating efficient search, insertion, and deletion operations.
int treeHeight(struct Node *root) {
if (root == NULL)
return 0;
int leftHeight = treeHeight(root->left);
int rightHeight = treeHeight(root->right);
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
Correct Answer: Height calculation operation
Explanation: The function `treeHeight` recursively calculates and returns the height of a binary tree, which is the number of edges on the longest path from the root to a leaf node.
Correct Answer: Array
Explanation: Arrays are commonly used to represent graphs using adjacency matrices or adjacency lists in computer memory.
Correct Answer: Cycle
Explanation: A cycle in a graph is a path that starts and ends at the same vertex, traversing through other vertices and edges without repetition.
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
void initGraph() {
int i, j;
for (i = 0; i < MAX_VERTICES; i++) {
for (j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = 0;
}
}
}
Correct Answer: Initializes an adjacency matrix for a graph
Explanation: The function `initGraph` initializes an adjacency matrix for a graph by setting all elements to 0, indicating no edges initially.
Correct Answer: Adjacency list
Explanation: Adjacency lists are more space-efficient for sparse graphs because they only store connections (edges) explicitly.
void addEdge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1; // Assuming undirected graph
}
Correct Answer: Insertion operation
Explanation: The function `addEdge` inserts an undirected edge between vertices `u` and `v` in an adjacency matrix representation of a graph.
Correct Answer: Adding a vertex
Explanation: Adding a vertex in an adjacency list representation is more efficient (O(1)) compared to an adjacency matrix (O(V^2)), especially for sparse graphs.
Correct Answer: Array of linked lists
Explanation: An adjacency list in C is typically implemented using an array of linked lists where each array element represents a vertex and the linked list contains its adjacent vertices.
void printGraph(int vertices) {
int i;
for (i = 0; i < vertices; i++) {
struct Node *temp = graph[i];
printf("Adjacency list of vertex %d\n", i);
while (temp) {
printf(" -> %d", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
Correct Answer: Prints an adjacency list representation of a graph
Explanation: The function `printGraph` prints the adjacency list representation of a graph, showing each vertex and its adjacent vertices.
Correct Answer: Adjacency matrix
Explanation: Adjacency matrices are more suitable for dense graphs with many edges because they directly represent all possible edges between vertices.
Correct Answer: Depth-first search (DFS)
Explanation: DFS is commonly used for traversing or searching in graphs, exploring as far as possible along each branch before backtracking, making it useful for finding connected components.