Data Structures Test - 3

490 Views
93 Downloads
PDF 4,393,827 Bytes

GATE
CSE

Data
Structures

Test-03Solutions

DATA STRUCTURES
1. In what order, the elements of a pushdown stack are accessed?

a) First In First Out (FIFO)
b) Last In Last Out (LILO)
c) Last In First Out (LIFO)
d) None of these
Answer: (c)
2. Which of the following is useful in implementing quick sort?
a) Stack
b) List
c) Set
d) Queue
Answer: (a)
3. What is the worst-case time complexity of straight insertion sort
algorithm to sort n elements?
a) O(n)
b) O(log2n)
c) O(n1.2)
d) O(n2)
Answer: (d)
4. in a dot matrix printer, the time to print a character is 6 m sec,
time to space in between characters is 2 m sec, and the number
of characters in a line are 200. The printing speed of the dot
matrix printer in characters per second and the time to print a
character line are given by which of the following options?

1

a) 125 chars / second and 0.8 seconds

b) 250 chars / second and 0.6 seconds

c) 166 chars / second and 0.8 seconds

d) 250 chars / second and 0.4 seconds

Answer: (a)

Solution:

Time to print a character = 6+2 = 8 msec

Number of characters in the line =200

Time to print character line = 200*8 =1600msec =1.6 seconds

Printing speed in characters per second = 200
1.6

= 125 characters/second

5. Which of the following sorting methods sorts a given set of

items that is already in order or in reverse order with equal

speed?

a) Heap sort

b) Quick sort

c) Insertion sort

d) Selection sort

Answer: (b)

6. Which of the following sorting procedure is the slowest?

a) Quick sort

b) Heap sort

c) Shell sort

d) Bubble sort

Answer: (d)

2

7. Consider an array A [20, 1O], assume 4 words per memory cell
and the base address of array A is 100. What is the address of A
[11, 5]? Assume row major storage
a) 560
b) 565
c) 570
d) 575
Answer: (a)
Solution:
Addressing of 2D array = Base address + (Row*# column size
+Col)*e
LOC(A[11][5]) = 100 + (11*10 + 5) *4 = 560

8. The for loop
for (i = 0; i < 10; ++i)
printf("%d", i&1);
prints

a) 0101010101
b) 0111111111
c) 0000000000
d) 1111111111
Answer: (a)
Solution:
The operation is ‘Bitwise AND operations’
0000 & 0001 = 0
0001 & 0001 = 1

3

0010 & 0001 = 0
0011 & 0001 = 1
0100 & 0001 = 0
0101 & 0001 = 1
0110 & 0001 = 0
0111 & 0001 = 1
1000 & 0001 = 0
1001 & 0001 = 1
Hence, the output is 01010101
9. Consider the following pseudo-code:

if (A > 8) and (C > D) then
A = A+1
B = B+1
Endif

The cyclamate complexity of the pseudo-code is
a) 2
b) 3
c) 4
d) 5
Answer: (b)
Solution:
Cyclomatic complexity directly measures the number of
linearly independent paths though a program’s resource code:

Given, if (A >B) and (C >D) then
A = A+1

4

B = B+1
End if
case (i): if (true) and (true) then
//execute some code
end if
case (ii): if (true) and (false) then
//don’t execute some code
end if
case (iii): if (false) and (2nd part won’t be exicuted) then
//don’t execute code
end if
so cyclomatic complexity will e 3
10. In what type of storage structure for string, one can easily
insert, delete, concatenate, and rearrange substrings?
a) Fixed length storage structure
b) Variable length storage with fixed maximum
c) Linked list storage
d) Array type storage
Answer: (c)
11. ln Unix operating system, special files are used to
a) buffer data received in its input from where a process reads
b) provide a mechanism to map physical device to file names
c) store list of file names plus pointers associated with i-nodes
d) store information entered by a user application program or
utility program

5

Answer: (b)

Solution:

UNIX file system, six types of files are distinguished

Special: contains no data, but provides a mechanism to map

physical devices file names. The file names are used to access

peripheral devices, such as terminals and printers

1) Named pipes

2) Links

3) Symbolic links

4) Regular or ordinary

5) Directory

Option defines: (a) Named pipes (b) special, (c) Directory and

(d) regular or ordinary

12. Given two spatial masks

010 111
1 = �1 −4 0�and 2 = �1 −8 1�

010 111

The Laplacian of an image at all points (r, y) can be

implemented by convolving the image with spatial mask. Which

of the following can be used as the spatial mask?

a) only S,

b) only S,

c) Both S, and S,

d) None of these

Answer: (b)

6

13. Queue can be used to implement

a) radix sort

b) quick sort

c) recursion

d) depth first search

Answer: (a)

14. Which of the following is NOT represented in a subroutine's

activation record frame for a stack-based programming

language?

a) Values of local variables

b) Return address

c) Heap area

d) Information needed to access non-local variables

Answer: (c)

Solution:

Heap area is not represented in a subroutine’s activation record

frame for a stack-based programming language because if we

create memory dynamically it would be created in the heap area.

So, if we exit from the function without free ( ) the dynamically

created node, it would be still persisting in the heap area.
15. Given an open address hash table with load factor < 1, the

expected number of probes in a successful search is

a) At most 1 in �(1− )�

b) At most 1 in �1(−1) �

7

c) At most 1 in �1(−1) �

d) At most 1 in �1(− ) �

Answer:(b)

Solution:
Theorm: given an open address hash table with load factor ∝ =

n/m

Data Loading...

Data Structures Test - 3 - PDF Flipbook