Data Structures Test - 3 - PDF Flipbook
Data Structures Test - 3
491 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...