Correct Answer: \( \frac{V(V-1)}{2} \)
Explanation: A complete graph with \( V \) vertices has every pair of distinct vertices connected by an edge, resulting in \( \frac{V(V-1)}{2} \) edges.
int hasEdge(int u, int v) {
return graph[u][v];
}
Correct Answer: Search operation
Explanation: The function `hasEdge` checks if there is an edge between vertices `u` and `v` in an adjacency matrix representation of a graph.
Correct Answer: Breadth-first search (BFS)
Explanation: BFS is commonly used to find the shortest path in an unweighted graph because it explores all neighbors at the present depth level before moving on to nodes at the next depth level.
void removeEdge(int u, int v) {
graph[u][v] = 0;
graph[v][u] = 0; // Assuming undirected graph
}
Correct Answer: Deletion operation
Explanation: The function `removeEdge` deletes the edge between vertices `u` and `v` in an adjacency matrix representation of a graph.
Correct Answer: Array
Explanation: Queues in C are commonly implemented using arrays, where elements are added at one end (rear) and removed from the other end (front).
#define MAX_VERTICES 100
struct Node {
int vertex;
struct Node *next;
};
struct Node *adjList[MAX_VERTICES];
void initGraph(int vertices) {
int i;
for (i = 0; i < vertices; i++) {
adjList[i] = NULL;
}
}
Correct Answer: Initializes an adjacency list for a graph
Explanation: The function `initGraph` initializes an adjacency list for a graph with `vertices` number of nodes, setting all adjacency list heads to NULL initially.
Correct Answer: Depth-first search (DFS)
Explanation: DFS is commonly used to detect cycles in a graph by keeping track of visited vertices and checking for back edges during traversal.
void addVertex(int vertex) {
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->vertex = vertex;
newNode->next = NULL;
adjList[vertex] = newNode;
}
Correct Answer: Vertex addition operation
Explanation: The function `addVertex` adds a vertex to an adjacency list representation of a graph, initializing it with a new node.
Correct Answer: Depth-first search (DFS)
Explanation: DFS is commonly used for topological sorting of a DAG because it processes vertices in a linear order that respects the partial order imposed by the edges of the graph.
Correct Answer: Connected property
Explanation: A connected graph is one in which there is a path between any two vertices, ensuring connectivity throughout the graph.
struct Node {
int data;
struct Node *next;
};
struct Node *reverseList(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 operation
Explanation: The function `reverseList` reverses a singly linked list by changing the direction of pointers, starting from the head of the list.
struct Node *mergeLists(struct Node *list1, struct Node *list2) {
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
struct Node *mergedList = NULL;
if (list1->data <= list2->data) {
mergedList = list1;
mergedList->next = mergeLists(list1->next, list2);
} else {
mergedList = list2;
mergedList->next = mergeLists(list1, list2->next);
}
return mergedList;
}
Correct Answer: Merging operation
Explanation: The function `mergeLists` merges two sorted linked lists into one sorted linked list by comparing elements and rearranging pointers.
#include <stdbool.h>
struct Node {
int data;
struct Node *next;
};
bool 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 true;
}
return false;
}
Correct Answer: Checking operation
Explanation: The function `hasCycle` checks if a singly linked list has a cycle using the slow and fast pointer technique to detect a loop.
struct Node {
int data;
struct Node *next;
};
int length(struct Node *head) {
int len = 0;
while (head != NULL) {
len++;
head = head->next;
}
return len;
}
struct Node *intersectionPoint(struct Node *list1, struct Node *list2) {
int len1 = length(list1);
int len2 = length(list2);
int diff = abs(len1 - len2);
if (len1 > len2) {
while (diff--)
list1 = list1->next;
} else {
while (diff--)
list2 = list2->next;
}
while (list1 != NULL && list2 != NULL) {
if (list1 == list2)
return list1;
list1 = list1->next;
list2 = list2->next;
}
return NULL;
}
Correct Answer: Searching operation
Explanation: The function `intersectionPoint` finds the intersection point of two singly linked lists by adjusting pointers based on their lengths and iterating until they meet.
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
void deleteNode(struct Node **headRef, struct Node *delNode) {
if (*headRef == NULL || delNode == NULL)
return;
if (*headRef == delNode)
*headRef = delNode->next;
if (delNode->next != NULL)
delNode->next->prev = delNode->prev;
if (delNode->prev != NULL)
delNode->prev->next = delNode->next;
free(delNode);
}
Correct Answer: Deletion operation
Explanation: The function `deleteNode` deletes a specified node from a doubly linked list by adjusting pointers and freeing memory allocated to the node.
struct Node {
int data;
struct Node *next;
};
struct Node *findMiddleNode(struct Node *head) {
struct Node *slow = head;
struct Node *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
Correct Answer: Searching operation
Explanation: The function `findMiddleNode` finds the middle node of a singly linked list using the slow and fast pointer technique, which is useful for various operations like midpoint insertion or partitioning.
#include <stdbool.h>
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
bool isBSTUtil(struct TreeNode *root, int min, int max) {
if (root == NULL)
return true;
if (root->data < min || root->data > max)
return false;
return isBSTUtil(root->left, min, root->data - 1) &&
isBSTUtil(root->right, root->data + 1, max);
}
bool isBinarySearchTree(struct TreeNode *root) {
return isBSTUtil(root, INT_MIN, INT_MAX);
}
Correct Answer: Checking operation
Explanation: The function `isBinarySearchTree` checks if a binary tree is a binary search tree (BST) by validating the BST properties recursively with a helper function `isBSTUtil`.
#include <stdio.h>
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
void inOrderTraversal(struct TreeNode *root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
Correct Answer: Traversal operation
Explanation: The function `inOrderTraversal` performs an in-order traversal of a binary tree, printing node values in ascending order when the tree nodes are visited.
#include <stdbool.h>
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
int getHeight(struct TreeNode *root) {
if (root == NULL)
return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return 1 + ((leftHeight > rightHeight) ? leftHeight : rightHeight);
}
bool isBalanced(struct TreeNode *root) {
if (root == NULL)
return true;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs(leftHeight - rightHeight) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return true;
return false;
}
Correct Answer: Checking operation
Explanation: The function `isBalanced` checks if a binary tree is balanced by calculating the height of left and right subtrees and ensuring the height difference is within one level.
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode *lowestCommonAncestor(struct TreeNode *root, struct TreeNode *p, struct TreeNode *q) {
if (root == NULL || root == p || root == q)
return root;
if (root->data > p->data && root->data > q->data)
return lowestCommonAncestor(root->left, p, q);
if (root->data < p->data && root->data < q->data)
return lowestCommonAncestor(root->right, p, q);
return root;
}
Correct Answer: Searching operation
Explanation: The function `lowestCommonAncestor` finds the lowest common ancestor (LCA) of two nodes `p` and `q` in a binary search tree (BST) by traversing based on BST properties.