GATE CSE & IT

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 elt;...

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2 -colorable if there exists a function $c: V \rightarrow\{0,1\}$ such that for every $(u, v) \in E, c(u) \neq c(v)$...

The set T represents various traversals over binary tree. The set S represents the order of visiting nodes during a traversal. $$ \begin{array}{ll}\,\,\,\,\, \text { T } &\,\,\,\,\...

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst case time...

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 $\operatorname{Val}(V)$. All the keys present in th...

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 $\_\_...

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time and finishi...

Consider a hash table $P[0,1, \ldots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h(x)=(x+7) \b...

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 $P$ do/d...

The following sequence corresponds to the preorder traversal of a binary search tree: $$ 50,25,13,40,30,47,75,60,70,80,77 $$ The position of the element 60 in the postorder travers...

The keys $5,28,19,15,26,33,12,17,10$ are inserted into a hash table using the hash function $h(k)=k \bmod 9$. The collisions are resolved by chaining. After all the keys are insert...

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 that or...

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$ is...

In a double hashing scheme, $h_1(k)=k \bmod 11$ and $h_2(k)=1+(k \bmod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is 11 . The hash function for the $i^{\t...

Let $G(V, E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maxi...

Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?

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 doubly...

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 wi...

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

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 of edges...

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 $T$ th...

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below. Operator Precedence Associativity + Highest Left − High Righ...

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?

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 values o...

Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. W...

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 the...

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 shown below. S...

Which one of the following sequences when stored in an array at locations $$A[1],....,A[10]$$ forms a max-heap?

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 another function th...

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 number...

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 maximum...

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 which are initially e...

Suppose we are given n keys, m has 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 h 2 for the eve...

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 the a...

Consider the following statements. S 1 : The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S 2 : The sequence of procedure returns corresp...

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 the se...

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 empty...

Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an a...

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 _______.

Let G = (V, E) be a directed, weighted graph with weight function w: E $$ \to $$ R. For some function f: V $$ \to $$ R, for each edge (u, v) $$ \in $$ E, define w'(u, v) as w(u, v)...

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 elements is k...

Consider the following C program. #include < stdio.h > int main () { int a [4] [5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}, {16, 17, 18, 19, 20}}; printf (“%d\n”...

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?

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?

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 table size is 23....

What is the worst case time complexity of inserting n 2 elements into an AVL-tree with n elements initially?

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. The expected...

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 longes...

Let $$G$$ be a graph with $$100!$$ vertices, with each vertex labelled by a distinct permutation of the numbers $$1,2, … , 100.$$ There is an edge between vertices $$u$$ and $$v$$...

Let $$G$$ be a simple undirected graph. Let $${T_D}$$ be a depth first search tree of $$G.$$ Let $${T_B}$$ be a breadth first search tree of $$G.$$ Consider the following statement...

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.

Breadth First Search $$(BFS)$$ is started on a binary tree beginning from the root vertex. There is a vertex $$t$$ at a distance four from the root. If t is the $$n$$-th vertex in...

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 numb...

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 _____________. $$N...

$$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 pointe...

Consider the following $$New-order$$ strategy for traversing a binary tree: $$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the root; $$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit the ri...

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 $$...

Consider a complete binary tree where the left and the right sub-trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is

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

Let $$G$$ be a connected undirected graph of $$100$$ vertices and $$300$$ edges. The weight of a minimum spanning tree of $$G$$ is $$500.$$ When the weight of each edge of $$G$$ is...

A binary tree $$T$$ has $$20$$ leaves. The number of nodes in $$T$$ having two children is _______________.

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

Consider a binary tree $$T$$ that has $$200$$ leaf nodes. Then, the number of nodes in $$T$$ that have exactly two children are ________.

Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For $$x \in V$$, let d(x) denote the shortest distance in G from s to x. A breadt...

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Given a hash table $$𝑇$$ with $$25$$ slots that stores $$2000$$ elements, the load factor $$\alpha $$ for $$𝑇$$ is ____________ .

Which one of the following hash functions on integers will distribute keys most uniformly over $$10$$ buckets numbered $$0$$ to $$9$$ for $$𝑖$$ ranging from $$0$$ to $$2020$$?

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. 2, 7, 10, 8, 14, 16, 20 IV....

The result evaluating the postfix expression $$10\,\,5\, + 60$$ $$\,\,6/\, * \,8\, - $$ is

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 represen...

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 fo...

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 the...

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, 15, 20,...

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

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 H. Suppose there...

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 O(n a Log b n...

Consider the following C functions in which size is the number of elements in the array E: int MyX(int *E, unsigned int size){ int Y = 0; int Z; int i,j,k; for(i = 0; i < size; i++...

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j, k; i =...

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

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?