# Data Structures Test - 4 - PDF Flipbook

Data Structures Test - 4

226 Views

54 Downloads

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)

Answer: (d)

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

c) linked list

d) heap

Answer: (a)

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

Answer: (b)

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

Answer: (c)

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

Answer: (a)

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

Answer: (b)

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*

Answer: (b)

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.

Answer: (c)

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

Answer: (b)

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)

Answer: (a)

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)

Answer: (a)

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%

Answer: (b)

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

Answer: (d)

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

Answer: (d)

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)

Answer: (a)

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

Answer: (b)

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)

Answer: (b)

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

Answer: (a)

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.

Answer:(d)

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) -.?

Answer: (c)

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

Answer: (a)

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)

Answer: (a)

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

Answer: (d)

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

Answer: (c)

25. The process of accessing data stored in a tape is similar to

manipulating data on

a) stack

b) queue

c) list

d) heap

Answer: (b)

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

Answer: (c)

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

Answer: (a)

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

Answer: (d)

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

Answer: (b)

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]

Answer: (c)

16

Solution:

A max heap is a complete binary tree in which the value in each

internal node is greater than or equal to the values in the

children of that node

17

Data Loading...