Data Structures 01

1. Which of the following permutations can be obtained in the output using a stack of size 3 elements assuming that input, sequence is 1, 2, 3, 4, 5?                [Paper III December 2012]

(A) 3, 2, 1, 5, 4

(B) 5, 4, 3, 2, 1

(C) 3, 4, 5, 2, 1

(D) 3, 4, 5, 1, 2

2. Suppose there are log_n sorted lists of n log_n elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)             [Paper III December 2012]

(A) O (n log log_n)

(B) θ (n log_n)

(C) Ω (n log_n)

(D) Ω (n^3/2)

3. Which of the following data structure is Non-linear type?         [Paper II Dec 2011]

 (A) Strings          (B) Lists

 (C) Stacks          (D) None of the above

4. The total number of comparisons in a bubble sort is:                [Paper II Dec 2011]

 (A) 0(log n)                (B) 0(n log n)

 (C) 0(n)                     (D) None of the above

5. Which of the following is a bad example of recursion?          [Paper II Dec 2011]

 (A) Factorial                        (B) Fibonacci numbers

 (C) Tower of Hanoi             (D) Tree traversal

6. The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.

(A) ABFCDE              (B) ADBFEC

(C) ABDECF              (D) ABDCEF

7. B + tree are preferred to binary tree in database because

(A) Disk capacities are greater than memory capacities

(B) Disk access much slower than memory access

(C) Disk data transfer rates are much less than memory data transfer rate

(D) Disk are more reliable than memory

8. The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to

(A) 2⁰ + 2¹ + ….. 2^h

(B) 2⁰ + 2¹ + ….. 2^{h – 1}

(C) 2⁰ + 2¹ + ….. 2^{h + 1}

(D) 2¹ + ….. 2^{h + 1}

9. Number of binary trees formed with 5 nodes are             [Paper III June 2012]

(A) 32              (B) 36

(C) 120            (D) 42

10. The following postfix expression is evaluated using a stack 823^/23* + 51* –

The top two elements of the stack after first * is evaluated   [Paper III June 2012]

(A) 6, 1            (B) 5, 7

(C) 3, 2            (D) 1, 5

SOLUTIONS

1. A, C (UGC Agrees only C!)

Above sequences can be obtained by the following sequence of operations

A: Push 1, Push 2, Push 3, Pop 3, Pop 2, Pop 1, Push 4, Push 5, Pop 5, Pop 4

C: Push 1, Push 2, Push 3, Pop 3, Push 4, Pop 4, Push 5, Pop 5, Pop 2, Pop 1

2. A

3. D

4. D

Bubble sort has worst-case and average complexity both О(n²)

5.

6.

7.

8. A

In a binary tree of height h the total number of nodes is at most 2⁰ + 2¹ + ….. 2^h   =   2^{h + 1} – 1

A binary tree is a complete binary tree, when it has maximum number of nodes.

9. D
Let C(n) be the number of distinct binary trees with n nodes, Then:

C(n) =

so for n=5, C(n) = 10! / (6!)5! = 42

10. A
The evaluation is as follows:
Step       Symbol               Action                                                Stack
1.                8           Push 8 on to stack                                        8,
2.                2           Push 2 on to stack                                        8, 2
3.                3           Push 3 on to stack                                        8, 2, 3
4.                ^           Pop 2, 3. Find 2^3, Push result on to stack   8, 8
5.                /            Pop 8, 8. Find 8/8, Push result on to stack    1
6.                2           Push 2 on to stack                                        1, 2
7.                3           Push 3 on to stack                                        1, 2, 3
8.                *           Pop 2, 3. Find 2*3, Push result on to stack   1, 6