Recent questions tagged data-structures

A program attempts to generate as many permutations as possible of the string, '$abcd$' by pushing the characters $a, b, c, d$ in the same order onto a stack, but it may ...

Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to del...

An array $X$ of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If the root node is at level $0$, the le...

An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. If only the root node does not satisfy...

An array $X$ of $n$ distinct integers is interpreted as a complete binary tree. The index of the first element of the array is $0$. The index of the parent of element $X[...

Suppose that we have numbers between $1$ and $100$ in a binary search tree and want to search for the number $55$. Which of the following sequences CANNOT be the sequence...

Which of the following sequences of array elements forms a heap?$\{23, 17, 14, 6, 13, 10, 1, 12, 7, 5\}$$\{23, 17, 14, 6, 13, 10, 1, 5, 7, 12\}$$\{23, 17, 14, 7, 13, 10, ...

Which of the following statement(s) is TRUE?A hash function takes a message of arbitrary length and generates a fixed length code.A hash function takes a message of fixed...

In a binary tree, the number of internal nodes of degree $1$ is $5$, and the number of internal nodes of degree $2$ is $10$. The number of leaf nodes in the binary tree i...

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:$\text{isEmpty (Q)}$ — returns true if the queue is ...

When searching for the key value $60$ in a binary search tree, nodes containing the key values $10, 20, 40, 50, 70, 80, 90$ are traversed, not necessarily in the order gi...

Consider a hash function that distributes keys uniformly. The hash table size is $20$. After hashing of how many keys will the probability that any new key hashed collide...

A binary tree with $n 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respec­tively. The degree of a node is defined as the number of its neighbou...

A binary tree with $n 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respec­tively. The degree of a node is defined as the number of its neighbou...

How many distinct BSTs can be constructed with $3$ distinct keys?$4$$5$$6$$9$

A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys.$81, 537, 102, 439, 285, 376, 305$$52, 97, 121, 195, 242, 381...

A Binary Search Tree (BST) stores values in the range $37$ to $573$. Consider the following sequence of keys.$81, 537, 102, 439, 285, 376, 305$$52, 97, 121, 195, 242, 381...

Consider a hash table of size $11$ that uses open addressing with linear probing. Let $h(k) = k \mod 11$ be the hash function used. A sequence of records with keys$43 \ 3...

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which.$MBCAFHPYK$$KAMCBYPFH$$MABCKYFPH$Pi...

Which of the following is TRUE?The cost of searching an AVL tree is $\Theta (\log n)$ but that of a binary search tree is $O(n)$The cost of searching an AVL tree is $\The...

Insert the characters of the string $K \ R \ P \ C \ S \ N \ Y \ T \ J \ M$ into a hash table of size $10$.Use the hash function$$h(x)=( ord (x) – ord (\text{“}a\text{”}...

A binary search tree is used to locate the number $43$. Which of the following probe sequences are possible and which are not? Explain.$\begin{array}{llllll} \text{(a)} ...

A binary search tree is generated by inserting in order the following integers:$$50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24$$The number of nodes in the left subtree and ...

The minimum number of interchanges needed to convert the array into a max-heap is$89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70$$0$$1$$2$$3$

Which of the following sequences denotes the post order traversal sequence of the below tree?$f\; e\; g\; c\; d\; b\; a$$g\; c\; b\; d\; a\; f\; e$$g\; c\; d\; b\; f\; e\...

In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?$1$$3$$7$$8$

An advantage of chained hash table (external hashing) over the open addressing scheme isWorst case complexity of search operations is lessSpace used is lessDeletion is ea...

Consider the following statements:First-in-first out types of computations are efficiently supported by STACKS.Implementing LISTS on linked lists is more efficient than i...

What is the number of binary trees with $3$ nodes which when traversed in post-order give the sequence $A, B, C ?$ Draw all these binary trees.