Easytolearn: September 2014

UNIT I

1. What is the number of swaps required to sort n elements using selection sort, in the worst case? 1M
(A) O(n)
(B) O(n log n)
(C) O (n^2 )
(D) O (n^2 log n)

2. Which of the following sorting algorithms has the lowest worst-case complexity? 1M
(A) Merge sort
(B) Bubble sort
(C) Quick sort
(D) Selection sort

3. Which one of the following in place sorting algorithms needs the minimum number of swaps? 1M
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort

4. ______________ is an operator in C++.

a) else b) case c) delete d) TRUE

5. How many passes will be performed in radix/bucket sort if ‘n’ numbers are present? 1M

a. N b.n-1 C. number of digits present in largest number of given number. D. None of the above.

6. __________ is not a Software development cycle activity.

a) Coding

b) Workflow

c) Requirement analysis

d) Testing

7. ----- is he operation to be evaluated first in following expression. A+B*C/--B^4

a) B^4 b) - - B c) B*C d)- -B^4

8. Two main measures for the efficiency of an algorithm are a. Processor and memory -1M

a. Complexity and capacity b. Time and space c. Data and space D. none of these

9. What is the worst-case time for merge sort to sort an array of n elements? - 1M

a. O(log n)

b. O(n)

c. O(n log n)

d. O(n²)

10. The time complexity of Bubble sort algorithm is 1M

a. O(n) b. O(log n) c. O(n2) d. O(n log n)

11. The best case time complexity of merge sort algorithm is 1M

a. O(n) b. O(log n) c. O(n2) d. O(n log n)

12. State whether the function is true or false: 10n² + 4n + 2 = O(n²) 1M

A) True B) False C) can’t say D) none of these

13. The datatype for “87654” is 1M

a) integer b)char c)string d)real

14. The Software development cycle will not include 1M

a) Coding b) Search c) Analysis d) Testing

15. External sorting method is 1M

a) Merge sort b) Quick sort c) Radix sort d) Exchange sort

16. The best case time complexity of internal sorting is 1M

a)O(n) b) O(n log n) c) O(n2) d) O(log n)

17. ) The quick sort uses the approach of 1M

i) divide and solve ii) divide and conquer

iii) merging iv) increments

18. Radix sort uses 1M

a) bucket sort b) insertion sort

c) selection sort d) MSD sort

19. The datatype for 2.45E6 is 1M

a) integer b)char c)string d)real

20. The non stable sorting algorithm is 1M

a) quicksort b) merge sort c) makesort d) insertion sort

21. The value of 5MOD 355 is 1M

a) 0 b)3 c)5 d)55

22. The non stable sorting algorithm is 1M

a) quicksort b) merge sort c) makesort d) insertion sort

23. What is wrong if LN is the identifier for last name? 1M

a) It has only 2 characters b) The first letter is capital

c) Is not valid d) Inconsistent name

24) The first pass of quick sort divides the list in to 1M

a) 2 sorted lists

b) 2 unsorted lists

c) 2 sorted elements

d) 2 merged lists

25) The worst case time complexity of merge sort is 1M

a)O(log n) b) O(n) c) O(n2) d) O(n log n)

26) _________ requires additional space for sorting. 1M

a) quicksort b)shell sort

c) merge sort d) radix sort

27) In place sort uses 1M

a) a temporary list b) an extra list

c) original list d) merged list

28) The parallelogram in flowchart stands for 1M

a) input/output b) function

c) flow d) module

29. The internal documentation can be 1M

Help file b) Manual c) Comments d) Search

30. What is the worst-case time for quicksort to sort an array of n elements? 2M

a. O(log n)

b. O(n)

c. O(n log n)

d. O(n²)

31. Merge sort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step? 2M

a. The array elements form a heap.

b. Elements in each half of the array are sorted amongst themselves.

c. Elements in the first half of the array are less than or equal to elements in the second half of the array.

d. None of the above.

32. Suppose we are sorting an array of eight integers using quick sort, and we have just finished the first partitioning with the array looking like this: 2M

2 5 1 7 9 12 11 10

Which statement is correct?

a. A. The pivot could be either the 7 or the 9.

b. B. The pivot could be the 7, but it is not the 9.

c. C. The pivot is not the 7, but it could be the 9.

d. D. Neither the 7 nor the 9 is the pivot.

33. What is the worst-case time for heapsort to sort an array of n elements? 2M

a. A. O(log n)

b. B. O(n)

c. C. O(n log n)

d. D. O(n²)

34. Here is an array of ten integers: 2M

5, 3, 8, 9, 1, 7, 0, 2, 6 4 Draw this array after the FIRST pass of the shell sort (sorting from smallest to largest by considering span for first iteration n/2).

a.5,0,8,6,1,7,3,2,9,4

b.5,0,2,6,1,7,3,8,9,4

c.5,0,2,9,1,7,3,8,6,4

d.5,3,8,6,1,7,0,2,9,4

35. In a bubble sort of n elements, how many times is the swap function called in the complete execution of the algorithm? 2M

a. A. 1

b. B. n - 1

c. C. n log n

d. D. n²

36. Selection sort and quick sort both fall into the same category of sorting algorithms. What is this category? 2M

a. A. O(n log n) sorts

b. B. Divide-and-conquer sorts

c. C. Interchange sorts

d. D. Average time is quadratic.

37. Suppose that a selection sort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)? 4M

a. A. 21

b. B. 41

c. C. 42

d. D. 43

38. The time complexity of shell sort is 2M

^a.n² b.n(logn) c. n(log n)² d.n³

39. Arrange following from lowest to highest order by complexity wise 2M

I log n II. n! III. nlogn IV. n²

^{A. I,II,III,IV B. II, III,I ,IV C}^{I, III,IV,II}^{D. II, I, IV, III}

40. Arrange following from highest to lowest order by complexity wise 2M

I log n II. n! III. nlogn IV. n²

^{A. I,II,III,IV B. II, III,I ,IV C I, III,IV,II D}^{. II, IV, III, I}

41. Suppose that a bubble sort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)? 2M

a. A. 21

b. B. 41

c. C. 42

d. D. 43

42. When is insertion sort a good choice for sorting an array? 2M

a. Each component of the array requires a large amount of memory.

b. Each component of the array requires a small amount of memory.

c. The array has only a few items out of place.

d. The processor speed is fast.

43. What is the complexity of T(n)=T(n/2) + 1 in recursive manner? 2M

O(log n)
O(n log n)
O(n)
O(n^2)

44.

The time factor when determining the efficiency of algorithm is measured by -- 2M a. Counting microseconds b. Counting the number of key operations

c. Counting the number of statements d. Counting the kilobytes of algorithm

45. The space factor when determining the efficiency of algorithm is measured by 2M

a. Counting the maximum memory needed by the algorithm

b. Counting the minimum memory needed by the algorithm

c. Counting the average memory needed by the algorithm

d. Counting the maximum disk space needed by the algorithm

46. What will be the output after first pass of the quick sort for sorting in ascending order by considering first element as pivot element for following data? 2M

8,5,3,2,9,7,12,15

a. 5,3,7,2,8,9,12,15

b.7, 5,3, 2,8,9,12,15

c.8,5,3,2,7,9,12,15

d.12,15,9,7,2,3,8,5

47. If the following is the list to be sorted by radix sort, which bin will have the most number of elements from the list in first pass?

150,270,989,83,97,234, 334, 535, 457, 527,539,667

a) 1

b) 0

c) 5

d)7

a. The value of the expression (A-B) *C+D/A is _____ for A=2, B=4, C=2,D=4

a) -2 b)-4 c) 2 d) 6

b. The expression for the discount of 10% for general product and 40% for books is given by

a) discount= 10/100 *price_book

b) discount= 40/100*book_price

c) discount = 40/100*price_generalproduct

d) discount=book_price-40/100*book_price

c. = stands for __________ operator in the expression, X+C=B+C and its value if X=C=8 and B=4

a) assignment,12

b) relational, FALSE

c) logical, FALSE

d) assignment,0

6) The first pass of shell sort will give the result as (with increment 3) _______for the list 17,34, 56,10,78,45,8

a) 10, 17,34,56,78,45,8

b)8,34,45,10,78,56,17

c)8,34,56,10,78,45,17

d)8,34,56,17,78,45,10

7) The order of evaluation for the expression A*B/C-D+B<A is

a) *,/,-,+,<

b) *,/,<,-,+

c) *,/,+,<,-

d) /,*,<,-,+,<

8) The merging for the non recursive merge sort for pass2 is

a) merging of lists of size 1

b) merging of lists of size 2

c) merging of 2 lists of size 2

d) merging 1 list of size 2

9) The appropriate modules in a structure chart ‘to search for a odd number in a list of numbers’ can be

a) Read, search, check_even, display

b) Read_list, check_odd, display

c)Read_list, search, display

d) ) Read_list, search, check_odd, display

10) The value of expression in C++ for the following expression

x+y*--x/z-- for x=1, y=5, z=9 is

a) 1

b)0.1

c)0

d)1.1

11) The expression for the x+y(7+z) is

--------

x-y

a)x+y*7+z/x-y

b)x+y*(7+z)/x-y)

c)x+y*(7+z)/(x-y)

d) (x+y)*(7+z)/x-y)

12) The following relational expression evaluates to be____ for x=2, y=9,z=1

if(x<y and z==1)

z++;

47.Suppose we are sorting an array of eight integers using heap sort, and we have just finished one of the reheapifications downward. The array now looks like this: 6 4 5 1 2 7 8

How many reheapifications downward have been performed so far? 4M

a. A. 1

b. B. 2

c. C. 3 or 4

d. D. 5 or 6

48. What is the output of following

4*5 -2/(3+3)*9

a. 20 b. 27. c .81 d.1/3

49. Which of the following are stable sorting methods

a. bubble b. Quick c. Merge

A. a & b B. b & c C. a & c D. a, b & c

50. Which of the following are not stable sorting methods

a. bubble b. Quick c. Merge

A. a & b B. b & c C. Only b D. Only a

51. Which of the following are stable sorting methods

a. merge b. Quick c. radix

A. a & b B. Only a C. Only c D. Only b

52. Which of the following are not stable sorting methods

a. merge b. Quick c. radix

A. a & b B. Only b C. B& c D. Only c

53. PAC shows

a. end of problem

b. layout of solution

c. beginning of analysis of problem

d. All above

54. Structure/Iteractivity chart shows

a. end of problem

b. overall layout of solution

c. beginning of analysis of problem

d. All above

55. While solving a problem with computers the term 'solution' means

ñ outcome

ñ result

ñ Set of instructions

ñ all of above

56. ______________ is an operator.

a) if b) case c) new d) TRUE

57. While solving a problem with computers the term 'Result' means

ñ outcome

ñ solution

ñ Set of instructions

ñ all of above

58. ___________ is the first step in Software Development Cycle.

a) Analysis b) Design c) Testing d) Modeling

59. if x is float variable, y is integer variable,what is correct way of getting integer part of x in y?

a. Not possible

b. can't say

c. y = (int)x

d. y = x.int();

60. _____________ is the operation to be evaluated first in following expression.

A+B*C/B^4

a) B^4 b) A+ B c) B*C d) C/B

61. random() is what type of function

a. statistical

b. mathematical

c. utility

d. conversion

62. _____________ is the operation to be evaluated first in following expression.

B*C%B^4

a) B^4 b) C% B c) B*C d) all have same priority

63. Which of the following has equal priority in expression <, <=, > , >=

a. <,>

b. <=,>=

c. <,<=,>,>=

d. <,>=

64. _______ are small sets of instructions that perform specific tasks and return values.

1. Functions

2. Algorithm

3. Expression

4. Equation

65. ______ are combined with constants and variables to create expressions and equations.

(I)Operands (II)Data types (III)Operators

a. All

b. I and III

c. III only

d. II only

66. The tic tac toe problem has algorithmic solution.

a)True b)False c)Can not say d) always

67. Which of the following steps of problem solving can be implemented by computer.

1. Selecting best of the alternatives

2. Understanding the problem

3. Writing instructions

4. Evaluating the solution

68. The three constructs that can be used in algorithm are

1. Sequence, loop, iteration

2. Sequence, loop, block

3. Sequence , if, block

4. Sequence, iteration, decision

69. The balancing cheque book problem has algorithmic solution.

a)True b)False c)Can not say d) No, heuristic

70. What represent the following two symbols

=, ==

a. equality,equality

b. assignment,equality

c. equality, assignment

d. assignment, assignment

71. Variables and constant can be of different data type.

a)True b)False c)Can not say d) No, fixed

72. “XX98” is a ___________ constant.

Interger b) Char c) String c) hex

73. Data set of natural numbers can be

1. All Numbers >0

2. All whole numbers

3. All rational numbers

4. All whole and decimal numbers

74. The variable name , Hours-worked_for gives error because

1. It has operator –

2. It exceeds length

3. It starts with capital alphabet

4. It has character _

75. Logical data types can not have values of

1. TRUE or FALSE

2. Y or N

3. 0 or >0

4. Yes or No

76. Data set of real numbers can be

1. All Numbers >0

2. All whole numbers

3. All rational numbers

4. All whole and decimal numbers

77. Data type for Date can be i)integer ii)float iii)string

1. i only

2. ii only

3. iii only

4. i or ii only

78. Data files are stored in

1. External storage

2. Internal memory

3. Variables

4. Constants

79. Time() function is

1. Mathematical function

2. Statistical function

3. Utility function

4. String function

80. A+B = C(A-D) is equivalent to ________ statement.

----------

1. A=C*(A-D ) /Y

2. B=C(A-D)/Y-B

3. A=C*(A-D)/Y-B

4. B=((C*(A-D))/Y)-A

81. ___________ can be used to represent the algorithm.

1. Problem analysis chart

2. Pseudocode

3. Structure chart

4. Interactivity chart

82. Set up a logical expression to check data using the following criteria. The data is assumed to be correct when:

a. Number is <1000

b. Number is positive

c. Number is divisible by 2

(a) (N<1000)&&(N>0)&&(N MOD 2)

(b) (N<1000)||(N>0)||(N MOD 2)

(c ) (N<1000)&&(N>0)&&NOT(N MOD 2)

(d) (N<1000)||(N>0) ||NOT(N MOD 2)

83. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence

do, where 1 < k <= n:

  reverse (s, 1, k);

  reverse (s, k + 1, n);

  reverse (s, 1, n);

(a) Rotates s left by k positions
(b) Leaves s unchanged
(c) Reverses all elements of s
(d) None of the above

84. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)

A) f3, f2, f4, f1
B) f3, f2, f1, f4
C) f2, f3, f1, f4
D) f2, f3, f4, f1

85. What is frequency count of the following code

float avg(int a[10],int n)

{

int s = 0;

flaot avg;

for(int i=1;i<=n;i++)

s+=a[i];

avg = s/n;

return(avg);

}

a.2n

b.2n+2

c.2n+3

d.2n+4

27. Explain the Asymptotic notations with example - Omega, Theta 4M

· 28. Explain the Asymptotic notations with example - Omega, Sigma 4M

· 29. Explain the Asymptotic notations with example - Theta, Sigma 4M

· Write an algorithm for Quick Sort. Also explain its time complexity for best case, worst case & average case. --- 8M

· Write an algorithm for Merge Sort algorithm. Draw the tree structure of the recursive calls made. ---8M

· Describe a case where quicksort will result in quadratic behavior. 8M

· Here is an array apply quicksort on it & show step by step output. ---8M

§ 3, 0, 2, 4, 5, 8, 7, 6, 9

· Write an algorithm for to describe a heapsort & explain with example -8M

· Fill in the following table for the times to sort an array of n items. Use only big-O notation, and do not have any extraneous constants in your expressions.

	Worst Case	Average Case
Binary search of a sorted array	.	.
Insertion sort	.	.
Merge sort	.	.
	.	.
Quick sort with "median of three" pivot selection	.	.
Selection sort	.	.
Heap sort	.	.

· Suppose that you implement quicksort nonrecursively using a stack, as in your last programming assignment. You use your algorithm to sort an array of 100 items, and at the start of the final iteration of the while loop, the stack contains just two numbers: 10 (on top) and 90 (on bottom). Write one or two clear sentences to describe which parts of the array are sorted at this point, and which parts of the array remain to be sorted.

UNIT II Binary Tree

1. What are the maximum numbers of levels in a binary tree containing n nodes? 1- M

a. N-1 b. n+1 c. n d. either a or c

2. Which of the following data structure is not linear data structure? 1M

a. Arrays b. Linked lists c. Both of above d. None of above

3. Which of the following data structure is linear data structure? 1M

a. Trees b. Graphs c. Arrays d. None of above

4. What are the maximum number of nodes at level k in a binary tree? 1-M

a.2^k-1b 2k c.2(k+1) d. none of these

Consider This Tree for

Question Q3 to Q8

/ \

2 11

/ \ / \

1 3 10 30

/ /

7 40

5. There is a tree in the box at the top of this section. How many leaves does it have? 1-M

o A. 2

o B. 4

o C. 6

o D. 8

o E. 9

6. There is a tree in the box at the top of this section. How many of the nodes have at least one sibling? 1-M

o A. 5

o B. 6

o C. 7

o D. 8

o E. 9

7. There is a tree in the box at the top of this section. What is the value stored in the parent node of the node containing 30? 1-M

o A. 10

o B. 11

o C. 14

o D. 40

o E. None of the above

8. There is a tree in the box at the top of this section. How many descendants does the root have? 1-M

o A. 0

o B. 2

o C. 4

o D. 8

9. There is a tree in the box at the top of this section. What is the depth of the tree? 1-M

o A. 2

o B. 3

o C. 4

o D. 8

o E. 9

10. There is a tree in the box at the top of this section. How many children does the root have? 1-M

o A. 2

o B. 4

o C. 6

o D. 8

o E. 9

11. How many nodes are in a full binary tree having k levels? 1-M

a.2^k-1b 2^k c.2^(k+1) d. none of these

12. A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is known as 1-M

A. Full binary tree B. AVL C. Threaded binary tree D. Complete binary tree

13. Consider the binary_tree_node t. Which expression indicates that t represents an empty tree? 1-M

o A. (t == NULL)

o B. (t->data( ) == 0)

o C. (t->data( ) == NULL)

o D. ((t->left( ) == NULL) && (t->right( ) == NULL))

14. If a node having two children is deleted from a binary tree, it is replaced by it’s - 1M

o A. inorder predecessor

o B.inorder successor

o C. A or B

o D. none of the above

15. In a binary tree, certain null entries are replaced by special pointers which point to nodes higher in the tree for efficiency. These special pointers are called A. Leaf B. branch C. Path D. Thread 1-M

16. The depth of a complete binary tree is given by 1-M

o A. Dn = n log2n

o B. Dn = n log2n+1

o C. Dn = log2n

o D. Dn = log2n+1

17. The number of leaf nodes in a complete binary tree of depth d is 1-M

o A. 2^d

o B. 2^(d+1) – 1

o C. 2^(d-1) – 1

o D. 2^d + 1.

18. What are the maximum number of nodes in a binary tree containing k levels? - 2M

a.2^k-1b 2^k c.2^(k+1) d. none of these

19. How many nodes are in a full binary tree with k levels? 2-M

a.2^k-1b 2^k c.2^(k+1) d. none of these

20. What are the minimum possible number of levels in a binary tree of n nodes? - 2M

a. N b.n-1 c. floor(log₂n)+1. D.none of these

21. How many different binary trees containing exactly n nodes are there? 2-M

a. (2n)!/((n+1)!n!). b.2ⁿc. n! d. n(n+1)

22. Consider the binary tree in the box at the top of this section. Which statement is correct? 2-M

o A. The tree is neither complete nor full.

o B. The tree is complete but not full.

o C. The tree is full but not complete.

o D. The tree is both full and complete.

23. What are the minimum number of nodes in a full binary tree with depth 3? 2-M

o A. 3

o B. 4

o C. 8

o D. 11

o E. 15

24. What are the minimum number of nodes in a complete binary tree with depth 3? 2-M

o A. 3

o B. 4

o C. 8

o D. 11

o E. 15

25. Select the one true statement. 2-M

o A. Every binary tree is either complete or full.

o B. Every complete binary tree is also a full binary tree.

o C. Every full binary tree is also a complete binary tree.

o D. No binary tree is both complete and full.

26. Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T? 2-M

o A. 0

o B. 3

o C. 4

o D. 5

27. Select the one FALSE statement about binary trees: 2-M

o A. Every binary tree has at least one node.

o B. Every non-empty tree has exactly one root node.

o C. Every node has at most two children.

o D. Every non-root node has exactly one parent.

28. Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored? 2-M

o A. data[i+1]

o B. data[i+2]

o C. data[2*i + 1]

o D. data[2*i + 2]

29. Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree? 2-M

o A. 1

o B. 3

o C. 5

o D. 7

o E. 8

/ \

2 11

/ \ / \

1 3 10 30

/ /

7 40

30. There is a tree in the box at the top of this section. What is the order of nodes visited using a pre-order traversal? 2M

o A. 1 2 3 7 10 11 14 30 40

o B. 1 2 3 14 7 10 11 40 30

o C. 1 3 2 7 10 40 30 11 14

o D. 14 2 1 3 11 10 7 30 40

31. There is a tree in the box at the top of this section. What is the order of nodes visited using an in-order traversal? 2-M

o A. 1 2 3 7 10 11 14 30 40

o B. 1 2 3 14 7 10 11 40 30

o C. 1 3 2 7 10 40 30 11 14

o D. 14 2 1 3 11 10 7 30 40

32. There is a tree in the box at the top of this section. What is the order of nodes visited using a post-order traversal? 2-M

o A. 1 2 3 7 10 11 14 30 40

o B. 1 2 3 14 7 10 11 40 30

o C. 1 3 2 7 10 40 30 11 14

o D. 14 2 1 3 11 10 7 30 40

33. Consider this binary search tree:

/ \

2 16

/ \

1 5

4 Suppose we remove the root, replacing it with something from the left subtree. What will be the new root? 2-M

o A. 1

o B. 2

o C. 4

o D. 5

o E. 16

34. A binary tree of depth d is an almost complete binary tree if 2-M

o A. Each leaf in the tree is either at level d or at level d-1

o B. For any node n in the tree with a right descendant at level d all the left descendants of n that are leaves, are also at level d

o C. Both (A) & (B)

o D.None of the Above

35. A full binary tree with 2n+1 nodes contain 2-M

o A. n leaf nodes

o B. n non-leaf nodes

o C. n-1 leaf nodes

o D. n-1 non-leaf nodes

36. A full binary tree with n leaves contains 2-M

o A. n nodes

o B. 2n + 1 nodes

o C. log n nodes

o D. 2^ n nodes

37. To arrange a binary tree in ascending order we need 2-M

o A. Inorder traversal

o B.Preorder Traversal

o C.Postorder traversal

o D. None of the avobe

38. To arrange a binary search tree in ascending order we need 2-M

o A. Inorder traversal

o B.Preorder Traversal

o C.Postorder traversal

o D. None of the avobe

39. A BST is traversed in the following order recursively: Right, root, left The output sequence will be in 2-M

o A. Ascending order

o B. Descending sequence

o C. Can’t say

o D.None of the above.

40. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true? 2-M
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) None of the above

41. The most appropriate matching for the following pairs 2-M

X: depth first search            1: heap

Y: breadth-first search          2: queue

Z: sorting                              3: stack    is

(a)       X—1 Y—2 Z-3

(b)       X—3 Y—1 Z-2

(c)       X—3 Y—2 Z-1

(d)      X—2 Y—3 Z-1

42.  Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?    2M

(a) (1 2 (4 5 6 7))

(b) (1 (2 3 4) 5 6) 7)

(c) (1 (2 3 4)(5 6 7))

(d) (1 (2 3 NULL) (4 5))

The number of unused pointers in a complete binary tree of depth 5 is 2M

A 4   B 8    C 10   D 16

44.  Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?                               4M

i) preorder and postorder

ii) inorder and postorder

iii) preorder and inorder

iv) level order and postorder

a) (i) only
b) (ii), (iii)
c) (iii) only
d) (iv) only

45. Post-order traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T? 4-M

a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

c) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95

d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

46. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree & how many leaf nodes are there (the height is the maximum distance of a leaf node from the root)? 4M
a) 2
b) 3
c) 4
d) 6

47. The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root. 4M

The appropriate expression for the two boxes B1 and B2 are
(A) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))
(B) B1 : (height(n->right)), B2 : (1 + max(h1,h2))
(C) B1 : height(n->right), B2 : max(h1,h2)
(D) B1 : (1 + height(n->right)), B2 : max(h1,h2)

48. What is the post order traversal of a tree if the preorder traversal is 14 2 1 3 11 10 7 30 40 & in-order traversal is 1 2 3 14 7 10 11 40 30. 4M

a. 40 30 14 11 10 7 3 2 1

b. 1 2 3 40 30 10 7 11 14

c. 1 3 2 7 10 40 30 11 14

d. None of these

UNIT III

1. Which of the following statements is true? 1M

A. A graph can drawn on paper in only one way.

B. Graph vertices may be linked in any manner.

C. A graph must have at least one vertex.

D. A graph must have at least one edge.

2. A simple graph has no loops. What other property must a simple graph have? - - 1M

o A. It must be directed.

o B. It must be undirected.

o C. It must have at least one vertex.

o D. It must have no multiple edges.

3. Which graph traversal algorithm uses a queue to keep track of vertices which need to be processed? 1M

o A. Breadth-first search.

o B. Depth-first search.

o Both

o Neither A nor B

4. Which graph traversal algorithm uses a stack to keep track of vertices which need to be processed? 1M

o A. Breadth-first search.

o B. Depth-first search.

o Both

o Neither A nor B

5. Which graph representation allows the most efficient determination of the existence of a particular edge in a graph? 1M

o A. An adjacency matrix.

o B. Edge lists.

o Both

o Neither A nor B

6. How many total number of edges present in complete undirected graph if it has n nodes 1M

o N

o N(n-1)

o N(n-1)/2

o None of these

7. How many total number of edges present in complete directed graph if it has n nodes 1M

o N

o N(n-1)

o N(n-1)/2

o None of these

8. The data structure required for breadth first traversal on a graph is 1M

o Stack

o Queue

o Both

o Tree

9. The data structure required for Depth first traversal on a graph is 1M

o Stack

o Queue

o Both

o Tree

10. Suppose you have a game with 5 coins in a row and each coin can be heads or tails. What number of vertices might you expect to find in the state graph? 2M

o A. 7

o B. 10

o C. 25

o D. 32

11. Why is the state graph for tic-tac-toe a directed graph rather than an undirected graph? 2M

o A. Once a move is made, it cannot be unmade.

o B. There is an odd number of vertices.

o C. There is an odd number of edges.

o D. There is more than one player in the game.

12. Suppose you have a directed graph representing all the flights that an airline flies. What algorithm might be used to find the best sequence of connections from one city to another? 2M

o A. Breadth first search.

o B. Depth first search.

o C. Prims algorithm

o D. A shortest-path algorithm.

13. If G is an directed graph with 20 vertices, how many boolean values will be needed to represent G using an adjacency matrix? 2M

o A. 20

o B. 40

o C. 200

o D. 400

14. How many linked lists are used to represent a graph with n nodes and m edges, when using an adjacency list representation, 2M

o A. m

o B. n

o C. m + n

o D. m*n

15. How many total nodes will be present if a graph has n nodes and m edges, & created using an adjacency list representation, 2M

o A. 2n

o B. 2m

o C. m + n

o D. m*n

16. What is the expected number of operations needed to loop through all the edges terminating at a particular vertex given an adjacency matrix representation of the graph? (Assume n vertices are in the graph and m edges terminate at the desired node.) 2M

o A. O(m)

o B. O(n)

o C. O(m²)

o D. O(n²)

17. Shortest path algorithm gives minimum spanning tree. 2M

o A true

o B. False

o C. Not always

o D. None of these

An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below.

18. Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.


A.	SDT	B.	SBDT
C.	SACDT	D.	SACET

19. What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes? 4M
(A) 1/12(11n^2 – 5n)
(B) n^2 – n + 1
(C) 6n – 11
(D) 2n + 1

20. The length of the path from v5 to v6 in the MST of previous question with n = 10 is - 4M
(A) 11
(B) 25
(C) 31
(D) 41

21. Which is correct statement with respect to Shortest path algorithm 1M

A. Always gives Minimum cost spanning tree

B. Sometimes gives Minimum cost spanning tree

C. Never gives Minimum cost spanning tree

D. None of these.

22. The number of distinct simple graphs with up to three nodes are

A	15




C	7
D	9

23.

24. Consider the following graph: 4M Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?
A.	(b,e) (e,f) (a,c) (b,c) (f,g) (c,d)	B.	(b,e) (e,f) (a,c) (f,g) (b,c) (c,d)
C.	(b,e) (a,c) (e,f) (b,c) (f,g) (c,d)	D.	(b,e) (e,f) (b,c) (a,c) (f,g) (c,d)

UNIT IV

1. What is the worst-case time for serial search finding a single item in an array? - 1M

o A. Constant time

o B. Logarithmic time

o C. Linear time

o D. Quadratic time

2. What is the worst-case time for binary search finding a single item in an array? - 1M

o A. Constant time

o B. Logarithmic time

o C. Linear time

o D. Quadratic time

3. What additional requirement is placed on an array, so that binary search may be used to locate an entry? 1M

o A. The array elements must form a heap.

o B. The array must have at least 2 entries.

o C. The array must be sorted.

o D. The array's size must be a power of two.

4. What is the best definition of a collision in a hash table? 2M

o A. Two entries are identical except for their keys.

o B. Two entries with different data have the exact same key.

o C. Two entries with different keys have the same exact hash value.

o D. Two entries with the exact same key have different hash values.

5. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table? 2M

o A. 256

o B. 511

o C. 512

o D. 1024

o E. There is no maximum.

6. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor? 2M

o A. s + m

o B. s - m

o C. m - s

o D. m * s

o E. m / s

7. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173 and 4199) and the hash function x mod 10, which of the following statements are true? 2M
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value
a)i only
b) ii only
c) i and ii only
d) iii or iv

8. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0. 2M

o A. 2 b. 3 c. 4 d. 5

9. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? 2M

I. 7, 6, 5, 4, 4, 3, 2, 1	II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2	IV. 8, 7, 7, 6, 4, 2, 1, 1

I and II

III and IV

IV only

II and IV

10. insert the characters of string K R P C S N Y T J M into a hash table of size 10.
use the hash function H(x)=(ord(x)-ord('a')+1) mod 10 and linear probing to resolve collisions. which insertions cause collision? 4M

a.j,m
b.j,k
c.n,y
d.t,p

11. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. How many average number of comparisons are required in resultant hash table? 4M

e. 18/8 b.21/8 c. 24/8 d.25/8

12. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table. 4M
(a) 8, _, _, _, _, _, 10 (b) 1, 8, 10, _, _, _, 3
(c) 1, _, _, _, _, _,3 (d) 1, 10, 8, _, _, _, 3

13. Draw a hash table with open addressing and a size of 9. Use the hash function "k%9". Insert the keys: 5, 29, 20, 0, 27,77,58,49 and 18 into your table (in that order). – 8M

14. I plan to put 1000 items in a hash table, and I want the average number of accesses in a successful search to be about 2.0. 8M

A. About how big should the array be if I use open addressing with linear probing? NOTE: For a load factor of A, the average number of accesses is generally ½(1+1/(1-A)).

B. About how big should the array be if I use chained hashing? NOTE: For a load factor of A, the average number of accesses is generally (1+A/2).

15. Which guideline is NOT suggested from empirical or theoretical studies of hash tables:

o A. Hash table size should be the product of two primes.

o B. Hash table size should be the upper of a pair of twin primes.

o C. Hash table size should have the form 4K+3 for some K.

o D. Hash table size should not be too near a power of two.

16. In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which function has a better implementation because of this difference?

o A. insert

o B. is_present

o C. remove

o D. size

o E. Two or more of the above functions

17. What kind of initialization needs to be done for an open-address hash table?

o A. None.

o B. The key at each array location must be initialized.

o C. The head pointer of each chain must be set to NULL.

o D. Both B and C must be carried out.

18. What kind of initialization needs to be done for an chained hash table?

o A. None.

o B. The key at each array location must be initialized.

o C. The head pointer of each chain must be set to NULL.

o D. Both B and C must be carried out.

Easytolearn

Friday, September 12, 2014

Data Structure and graph theory objectives to students