Data Structures

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) \bmod 11$. Consider the following sequence...

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/does NOT correspond to any leaf node of t...

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 traversal of $T$ is $\_\_\_\_$ . (answer in int...

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 inserted, the length of the longest chain is $...

Consider the following ANSI-C program. #include <stdio.h> int main( ) { int *ptr, a, b, c; a=5; b=11; c=20; ptr=&a; *ptr=c; ptr=&c; a=*(&b); c=*ptr-a; printf("%d",c); return(0); } The output of this program is $\_\_\_\_$...

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; struct node *next; }; int getListSize (...

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 } &\,\,\,\,\,\, \text { S } \\ \text { I: } \text {...

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 the given BST are distinct. The keys belon...

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 order. When an element arrives, it is assi...

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 $\_\_\_\_$ . (answer in integer)

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 in the path from the node containing 19...

#include void foo(int *p, int x) { *p = x; } int main( ) { int *z; int a = 20, b=25; z = &a; foo(z, b); printf("%d", a); return 0; } The output of the given C program is _________. (Answer in integer)

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

Consider the following C program : #include <stdio.h> void stringcopy(char *, char *); int main( ) { char a[30] = "@#Hello world!"; stringcopy(a,a+2); printf("%s\n", a); return 0; } void sringcopy(char *s, char *t) { whi...

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$ that have exactly two children?

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 wish to augment the stack data structure w...

Consider an unordered list of $N$ distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

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 linked list with pointers to the head no...

Consider the following C program : #include <stdio.h> int main( ) { int a; int arr[5]={30,50,10}; int *ptr; ptr = &arr[0] + 1; a = *ptr; (*ptr)++; ptr++; printf("%d",a + (*ptr) + arr[1]); return 0; } The output of the ab...

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 ________ (Answer in integer)

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^{\text {th }}$ probe in the open address ta...

#include <stdio.h> int foo(int S[ ], int size) { if(size == 0) return 0; if(size == 1) return 1; if(S[0]!=S[1]) return 1 + foo(S + 1, size - 1); return foo(S + 1, size - 1); } int main( ) { int A[] ={0,1,2,2,2,0,0,1,1};...

Consider the following C function definition. int fX(char *a) { char *b = a; while(*b) b++; return b - a; } Which of the following statements is/are TRUE?

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 convention that, at each node, all valu...

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 an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the...

What is the output of the following C program? #include <studio.h> int main() { double a[2]={20.0, 25.0}, *p, *q; p = a; q = p + 1; printf("%d,%d", (int)(q - p), (int)(*q - *p)); return 0;}

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 of k is

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 of keys, $$m$$ be the number of slots i...

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 element from A. The operation INSERT(A,...

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 empty. I: push the elements of a from a$$...

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 that deletes a node in a doubly-linked lis...

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

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 array indices start with 0, the 3 rd larg...

What is printed by the following ANSI C program? #include <stdio.h> int main(int argc, char *argv[ ]) { int a[3][3][3] = {{1, 2, 3, 4, 5, 6, 7, 8, 9}, {10, 11, 12, 13, 14, 15, 16, 17, 18}, {19, 20, 21, 22, 23, 24, 25, 26...

What is printed by the following ANSI C program? #include <stdio.h> int main(int argc, char *argv[ ]) { int x = 1, z[2] = {10, 11}; int *p = NULL; p = &x; *p = 10; p = &z[1]; *(&z[0] + 1) += 3; printf("%d, %d, %d\n", x,...

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 even keys. What is the expected number of k...

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?

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 arbitrary of n elements. Which one of the...

Consider the following ANSI C program. #include<stdio.h> int main(){ int arr[4][5]; int i, j; for(i =0; i<4; i++){ for (j =0; j<5; j++){ arr [i][j] = 10*i + j; } } print("%d", *(arr[1] + 9)); return 0; } What is the outp...

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 queue. enqueue(21); enqueue(24); dequeu...

Consider the following ANSI C function: int SimpleFunction (int y[], int n, int x) { int total = y[0], loopIndex; for (loopIndex = 1; loopIndex <= n - 1; loopIndex ++ ) total = x * total + y[loopIndex]; return total : }...

Consider the following ANSI C program: #include <stdio.h> #include <stdlib.h> struct Node{ int value; struct Node ⋆next;}; int main(){ struct Node ⋆boxE, ⋆head, ⋆boxN; int index = 0; boxE = head = (struct Node ⋆) malloc...

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?

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?

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.

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?

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”, *(*(a+**a+2) +3)); return (0); } The o...

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. Then the address returned by probe 1 in...

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

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

Consider the following C program: #include < stdio.h > int main() { int a[] = {2, 4, 6, 8, 10} ; int i, sum = 0, *b = a + 4 ; for (i = 0; i < 5; i++) sum = sum + (*b - i) - *(b - i) ; printf ("%d\n", sum) ; return 0 ; }...

Consider the following C program : #include < stdio.h > int main () { int arr [] = {1,2,3,4,5,6,7,8,9,0,1,2,5}, *ip = arr+4; printf ("%d\n", ip[1]); return 0; } The number that will be displayed on execution of the progr...

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 III. A max-heap can be constructed from a...

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 value of the distance between a and b i...

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 path from the root to any leaf. The he...

Consider the following C program: #include< stdio.h > void fun1(char *s1, char *s2){ char *tmp; tmp = s1; s1 = s2; s2 = tmp; } void fun2(char **s1, char **s2){ char *tmp; tmp = *s1; *s1 = *s2; *s2 = tmp; } int main(){ ch...

The number of possible min-heaps containing each value from $$\left\{ {1,2,3,4,5,6,7} \right\}$$ exactly once is _____.

Consider the following C program. #include< stdio.h > struct Ournode{ char x,y,z; }; int main(){ struct Ournode p = {'1', '0', 'a'+2}; struct Ournode *q = &p; printf ("%c, %c", *((char*)q+1), *((char*)q+2)); return 0; }...

2017 PYQ

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 this $$BFS$$ traversal, then the maximum...

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 number of items in the queue)?

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 to the $$i$$-th index of the array. If th...

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

$$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 provided to the record on which the...

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\,\,height\,\,of\,\,a\,tree...

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 that node. Thus, the root is at depth $$0....

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. 4, 6, 7, 9 18, 20, 25

Consider the following C program segment. #include < stdio.h > int main() { char s1[7] = "1234", *p; p = s1 + 2; *p = ‘0’; printf("%s", s1); } What will be printed by the program?

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 entry to the right of, or below a $$\inf...

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

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

Consider the following function written in the C programming language. void foo(char *a){ if ( *a && *a != ' '){ foo(a+1); putchar(*a); } } The output of the above function on input “ABCD EFGH” 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

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

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-heap is

Consider the C program below. #include < stdio.h > int *A, stkTop; int stkFunc(int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case -1: size = val; break; case 0: if (stkTop < size) A[stkTop++] = va...

An algorithm performs $${\left( {\log N} \right)^{1/2}}$$ find operations, N insert operations, $${\left( {\log N} \right)^{1/2}}$$ delete operations, and $${\left( {\log N} \right)^{1/2}}$$decrease-key operations on a s...

Hard✓

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

What is the output of the following C code? Assume that the address of x is 2000 (in decimal) and an integer requires four bytes of memory. int main () { unsigned int x[4][3] = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}}; print...

Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Array Index 1 2 3 4 5 6 7 8 9 Value 40 30 20 10 15 16 17 8 4 Now consider that a value 35 is inserted into this heap. After insertion, the...

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

Consider the following program in C language: #include < stdio.h > main() { int i; int *pi = &i; scanf("%d", pi); printf("%d\n", i + 5); } Which one of the following statements is TRUE?

Let A be a square matrix size $$n \times n$$. Consider the following pseudocode. What is the expected output? C = 100; for i = 0 to n do for j = 1 to n do { Temp = A[ i ][ j ] + C ; A[ i ][ j ] = A[ j ][ i ] ; A[ j ][ i...

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 representation. Each node of the tree is of type...

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 following statements is TRUE with respect...

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 first 3 insertions?

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, 33, 12, 17, 10. The maximum, minimum, a...

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 are m such numbers in T. If the tightest...

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 ). Then the value of a + 10b is ________...

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 the heap in that order. The level-order tr...

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________

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++) Y = Y + E[i]; for(i = 0; i < size; i++...

2013 PYQ

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?

2013 PYQ

The procedure given below is required to find and replace certain characters inside an input character string supplied in array $$A.$$ The characters to be replaced are supplied in array $$oldc,$$ while their respective...

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object in to a binary search tree of n nodes?

2012 PYQ

The worst case running time to search for an element in a balanced binary search tree with n2 n elements is

2012 PYQ

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 REAR and FRONT as array index variables, respectiv...

2012 PYQ

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 height of a binary tree rooted at the tree poi...

What does the following fragment of C-program print? char c[ ] = "GATE2011"; char *p = c; printf("%s", p + p[3] - p[1]);

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?

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?

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 search tree?

2010 PYQ

The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank. typedef...

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

Consider a binary max-heap implemented using an array. What is the content of the array {25, 14, 16, 13, 10, 8, 12} after two delete operations?

You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree that has P as its post order traversal. What is the time complexity of...

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV....

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complex...

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 Pick the true statement from the following.

Which of the following is TRUE?

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What...

How many distinct BSTs can be constructed with 3 distinct keys?

Choose the correct option to fill ? 1 and ? 2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character. void recerse (void) { int c; if (?1) rev...

What is printed by the following C program? #include < stdio.h > int f(int x, int *py, int **ppz) { int y, z; **ppz += 1; z = **ppz; *py += 2; y = *py; x += 3; return x + y + z; } void main() { int c, *b, **a; c = 4; b =...

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 36 92 87 11 4 71 13 14 is inserted into an initially empty...

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly...

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 given. How many different orders are possible in which th...

Hard✓

Consider the following C program segment where CellNode represents a node in a binary tree: struct CellNode { struct CellNOde *leftChild; int element; struct CellNode *rightChild; }; int GetValue(struct CellNode *ptr) {...

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8,...

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 collides with an existing one exceed 0.5.

The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

The maximum number of binary trees that can be formed with three unlabeled nodes is:

Consider the following C program: #include #define EOF -1 void push (int); /* push the argument on the stack */ int pop (void); /* pop the top of the stack */ void flagError (); int main () { int c, m, n, r; while ((c =...

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height $$h$$ is:

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: i. isEmpty (Q) — returns true if the queue is empty, false otherwise. ii. delete (Q) — deletes the el...

The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluat...

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 the heap property, the algorithm to convert the complet...

An implementation of a queue Q, using two stacks S1 and S2, is given below : void insert(Q, X){ push(S1, X); } void delete(Q){ if(stack - empty(S2)) then { if(stack - empty(S1)) then { print("Q is empty"); return; }else...

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child...

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 of nodes examined?

Which of the following sequences of array elements forms a heap?

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 level of element X[i], i ≠ 0, is

Consider this C code to swap two integers and these five statements: void swap(int *px, int *py) { *px = *px - *py; *py = *px + *py; *px = *py - *px; } S1: will generate a compilation error S2: may generate a segmentatio...

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 is

In a binary max heap containing n numbers, the smallest element can be found in time

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next leve...

Given two arrays of numbers a 1 ,......,a n and b 1 ,......, b n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that a i +a i+1 ......a j = b i +b i+1 ......b j or report that the...

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[i],i≠0 is?

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is...

How many distinct binary search trees can be created out of 4 distinct keys?

The numbers 1, 2, ........, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements '1' and '7' are inserted in the heap in that order, The l...

In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all these elements is : (Hint : Use a heap...

A program P reads in 500 integers in the range [0, 100] representing the cores of 500 students. It then print the frequency of each score above 50. What would be the best way for P to store the frequencies?

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

An Abstract Data Type (ADT) is

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The l...

Postorder traversal of a given binary search tree T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an inorder trave...

A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. If a stack S contains the integers 2, -3, 2, -1, 2 in order...

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what l...

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. The postfix expression corresponding to the infix expression a + b×c-d^e...

The best data structure to check whether an arithmetic expression has balanced parentheses is a

The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a max Heap. The resultant max Heap is

Consider the following C program segment struct CellNode{ struct CellNode *leftChild; int element; struct CellNode *rightChild; }; int Dosomething (struct CellNode *ptr) { int value = 0; if (ptr ! = NULL) { if (ptr - > l...

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely? i) preorder and postorder ii) inorder and postorder iii) preorder and in...

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the ro...

Consider the following C program segment: char p[20]; char *s = "string"; int length = strlen(s); for(i=0; i < length; i++) p[i] = s[length-i]; printf("%s",p); The output of the program is

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 delete the node x from the list?

A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks,...

A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, but it may pop off the top character at any time. Which one of the foll...

Two matrices M 1 and M 2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute...

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true? i) 9679, 1989, 4199 hash to the same value ii) 1471, 6171 has to the...

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y s...

Assume the following C variable declaration int * A[10], B[10][10]; Of the following expressions I. A[2] II. A[2] [3] III. B[1] IV. B[2] [3] Which will not give compile-time errors if used as left hand sides of assignmen...

Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal se...

Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p ->next == NULL) || ((p->data <= p -> next -> data) && f(p-> next))); } For a given l...

In a heap with n elements with the smallest element at the root, the 7 th smallest element can be found in time

2002 PYQ

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

2002 PYQ

Consider the following declaration of a two-dimensional array in C: char a[100][100]; Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a[40][50...

2002 PYQ

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

2001 PYQ

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array $$\left( {i \le n} \right)$$, the index of...

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always tree?

Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following...

Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverse the order of elements in s between positions i and j (both inclusive). What does the following sequence do, where $$1 \le k < n:$$ re...

The most appropriate matching for the following pairs X: m=malloc(5); m= NULL; Y: free(n); n->value = 5; Z: char *p; *p='a'; 1: using dangling 2: using uninitialized pointers 3. lost memory is:

An n $$\times$$ n array v is defined as follows V [i, j] = i - j for all i, j, $$1 \le i \le n,\,1 \le j \le n$$ The sum of the elements of the array v is

The following C declarations struct node{ int i: float j; }; struct node *s[10]; define s to be

1998 PYQ

Which of the following statements is false?

1998 PYQ

A complete n-ary tree is one in which every node has O or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

1998 PYQ

Let A be a two dimensional array declared as follows: A : array [ 1... 10] [1... 15] of integer; Assuming that each integer takes one memory locations the array is stored in row-major order and the first element of the a...

Which of the following is essential for converting an infix expression to the postfix form efficiently?

The concatenation of two lists is to be performed on 0(1) time. Which of the following implementations of a list should be used?

A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For...

An advantage of chained hash table (external hashing) over the open addressing scheme is

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 right subtree of the root respectively is

The minimum number of interchanges needed to convert the array 89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70 into a heap with the maximum element at the root is

Which of the following sequences denotes the post order traversal sequence of the tree of previous question?

Consider the following statements: (i) First-in-first out types of computations are efficiently supported by STACKS. (ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almos...

A binary search tree is used to locate the number 43. Which of the following probe sequences are not possible?

1995 PYQ

Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive programs are efficient III. The worst case complexity for Quicksort is O...

1995 PYQ

A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:

1994 PYQ

Linked lists are not suitable data structures of which one of the following problems?

1994 PYQ

Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?

1994 PYQ

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n $$\times$$ n, non-zero elements (i.e., elements of the lower triangle) of ea...

1991 PYQ

The following sequence of operations is performed on stack: PUSH (10),PUSH (20),POP,PUSH (10),PUSH (20),POP,POP,POP,PUSH (20),POP The sequence of the value popped out is:

1990 PYQ

Match the pairs in the following: List - I (a) Heap construction (b) Constructing hash table witn linear probing (c) AVL Tree construction (d) Digital tree construction List - II (p) $$\Omega \left( {n\log _{10}^n} \righ...

1987 PYQ

It is possible to construct a binary tree uniquely whose pre-order and post-order traversals are given.

1987 PYQ

If the no of leaves in a tree is not a power of 2,then the tree is not a binary tree.

1987 PYQ

In a circular linked list organization,insertion of a record involves modification of :