Data Structures B

1. 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

2. 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

3. 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

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

Bubble sort

Selection sort

Insertion sort

Merge sort

5. 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 |------------

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

Bubble sort

Quick sort

Merge sort

Heap sort

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

Symbol table

Dope vector

Register vector

Activation table

8. 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

9. On which principle does stack work?

FILO

FIFO

LIFO

Both a and c above

10. In linked lists there are no NULL links in

Single linked list

Linear doubly linked list

Circular linked list

None of these

11. 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

12. 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

13. 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

14. Under which condition circular queue is Full

Front=-1

Front=(rear+1)%maxsize

Front=(front+1)%maxsize

Rear=(rear+1)%maxsize

15. A leaf node have degree

1

2

0

3

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

Malloc

Calloc

Free

Realloc

17. How many types of queue's are available

0

1

2

4

18. Disadvantage of linear queue is overcome by using

Link list

Circular queue

Stack

Double ended queue

19. What is Non-linear data structure

Tree

Stack

Linked-list

Array

20. 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

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

2

1

0

3

22. Depth of a binary tree with n node is

Log (n +1) - 1

Log (n)

Log (n -1)n -1

Log (n) + 1

23. 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

24. 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

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

N/2

(n-1)/2

(n+1)/2

Log (n) + 1

26. 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

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

0

5

10

15

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

Post order traversal

Inorder traversal

Preorder traversal

None of above

29. Which is not application of stack

Reversal of string

Evaluation of arithimatic operation

Real operating system

Recursion

30. 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

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

16

12

6

10

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

2

5

3

0

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

O(n logn)

O(2n)

O(n2)

None of above

34. The order of binary search algorithm is

N

N2

N log n

Log n

35. 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

36. 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

37. 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)

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. The Worst case occur in linear search algorithm when

2.

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

2. 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

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

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

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

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

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

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

9. On which principle does stack work?

10. In linked lists there are no NULL links in

11. Arrays are best data structures

12. Linked lists are best suited

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

14. Under which condition circular queue is Full

15. A leaf node have degree

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

17. How many types of queue's are available

18. Disadvantage of linear queue is overcome by using

19. What is Non-linear data structure

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

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

22. Depth of a binary tree with n node is

23. 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

24. 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

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

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

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

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

29. Which is not application of stack

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

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

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

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

34. The order of binary search algorithm is

35. The dummy header in linked list contain

36. 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

37. An algorithm consists of two modules X1, X2. Their order is f(n) and g(n), respectively. The order of 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

2. 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

7.
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