Data Structures: GATE CS previous year questions, 2011 to 2026

Topics

All Data Structures questions

GATE CS 2026 Set 1MSQ1 markEasy (estimate)
GATE CS 2026 Set 1, Q.23
Let $n$ be an odd number greater than $100$ . Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from $1$ . Which of the following indices of…
Binary Heaps and Priority Queues
GATE CS 2026 Set 1MSQ1 markEasy (estimate)
GATE CS 2026 Set 1, Q.24
Consider a hash table $P [0, 1, \dots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is…
Hash Tables and Collision Resolution
GATE CS 2026 Set 1NAT1 markEasy (estimate)
GATE CS 2026 Set 1, Q.33
The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 1MCQ2 marksEasy (estimate)
GATE CS 2026 Set 1, Q.39
Consider the following code snippet in C language that computes the number of nodes in a non-empty singly linked list pointed to by the pointer variable head. struct node{ int...
Arrays and Linked Lists
GATE CS 2026 Set 1MCQ2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.40
Let $P$ be the set of all integers from $1$ to $15$ . Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 1NAT2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.62
The following sequence corresponds to the preorder traversal of a binary search tree $T$ : $50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77$ The position of the element $60$ in the...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 2MCQ1 markEasy (estimate)
GATE CS 2026 Set 2, Q.12
The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal. T S I: Inorder L: left subtree, node, right subtre...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 2NAT1 markEasy (estimate)
GATE CS 2026 Set 2, Q.30
The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the hash function $h (k) = k mod 9$ . The collisions are resolved by chaining. After all the keys...
Hash Tables and Collision Resolution
GATE CS 2026 Set 2MSQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.49
Consider a binary search tree (BST) with $n$ leaf nodes ( $n > 0$ ). Given any node $V$ , the key present in the node is denoted as $V a l (V)$ . All the keys present in the given BST...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2026 Set 2MSQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.50
Consider a stack $S$ and a queue $Q$ . Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in tha...
Stacks and Queues
GATE CS 2025 Set 1MSQ1 markEasy (estimate)
GATE CS 2025 Set 1, Q.26
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 1NAT1 markEasy (estimate)
GATE CS 2025 Set 1, Q.35
The height of any rooted tree is defined as the maximum number of edges in the path from the root node to any leaf node. Suppose a Min-Heap $T$ stores 32 keys. The height of $T$ ...
Binary Heaps and Priority Queues
GATE CS 2025 Set 1NAT2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.62
Let LIST be a datatype for an implementation of linked list defined as follows: typedef struct list { int data; struct list *next; } LIST; Suppose a program has created two li...
Arrays and Linked Lists
GATE CS 2025 Set 1NAT2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.65
In a double hashing scheme, $h_{1} (k) = k mod 11$ and $h_{2} (k) = 1 + (k mod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is $11$ . The hash function for...
Hash Tables and Collision Resolution
GATE CS 2025 Set 2MCQ1 markEasy (estimate)
GATE CS 2025 Set 2, Q.13
Consider a binary tree $T$ in which every node has either zero or two children. Let $n > 0$ be the number of nodes in $T$ . Which ONE of the following is the number of nodes in…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 2NAT1 markEasy (estimate)
GATE CS 2025 Set 2, Q.35
Suppose the values $10, - 4, 15, 30, 20, 5, 60, 19$ are inserted in that order into an initially empty binary search tree. Let $T$ be the resulting binary search tree. The number...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 2MCQ2 marksMedium (estimate)
GATE CS 2025 Set 2, Q.38
A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures: P: Unsorted doub...
Arrays and Linked Lists · Binary Heaps and Priority Queues · Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2025 Set 2MSQ2 marksEasy (estimate)
GATE CS 2025 Set 2, Q.45
Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We...
Stacks and Queues
GATE CS 2024 Set 1MCQ2 marksMedium (estimate)
GATE CS 2024 Set 1, Q.41
An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options represents the first three elements in the heapified array?
Binary Heaps and Priority Queues
GATE CS 2024 Set 1MCQ2 marksEasy (estimate)
GATE CS 2024 Set 1, Q.43
Consider a binary min-heap containing 105 distinct elements. Let $k$ be the index (in the underlying array) of the maximum element stored in the heap. The number of possible val...
Binary Heaps and Priority Queues
GATE CS 2024 Set 2MCQ2 marksEasy (estimate)
GATE CS 2024 Set 2, Q.39
You are given a set $V$ of distinct integers. A binary search tree $T$ is created by inserting all elements of $V$ one by one, starting with an empty tree. The tree $T$ follows...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2024 Set 2MSQ2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.48
Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as...
Stacks and Queues
GATE CS 2023MCQ1 markEasy (estimate)
GATE CS 2023, Q.12
Which one of the following sequences when stored in an array at locations $A [1], \dots, A [10]$ forms a max-heap?
Binary Heaps and Priority Queues
GATE CS 2023MCQ1 markEasy (estimate)
GATE CS 2023, Q.13
Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be a function that...
Arrays and Linked Lists
GATE CS 2023MCQ1 markEasy (estimate)
GATE CS 2023, Q.20
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the numbe...
Hash Tables and Collision Resolution
GATE CS 2023MCQ2 marksEasy (estimate)
GATE CS 2023, Q.46
Let $A$ be a priority queue for maintaining a set of elements. Suppose $A$ is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the...
Binary Heaps and Priority Queues
GATE CS 2023MCQ2 marksEasy (estimate)
GATE CS 2023, Q.47
Consider the C function foo and the binary tree shown. Binary tree with root 10, left child 5 (with left child 3 and right child 8), and right child 11 (with right child 13). ty...
Binary Trees, Binary Search Trees and Balanced Trees · Functions, Recursion, Scope and Storage Classes
GATE CS 2023NAT2 marksEasy (estimate)
GATE CS 2023, Q.59
Consider a sequence $a$ of elements $a_{0} = 1, a_{1} = 5, a_{2} = 7, a_{3} = 8, a_{4} = 9$ , and $a_{5} = 2$ . The following operations are performed on a stack $S$ and a queue $Q$ , both of...
Stacks and Queues
GATE CS 2022MCQ1 markEasy (estimate)
GATE CS 2022, Q.15
Consider the problem of reversing a singly linked list. To take an example, given the linked list below, Singly linked list starting at head with nodes a, b, c, d, e followed by...
Arrays and Linked Lists
GATE CS 2022MCQ1 markEasy (estimate)
GATE CS 2022, Q.16
Suppose we are given $n$ keys, $m$ hash table slots, and two simple uniform hash functions $h_{1}$ and $h_{2}$ . Further suppose our hashing scheme uses $h_{1}$ for the odd keys and…
Hash Tables and Collision Resolution
GATE CS 2022NAT1 markHard (estimate)
GATE CS 2022, Q.28
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that th...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2022NAT2 marksHard (estimate)
GATE CS 2022, Q.62
Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,...
Stacks and Queues
GATE CS 2021 Set 1MCQ1 markMedium (estimate)
GATE CS 2021 Set 1, Q.20 (CS Q.10)
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$ ?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2021 Set 1NAT1 markEasy (estimate)
GATE CS 2021 Set 1, Q.31 (CS Q.21)
Consider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s = pop(); Consider the following sequence of operations on an...
Stacks and Queues
GATE CS 2021 Set 2MCQ1 markEasy (estimate)
GATE CS 2021 Set 2, Q.12 (CS Q.2)
Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$ ?
Binary Heaps and Priority Queues
GATE CS 2021 Set 2NAT1 markEasy (estimate)
GATE CS 2021 Set 2, Q.26 (CS Q.16)
Consider a complete binary tree with 7 nodes. Let $A$ denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let $B$ denote...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2020MCQ1 markEasy (estimate)
GATE CS 2020, Q.15 (CS Q.5)
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2020MCQ1 markMedium (estimate)
GATE CS 2020, Q.16 (CS Q.6)
What is the worst case time complexity of inserting $n^{2}$ elements into an AVL-tree with $n$ elements initially?
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
GATE CS 2020MCQ1 markEasy (estimate)
GATE CS 2020, Q.26 (CS Q.16)
What is the worst case time complexity of inserting $n$ elements into an empty linked list, if the linked list needs to be maintained in sorted order?
Arrays and Linked Lists · Asymptotic Analysis and Time/Space Complexity
GATE CS 2020NAT1 markEasy (estimate)
GATE CS 2020, Q.33 (CS Q.23)
Consider a double hashing scheme in which the primary hash function is $h_{1} (k) = k mod 23$ , and the secondary hash function is $h_{2} (k) = 1 + (k mod 19)$ . Assume that the tab...
Hash Tables and Collision Resolution
GATE CS 2020MCQ2 marksEasy (estimate)
GATE CS 2020, Q.51 (CS Q.41)
In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a, b]$ ? Assume that the number of reported elemen...
Binary Trees, Binary Search Trees and Balanced Trees · Asymptotic Analysis and Time/Space Complexity
GATE CS 2020NAT2 marksMedium (estimate)
GATE CS 2020, Q.57 (CS Q.47)
Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is _______.
Binary Heaps and Priority Queues
GATE CS 2019MCQ2 marksMedium (estimate)
GATE CS 2019, Q.50 (CS Q.40)
Consider the following statements: I. The smallest element in a max-heap is always at a leaf node II. The second largest element in a max-heap is always a child of the root node...
Binary Heaps and Priority Queues
GATE CS 2019NAT2 marksMedium (estimate)
GATE CS 2019, Q.56 (CS Q.46)
Let $T$ be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. T...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2018MCQ1 markEasy (estimate)
GATE CS 2018, Q.13 (CS Q.3)
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the...
Stacks and Queues
GATE CS 2018NAT1 markEasy (estimate)
GATE CS 2018, Q.30 (CS Q.20)
The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest pat...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2018NAT2 marksMedium (estimate)
GATE CS 2018, Q.56 (CS Q.46)
The number of possible min-heaps containing each value from ${1, 2, 3, 4, 5, 6, 7}$ exactly once is _____.
Binary Heaps and Priority Queues
GATE CS 2017 Set 1MCQ1 markEasy (estimate)
GATE CS 2017 Set 1, Q.6 (CS Q.6)
Let $T$ be a binary search tree with 15 nodes. The minimum and maximum possible heights of $T$ are: Note: The height of a tree with a single node is 0.
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2017 Set 2MCQ1 markEasy (estimate)
GATE CS 2017 Set 2, Q.13 (CS Q.13)
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two exte...
Stacks and Queues · Arrays and Linked Lists
GATE CS 2017 Set 2MCQ2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.36 (CS Q.36)
The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2016 Set 1MCQ1 markEasy (estimate)
GATE CS 2016 Set 1, Q.20 (CS Q.10)
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ( $n$ refers to the num...
Stacks and Queues
GATE CS 2016 Set 1MCQ2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.47 (CS Q.37)
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the $i$ -th node. Assume that the heap is implemented in an array and $i$ refers...
Binary Heaps and Priority Queues
GATE CS 2016 Set 1NAT2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.51 (CS Q.41)
Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head (Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$ . Simi...
Stacks and Queues
GATE CS 2016 Set 2MCQ1 markMedium (estimate)
GATE CS 2016 Set 2, Q.25 (CS Q.15)
$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provid...
Arrays and Linked Lists
GATE CS 2016 Set 2NAT2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.44 (CS Q.34)
A complete binary min-heap is made by including each integer in $[1, 1023]$ exactly once. The depth of a node in the heap is the length of the path from the root of the heap to...
Binary Heaps and Priority Queues
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.46 (CS Q.36)
Consider the following New-order strategy for traversing a binary tree: - Visit the root; - Visit the right subtree using New-order; - Visit the left subtree using New-order; Th...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2016 Set 2NAT2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.50 (CS Q.40)
The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is ________. Note: The hei...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.51 (CS Q.41)
In an adjacency list representation of an undirected simple graph $G = (V, E)$ , each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$ , and $[u]$ ...
Graph Representations and Disjoint Sets · Asymptotic Analysis and Time/Space Complexity
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.20 (CS Q.10)
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. $3, 5, 7, 8, 15, 19, 25$ II. $5, 8, 9, 12, 10, 15, 25$ III.…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.33 (CS Q.23)
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 1MCQ1 markEasy (estimate)
GATE CS 2015 Set 1, Q.35 (CS Q.25)
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height $5$ are:
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 1MCQ2 marksEasy (estimate)
GATE CS 2015 Set 1, Q.42 (CS Q.32)
Consider a max heap, represented by the array: | Array Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---...
Binary Heaps and Priority Queues
GATE CS 2015 Set 1MCQ2 marksHard (estimate)
GATE CS 2015 Set 1, Q.50 (CS Q.40)
An algorithm performs $(lo g N)^{1/2}$ find operations, $N$ insert operations, $(lo g N)^{1/2}$ delete operations, and $(lo g N)^{1/2}$ decrease-key operations on a set of data...
Arrays and Linked Lists
GATE CS 2015 Set 2NAT1 markEasy (estimate)
GATE CS 2015 Set 2, Q.20 (CS Q.10)
A binary tree $T$ has 20 leaves. The number of nodes in $T$ having two children is _____.
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 2MCQ1 markMedium (estimate)
GATE CS 2015 Set 2, Q.27 (CS Q.17)
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
Binary Heaps and Priority Queues
GATE CS 2015 Set 2NAT2 marksMedium (estimate)
GATE CS 2015 Set 2, Q.41 (CS Q.31)
A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$ , and hence there cannot be any entr...
Arrays and Linked Lists
GATE CS 2015 Set 2MCQ2 marksMedium (estimate)
GATE CS 2015 Set 2, Q.43 (CS Q.33)
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for $i$ ranging from 0 to 2020?
Hash Tables and Collision Resolution
GATE CS 2015 Set 3MCQ1 markEasy (estimate)
GATE CS 2015 Set 3, Q.22 (CS Q.12)
The result evaluating the postfix expression $105 + 606 / * 8 -$ is
Stacks and Queues
GATE CS 2015 Set 3MCQ1 markEasy (estimate)
GATE CS 2015 Set 3, Q.23 (CS Q.13)
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2015 Set 3NAT1 markEasy (estimate)
GATE CS 2015 Set 3, Q.27 (CS Q.17)
Given a hash table $T$ with 25 slots that stores 2000 elements, the load factor $α$ for $T$ is _____.
Hash Tables and Collision Resolution
GATE CS 2015 Set 3MCQ1 markMedium (estimate)
GATE CS 2015 Set 3, Q.29 (CS Q.19)
Consider the following array of elements $⟨ 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 ⟩$ The minimum number of interchanges needed to convert it into a max-he...
Binary Heaps and Priority Queues
GATE CS 2015 Set 3NAT1 markEasy (estimate)
GATE CS 2015 Set 3, Q.35 (CS Q.25)
Consider a binary tree $T$ that has 200 leaf nodes. Then, the number of nodes in $T$ that have exactly two children are _____.
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 1NAT1 markMedium (estimate)
GATE CS 2014 Set 1, Q.22 (CS Q.12)
Consider a rooted $n$ node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 1MCQ2 marksEasy (estimate)
GATE CS 2014 Set 1, Q.50 (CS Q.40)
Consider a hash table with 9 slots. The hash function is $h (k) = k mod 9$ . The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19,...
Hash Tables and Collision Resolution
GATE CS 2014 Set 2MCQ1 markEasy (estimate)
GATE CS 2014 Set 2, Q.22 (CS Q.12)
A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into...
Binary Heaps and Priority Queues
GATE CS 2014 Set 2NAT2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.49 (CS Q.39)
Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possib...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 2MCQ2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.51 (CS Q.41)
Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the...
Stacks and Queues
GATE CS 2014 Set 3MCQ1 markMedium (estimate)
GATE CS 2014 Set 3, Q.22 (CS Q.12)
Consider the following rooted tree with the vertex labeled P as the root: Rooted tree with root P having left child Q and right child R; Q has child S; R has three children T, U...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 3NAT2 marksMedium (estimate)
GATE CS 2014 Set 3, Q.49 (CS Q.39)
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and…
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2014 Set 3MCQ2 marksEasy (estimate)
GATE CS 2014 Set 3, Q.50 (CS Q.40)
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after...
Hash Tables and Collision Resolution
GATE CS 2014 Set 3MCQ2 marksMedium (estimate)
GATE CS 2014 Set 3, Q.51 (CS Q.41)
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling repres...
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2013MCQ1 markEasy (estimate)
GATE CS 2013, Q.7 (CS Q.7)
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2013MCQ2 marksEasy (estimate)
GATE CS 2013, Q.43 (CS Q.43)
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2013MCQ2 marksMedium (estimate)
GATE CS 2013, Q.44 (CS Q.44)
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and...
Stacks and Queues
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.5 (CS Q.5)
The worst case running time to search for an element in a balanced binary search tree with $n 2^{n}$ elements is
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2012MCQ2 marksEasy (estimate)
GATE CS 2012, Q.35 (CS Q.35)
Suppose a circular queue of capacity ( $n - 1$ ) elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using REA...
Stacks and Queues
GATE CS 2012MCQ2 marksEasy (estimate)
GATE CS 2012, Q.47 (CS Q.47)
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the he...
Binary Trees, Binary Search Trees and Balanced Trees · Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2011MCQ1 markEasy (estimate)
GATE CS 2011, Q.23 (CS Q.23)
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
Binary Trees, Binary Search Trees and Balanced Trees
GATE CS 2011MCQ2 marksEasy (estimate)
GATE CS 2011, Q.29 (CS Q.29)
We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary...
Binary Trees, Binary Search Trees and Balanced Trees