# GATE Data Structure Online Test

50 Questions  Settings  Related Topics
• 1.
• A.

• B.

• C.

• D.

None of these

• 2.
In a stack the command to access nth element from the top of the stack S will be
• A.

S [Top-n]

• B.

S [Top+n]

• C.

S [Top-n-1]

• D.

None of the above

• 3.
If yyy, xxx and zzz are the elements of a lexically ordered binary tree, then in preorder traversal which node will be traverse first
• A.

Xxx

• B.

Yyy

• C.

Zzz

• D.

Can not be determined

• 4.
In a balance binary tree the height of two sub trees of every node can not differ by more than
• A.

2

• B.

1

• C.

0

• D.

3

• 5.
The result of evaluating prefix expression */b+0dacd, where a=3, b=6, c=1, d=5 is
• A.

0

• B.

5

• C.

10

• D.

15

• 6.
In array representation of binary tree teh right child of root will be at location of
• A.

2

• B.

5

• C.

3

• D.

0

• 7.
The total number of comparisons in a bubble sort is
• A.

O(n logn)

• B.

O(2n)

• C.

O(n2)

• D.

None of above

• 8.
• A.

First record of the actual data

• B.

Last record of the actual data

• C.

Pointer to the last record of the actual data

• D.

None of above

• 9.
Write the output of following program:int a[ ] = {1,2,3,} *p;
• A.

3

• B.

Junk value

• C.

Run time error

• D.

• 10.
If the out degree of every node is exactly equal to M or 0 and the num ber of nodes at level K is Mk-1 [con sider root at level 1], then tree is called as  (i) Full m-ary try(ii) Com plete m-ary tree(iii)Positional m-ary tree
• A.

Only (i)

• B.

Only (ii)

• C.

Both (i) and (ii)

• D.

Both (ii) and (III)

• 11.
In the following tree:If post order traversal generates sequence xy-zw*+, then label of nodes 1,2,3,4,5,6,7 will be
• A.

+, -, *, x, y, z, w

• B.

X, -, y, +, z, *, w

• C.

X, y, z, w, -, *, +

• D.

-, x, y, +, *, z, w

• 12.
If the following tree is used for sorting, then a new number 10 should be placed at
• A.

Right child of node labeled 7

• B.

Left child of node labeled 7

• C.

Left child of node labeled 14

• D.

Right child of node labeled 8

• 13.
A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of
• A.

• B.

• C.

• D.

• 14.
Number of possible ordered trees with 3 nodes A,B,C is
• A.

16

• B.

12

• C.

6

• D.

10

• 15.
Number of swapping, operations need to sort numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort
• A.

11

• B.

12

• C.

13

• D.

14

• 16.
Consider two sorted lists of size L1, L2. Number of comparisions needed in worst case my merge sort algorithm will be
• A.

L1,L2

• B.

Max(L1,L2)

• C.

Min(L1,L2)

• D.

L1+L2-1

• 17.
• A.

4

• B.

5

• C.

6

• D.

3

• 18.
Following sequence of operation is performed on a stack. Push(1), Push(2), Pop, Push(1), Push(2), Pop, Pop, Pop, Push(2), Pop. The sequences of popped out values are
• A.

2,2,1,2,2

• B.

2,2,1,1,2

• C.

2,1,2,2,1

• D.

2,1,2,2,2

• 19.
A binary tree in which every non-leaf node has non-empty left and right sub trees is called a strictly binary tree. Such a tree with 10 leaves
• A.

Has 19 nodes

• B.

Has 16 nodes

• C.

Has 15 nodes

• D.

None of the above

• 20.
Depth of a binary tree with n node is
• A.

Log (n +1) - 1

• B.

Log (n)

• C.

Log (n -1)n -1

• D.

Log (n) + 1

• 21.
To arrange a binary tree in ascending order we need
• A.

Post order traversal

• B.

Inorder traversal

• C.

Preorder traversal

• D.

None of above

• 22.
Average successful search time taken by binary search on sorted array of 10 items is
• A.

2.6

• B.

2.7

• C.

2.8

• D.

2.9

• 23.
Hash function f is defined as f(key) = key mod 7. If linear probing is used to insert the key 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6,  11 will be stored at the location
• A.

3

• B.

4

• C.

5

• D.

6

• 24.
Average successful search time for sequential search on 'n' item is
• A.

N/2

• B.

(n-1)/2

• C.

(n+1)/2

• D.

Log (n) + 1

• 25.
• A.

N2

• B.

Nn

• C.

N3

• D.

N

• 26.
6 files X1, X2, X3, X4, X5, X6 have 150, 250, 55, 85, 125, 175 number of records respectively. The order of storage ot optimize access time is
• A.

X1, X2, X3, X4, X5, X6

• B.

X3, X4, X1, X5, X6, X2

• C.

X1, X3, X2, X4, X5, X6

• D.

None of the above

• 27.
In above question average access time will be
• A.

150

• B.

140

• C.

55

• D.

None of the above

• 28.
An algorithm consists of two modules X1, X2. Their order is f(n) and g(n), respectively. The order of algorithm is
• A.

Max(f(n),g(n))

• B.

Min(f(n),g(n))

• C.

F(n)+g(n)

• D.

F(n)*g(n)

• 29.
Bib O notation w.r.t algorithm signifies
• A.

It decides the best algorithm to solve a problem

• B.

It determines maximum size of a problem, that can be solved in given system in given time

• C.

It is the lower bound of growth rate of algorithm

• D.

None of the above

• 30.
Running time T(n), where 'n' is input size of recursive algorithm is given as follows:T(n) = c + T(n-1), if n>1,T(n) = d if n<1. The order of algorithm is
• A.

N2

• B.

N

• C.

N3

• D.

Nn

• 31.
Four altorithm A1, A2, A3, A4 solves a problem with order log(n), log log(n), nlog(n), n. Which is best algorithm
• A.

A1

• B.

A2

• C.

A3

• D.

A4

• 32.
Time complexity of an algorithm T(n), where n is the input size is given by T(n) = T (n-1) + 1/n, if n>1 otherwise T(n) = 1. The order of algorithm is
• A.

Log n

• B.

N

• C.

N2

• D.

Nn

• 33.
• A.

Internal sorting is used, if number of items to be sorted is very large

• B.

External sorting is used, if number of items to be sorted is very large

• C.

External sorting needs auxiliary storage

• D.

Internal sorting needs auxuliary storage

• 34.
A sorting technique which guarrantees that records with same primary key occurs in the sorted list as in the original unsorted list is said to be
• A.

Stable

• B.

Consistent

• C.

External

• D.

Linear

• 35.
A text is made up of five characters, T1, T2, T3, T4, T5. The probability of occurance of each character is .12, .4, .15, .88 and .25, respectively. The optimal coding technique will have average length of
• A.

2.15

• B.

3.01

• C.

2.3

• D.

1.78

• 36.
• A.

T(1)=T(2)=T(3)

• B.

T(1) + T(2) = 2T2

• C.

T(1) - T(3) = T(2)

• D.

T(1) + T(2) = T(3)

• 37.
Arranging a pack of cards by picking one by one is an example of
• A.

Bubble sort

• B.

Selection sort

• C.

Insertion sort

• D.

Merge sort

• 38.
In evaluating arithmatic expression 2*3-(4+5) using postfix stack form. Which of the following stack configuration is not possible
• A.

------------ | 4 | 6 | ------------

• B.

------------ | 5 | 4 | 6 | ------------

• C.

------------ | 9 | 6 | ------------

• D.

------------ | 9 | 3 | 2 | ------------

• 39.
The order of an algorithm that finds whether a given boolean function of 'n' variable produces a '1' is
• A.

Constant

• B.

Linear

• C.

Logarithmic

• D.

Exponential

• 40.
The average number of comparisions performed by merge sort alrotithm in merging two sorted list of length 2 is
• A.

8/3

• B.

8/5

• C.

11/7

• D.

11/6

• 41.
To arrange the books of library the best method is
• A.

Bubble sort

• B.

Quick sort

• C.

Merge sort

• D.

Heap sort

• 42.
Which of the following algorithm has n  log (n) time complexity
• A.

Heap sort

• B.

Quick sort

• C.

Insertion sort

• D.

Selection sort

• 43.
Which algorithm solves all pair shortest path problem
• A.

Dijkastra's algorithm

• B.

Floyd's algorithm

• C.

Prim's algorithm

• D.

Worshal's algorithm

• 44.
The centricity of node labeled 5 is
• A.

6

• B.

7

• C.

2

• D.

5

• 45.
The information about an array used in a program will be stored in
• A.

Symbol table

• B.

Dope vector

• C.

Register vector

• D.

Activation table

• 46.
In which of the following cases linked list implementaion of sparse matrices consumes same memory as a normal array
• A.

5 x 6 matrix with 9 non-zero entries

• B.

5 x 6 matrix with 8 non-zero entries

• C.

6 x 5 matrix with 8 non-zero entries

• D.

6 x 5 matrix with 9 non-zero entries

• 47.
The advantage of sparse matrix linked list representationn over dope vector method is, that the former is
• A.

Conceptually easier

• B.

Completely dynamic

• C.

Efficient in accessing an entry

• D.

Efficient if the sparse matr4ix is a band matrix

• 48.
If the address of (I,J)th entry, in dope vector representation, where it stores the position of first and last non-zero entries of each row is given by C, assume l(n) and f(n) represent the last and first non-zero entries in row xi. ii. iii. iv.
• A.

• B.

• C.

• D.

• 49.
On which principle does stack work?
• A.

FILO

• B.

FIFO

• C.

LIFO

• D.

Both a and c above

• 50.
The order of binary search algorithm is
• A.

N

• B.

N2

• C.

N log n

• D.

Log n