DATA STRUCTURES

Data Structure Quiz 3

1. Pick the odd one out
a. Composite data type b. User defined data type c. stack d.Array
2. No. of elements in the array A[-2:5, -1:5, 0:5] is
a. 48 b. 125 c. 336 d. 512
3. Pick the odd one out
a. Counting sort b. Bucket sort c. Shell Sort d. Radix sort
4. The complexity of merge operation on two sorted arrays of size m & n (given m > n)
a. O(mn) b. O(m+n) c. O(m/n) d. O(m)
5. Pick the odd one out
a. Random Value b. Return Address c. Local variable space d. Global variable space
6. The function for which among the following will not be linear recursion
a. Factorial b. Fibonaci Series c. ab d. sum of the natural numbers
7. The Order followed by stack data structure is
a. Random b. FIFO c. LIFO d. None
8. How many stack will be needed for the evaluation of a prefix expression
a. 1 b. 2 c. 0 d. 3
9. If the two stacks are implemented on a single array, the overflow occurs at
a. top1=top2 b. top1=top2-1 c. top1-1=top2 d. none of these
10. If PRCD(x,y) is a function that returns TRUE is x has higher precedence that y or if x has the same precedence as that of y but left associative. A call for PRCD($,$) will return ($ is exponentiation)
11. No. of steps needed for transfer of n disks from Tower A to Tower B using Tower C in the Tower of Hanoi problem is
a. 2n b. 2n – 1 c. 2n+1 d. 2n-1
12. Which item is selected in the first partition of Set by quick sort if pivot element is first element?
a. D b. A c. C d. T
13. The array set after the Heapify heap operation changes to
…………………………………
14. What is the reason for selection of prime no in the division method of hashing?
………………………………….
15. The evaluated value of POSTFIX EXPRESSION 4 3 * 4 2 / - 3 2 $ 2 * + is ………………
16. a if a=b
gcd(a,b)= gcd(a-b, b) if a>b
gcd(a,b-a) if b>a

gcd(27,15)is ………………….
17. Match the elements of Table 1 with 2
Table 1 Table 2
a) Bubble Sort (Best case) i) O(n2)
b) Heap sort ii) O(nlog2n)
c) Quick sort (Worst case) iii) O(1)
d) Binary Search (worst case) iv) O(n)

18. The average number of probes required for successful search on Hash Table with 12 slots and Linear probing method for collision resolution with the following records is ………………..
19. Postfix Equivallent of A$B$C$D$E is
a. ABCDE$$$$ b. AB$C$D$D$E$ c. abc$$DE$$ d. ABCD$$$E$
20. How many calls for f(3) will be made for the following recurrence in the call of f(8)
0 n=1
f(n) = 1 n=2
f(n-1)+f(n-2) n>2
a. 7 b. 6 c. 5 d. 8

21. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
22. Which of the following applications may use a stack?
A. A parentheses balancing program.
B. Keeping track of local variables at run time.
C. Syntax analyzer for a compiler.
D. All of the above.
23. Consider the following pseudocode:
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
write the stack's top character to the screen
pop a character off the stack
}
What is written to the screen for the input "carpets"?
A. serc
B. carpets
C. steprac
D. ccaarrppeettss
24.
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
Which of these unbalanced sequences does the above code think is balanced?
A. ((())
B. ())(()
C. (()()))
D. (()))()

25. Here is an infix expression: 4+3*(6*3-2). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
A. 1
B. 2
C. 3
D. 4
E. 5


Answers:
1. d
2. c
3. c
4. b
5. d
6. b
7. b
8. c
9. a & b both
10. FALSE
11. b
12. a
13. V T L S R E I A O K
14. to avoid the collision
15. d
16. 3
17. a-iv b-ii c-i d-iii
18. 15/9
19. a
20. a
21. Polish and Reverse Polish notations.
22. d
23. c
24. b
25. d