Recent questions tagged data-structures

Rebalance the following tree so that it becomes a valid AVL tree:What will be the root after rebalancing?$10$ $12$ $16$ $20$

For the keys:$47, 61, 36, 52, 56, 33, 92$consider the hash function:$h(k) = ((10k + 4) \bmod c) \bmod 7$Find the smallest positive integer $c$ such that no collisions occ...

Suppose vector $A$ is a min-heap:$A = [2, 4, 3, 6, 7, 3, 5, 8, 9]$After calling $\texttt{Push(1)}$, what is the final heap array?$[1, 2, 3, 6, 4, 3, 5, 8, 9, 7]$ $[1, 4, ...

A binary tree has:$1000$ nodes in the left subtree $100$ nodes in the right subtreeHow many nodes are processed before the root in preorder, inorder, and postorder traver...

Which of the following statements are true?$\text{S1}$. The worst-case complexity of checking whether an object is present in a hash set is $O(1)$.$\text{S2}$. The worst-...

Given a stack $S$ with $5$ elements from top to bottom as:$2, 4, 6, 8, 10$and an empty queue $Q$.First, remove the elements one by one from $S$ and insert them into $Q$.T...

Insert the following keys into an initially empty AVL tree:$1, 2, 3, 4, 5, 6$What is the root of the final AVL tree?

Insert the keys$47, 61, 36, 52, 56, 33, 92$in order into a hash table of size $7$ using:$h(k) = (10k + 4) \bmod 7$Each slot stores a linked list, and later insertions are...

Suppose numbers between $1$ and $1000$ are stored in a binary search tree. We search for the key $363$.Which of the following sequences could not be the sequence of nodes...

Which of the following statements are true?$\text{S1.}$ Stack operations $\texttt{push}$, $\texttt{pop}$, and $\texttt{isEmpty}$ can be worst-case $O(1)$ for a linked-lis...

Given the following AVL tree, delete node $\text{A}$.How many rotations are required to rebalance the AVL tree after deleting node $A$?(Count each rotation only once, whe...

Consider the following AVL tree:What is the minimum number of keys that must be deleted before a double rotation occurs?

Insertion of a new element into an AVL tree may violate the AVL balance condition. Usually, we perform a rotation at the first node on the path from the inserted element ...

Consider the following AVL tree:First insert $10$ into the AVL tree. Then delete $28$ from the resulting AVL tree.What is the root of the AVL tree after both operations?$...

Given the following AVL tree, delete the key $1$ and rebalance the tree. What will be the root of the final AVL tree after deletion and rebalancing?$7$ $10$ $15$ $3$

For the following three trees, choose the correct classification.Tree (a):Tree (b):Tree (c):Which option is correct?All three are valid AVL trees. Tree (a) is not a valid...

What is the time complexity for efficiently finding an arbitrary item in an arbitrary AVL tree of $n$ nodes?$\Theta(n)$ $\Theta(\log_2 n)$ $\Theta(n \log_2 n)$ $\Theta(n^...

Which statement is true for AVL trees?Adding a node may cause the tree to increase in height. Adding a node will cause the tree to increase in height. Adding a node may c...

We have just inserted $51$ into the following AVL tree. Rebalance the tree.What is the root of the AVL tree after rebalancing?$35$ $42$ $47$ $57$

Which of the following trees are valid AVL trees? 

Heaps are usually implemented using arrays.If an element is present at a known array index in a heap of size $N$, what is the time complexity to remove that element and r...

Given a binary min-heap storing $n$ comparable keys, can we always build a Set AVL Tree containing the same keys using only $O(n)$ comparisons?True False

Consider the following min-heap where each node is written as $\texttt{(value, priority)}$:Now perform these operations in order:$\texttt{updatePriority(A, 8)}$ $\texttt{...

Start with the min-heap obtained after inserting:$$10, 12, 1, 14, 6, 5, 8, 15, 3, 9$$The heap array is:$$[1, 3, 5, 6, 9, 10, 8, 15, 14, 12]$$Now perform three $\texttt{De...

Insert the following values one by one into an initially empty minimum binary heap:$$10, 12, 1, 14, 6, 5, 8, 15, 3, 9$$What is the final heap array in level-order?$[1, 3,...

During heap sort, the array looks like this:$J = [7, 3, 6, 2, 1, 4, 5, 8, 9]$Assume heap sort is using a max-heap to sort the array in increasing order.How many elements ...

A max-heap is stored using $0$-based indexing as:$$[60, 30, 45, 15, 5, 10, 20]$$During the first iteration of heap sort:Swap the root with the last element. Reduce the he...

A min-heap is stored using $1$-based indexing as:$[2, 13, 7, 17, 14, 22, 8, 21]$After one $\texttt{DeleteMin}$ operation, what is the final heap array?$[7, 13, 8, 17, 14,...

The following max-heap is stored using $1$-based indexing:$[57, 53, 42, 48, 25, 34, 29, 18, 30, 25]$Insert $55$ into this max-heap. What is the final heap array?$[57, 55,...

Consider the following binary min-heap:Perform the following operations in order:$\text{DeleteMin}$ $\text{Insert 8}$ $\text{Insert 2}$ What is the final array representa...