Recent questions tagged data-structures

The UNIX editor $\texttt{vi}$ allows searching in both directions, and if the search reaches one end, it wraps around and continues from the other end.If the sequence of ...

A circular linked list has $n$ nodes. A function prints every node exactly once and stops when it reaches the starting node again.What is the running time of printing the...

A singly linked list contains $n$ nodes. We want to reverse the order of the elements in the linked list by changing links, not by copying all elements into an array.Whic...

The following function is supposed to reverse a singly linked list:struct node { int data; struct node *next; }; static void reverse(struct node head_ref) { struct node ...

Consider the following C-style code fragment for reversing a non-empty singly linked list:curr = front; next = curr->next; prev = NULL; while (curr != NULL) { (*) } front...

Consider the following singly linked list:$\texttt{'B' - 'A' - 'S' - 'E' - NULL}$The pointer $\texttt{head}$ points to the first node containing $\texttt{'B'}$.What chara...

A singly linked list maintains two pointers:struct Node *front; // points to first node struct Node *rear; // points to last nodeWhich operation would be inefficient when...

Consider the problem of finding the middle node in a list $l$ of size $n$, given that $n$ is odd. Count the number of accesses to positions of list $l$ needed to find the...

Consider the following C function intended to delete the last node of a singly linked list:void removeLast(struct Node *head) { struct Node *p = head; struct Node *q = p-...

Consider the following structure:struct Node { int data; struct Node *next; };A function should insert a new node containing value $\texttt{x}$ at the beginning of a sing...

Consider the following singly linked list:$\texttt{12 - 18 - 25 - 31 - 44 - 57 - NULL}$Now, consider the following function:int Size(struct Node *list) { int count = 0; w...

A singly linked list is:$\texttt{5 - 8 - 20 - NULL}$A new node $\texttt{​newP}$ contains data $9$. Pointer $\texttt{​prevP}$ points to the node containing $8$.The inserti...

A singly linked list is:$\texttt{5 - 8 - 20 - 9 - 20 - 7 - NULL}$The function $\texttt{deleteByValue(L, val)}$ removes only the first node whose data is equal to $\texttt...

A sequence of $n$ elements is implemented in two ways:As a normal array with contiguous memory and no extra empty slot. As a singly linked list with only a $\texttt{head}...

For a singly linked list storing only the head pointer, which of the following operations can be done in worst-case $O(1)$ time?Access the $i$-th element Modify the $i$-t...

Which of the data structures supports both insertion of unique elements (no duplicates allowed) and deletion of the minimum element in $\mathrm{O}(\log n)$ time complexit...

How many distinct binary trees can be formed using $3$ unlabelled nodes?

Given the Post-order and In-order traversals of a binary tree:Post-order: $\{8,6,7,3,4,2,5,1\}$ In-order: $\{8,6,3,7,2,4,1,5\}$ Construct the binary tree and find the hei...

Consider a binary max-heap implemented using an array. Which one of the following arrays represents a valid binary max-heap?$\{25,12,16,13,10,8,14\}$ $\{25,14,13,16,10,8,...

The inorder and preorder traversal of binary tree are $\mathrm{d}, \mathrm{b}, \mathrm{e}, \mathrm{a}, \mathrm{f}, \mathrm{c}, \mathrm{g}$ and $\mathrm{a}, \mathrm{b}, \m...

Consider $B^{+}$tree in which the maximum number of keys in a node is $5$. What is the minimum number of keys in any non-root node?$1$$2$$3$$4$

How many number of comparison are required in worst case to find out second smallest element of $n$ elements list?$n+\lceil\log n\rceil-1$$n+\lceil\log n\rceil$$\lceil\lo...

Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason RAssertion A: Depth first search can be used to perform a topological s...

Consider the following function that reverses a singly linked list.Node* reverseList(Node* head) { Node* prev = NULL; Node* current = head; Node* next = NULL;...

Consider the following function:void f(stack S) { int x ; if (!isEmpty(S)) { x = pop(S); f(S); push(S, x); } }What operation is performed by t...

Consider inserting the following sequence of keys into an initially empty AVL tree:$$38,53,42,26,33,60,79,21,20$$During the construction of the AVL tree, rotations are pe...

A queue initially contains the elements (from front to rear):$$1~2~3~4~5~6$$An empty stack is also available. The following operations can be performed:Dequeue an element...

In the balanced binary search tree in the below figure, how many nodes will become unbalanced when a node with value $97$ is inserted?$1$ $2$ $3$ $4$

Consider the following function defined on a binary tree:int func(Node* root) { if (root == NULL) { return 0; } int l = func(root->left); int...