Data Structure Quiz

Data Structure Quiz

1. A 3-D row major order array A [1:u1, 1:u2, 1:u3] has the base address α. If every element occupies n words of m/y, find the address of the element A [i, j, k].

2. Which among the following doesn’t work like a stack
a. Browsing the Internet
b. Opening the multiple windows
c. Playing the multistage game
d. Undo in the text editor

3. If the expression A + (B * C * (D /E ↑ F)) were converted to postfix equivalent using stacks, No of Push & Pop operations required will be …………….

4. Use the Ackerman’s function given below to find the value of A(2,2)
A(m,n) = n+1 if m=0
A(m,n) = A(m-1, 1) if m! = 0, n = 0
Am,n) = A(m-1, A(m, n-1)) if m!= 0, n! = 0

5. If a double ended queue is Input restricted as well as Output restricted, it becomes
a. Linear queue
b. Priority queue
c. Circular queue
d. It does not behave like a queue

6. If a circular linked list of size n were broken from the mid to form two different linked list of approximately the same length, effort required for the same will be
a. O(n)
b. O(1)
c. O(nlogn)
d. O(n2)

7. Dynamic implementation of linked list is preferred than array representation (static) because the former makes the efficient m/y utilization. However there are some situation like ………………, in which static implementation is also preferred.
a. Distributed system
b. Networked system
c. Real time system
d. None of these

8. Linked implementation of a particular graph occupies …………. m/y than adjacency matrix representation.
a. Equal
b. More
c. Less
d. Less than or equal


9. Linked list can not be applicable for
a. Josephus Problem
b. Procedure Call
c. Calculators
d. Air traffic simulation

10. In the linked representation of polynomials, one header node is also used that contains invalid information. If the structure of a node is as given below, what will be the value of Coef & Exp part?
Coef Exp Next


11. Given an ordered circular list of size n. Insertion of x at the appropriate position in the list requires …………. Time
a. O(n)
b. O(log n)
c. O(1)
d. None of these

12. If two polynomials of degree one & n terms are represented in the form of linked list, the multiply operation of these polynomials requires …………. Time
a. O(n)
b. O(n3)
c. O(nlogn)
d. O(n2)

13. Which of the following statement is false with respect to almost complete binary tree of depth d
a. Any node at level less that d-1 has two child
b. Any node in the tree with a right descendant at level d, must have its left descendant also.
c. Any node in the tree with a left descendant at level d, must have its right descendant also.
d. It can be used in the construction of Binary heap

14. A binary tree with 106 nodes has the minimum depth equal to
a. 10
b. 5
c. 7
d. 6

15. The expression tree for A + (B – C * D / E) ↑ (F * G - H) has depth
a. 4
b. 5
c. 6
d. 7

16. Which among the following is not true for a mirror similar binary trees
a. If one is empty other one is also empty
b. Their left subtrees are mirror similar and right subtrees are also mirror similar to each other
c. Left subtree of one tree is mirror similar to right subtree of the other
d. Right subtree of one tree is mirror similar to left subtree of the other

17. Let a binary search tree contains duplicate numbers. The duplicate numbers are kept on the right subtree of the original. What is the time required to insert such a duplicate value in the binary tree with n nodes
a. O(n)
b. O(nlogn)
c. O(1)
d. O(og n)

18. In the binary tree given below, find which node points to which node using thread


19. Given an algorithm to find the inorder traversal of a binary tree. What changes are required to be made for this algorithm to work for finding no of nodes in the tree?
Inordertraverse(tree)
{
if(tree!=NULL)
{
Inordertraverse(left(tree));
write(info(tree));
Inordertraverse(right(tree));
}
}

20. A set of elements are stored as Binary search tree. Write a sequence of instructions to find the nodes in sorted sequence

21. A binary tree with nodes n (t) is converted to extended binary tree with nodes e (t). What is the relation between n (t) & e (t)?




22. n distinct 3-digit numbers are sorted using Radix sort method. What is the maximum no of queue operations performed for the same
a. 2n
b. 3n
c. 6n
d. n

23. If searching is performed on the ordered table of size n where the keys are uniformly distributed between Key(1) – Key(n), which of the following techniques will require least effort
a. Sequential search
b. Index sequential search
c. Binary search
d. Interpolation search

24. Pick the odd one out
a. Open addressing
b. Separate chaining
c. Linear Hashing
d. Rehashing

25. Pick the odd one out
a. Dijikstra’s Algorithm
b. Ford – Fulkerson’s Algorithm
c. Bellman Ford algorithm
d. Huffman algorithm





Answers

1. α + [(i-1)*u2*u3 + (j-1)*u3 + (k-1)] * n
2. c
3. Push – 7, POP – 7
4. 7
5. c
6. a
7. c
8. b
9. b
10. coef – 0, exp – (-1)
11. a
12. d
13. c
14. c
15. b
16. b
17. d
18.
a. J points to B
b. D points to C
c. I points to A
d. H points to I
e. F points to E
19.
Inordertraverse(tree, static n)
{
if(tree!=NULL)
{
Inordertraverse(left(tree));
n=n+1;
Inordertraverse(right(tree));
}
}
20.
Procedure sorted_BST
1. Find the minimum of the tree using procedure min (let min node is p), print this node
2. Find the inorder successor of node p and print the node
3. Repeat 2 until no inorder successor can be found.

21. e (t) = 2* n (t) + 1
22. c
23. d
24. c
25. d