# Data Structures Test - 4 - PDF Flipbook

Data Structures Test - 4

226 Views
PDF 4,013,901 Bytes

GATE
CSE

Data
Structures

Test-04Solutions

DATA STRUCTURES
1. What is the worst-case time complexity of binary insertion sort

algorithm to sort n elements? 1
a) O(n)
b) O(log2n)
c) O(n1.2)
d) O(n2)
2. A list of data items usually words or bytes with the accessing
restriction that elements can be added or removed at one end of
the list only, is called
a) stack
b) memory
d) heap
3. How many PUSH and POP operations will be needed to
evaluate the following expression by reverse polish notation in a
stack machine

(A*B) + (C*D/E)?
a) 4 push and 3 POP instructions
b) 5 Push and 4 POP instructions
c) 6 push and 2 POP instructions
d) 5 Push and 3 POP instructions

1

Solution:
To evaluate postfix expression we need operand stack given
expression is infix, so convert it into postfix. So, resulting
postfix expression:\AB*CD*E /

So, total 5 push and 9 POP, we can reduce POP since keep one
operand in separation register, so, can be answer but if 5 push
and 8 POP given then ‘b’ is wrong
4. A computer program selects an integer in the set {k: 1 < k< 10,
00,000} at random and prints out the result. This process is
repeated 1 million times what is the probability that the value k=
1 appears in the Printout at least once?
a) 05
b) 0.704
c) 0.632121
d) 0.68
Solution:
Probability that the value k = 1 appears in the print out at least
once = 1‒ Appear none time

= 1‒ 0 �1 − 1106�
=1‒ �991909699�106 = 1‒ 0.36788 = 0.632121

2

5. When an array is passed as parameter to a function, which of the
following statements is correct?
a) The function can change values in the original arrays
b) ln C, parameters are passed by value, the function cannot
change the original value in the array
c) Lt results in compilation error when the function tries to
access the elements in the array
d) Results in a run time error when the function tries to access
the elements in the array
Solution:
When we passing an array in C, we will pass it by reference so,
whatever changes we made is called function that will be
reflected in calling function

6. Access time of the symbolic table will be logarithmic if it is
implemented by
a) Linear list
b) Search tree
c) Hash table
d) Self-organization list
Solution:
Search trees like "B-tree search", "AVL search", will take
logarithmic search time.

3

7. The infix expression A + (B – C)*D is correctly represented in
prefix notation as 4
a) A+B- C*D
b) +A*‒ BCD
c) ABC ‒ D*+
d) A + BC – D*
Solution:
Given infix expression: A + (B – C) ×D
A + ‒BC × D
A+ × – BCD
+A+ × – BCD

8. We can make a class abstract by
a) Declaring it abstract using the virtual keyword
b) Making at least one member function as virtual function
c) Making at least one member function as pure virtual function
d) Making all member function const.
Solution:
We can make a class abstracted by making at least one member
function as pure virtual function. A pure virtual is a virtual
function which does not have any sort of implementation, they
just can be declared.

4

9. What is the output of the following C code?
#include
#include
void main()
{
int index;
for(index = 1; index < = 5; i++)
{
printf(“%d”, index);
if(i = =3)
Continue;
}
}

a) 1245
b) 12345
c) 12245
d) 12354
Solution:
At each iteration of the for loop, the value of 'i' will be printed.
Since, 'continue' is the last line of the code, hence it will not skip
any number.

5

10. In a linked list implementation of a queue with two pointers:
front and rear, the time needed to insert element in a queue of
length n is
a) O(1)
b) O(log2n)
c) O(n)
d) O(n log2n)

11. The correct way to round off a floating number to an integer
value is
a) y = (int) (x + 0.5)
b) y = int(r + 0.5)
c) y = (int)r + 0.5
d) y = (int)((int)r + 0.5)
Solution:
For positive floating point values, the simplest way to chive a
rounding conversion is to use expression
(int) (x +0.5)

12. Below is the precedence graph for a set of tasks to be executed
on a parallel processing system S.

6

What ls the efficiency of this precedence graph on S if each of
the tasks T1, ...., T8 takes the same time and the system S has
five processors?
a) 25%
b) 40%
c) 50%
d) 90%
Solution:
There are total five processors and 8 tasks to be finished as per
the precedence graph.
13. if we have six stack operations-pushing and popping each of
A, B and C-such that push (A) must occur before push (B)
which must occur before push (C), then A, C, B is a possible
order for the pop operations, since this could be our sequence:
push (A), pop (A), push (B), push (C), pop (C), pop (B)Which
one of the following orders could not be the order the pop
operations are run, if we are to satisfy the requirements
described above?
a) ABC
b) CBA
c) BAC
d) CAB
Solution:

7

(a) PUSH (A), POP, PUSH (B), POP, PUSH(c), POP
(b) PUSH(A), PUSH(B), PUSH(c), PUSH, POP, POP
(c) PUSH (A), PUSH(B), POP, POP,PUSH(c), POP
(d) Can not possible , because after POP of C either none

element to be popped or only B can be popped
14. The data structure needed to convert infix notations to postfix

notations is
a) Linear list
b) Queue
c) Tree
d) Stack
15. In a linked list of n elements, what is the time taken to insert an
element after an element pointed by some pointer?
a) O(1)
b) O(log2n)
c) O(n)
d) O(n log2n)
16. The maximum degree of any vertex in a simple graph with n
vertices is
a) n
b) n – 1
c) n + 1
d) 2n – 1

8

17. The time required to search on element in a binary search tree

having n elements is
a) O(1)
b) O(log2n)
c) O(n)
d) O(n log2n)
18. Number of children it can have. Suppose that block size is 1
kilobytes, the child pointer takes 7 bytes long and search field
value takes 14 bytes long the order of the leaf node is-________
a) 16
b) 63
c) 64
d) 65
Solution:

In B++tree;
For leaf node: order = Maximum number of pointers

So, P-1(key) + P(B) ≤ Block size
P-1 (14) B + P(7p) ≤ 1KB
P-1 (14) + P(7B) ≤ 1024
21P – 4 ≤ 1024
21P ≤ 1024 +14

P ≤ �120138� = 49, So, answer is none of these

9

19. Consider the following statements for priority queue:
S1: it is a data structure in which the in trans ordering of the
elements does determine the result of rts basic operations.
S2: The elements of a priority queue may be complex structures
that are ordered on one or several fields.
Which of the following is correct?
a) Both S1, and S2, are incorrect.
b) S1 is correct and S2, is incorrect.
c) S1 is incorrect and S2, is correct.
d) Both S1, and S2, are correct.
Solution:
A priority queue is a data structure in which the intrinsic
ordering of the elements determines the results of its basic
operations there are two types of priority queues:
Ascending order and descending order priority queues, the
elements of a priority
Queue need not be numbers or characters that can be compared
directly; they may be complex structures that are ordered on one
or several fields

20. ln XML we can specify the frequency of an element by using
the symbols:
a) +. !
b) #. !
c) +.?

10

d) -.?

Solution:

character Meaning

+ The element can occur one or more time

* The element can occur zero or more time

? The element can occur zero or one time

21. What is the value returned by the function f given Below when

n = 100?

int f (int n)

{

if (n ‒ ‒ 0) then return n;

else

return n + f(n ‒ 2);

}

a) 2550

b) 2556

c) 5220

d) 5520

Solution:

The given function is a recursive function which takes

starting value as 100. It keeps on adding the present value and

the value obtained by calling the function f(n-2) where n is

current value. it stops at n =0 where it returns 0. As a result, it

11

forms a arithmetic series, where a = 100 and d = 2 and l = 2 so

sum of series is

100 = ( 1+ ) = 50(2+100) = 2550
2 2

22. Which of the following statements regarding the features of the

object-oriented approach to databases are true?

(i) The ability to develop more realistic models of the real

world.

(ii) The ability to represent the world in a non-geometric way.

(iii) The ability to develop databases using natural language

approaches.

(iv) The need to split objects into their component parts.

(v) The ability to behaviour.

a) (i), (ii) and (iii)

b) (ii), (iii) and (iv)

c) (i), (iv) and (v)

d) (iii), (iv) and (v)

Solution:

Oop (object oriented programming) can be used to associate real

word objects and processes with digital counter parts. In

addition to potentially mirroring real- world relationship in an

intuitive way only statements (i), (ii) and (iii) are true.

12

23. Consider the following Java code fragment.
Line Code statement
1. Public class while
2. {
3. Public void loop()
4. {
5. Int x = 0
6. While (i)
7. {
8. System.out.println(“x plus one is” +(x + 1));
9. }
10. }
11. }

Which of the following statements is true?
a) There is syntax error in line no. 1
b) There is syntax errors in line nos. 1 & 6
c) There is syntax error in line no. 8
d) There is syntax error in line no. 6
Solution:
In Java language, while (1) will give compiler time error as it
treats as type mismatch to convert from integer to Boolean
value.

13

24. The Unix Kernel maintains two key data structures related to
processes, the process table and the user structure. Which of the
following information is not the part of user structure?
a) File descriptor table
b) System call state
c) Scheduling parameters
d) Kernel stack

25. The process of accessing data stored in a tape is similar to
manipulating data on
a) stack
b) queue
c) list
d) heap

26. Which of the following algorithm design technique is used in
the quick sort algorithm?
a) Dynamic programming
b) Backtracking
c) Divide and conquer
d) Greedy method

14

27. Loop unrolling is a code optimization technique: 4
a) that avoids tests at every iteration of the loop.
b) that improves performance by decreasing the number of
instructions in a basic block.
c) that exchanges inner loops without loops.
d) that reorders operations to allow multiple computations to
happen in para
Solution:
Loop unrolling is used to reduce the number of jump and
branch instructions which could potentially make the binary
dependency on the implementation and platform, either could
be faster

28. Which one of the following is correct about the statements
given below? 2o 3
I. All function calls are resolved at compile time in C lang

II. All function calls are resolved at compile time in C++
language

a) Only II is correct
b) Both I and II are correct
c) Only I is correct
d) Both I and II are incorrect

15

Solution:
Branch address is not known at compile time so all function call
is not resolved at compile time. Because branch address are
known at runtime in both C and C++ (in branch condition)
29. The following 'C' statement:

int * f [] ();
declares:
a) A function returning a pointer to an array of integers.
b) Array of functions returning pointers to integers.
c) A function returning an array of pointers to integers.
d) An illegal statement
Solution:
Int*f [ ] ( ) represents array of functions returning pointers to
integers
Int*f ( ) [ ] represents a function returning a pointer to an array
of integers
30. Which one of the following array represents a binary max-
heap?
a) [26, 13, 17 , 14, 11 , 9, 15]
b) [26, 15, 14, 17, 11 , 9, 131
c) [26, 15,17,14, 11, 9,13]
d) [26, 15, 13, 14, 11 , 9,17]