## Data-Structures

 Question 1

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 O(n) B O(log2 n) C O(logn) D O(1)
Question 1 Explanation:
Worst case complexity for deleting a node from singly linked list is O(1).
 Question 2

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?

 A 20, 19, 18, 16, 15, 12, 11, 10 B 11, 12, 10, 16, 19, 18, 20, 15 C 10, 11, 12, 15, 16, 18, 19, 20 D 19, 16, 18, 20, 11, 12, 10, 15
Data-Structures       Binary-Trees       GATE 2020       Video-Explanation
Question 2 Explanation:  Postorder:
11, 12, 10, 16, 19, 18, 20, 15
 Question 3

Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k=90 is _______.

 A 13
Data-Structures       Hashing       GATE 2020       Video-Explanation
Question 3 Explanation:
• Probe sequence is the list of locations which a method for open addressing produces as alternatives in case of a collision.
• K=90
• h1(k) = k mod 23 = 90 mod 23 = 21
• In case of collision, we need to use secondary hash function.
• h2(k) = 1 + (k mod19) = 1 + 90mod19 = 1+14 = 15
• Now (21+15) mod 23 = 36 mod 23 = 13
• So the address is 13.
 Question 4

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?

 A θ(n log n) B θ(n2) C θ(1) D θ(n)
Question 4 Explanation:
The Linked list insertion operations will take O(1) time. It means a constant amount of time for insertion.
Total number of elements inserted into an empty linked list is O(n). So, it will take O(n) time in the worst case.
After inserting elements into an empty linked list we have to perform sorting operation.
To get minimum time complexity to perform sorting order is merge sort. It will give O(nlogn) time complexity only.
The head in MergeSort as the below implementation changes next links to sort the linked lists (not data at the nodes), so head node has to be changed if the data at the original head is not the smallest value in the linked list.
Note: There are other sorting methods also will give decent time complexity but quicksort will give O(n2) and heap sort will not be suitable to apply.
 Question 5

Consider the following C program.

```#include
int main ()  {
int a   = {{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 output of the program is _______.

 A 19
Data-Structures       Arrays       GATE 2020       Video-Explanation
Question 5 Explanation:
Check out the step by step program and its output in the comment:
#include
int main()
{
int a = { {1,2,3,4,5},
{6,7,8,9,10},
{11,12,13,14,15},
{16,17,18,19,20}
};
printf("%d\n",a); //880 (consider base address = 880)
printf("%d\n",*a); //880
printf("%d\n",**a); //1
printf("%d\n",**a+2); //3
printf("%d\n",a+**a+2); //940
printf("%d\n",*(a+**a+2));//940
printf("%d\n",*(a+**a+2)+3);//952
printf("%d\n",*(*(a+**a+2)+3));//19
return 0;
} Question 6

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

 A θ(n4) B θ(n2) C θ(n3) D θ(n2 log n)
Data-Structures       Binary-Trees       GATE 2020       Video-Explanation
Question 6 Explanation:
AVL Tree all operations(insert, delete and search) will take O(logn) time.
So, In worst case it will take o(n2 log n) time.
 Question 7

Let G = (V,E) be a directed, weighted graph with weight function w:E → R. For some function f:V → R, for each edge (u,v) ∈ E, define w'(u,v) as w(u,v) + f(u) - f(v).
Which one of the options completes the following sentence so that it is TRUE?

“The shortest paths in G under w are shortest paths under w’ too, _______”.

 A if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G B if and only if ∀u ∈ V, f(u) is positive C if and only if ∀u ∈ V, f(u) is negative D for every f: V→R
Data-Structures       Graphs-and-Tree       GATE 2020       Video-Explanation
Question 7 Explanation:  Question 8

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.

 A θ(n log k) B θ(log n + k) C θ(k log n) D θ(log n)
Data-Structures       Binary-Trees       GATE 2020       Video-Explanation
Question 8 Explanation:
The idea is to traverse the given binary search tree starting from root. For every node being visited, check if this node lies in range, if yes, then add 1 to result and recur for both of its children. If the current node is smaller than the low value of range, then recur for right child, else recur for left child.
Time complexity of the above program is O(h + k) where h is the height of BST and k is the number of nodes in a given range.
Here h is log n, hence O(log n+k).
 Question 9

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

 A 511
Data-Structures       Heap-Tree       GATE 2020       Video-Explanation
Question 9 Explanation:
The binary heap contains 1023 elements. When it performs minimum comparisons it will take Ceil(n/2)
n=1023
= Ceil(1023/2)
= 512
So, the maximum element is also part of n/2.
So, we have to subtract from the total elements
= 512-1
= 511
 Question 10
Consider the problem of reversing a singly linked list. To take an example, given the linked list below, Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O (1) space?
 A B C D It is not possible to reverse a singly linked list in O (1) space.
Question 10 Explanation:
struct Node {
int data;
struct Node* next;
{
this->data = data;
next = NULL;
}
};
/* Function to reverse the linked list */
void reverse()
{
// Initialize current, previous and
// next pointers
Node *prev = NULL, *next = NULL;
while (current != NULL) {
// Store next
next = current->next;
// Reverse current node's pointer
current->next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
}
For the above algorithm :
Time Complexity: O(n)
Space Complexity: O(1)
 Question 11
Consider the queues Q 1 containing four elements and Q 2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q). The minimum number of Enqueue operations on Q 1 required to place the elements of Q 1 in Q 2 in reverse order (shown as the Final State in the figure) without using any additional storage is___________. A 6
Data-Structures       Enqueue-Dequeue       GATE 2022       Video-Explanation
Question 11 Explanation:
Count Q1 enqueue Question 12

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 almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Which of the following is correct?

 A (ii) and (iii) are true B (i) and (ii) are true C (iii) and (iv) are true D (ii) and (iv) are true
Data-Structures       Stack-and-Queue       GATE 1996
Question 12 Explanation:
(i) FIFO computation efficiently supported by queues.
(iv) LIFO computation efficiently supported by stacks.
Then given (i) and (iv) are false.
 Question 13

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

 A Worst case complexity of search operations is less? B Space used is less C Deletion is easier D None of the above
Data-Structures       Hashing       GATE 1996
Question 13 Explanation:
In chained hash tables have advantages over open addressed hash tables in that the removal operation is simple and resizing can be postponed for longer time.
 Question 14

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”? A 1 B 3 C 7 D 8
Data-Structures       Binary-Trees       GATE 1996
Question 14 Explanation: a, b, c are going to unbalance.
 Question 15

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

 A f e g c d b a B g c b d a f e C g c d b f e a D f e d g c b a
Data-Structures       Binary-Trees       GATE 1996
Question 15 Explanation:
Postorder:-
Left → Right → Root
g c d b f e a
 Question 16

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

 A 0 B 1 C 2 D 3
Data-Structures       Heap-Tree       GATE 1996
Question 16 Explanation:
Lets draw first heap from given sequence,  Question 17

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

 A (4, 7) B (7, 4) C (8, 3) D (3, 8)
Data-Structures       Binary-Trees       GATE 1996
Question 17 Explanation:
50 is the root node in BST.
So greater than 50 will be in right subtree of 50 and less than 50 in left subtree.
So, answer will be (7, 4).
 Question 18

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

 A 61 52 14 17 40 43 B 2 3 50 40 60 43 C 10 65 31 48 37 43 D 81 61 52 14 41 43 E 17 77 27 66 18 43
Data-Structures       Binary-search-tree       GATE 1996
 Question 19

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

 A Singly linked list B Doubly linked list C Circular doubly linked list D Array implementation of list
Question 19 Explanation:
In circular doubly linked list concatenation of two lists is to be performed on O(1) time.
 Question 20

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

 A An operator stack B An operand stack C An operand stack and an operator stack D A parse tree
Data-Structures       Stacks       GATE 1997
Question 20 Explanation:
An operator stack ⇒ Infix to (Postfix or Prefix)
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
 Question 21

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 5 3 1 2 4 7 8 6 B 5 3 1 2 6 4 8 7 C 5 3 2 4 1 6 7 8 D 5 3 1 2 4 7 6 8
Data-Structures       Binary-Trees       GATE 1997
Question 21 Explanation:
Preorder traversal means (Root, left, right)
Option D:
Let draw binary search tree for the given sequence, After traversing through this tree we will get same sequence.
 Question 22

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 a sequence of operations, the keys chosen are in

 A non-increasing order B non-decreasing order C strictly increasing order D strictly decreasing order
Data-Structures       Stack-and-Queue       GATE 1997
Question 22 Explanation:
In stack last element pushed should be popped first. And in priority queue Q, minimum element is given the highest priority. So whenever we will call DELETEMIN(Q), it will pop the element with min value. So we can conclude that the minimum element should be inserted last or the insertion should be in decreasing order. And also it should be in strictly decreasing order, because for two elements with equal value the priority queue will pick any of one randomly which should not be the case in the stack.
 Question 23

Which of the following statements is false?

 A A tree with a n nodes has (n – 1) edges B A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results C A complete binary tree with n internal nodes has (n + 1) leaves D Both B and C
Data-Structures       Binary-Trees       GATE 1998
Question 23 Explanation:
A: Tree with n nodes must have (n-1) edges.
D: The maximum no. of nodes in a binary tree of height h is 2h+1 - 1.
h=2 ⇒ 23 - 1 ⇒ 7 Question 24

A complete n-ary tree is one in which every node has 0 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

 A x(n-1) + 1 B xn - 1 C xn + 1 D x(n+1)
Data-Structures       N-array-Tree       GATE 1998
Question 24 Explanation:
No. of internal node = x
Let no. of leaf nodes = L
Let nt be total no. of nodes.
So, L+x = nt -----(I)
Also for n-ary tree with x no. of internal nodes, total no. of nodes is,
nx+1 = nt -----(II)
So, equating (I) & (II),
L+x = nx+1
L = x(n-1) + 1
 Question 25

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 location, the array is stored in row-major order and the first element of the array is stored at location 100, what is the address of the element a[i][j]?

 A 15i + j + 84 B 15j + i + 84 C 10i + j + 89 D 10j + i + 89
Data-Structures       Arrays       GATE 1998
Question 25 Explanation:
The address of element A[i][j] will be,
100 + 15 * (i-1) + (j-1)
= 100 + 15i - 15 + j - 1
= 15i + j + 84
 Question 26

Faster access to non-local variables is achieved using an array of pointers to activation records called a

 A stack B heap C display D activation tree
Data-Structures       Pointers       GATE 1998
Question 26 Explanation:
Properties of displays:
→ Use a pointer array to store the activation records along the static chain.
→ Fast access for non-local variables but may be complicated to maintain.
 Question 27

Let p be a pointer as shown in the figure in a single linked list. What do the following assignment statements achieve?

q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q

(b) Compute the postfix equivalent of the following Infix expression

`  3 * log(x+1) - a/2  `
 A Theory Explanation.
 Question 28

Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:

``` Inorder       a f b c d g e
Postorder     a f c g e d b ```
 A Theory Explanation.
Data-Structures       Binary-Trees       GATE 1998
 Question 29

(a) Derive a recurrence relation of the size of the smallest AVL tree with height h.

(b) What is the size of the smallest AVL tree with height 8.

 A Theory Explanation.
Data-Structures       AVL-Trees       GATE 1998
 Question 30

The number of articulation points of the following graph is A 0 B 1 C 2 D 3
Data-Structures       Graphs       GATE 1999
Question 30 Explanation:
Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3
 Question 31

(a) In a binary tree, a nil node is defined to be a node with 2 children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.

(b) Draw a min-heap that results from insertion of the following elements in order into an initially empty min-heap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.

 A Theory Explanation.
Data-Structures       Binary-search-tree       GATE 1999
 Question 32

The most appropriate matching for the following pairs

```          X: depth first search            1: heap
Z: sorting                       3: stack  ```

is

 A X – 1 Y – 2 Z – 3 B X – 3 Y – 1 Z – 2 C X – 3 Y – 2 Z – 1 D X – 2 Y – 3 Z – 1
Data-Structures       Match-the-Following       GATE 2000
Question 32 Explanation:
Stack is used in depth first search.
Queue is used in breadth-first search.
Heap is used in heap.
 Question 33

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 represents a valid binary tree?

 A (1 2 (4 5 6 7)) B (1 (2 3 4) 5 6) 7) C (1 (2 3 4) (5 6 7)) D (1 (2 3 NULL) (4 5))
Data-Structures       Binary-Trees       GATE 2000
Question 33 Explanation:
Option C: (Proper Representation)
 Question 34

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

```         reverse(s, 1, k) ;
reverse(s, k + 1, n);
reverse(s, l, n);  ```
 A Rotates s left by k positions B Leaves s unchanged C Reverses all elements of s D None of the above
Data-Structures       Arrays       GATE 2000
Question 34 Explanation:
If we perform the three given open operations it will result left rotation by K positions. If we perform n time it will result the initial array.
 Question 35

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?

 A LASTIN = LASTPOST B LASTIN = LASTPRE C LASTPRE = LASTPOST D None of the above
Data-Structures       Binary-Trees       GATE 2000
Question 35 Explanation:
In full Binary tree LASTIN = LASTPRE.
But in case of complete binary last level need not to be full in that case LASTPRE is not equal to LASTIN.
 Question 36

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

 A {u, v} must be an edge in G, and u is a descendant of v in T B {u, v} must be an edge in G, and v is a descendant of u in T C If {u, v} is not an edge in G then u is a leaf in T D If {u, v} is not an edge in G then u and v must have the same parent in T
Data-Structures       Graphs       GATE 2000
Question 36 Explanation: In DFS after visiting u, there is no child node then back tracking is happen and then visit the node v. There is no need of (u,v) be an edge.
 Question 37

Suppose a stack implementation supports, in addition to PUSH and POP, an operation REVERSE, which reverses the order of the elements on the stack.
(a) To implement a queue using the above stack implementation, show how to implement ENQUEUE using a single operation and DEQUEUE using a sequence of 3 operations.
(b) The following postfix expression, containing single digit operands and arithmetic operators + and *, is evaluated using a stack.

` 5 2 * 3 4 + 5 2 * * + `

Show the contents of the stack.

(i) After evaluating 5 2 * 3 4 +
(ii) After evaluating 5 2 * 3 4 + 5 2
(iii) At the end of evaluation.
 A Theory Explanation is given below.
Data-Structures       Descriptive       GATE 2000
Question 37 Explanation:
(a) Enqueue → push
Dequeue → reverse, pop, reverse
(b) (i) After evaluating 5 2 * 3 4 +
Sol:
7(3+4) 10(5*2)
(ii) After evaluating 5 2 * 3 4 + 5 2
Sol:
25(5*5) 7(3+4) 10(5*2)
(iii) At the end of evaluation
Sol: 80
 Question 38
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
 A log n B n/2 C (log2)n - 1 D n
Question 38 Explanation:
Worst case time complexity of singly linked list is O(n). So we need n number of comparisons needed to search a singly linked list of length n.
 Question 39

The results returned by function under value-result and reference parameter passing conventions

 A Do not differ B Differ in the presence of loops C Differ in all cases D May differ in the presence of exception
Data-Structures       Parameter-Passing       GATE 2002
Question 39 Explanation:
The result return by the function under value-result and reference parameter passing conventions may differ in presence of exception because in value-result the updated value can be returned to the original variable. But in case of reface parameter the value can change immediately.
 Question 40

Consider the following declaration of a two dimensional array in C:

`          char a;    `

Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a  is:

 A 4040 B 4050 C 5040 D 5050
Data-Structures       Arrays       GATE 2002
Question 40 Explanation:
Address for a = BaseAddress + [40 * 100 * element size] + [50 * element size]
= 0 + [40 * 100 * 1] + [50 * 1]
= 4000 + 50
= 4050
 Question 41

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

 A n/2 B (n-1)/3 C (n-1)/2 D (2n+1)/3
Data-Structures       Tree       GATE 2002
Question 41 Explanation: Question 42

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

 A log2n B log4/3n C log3n D log3/2n
Data-Structures       Tree       GATE 2002
Question 42 Explanation:
Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3) Height of the tree = log3/2 n
 Question 43

To evaluate an expression without any embedded function calls

 A One stack is enough B Two stacks are needed C As many stacks as the height of the expression tree are needed D A Turning machine is needed in the general case
Data-Structures       Stacks       GATE 2002
Question 43 Explanation:
To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.
 Question 44

Draw all binary trees having exactly three nodes labeled A, B and C on which Preorder traversal gives the sequence C, B, A.

 A Theory Explanation is given below.
Data-Structures       Binary-Trees       GATE 2002
Question 44 Explanation: Total 5 binary trees are possible with the preorder C, B, A.
 Question 45

The following recursive function in C is a solution to the Towers of Hanoi problem.

``` Void move (int n, char A, char B, char C)
{
if (…………………………………) {
move (…………………………………);
printf(“Move disk %d from pole %c to pole %c\n”, n,A,C);
move (………………………………….); ```

Fill in the dotted parts of the solution.

 A Theory Explanation is given below.
Data-Structures       Recursion       GATE 2002
Question 45 Explanation:
move (disk-1, source, aux, dest) //Step-1
move disk from source to dest //Step-2
move (disk-1, aux, dest, source) //Step-3
Recurrence: 2T(n - 1) + 1
T(n) = 2T (n - 1) + 1
= 2[2T(n - 2) + 1] + 1
= 22T(n - 2) + 3

2k T(n - k) + (2k - 1)
= 2n-1T(1) + (2n-1 - 1)
= 2n-1 + 2n-1 - 1
= 2n - 1
≅ O(2n)
void move (int n, char A, char B, char C) {
if (n>0)
move(n-1, A, C, B);
printf("Move disk%d from pole%c to pole%c\n", n,A,C);
move(n-1, B, A, C);
}
}
 Question 46

Assume the following C variable declaration

`int *A , B; `

Of the following expressions

`I. A     II. A     III. B     IV. B  `

which will not give compile-time errors if used as left hand sides of assignment statements in a C program?

 A I, II, and IV only B II, III, and IV only C II and IV only D IV only
Data-Structures       Arrays       GATE 2003
Question 46 Explanation:
i) A can be consider as a pointer and this will not give any compile-time error.
ii) A This results an integer, no error will come.
iii) B is a base address of an array. This will not be changed it will result a compile time error.
iv) B This also results an integer. No error will come.
 Question 47

Let T(n) be the number of different binary search trees on n distinct elements. Then , where x is

 A n – k + 1 B n – k C n – k – 1 D n – k – 2
Data-Structures       Binary-Search-Tree       GATE 2003
Question 47 Explanation:
A binary search tree consists of n distinct elements. Let consider on left subtree, it consists of (k-1) elements. Then right subtree consists of (n-k) elements. From this we c an write recursive function as T(k-1)*(n-k) i.e., Question 48

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 sequence of the resultant tree?

 A 7 5 1 0 3 2 4 6 8 9 B 0 2 4 3 1 6 5 9 8 7 C 0 1 2 3 4 5 6 7 8 9 D 9 8 6 4 2 3 0 1 5 7
Data-Structures       Binary-Search-Tree       GATE 2003
Question 48 Explanation: Inorder: 0 1 2 3 4 5 6 7 8 9
 Question 49

Consider the following graph Among the following sequences:

`(I) a b e g h f    (II) a b f e h g    (III) a b f h g e    (IV) a f g h b e `

Which are depth first traversals of the above graph?

 A I, II and IV only B I and IV only C II, III and IV only D I, III and IV only
Data-Structures       Graphs       GATE 2003
Question 49 Explanation:
I) a → b → e → g → h → f (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)
 Question 50

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

 A Θ(n log n) B Θ(n) C Θ(log n) D Θ(1)
Data-Structures       Heap-Tree       GATE 2003
Question 50 Explanation:
The 7th smallest elements can be present in any of 7 levels. Then total possible elements can be present is seven levels is
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7th smallest element in Θ(1) time.
There are 50 questions to complete.

Register Now