Data Structures B

1. What is Non-linear data structure

Tree

Stack

Linked-list

Array

2. In linked lists there are no NULL links in

Single linked list

Linear doubly linked list

Circular linked list

None of these

3. In a stack the command to access nth element from the top of the stack S will be

S [Top-n]

S [Top+n]

S [Top-n-1]

None of the above

4. In a balance binary tree the height of two sub trees of every node can not differ by more than

2

1

0

3

5. A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of

2 deletion and 3 additions

3 deletions and 2 additions

3 deletions and 3 additions

3 deletions and 4 additions

6. Following sequence of operation is performed on a stack. Push(1), Push(2), Pop, Push(1), Push(2), Pop, Pop, Pop, Push(2), Pop. The sequences of popped out values are

2,2,1,2,2

2,2,1,1,2

2,1,2,2,1

2,1,2,2,2

7. A binary tree in which every non-leaf node has non-empty left and right sub trees is called a strictly binary tree. Such a tree with 10 leaves

Has 19 nodes

Has 16 nodes

Has 15 nodes

None of the above

8. Depth of a binary tree with n node is

Log (n +1) - 1

Log (n)

Log (n -1)n -1

Log (n) + 1

9. Average successful search time for sequential search on 'n' item is

N/2

(n-1)/2

(n+1)/2

Log (n) + 1

10. Running time T(n), where 'n' is input size of recursive algorithm is given as follows:
T(n) = c + T(n-1), if n>1,
T(n) = d if n<1. The order of algorithm is

N2

N

N3

Nn

11. Four algorithm A1, A2, A3, A4 solves a problem with order log(n), log log(n), nlog(n), n. Which is best algorithm

A1

A2

A3

A4

12. Arranging a pack of cards by picking one by one is an example of

Bubble sort

Selection sort

Insertion sort

Merge sort

13. In evaluating arithmatic expression 2*3-(4+5) using postfix stack form. Which of the following stack configuration is not possible

-------Top--| 4 | 6 |------------

------Top--| 5 | 4 | 6 |------------

-------Top--| 9 | 6 |------------

------Top--| 9 | 3 | 2 |------------

14. To arrange the books of library the best method is

Bubble sort

Quick sort

Merge sort

Heap sort

15.
The information about an array used in a program will be stored in

Symbol table

Dope vector

Register vector

Activation table

16. In which of the following cases linked list implementaion of sparse matrices consumes same memory as a normal array

5 x 6 matrix with 9 non-zero entries

5 x 6 matrix with 8 non-zero entries

6 x 5 matrix with 8 non-zero entries

6 x 5 matrix with 9 non-zero entries

17. On which principle does stack work?

FILO

FIFO

LIFO

Both a and c above

18. The Worst case occur in linear search algorithm when

Item is somewhere in the middle of the array

Item is not in the array at all

Item is the last element in the array

Item is the last element in the array or is not there at all

19. Arrays are best data structures

For relatively permanent collections of data

For the size of the structure and the data in the structure are constantly changing

For both of above situation

For none of above situation

20. Linked lists are best suited

For relatively permanent collections of data

For the size of the structure and the data in the structure are constantly changing

For both of above situation

For none of above situation

21. The elements of an array are stored successively in memory cells because

The architecture of computer memory does not allow arrays to store other than serially

Both of above

None of above

22. Under which condition circular queue is Full

Front=-1

Front=(rear+1)%maxsize

Front=(front+1)%maxsize

Rear=(rear+1)%maxsize

23. A leaf node have degree

1

2

0

3

24. The value of structure is resizing during run time by using

Malloc

Calloc

Free

Realloc

25. How many types of queue's are available

0

1

2

4

26. Disadvantage of linear queue is overcome by using

Link list

Circular queue

Stack

Double ended queue

27. The result of evaluating prefix expression /b+dacd, where a=3, b=6, c=1, d=5 is

0

5

10

15

28. In array representation of binary tree the right child of root will be at location of

2

5

3

0

29. The total number of comparisons in a bubble sort is

O(n logn)

O(2n)

O(n2)

None of above

30. Number of possible ordered trees with 3 nodes A,B,C is

16

12

6

10

31. Number of swapping, operations need to sort numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort

11

12

13

14

32. To arrange a binary search tree in ascending order we need

Post order traversal

Inorder traversal

Preorder traversal

None of above

33. Which is not application of stack

Reversal of string

Evaluation of arithimatic operation

Real operating system

Recursion

34. The dummy header in linked list contain

First record of the actual data

Last record of the actual data

Pointer to the last record of the actual data

None of above

35. Hash function f is defined as f(key) = key mod 7. If linear probing is used to insert the key 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6, 11 will be stored at the location

3

4

5

6

36. An algorithm consists of two modules X1, X2. Their order is f(n) and g(n), respectively. The order of algorithm is

Max(f(n),g(n))

Min(f(n),g(n))

F(n)+g(n)

F(n)*g(n)

37. The order of binary search algorithm is

N

N2

N log n

Log n

38. A hash tabale with 10 buckets with one slot per bucket is depicted in following diagram. Symbols S1 to S7 are initially entered using a hashing function with linear probing. Maximum number of comparisions needed in searching an item that is not present is

4

5

6

3

39. Average successful search time taken by binary search on sorted array of 10 items is

2.6

2.7

2.8

2.9

40. Bib O notation w.r.t algorithm signifies

It decides the best algorithm to solve a problem

It determines maximum size of a problem, that can be solved in given system in given time

It is the lower bound of growth rate of algorithm

None of the above

Data Structures B

1. What is Non-linear data structure

2.

What first name or nickname would you like us to use?

2. In linked lists there are no NULL links in

3. In a stack the command to access nth element from the top of the stack S will be

4. In a balance binary tree the height of two sub trees of every node can not differ by more than

5. A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of

6. Following sequence of operation is performed on a stack. Push(1), Push(2), Pop, Push(1), Push(2), Pop, Pop, Pop, Push(2), Pop. The sequences of popped out values are

7. A binary tree in which every non-leaf node has non-empty left and right sub trees is called a strictly binary tree. Such a tree with 10 leaves

8. Depth of a binary tree with n node is

9. Average successful search time for sequential search on 'n' item is

10. Running time T(n), where 'n' is input size of recursive algorithm is given as follows:T(n) = c + T(n-1), if n>1,T(n) = d if n<1. The order of algorithm is

11. Four algorithm A1, A2, A3, A4 solves a problem with order log(n), log log(n), nlog(n), n. Which is best algorithm

12. Arranging a pack of cards by picking one by one is an example of

13. In evaluating arithmatic expression 2*3-(4+5) using postfix stack form. Which of the following stack configuration is not possible

14. To arrange the books of library the best method is

15. The information about an array used in a program will be stored in

16. In which of the following cases linked list implementaion of sparse matrices consumes same memory as a normal array

17. On which principle does stack work?

18. The Worst case occur in linear search algorithm when

19. Arrays are best data structures

20. Linked lists are best suited

21. The elements of an array are stored successively in memory cells because

22. Under which condition circular queue is Full

23. A leaf node have degree

24. The value of structure is resizing during run time by using

25. How many types of queue's are available

26. Disadvantage of linear queue is overcome by using

27. The result of evaluating prefix expression */b+*dacd, where a=3, b=6, c=1, d=5 is

28. In array representation of binary tree the right child of root will be at location of

29. The total number of comparisons in a bubble sort is

30. Number of possible ordered trees with 3 nodes A,B,C is

31. Number of swapping, operations need to sort numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort

32. To arrange a binary search tree in ascending order we need

33. Which is not application of stack

34. The dummy header in linked list contain

35. Hash function f is defined as f(key) = key mod 7. If linear probing is used to insert the key 37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6, 11 will be stored at the location

36. An algorithm consists of two modules X1, X2. Their order is f(n) and g(n), respectively. The order of algorithm is

37. The order of binary search algorithm is

38. A hash tabale with 10 buckets with one slot per bucket is depicted in following diagram. Symbols S1 to S7 are initially entered using a hashing function with linear probing. Maximum number of comparisions needed in searching an item that is not present is

39. Average successful search time taken by binary search on sorted array of 10 items is

40. Bib O notation w.r.t algorithm signifies

10. Running time T(n), where 'n' is input size of recursive algorithm is given as follows:
T(n) = c + T(n-1), if n>1,
T(n) = d if n<1. The order of algorithm is

15.
The information about an array used in a program will be stored in

27. The result of evaluating prefix expression /b+dacd, where a=3, b=6, c=1, d=5 is