[Solved] 300+ MCQs on Data structures & Algorithms

Data structures & Algorithms : Objective questions with answers

 1. Two main measures for the efficiency of an algorithm are 

 a. Processor and memory

 b. Complexity and capacity

 c. Time and space

 d. Data and space

  

 2. The time factor when determining the efficiency of algorithm is measured by

 a. Counting microseconds

 b. Counting the number of key operations

 c. Counting the number of statements

 d. Counting the kilobytes of algorithm

  

 3. The space factor when determining the efficiency of algorithm is measured by

 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

  

 4. Which of the following case does not exist in complexity theory

 a. Best case

 b. Worst case

 c. Average case

 d. Null case

  

 5. The Worst case occur in linear search algorithm when

 a. Item is somewhere in the middle of the array

 b. Item is not in the array at all

 c. Item is the last element in the array

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

  

 6. The Average case occur in linear search algorithm

 a. When Item is somewhere in the middle of the array 1 / 6

 b. When Item is not in the array at all

 c. When Item is the last element in the array

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

  

 7. The complexity of the average case of an algorithm is

a. Much more complicated to analyze than that of worst case

 b. Much more simpler to analyze than that of worst case

 c. Sometimes more complicated and some other times simpler than that of worst case

 d. None or above

  

 8. The complexity of linear search algorithm is

 a. O(n)

 b. O(log n)

 c. O(n2)

 d. O(n log n)

  

 9. The complexity of Binary search algorithm is

 a. O(n)

 b. O(log )

 c. O(n2)

 d. O(n log n)

  

 10. The complexity of Bubble sort algorithm is

 a. O(n)

 b. O(log n)

 c. O(n2)

 d. O(n log n)

 

 11. The complexity of merge sort algorithm is

 a. O(n)

 b. O(log n)

 c. O(n2)

 d. O(n log n)

  

 12. The indirect change of the values of a variable in one module by another module is called

 a. internal change

 b. inter-module change

 c. side effect

 d. side-module update

  

 13. Which of the following data structure is not linear data structure?

 a. Arrays

 b. Linked lists

 c. Both of above

 d. None of above

  

 14. Which of the following data structure is linear data structure?

 a. Trees

 b. Graphs

 c. Arrays

 d. None of above

  

 15. The operation of processing each element in the list is known as

 a. Sorting

 b. Merging

 c. Inserting

 d. Traversal

  

 16. Finding the location of the element with a given value is:

 a. Traversal

 b. Search

 c. Sort

 d. None of above

  

 17. Arrays are best data structures

 a. for relatively permanent collections of data

 b. for the size of the structure and the data in the structure are constantly changing

 c. for both of above situation

 d. for none of above situation

  

 18. Linked lists are best suited

 a. for relatively permanent collections of data

 b. for the size of the structure and the data in the structure are constantly changing

 c. for both of above situation

 d. for none of above situation

  

 19. Each array declaration need not give, implicitly or explicitly, the information about

 a. the name of array

 b. the data type of array

 c. the first data from the set to be stored

 d. the index set of the array

  

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

 a. by this way computer can keep track only the address of the first element and the addresses

of other elements can be calculated

 b. the architecture of computer memory does not allow arrays to store other than serially

 c. both of above

 d. none of above

Answers:

  

1. Two main measures for the efficiency of an algorithm are c. Time and space 2. The time

factor when determining the efficiency of algorithm is measured by

b. Counting the number of key operations

3. The space factor when determining the efficiency of algorithm is measured by

a. Counting the maximum memory needed by the algorithm

4. Which of the following case does not exist in complexity theory

d. Null case

5. The Worst case occur in linear search algorithm when

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

6. The Average case occur in linear search algorithm

a. When Item is somewhere in the middle of the array

7. The complexity of the average case of an algorithm is

a. Much more complicated to analyze than that of worst case

8. The complexity of linear search algorithm is

a. O(n)

9. The complexity of Binary search algorithm is

b. O(log n)

10. The complexity of Bubble sort algorithm is

c. O(n

2

)

11. The complexity of merge sort algorithm is

d. O(n log n)

12. The indirect change of the values of a variable in one module by another module is called

c. side effect

13. Which of the following data structure is not linear data structure?

d. None of above

14. Which of the following data structure is linear data structure?

c. Arrays

15. The operation of processing each element in the list is known as

d. Traversal

16. Finding the location of the element with a given value is:

b. Search

17. Arrays are best data structures

a. for relatively permanent collections of data

18. Linked lists are best suited

b. for the size of the structure and the data in the structure are constantly changing

19. Each array declaration need not give, implicitly or explicitly, the information about

c. the first data from the set to be stored

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

a. by this way computer can keep track only the address of the first element and the addresses of other

elements can be calculated

-----------

21. If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes

one of the following time.

(a) O(n log n) (b) O(n3) (c) O(n2) (d) O(log n) (e) O(n4).

Ans : O(n3)

22. For a 15-puzzle problem let the initial arrangement be the following one,

then answer the questions 4 – 7 with the following arrangement.

10 13 15 7

9 1 4 14

12 8 6

11 2 5 3

What is the value of ‘x’ used to find the reachability of the solution?

(a) 1 (b) 0 (c) 8 (d) 10 (e) 13.

Ans : 1

23. The upper bound on the time complexity of the nondeterministic

sorting algorithm is

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

Ans: O(n)

24. The worst case time complexity of the nondeterministic dynamic knapsack

algorithm is

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

Ans :O(n)

25. Recursive algorithms are based on

(a) Divideand conquer approach (b) Top-down approach

(c) Bottom-up approach (d) Hierarchical approach

(e) Heuristic approach.

Ans :Bottom-up approach

26. What do you call the selected keys in the quick sort method?

(a) Outer key (b)Inner Key (c) Partition key(d) Pivot key (e) Recombine key.

Ans :

7. How do you determine the cost of a spanning tree?

(a) By the sum of the costs of the edges of the tree

(b) By the sum of the costs of the edges and vertices of the tree

(c) By the sum of the costs of the vertices of the tree

(d) By the sum of the costs of the edges of the graph

(e) By the sum of thecosts of the edges and vertices of the graph. 

Ans :By the sum of the costs of the edges of the tree

28. The time complexity of the normal quick sort, randomized quick sort algorithms in the

worst case is

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

O(n log n), O(n log n) (e) O(n log n), O(n2 log n).

Ans :O(n2), O(n2)

29. Let there be an array of length ‘N’, and the selection sort algorithm is used to sort it,

how many times a swap function is called to complete the execution?

(a) N log N times (b) log N times (c) N2 times

(d) N-1 times (e) N times.

Ans :N-1 times

30. The Sorting methodwhich is used for external sort is

(a) Bubble sort (b) Quick sort (c) Merge sort

(d) Radix sort (e) Selection sort.

Ans :Radix sort

31. In analysis of algorithm, approximate relationship between the size of the job and

the amount of work required to do is expressed by using _________

(a) Central tendency (b) Differential equation (c) Order of execution (d)

Order of magnitude (e) Order of Storage.

Ans :Order of execution

32. Worst case efficiency of binary search is

(a) log2 n + 1

(b) n

(c) N2

(d) 2

n

(e) log n.

Ans : log2 n + 1

33. For defining the best time complexity, let f (n) = log n and g (n) = √n, _________

(a)f (n) Ω(g(n)), but g(n)  Ω (f(n)) (b) f (n) Ω(g(n)), but g(n)  Ω (f(n))

(c)f (n) Ω(g(n)), and g(n)  Ω (f(n)) (d) f (n) Ω(g(n)), and g(n)  Ω (f(n))

Ans :f (n) Ω(g(n)), but g(n)  Ω (f(n))

34. For analyzing an algorithm, which is better computing time?

(a)O (100 Log N) (b) O (N) (c)O (2N) (d) O (N logN) (e) O (N2).

Ans :O (100 Log N)

35. Let f, t: N→R  0, and t (n) O (f (n)) iff t(n)≤ c.f (n) where cis positive real

constant andn≥ no, then no is ___________

(a) Upper bound (b)Lower bound (c) Duality value

(d) Threshold value (e) Maximum value.

Ans :Lower bound

36. Consider the usual algorithm for determining whether a sequence of parentheses is

balanced. What is the maximum number of parentheses that will appear on the stack

AT ANY ONE TIME when the algorithm analyzes: (()(())(()))

(a) 1 (b)2 (c)3 (d) 4

Ans :3

37. Breadth first search __________

(a) Scans each incident node along with its children.

(b) Scans all incident edges before moving to other node.

(c) Issame as backtracking

(d) Scans all the nodes in random order.

Ans :Scans all incident edges before moving to other node.

38. Which method of traversal does not use stack to hold nodes that are waiting to be

processed?

(a) Dept First (b) D-search (c)Breadth first

(d) Back-tracking

Ans :Breadth first

39. The Knapsack problem where the objective function is to minimize the profit is

______

(a) Greedy (b) Dynamic 0 / 1 (c) Back tracking

(d) Branch & Bound 0/1

Ans :Branch & Bound 0/1

40. Choose the correct answer for the following statements:

I. The theory of NP–completeness provides a method of obtaining a

polynomial time for NPalgorithms.

II. All NP-complete problem are NP-Hard.

(a) I is FALSE and II is TRUE (b) I is TRUE and II is FALSE

(c) Both are TRUE (d) Both are FALSE

Ans :I is FALSE and II is TRUE

41. The Hamiltonian cycles problem uses the following line of code to generate a

next vertex, provided x[ ] is a global array and kth vertex is under consideration:

(a) x[k]  (x[k] + 1) mod n (b) x[k]  (x[k]) mod (n)

(c) x[k]  (x[k] + 1) mod (n+1) (d) x[k]  x[k+1] mod n

Ans :x[k]  (x[k] + 1) mod (n+1)

42. The graph colouringalgorithm’s time can be bounded by _________

(a) O(mnm) (b) O(nm) (c) O(nm. 2n) (d) O(nmn).

Ans :O(nmn).

43. For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for

memory table, and ______time to determine the optimal load, for N objects and

W as the capacity of KNAPSACK.

(a) O(N+W), O(NW) (b) (NW),O(N+W) (c)O(N),O(NW) (d) O(NW),O(N)

Ans :(b) (NW),O(N+W)

44. Sorting is not possible by using which of the following methods?

(a) Insertion (b) Selection (c) Deletion (d) Exchange

Ans :Deletion

45. What is the type of the algorithm used in solving the 8 Queens problem?

(a)Backtracking (b) Dynamic (c) Branch and Bound (d) DandC

Ans :Backtracking

46. The following are the statements regarding the NP problems. Chose the right option

from the following options:

I. All NP-complete problems are not NP-hard.

II. SomeNP-hard problems are not known to be NP-complete.

(a) Both (I) and (II) are true

(b) Both (I) and (II) are false

(c) Only (I) is true

(d) Only (II) is true

Ans :Only (II) is true

47. Let G be a graph with ‘n’ nodes and let ‘m’ be the chromatic number of the graph.

Then the time taken by the backtracking algorithm to color it is

(a) O(nm)

(b) O(n+m)

(c) O(mnm)

(d) O(nmn).

Ans :O(nmn).

48. The time complexity of the shortest path algorithm can be bounded by

(a) O(n2)

(b) O(n4)

(c) O(n3)

(d) O(n)

(e) O(n log n ).

Ans :O(n3)

49. Read the following statements carefully and pick the correct option:

I. The worst time complexity of the Floyd’s algorithm is O(n3). II.

The worst time complexity of the Warshall’s algorithm is O(n3).

(a) (I) is false but (II) is true

(b) (I) is true but (II) is false

(c) Both (I) and (II) are true

(d) (I) is true and (II) is not true always 

(e) Both (I) and (II) are false.

Ans :Both (I) and (II) are true

50. Theasymptotic notation for defining the average time complexity is

(a) Equivalence

(b) Symmetric

(c) Reflexive

(e) Both (c) and (d) above.

Ans :Equivalence

51. For the bubble sort algorithm, what is the time complexity of the best/worst case?

(assume that the computation stops as soon as no more swaps in one pass)

(a) best case: O(n) worst case: O(n*n)

(b) best case: O(n) worst case: O(n*log(n))

(c) best case: O(n*log(n)) worst case: O(n*log(n))

(d) best case: O(n*log(n)) worst case: O(n*n)

Ans : best case: O(n) worst case: O(n*n)

52. For the quick sort algorithm, what is the time complexity of the best/worst case?

(a) best case: O(n) worst case: O(n*n)

(b) best case: O(n) worst case: O(n*log(n))

(c) best case: O(n*log(n)) worst case: O(n*log(n))

(d) best case: O(n*log(n)) worst case: O(n*n)

Ans :best case: O(n*log(n)) worst case: O(n*n)

53. In an arbitrary tree ( not a search tree) of order M. Its size is N, and its height is K.

The computation time needed to find a data item on T is

(a) O(K*K)

(b) O(M*M)

(c) O(N)

(d) O(K)

Ans : O(N)

54. Which of the following belongs to the algorithm paradigm?

(a) Minimum & Maximum problem

(b) Knapsack problem

(c) Selection problem

(d) Merge sort

(e) Quick sort.

Ans : Knapsack problem

55. If f,t: N→ R+, then t (n)  Ω (f (n)), iff f(n)  O (t (n)) is known as

(a) Limit rule

(b) Rule of inference

(c) Duality rule

(d) Rule of consequences 

56. The time taken by NP-class sorting algorithm is

(a) O(1)

(b) O(log n)

(c) O(n2)

(d) O(n)

Ans :O(n)

57. Find the odd one out from the following categories of algorithms.

(a) TVSP

(b) N-Queens

(c) 15-Puzzle

(d) Bin-Packing.

Ans : Bin-Packing.

58. The time complexity of binary search in best, worst cases for an array of size N is

(a) N, N2

(b) 1, Log N

(c) Log N, N2

(d) 1, N log N

Ans : 1, Log N

59. Which of following algorithm scans the list by swapping the entries whenever pair

of adjacent keys are out of desired order?

(a) Insertion sort

(b) Quick sort

(c) Shell sort

(d) Bubble sort

Ans : Bubble sort

60. The mathematical definition for Omega can be defined as, provided f,g:NR+ and c is

a positive constant and n > n0,

(a) f(n) ≥ c. g(n) n

(b) f(n) = c. g(n) n

(c) f(n) ≥ c + g(n) n

(d) f(n) = c + g(n) n

Ans : f(n)≥ c. g(n) n

61. The  notation is

(a) Symmetric

(b) Reflexive

(c) Transitive

(d) (a), (b) and (c) above.

Ans : (a), (b) and (c) above.

62 From the following choose the one which belongs to the algorithm paradigm other than

. to which others from the following belongs to.

(a) Minimum & Maximum problem

(b) Knapsack problem

(c) Selection problem

(d) Merge sort

Ans : Knapsack problem

63 Pick the correct statement(s) from the following set of statements..

II. In Prim’s algorithm, for the construction of minimal spanning tree for a graph, the

selected edges always form an orchard.

III. DFS, BFS algorithms always make use of a queue, and stack respectively.

(a) Only (I) above

(b) Only (II) above

(c) Only (III) above

(d) Both (I) and (III) above

Ans : Only (I) above

64. Identify the name of the sorting in which time is not proportional to n2.

(a) Selection sort

(b) Bubble sort

(c) Qucik sort

(d) Insertion sort.

Ans : Insertion sort

65. The optimal solution to a problem is a combination of optimal solutions to its subproblems.

This is known as

(a) Principleof Duality

(b) Principle of Feasibility

(c) Principle of Optimality

(d) Principle of Dynamicity.

Ans : Principle of Optimality

66. Which of the following versions of merge sort algorithm does uses space efficiently?

(a) Contiguous version

(b) Array version

(c) Linked version

(d) Structure version

(e) Heap version.

Ans : Linked version

67. Identify the correct problem for multistage graph from the list given below.

(a) Resource allocation problem

(b) Traveling salesperson problem

(c) Producer consumer problem

(d) Barber’s problem

I. In the Kruskal’s algorithm, for the construction of minimal spanning tree for a graph,

the selected edges always form a forest.

Ans : Resource allocation problem

68. How many edges are there in a Hamiltonian cycle if the edge cost is ‘c’ and the

cost of cycle is ‘cn’

(a)c (b) cn

(c)n (d) 2c

Ans :n.

69. A problem L is NP-complete iff L is NP-hard and

(a) L ≈ NP

(b) L α NP

(c) L ε NP

(d) L = NP

Ans : L ε NP

70. What would be the cost value for any answering node of a sub tree with root ‘r’

using branch-bound algorithm?

(a) Maximum

(b) Minimum

(c) Optimal

(d) Average

Ans: Minimum

51. Name the node which has been generated but none of its children nodes have

been generated in state space tree of backtracking method.

(a) Dead node

(b) Live node

(c) E-Node

(d) State Node

Ans: Livenode

52. How many nodes are there in a full state space tree with n = 6?

(a) 65

(b) 64

(c) 63

(d) 32

Ans : 63

53. This algorithm scans the list by swapping the entries whenever pair of

adjacent keys are out of desired order.

(a) Insertion sort.

(b) Bubble sort.

(c) Shell sort.

(d) Quick sort.

Ans: Bubble sort.

54. The  notation is

(a) Symmetric

(b) Reflexive

(c) Transitive

(d) B & C only

Ans: Transitive

55. From the following chose the one which belongs to the algorithm paradigm

other than to which others from the following belongs to.

(a) Minimum & Maximum problem.

(b) Knapsack problem.

(c) Selection problem.

(d) Merge sort.

Ans: Knapsack problem.

56. To calculatec(i, j )’s, w( i, j)’s and r(i, j)’s; the OBST algorithm in worst case takes

the following time.

(a) O(log n)

(b) O (n4)

(c) O (n3)

(d) O (n log n)

Ans: O (n3)

57. What is the type of the algorithm used in solving the 4 Queens problem?

(a) Greedy

(b) Dynamic

(c) Branch and Bound

(d) Backtracking.

Ans: Backtracking.

58.In Knapsack problem, the best strategy to get the optimal solution, where Pi, Wi is the

Profit, Weight associated with each of the Xi

th object respectively is to

(a) Arrange the values Pi/Wi in ascending order

(b) Arrange the values Pi/Xi in ascending order

(c) Arrange the values Pi/Wi in descending order

(d) Arrange the values Pi/Xi in descending order

Ans: Arrange the values Pi/Xi in descending order

59.Greedy job scheduling with deadlines algorithms’ complexity is defined as

(a) O(N)

(b) Ω( n log n)

(c) O (n2 log n)

(d) O ( n log n)

Ans: O(N)

60.The divide and conquer merge sort algorithm’s time complexity can be defined as

(a)  (long n)

(b)  (n)

(c) Ω (n log n)

(d)  (n log n)

Ans:  (n log n)

61. In analysis of algorithm, approximate relationship between the size of the job and

the amount of work required to do it is expressed by using

(a) Order of magnitude or Big - O

(b) Central tendency

(c) Differential equation

(d) Polynomial equation

Ans: Order of magnitude or Big - O

62.Worst case efficiency of binary search is

(a) log2 n + 1

(b) n

(c) N2

(d) 2

n

Ans: log2 n + 1

63.Worst case efficiency of which search is O(n)?

(a) Sequential search

(b) Binary search

(c) Indexed search

(d) Hashing

Ans: Sequential search

64. Breadth first search

(a) Scans all incident edges before moving to other vertex

(b) Scans adjacentunvisited vertex as soon as possible

(c) Is same as backtracking

(d) Computes a path between two vertices of graph or equivalently

Ans: Scans all incident edges before moving to other vertex

65. Which of the following searching methods requires that all keys must reside

in internal memory?

(a) Binary search

(b) Sequential search

(c) Hashing

(d) Depth first search

Ans: Binary search

66. Which of the following formulas in Omega notation best represent the expression

n²+35n+6?

(a) Ω (n³) (b) Ω (n²) (c) Ω (n) (d) Ω (35)

Ans: Ω (n²)

67. What term is used to describe an O(n) algorithm?

(a) Constant (b) Non Polynomial Deterministic

(c) Logarithmic (d) Linear.

Ans: Linear.

68. Express the formula (n - 2)*(n - 4) using θ notation:

(a) θ (n2) (b) θ (8) (c) θ (log n) (d) θ (n)

Ans: θ (n2)

69. Read the following statements carefully and pick the right most option.

I. A linear algorithm to solve a problem must perform faster than a

quadratic algorithm to solve the same problem.

II. An algorithm with worst case time behavior of 3n takes at least 30 operations

for every input of size n=10.

(a) Both (I) and (II) are TRUE

(b) Both (I) and (II) are FALSE

(c) (I) is TRUE but (II) is FALSE

(e) (I) is FALSE and (II) is TRUE.

Ans: (I) is TRUE but (II) is FALSE

70. Which of the following are essential statement types for describing algorithms?

(a) Sequence (b) Selection (c) Repetition (d) All the above

Ans: All the above

71. When we say an algorithm has a time complexity of O (n), what does it mean?

(a) The algorithm has ‘n’ nested loops

(b) The computation time taken by the algorithm is proportional to n

(c) The algorithm is ‘n’ times slower than a standard algorithm

(d) There are ‘n’ number of statements in the algorithm

Ans: The computation time taken by the algorithm is proportional to n

72. Can we read a data item at any location of a list within a constant time (i.e.

O(1))?

(a) Yes

(b) Yes, only if the list is implemented by pointers (i.e. linked-list)

(c) Yes, only if the list is implemented by an array

(d) No, we need O(n) computation steps no matter what kind

of implementation is used 

Ans: Yes, only if the list is implemented by an array

73. Sequential search has a time complexity of O(n), and binary search has a time

complexity of O(log(n)). What difference will it make when the size n is 1000?

(a) You would not notice much difference because computers run very fast

anyway

(b) As n is 1000, binary search is twice as fast as sequential search

(c) As n is 1000, binary search is 10 times as fast as sequential search

(d) As n is 1000, binary search is 100 times as fast as sequential search.

Ans: As n is 1000, binary search is 100 times as fast as sequential search.

74. Readthe following statements carefully, and choose the correct answer.

I. The Ω notation is Anti Symmetric.

II. The big Oh notation is Semi Equivalence.

(a) (I) is FALSE but (II) is TRUE (b) Both (I), (II) are TRUE

(c) (I) is TRUE but(II) is FALSE (d) Both (I), (II) are FALSE

Ans: Both (I), (II) are TRUE

75. Find the odd one out.

(a) Merge Sort (b)TVSP Problem (c) KnapSack Problem(d) OBST Problem

Ans:Merge Sort

76. How many minimum number of spanning trees, one can have from a given

connected graph with N nodes is having different weights for the edges.

(a)N-1 (b) One (c) 1/(N+1) 2NCN (d) 2NCN

Ans: one

77. The mathematical definition for Omega can be defined as, provided f,g:NR+ and c

is a positive constant and n > n0,

(a) f(n)≥ c. g(n) n

(b) f(n) £ c. g(n) n

(c) f(n) ≥ c + g(n) n

(d) f(n) £ c + g(n) n

(e) f(n) £ g(n) n.

Ans:f(n)≥ c. g(n) n

78. The OBST algorithm in worst case takes _______ time if all c(i, j )’s and r(i, j)’s are

calculated.

(a) O(log n) (b) O(n4) (c) O(n3) (d) O(n log n)

Ans: O(n3)

79. The  notation is __________

I. Symmetric.

II. Reflexive.

III. Transitive.

(a) Only (I) above

(b) Only (II) above

(c) Only (III) above

(d) All (I), (II) and (III) above.

Ans:All (I),(II) and (III) above.

80. Breadth first search uses __________ as an auxiliary structure to hold nodes for

future processing.

(a) Stack (b) Linked list (c) Graph (d) Queue.

Ans : Queue

81. From the following pick the one which does not belongs to the same paradigm to which

others belongs to.

(a) Minimum & Maximum problem

(b) Knapsack problem

(c) Selection problem

(d) Merge sort

Ans:Knapsack problem

82. Primsalgorithm is based on _____________ method

a. Divide and conquer method c. Dynamic programming

b. Greedy method d. Branch and bound

Ans. Greedy Method

83. The amount of memory needs to run to completion is known as_____________

a. Space complexity c. Worst case

b. Time complexity d. Best case

Ans: Space complexity

84. The amount of time needs to run to completion is known as____________

a. Space complexity c. Worst case

b. Time complexity d. Best case

Ans: Time complexity

85. __________ is the minimum number of steps that can executed for the given

parameters

a. Average case c. Worst case

b. Time complexity d. Best case

Ans: Best case

86. __________ is the maximum number of steps that can executed for the given

parameters

a. Average case c. Worst case

b. Time complexity d. Best case

Ans:Worst case

87. __________ is the average number of steps that can executed for the given

parameters

a. Average case c. Worst case

b. Time complexity d. Best case

Ans: Average Case

88. Testing of a program consists of 2 phases which are ______________________

and ____________

a. Average case & Worst case b. Time complexity & Space complexity

c. Validation and checking errors d. Debugging and profiling

Ans: Debugging and profiling

89. Worst case time complexity of binary search is ______________

a. O(n) b. O(logn)

c. Ɵ(nlogn) d. Ɵ(logn)

Ans: Ɵ(logn)

90. Best case time complexity of binary search is ______________

a. O(n) c. Ɵ(nlogn)

b. O(logn) d. Ɵ(logn)

Ans: Ɵ(logn)

91. Average case time complexity of binary search is ______________

a. O(n) c. Ɵ(nlogn)

b. O(logn) d. Ɵ(logn)

Ans: Ɵ(logn)

92. Merge sort invented by _____________

a. CARHOARE c. HAMILTON

b. JOHN VON NEUMANN d. STRASSEN

Ans : JOHN VON NEUMANN

93. Quick sort invented by _____________

a. CARHOARE c. HAMILTON

b. JOHN VON NEUMANN d. STRASSEN

Ans : CARHOARE

94. Worst case time complexity of Quick sort is ______________

a. O(n2log7) c. O(nlogn)

b. O(n2) d. O(logn)

Ans : O(n2)

95. Best case time complexity of Quick sort is ______________

a. O(n2logn) c. O(nlogn)

b. O(logn) d. O(logn2)

Ans : O(nlogn)

96. Average case time complexity of Quick sort is ______________

a. Ɵ (nlogn) b. O(logn)

c. O(nlogn) d. Ɵ(logn) Ans : O(nlogn)

97. Which design strategy stops theexecution when it find the solution otherwise starts

the problem from top

a. Back tracking c. Divide and conquer

b. Branch and Bound d. Dynamic programming

Ans: Back Tracking

98. Graphical representation of algorithm is _____________________

a. Pseudo-code c. Graph Coloring

b. Flow Chart d. Dynamic programming

Ans: Flow Chart

99. In pseudo-code conventions input express as __________

a. input c. Read

b. Write d. Return

Ans : Write

100. In pseudo-code conventions output express as __________

a. input c. Read

b. Write d. Return

Ans : Read

101. Performance based criteria of algorithm , which has to do with its computing time is

_______________

a. Time Complexity c. Input

b. Space Complexity d. Finiteness

Ans : Time Complexity

102. Performance based criteria of algorithm , which has to do with its storage

requirements is _______________

a. Time Complexity c. Input

b. Space Complexity d. Finiteness

Ans :Space Complexity

103. O(1) means computing time is __________________

a. Constant c. Quadratic

b. Linear d. Cubic

Ans : Constant

104. O(n) means computing time is __________________

a. Constant c. Quadratic

b. Linear d. Cubic

Ans: Linear

105. O(n2) means computing time is __________________

a. Constant c. Quadratic

b. Linear d. Cubic

Ans : Quadratic

106. O(n3) means computing time is __________________

a. Exponential c. Quadratic

b. Linear d. Cubic

Ans :Cubic

107. O(2n) means computing time is __________________

a. Constant c. Quadratic

b. Linear d. Exponential

Ans : Exponential

108. Application of quicksort _________

a. Graphic card c. Data Processing

b. Tape sorting d. Card Sorting

Ans : Graphic card

109. Application of mergesort _________

a. Graphic card b. Networking

c. Card Sorting d. Data Processing

Ans : Data Processing

110. The method will choosing when sub problems share sub problems

a. Divideand conquer c. Greedy method

b. Dynamic programming d. Back tracking

Ans : Dynamic programming

111. Time complexity of given algorithm

Algorithm Display (A)

{

For I:=0 to n-1

{

For J:=0 to n-1

{

Write A;

}

}

}

a. 2n2+4n+4 c. 2n2+n

b. 2n2+4n+2 d. 2n2-1

Ans : 2n2+4n+2

112. The sorting , which works very well for small file is ______________

a. Count sort c. Selection sort

b. Merge sort d. Quick sort

Ans: Selection sort

113. Merge sort is _________.

a. Externalsorting c. Insertion sorting

b. Internal sorting d. Exponential sorting

Ans : External sorting

114. __________ is a step-by-step procedure for calculations

a. Program c. Algorithm

b. Greedy Method d. Problem

Ans : Algorithm

115. Advantage of finding maximum and minimum using divide and conquer method

instead of using conditional operators is __________________

a. Reduce Space complexity c. Get accurate value

b. Reduce Time complexity d. Simple calculations

Ans :Reduce Time complexity

116. Given two non-negative functions f(n)= 5n2+6n+1 and g(n)=n2 . Calculate upper

bound value ,C

a. C=5 c. C=12

b. C=6 d. C=11

Ans : C=12

117. Given two non-negative functions f(n)= 6n2+5n+1 and g(n)=n2 . Calculate lower bound

value ,C

a. C=5 c. C=12

b. C=6 d. C=11

Ans : C=6

118. The functions f &g are non-negative functions. The function f(n)=O(g(n)) if and only

if there exist positive constants c& n0 such that __________ for all n, n≥ n0

a. f(n)≤C*g(n) c. f(n) = C*g(n)

b. f(n) ≥ C*g(n) d. f(n) != C*g(n)

Ans : f(n)≤ C*g(n)

119. The functions f & g are non-negative functions. The function f(n)=Ω(g(n)) if and only

if there exist positive constants c& n0 such that ___________ for all n, n≥ n0

a. f(n) ≤ C*g(n) c. f(n) = C*g(n)

b. f(n) ≥ C*g(n) d. f(n) != C*g(n)

Ans : f(n)≥ C*g(n)

120. The functions f & g are non-negative functions. The function f(n)=θ(g(n)) if and only

if there exist positive constants c1,c2 & n0 such that ________for all n, n≥ n0

a. C2*g(n)≤ f(n) ≤ C1*g(n) c. C2*g(n)≥ f(n) = C1*g(n)

b. C2*g(n)!= f(n) = C1*g(n) d. C2*g(n)≤ f(n) = C1*g(n)

Ans :C2*g(n)≤ f(n) ≤ C1*g(n)

121. Tight bound is denoted as _______

a. Ω c. Θ

b. Ω d. O

Ans : Θ

122. Upper bound is denoted as _______

a. Ω c. Θ

b. ω d. O

Ans : O

123. lower bound is denoted as _______

a. Ω c. Θ

b. ω d. O

Ans :Ω

124. The function f(n)=o(g(n)) if and only if Limit f(n)/g(n)=0n->∞

a. Little oh b. Little omega

b. Big oh d. Omega

Ans : Little oh

125. The functionf(n)=o(g(n)) if and only if Limit g(n)/f(n)=0 n->∞

a. Little oh b. Little omega

b. Big oh d. Omega

Ans : Little omega

126. Thegeneralcriteriaof algorithm;zero or more quantities are externally supplied is

______

a. Output b. Finiteness

b. Effectiveness d. Input

Ans : Input

127. The general criteria of algorithm; at least one quantity is produced ______

a. Output b. Finiteness

b. Effectiveness d. Input

Ans : Output

128. The general criteria of algorithm; Each instruction is clear and unambiguous ______

a. Output b. Definiteness

b. Effectiveness d. Input

Ans : Definiteness

129. The general criteria of algorithm; algorithm must terminates after a finite number

of steps ______

a. Output b. Finiteness

b. Effectiveness d. Input

Ans : Finiteness

130. Which is not a criteria of algorithm

a. Input b. Output

b. Time complexity d. Best case

Ans : Best case

131. Which is not in general criteria of algorithm

a. Input b. Output

b. Time complexity d. Effectiveness

Ans : Time complexity

132. Time complexity of given algorithm

Algorithm Display(A)

{

S:=0.0;

For i:=0 to n-1

{

S:=S+A[i];

Return S;

}

}

a. 4n+4 c. 4n2+4

b. 2n2+2n+2 d. 4n+4

Ans : 4n+4

133. Time complexity of given algorithm

AlgorithmSum(A,S)

{

for i:=1 to n-1

{

for j:=2 to n-1

{

S:=S+i+j;

return S;

}

}

}

a. 6n2-14n+4 c. 4n2+6n+12

b. 6n2+14n+10 d. 6n2-14n+10

Ans :6n2-14n+10

134. kruskal algorithm is based on ___________method

a. Divide and conquer method b. Greedy method

c. Dynamic programming d. Branch and bound

Ans. Greedy method

135. Prims algorithm is based on _____________ method

a. Divide and conquer method c. Dynamic programming

b. Greedy method d. Branch and bound

Ans. Greedy Method

136. The output of Kruskal and Prims algorithm is ________________

a. Maximum spanning tree c. Spanning tree

b. Minimum spanning tree d. None of these

Ans. Minimum spanning tree

138. which is not feasible solution in the case of job sequence problem

item : 1 2 3 4

profit : 100 10 15 27

deadline : 2 1 2 1

a. (1,4) c. (4,3)

b. (2,4) b. (1,2)

Ans. (2,4)

139. which isoptimal value in the case of job sequence problem

item : 1 2 3 4 5

profit : 20 15 10 5 1

deadline : 2 2 3 3 3

a. (1,3,4) c. (4,2,3)

b. (1,2,4) d. (1,5,2)

Ans. (1,2,4)

140. which is optimal value in the case of job sequence problem

item : 1 2 3 4 5 6 7

profit : 3 5 20 18 1 6 30

deadline : 1 3 4 3 2 1 2

a. (1,5,6,4) c. (7,6,4,3)

b. (2,3,1,7) b. (1,2,3,4)

Ans. (7,6,4,3)

141. which is optimal value in the case of fractional knapsack problem, capacity of

knapsack is 20

item : 1 2 3

profit : 25 24 15

weight : 18 15 10

a. 498 c. 480

b. 499 d. 485

Ans. 498

142. which is optimal value in the case of fractional knapsack problem, capacity of

knapsack is 10

item : 1 2 3 4 5

profit : 12 32 40 30 50

weight : 4 8 2 6 1

a. 345 c. 384

b. 354 d. 350

Ans. 354

143. 4 -Queen problem what is the space complexity

a. O(|V|)

b. O(|E|)

c. O(|V|+|E|)

d. O(|V2

|)

Ans.O(|V|)

144. In the case of Fibnocci heap the running time of Prim's algorithm is _________

a. O(E log V)

b. O(V log E)

c. O( log V)

d. O(E log E)

Ans. O(E log V)

145. Time complexity of 4-queen problem

a. O(|V|)

b. O(|E|)

c. O(|V|+|E|)

d. O(|V2

|)

Ans.O(|V|+|E|)

146. If the graph is represented as an adjacency matrix then the time complexity

of Kruskal's algorithm is ____________

a. O(E log V)

b. O(VlogE)

c. O(V2)

d. O(logE)

Ans. O(E log V)

147. BFS is best compared to DFS in the case of ________________

a. The graph’s width is large

b. The graph’s depth is large

c. The graph consists of many nodes

d. The graph is complex

Ans. The graph’s depth is large

148. The timecomplexity of Strassen's algorithm is ___________

a. O(E log V)

b. O(V2

)

c. O(nlog7)

d. O(log n7)

Ans. O(nlog7)

149. By Strassen's equation what is wrong in the following equation

a. p1=(a+d)(e+h) c. c.p3=(a-c)(e+f)

b. b.p2=(-e+g)d d. d.p4=(a+b)h

Ans. p2=(-e+g)d

150. By Strassen's equation what is wrong in the following equation

a. p1=(a+d)(e+h) c. c.p3=(a-c)(e+f)

b. b.p7=(-e+g)d d. d.p4=(a-b)h

Ans. p4=(a-b)h

151. The advantage of selecting maxmin algorithm using divide and conquer

method compared to staightmaxmin algorithm is _____

a. Less time complexity c. High accuracy

b. Less space complexity d. High time complexity

Ans. Less time complexity

152. The number of comparisons of elements for best case is ____________ in the case

of maxmin algorithm based on divide and conquer method

a. 3n/2 c. n/4

b. n/2 d. n-1

ans. 3n/2

153. The number of comparisons of elements for average case is ____________ in the

case of maxmin algorithm based on divide and conquer method

a. 3n/2 c. n/4

b. n/2 d. n-1

ans. 3n/2

154. The number of comparisons of elements for worst case is ____________ in the case

of maxmin algorithm based on divide and conquer method

a. 3n/2 c. n/4

b. n/2 d. n-1

ans. 3n/2

155. The method which stops the execution ,if it find the solution. Otherwise it start from

the top

a. Branch and bound c. Dynamic programming

b. Back tracking d. Divide and conquer

Ans. Back tracking

156. Which is not return optimal solution from the following methods

a. Dynamic programming c. Backtracking

b. Branch and bound d. Greedy method

Ans. Backtracking

157. In the case ofsub problems share sub problems ,which method is suitable

a. greedy method c. branch and bound

b. dynamic programming d. divide and conquer

ans. Dynamic programming

158. The method which return different solutions from a single point ,which is

_________

a. greedy method c. branch and bound

b. dynamic programming d. divide and conquer

ans. Greedy method

159. ByQuicksortalgorithm from where is first partition done in the following array

a. 5 c. 3

b. 4 d. 1

Ans. 3

160. Binpackingproblem is the application of ____________

a. Knapsack c. Branch and bound

b. Back tracking d. Dynamic programming

Ans. Knapsack

161. job sequencing with deadline is based on ____________method

a. greedy method c. branch and bound

b. dynamic programming d. divide and conquer

ans. Greedy method

162. fractional knapsack is based on ____________method

a. greedy method c. branch and bound

2 8 7 1 3 5 6 4

b. dynamic programming d. divide and conquer

ans. Greedy method

163. 0/1 knapsack is based on ____________method

a. greedy method c. branch and bound

b. dynamic programming d. divide and conquer

ans. Dynamic programming

164. The files x1,x2,x3 are 3 files of length 30,20,10 records each. What is the optimal

merge pattern value?

a. 110 c. 60

b. 90 d. 50

Ans. 90

165. The optimal merge pattern is based on _________ method

a. Greedy method b. Dynamic programming

c. Knapsack method d. Branch and bound

Ans. Greedy method

166. Who invented the word Algorithm

a. Abu Ja’far Mohammed ibn Musa c. Abu Mohammed Khan

b. Abu Jafar Mohammed Kasim d. Abu Ja’far Mohammed Ali Khan

Ans. Abu Ja’far Mohammed ibn Musa

167. In Algorithm comments begin with____________

a. /* c. /

b. */ d. //

Ans : //

168. The ___________ of an algorithm is the amount of memory it needs to run to

completion.

a. Space Complexity c. Best Case

b. Time Complexity d. Worst Case

Ans : Space Complexity

169. ___________ is the process of executing a correct program on data sets and

measuring the time and space it takes tocompute the results.

a. Debugging c. Combining

b. Profiling d. Conqure

Ans : Profiling

170. In Algorithm Specification the blockes are indicated with matching _______

a. Braces c. Square Brackets

b. Parenthesis d. Slashes

Ans : Braces

171. Huffmancodes are the applications of _________ with minimal weighted external

path length obtained by an optimal set.

a. BST b. MST

c. Binary tree d. Weighted Graph

Ans : Binary tree

172. From the following which is not return optimal solution

a. Dynamic programming c. Backtracking

b. Branch and bound d. Greedy method

Ans. Backtracking

173. ____________ is an algorithm design method that can be used when the solution

to a problem can be viewed as the result of a sequence of decisions

a. Dynamic programming c. Backtracking

b. Branch and bound d. Greedy method

Ans : Dynamic programming

174. The name backtrack was first coined by _________

a. D.H.Lehmer c. L.Baumert

b. R.J.Walker d. S. Golomb

Ans : D.H.Lehmer

175. The term ________ refers to all state space search methods in which all hildren of 

the –nodes are generated before any other live node can becomethe E-node.

a. Backtacking c. Depth First Search

b. Branch and Bound d. Breadth First Search

Ans ; Branch and Bound

176. A __________ is a round trip path along n edges of G that visits every vertex once

and returns to its starting position.

a. MST c. TSP

b. Multistage Graph d. Hamiltonian Cycle

Ans :Hamiltonian Cycle

177. Graph Coloring is which type of algorithm design strategy

a. Backtacking c. Greedy

b. Branch and Bound d. Dynamic programming

Ans : Backtracking

178. Which of the following is not a limitation of binary search algorithm?

a. must use a sorted array

b. requirement of sorted array is expensive when a lot of insertion and deletions

are needed

c. there must be a mechanism to access middle element directly

d. binary search algorithm is not efficient when the data elements are more than 1000.

Ans : binary search algorithm is not efficient when the data elements are more than 1000.

179. Binary Search Algorithm cannot be applied to

a. Sorted linked list c. Sorted linear array

b. Sorted binary tree d. Pointer array

Ans :Sorted linked list

180. Two main measures for the efficiency of an algorithm are

a. Processor and memory c. Time and space

b. Complexity and capacity d. Data and space

Ans : Time and Space

181.The time factor when determining the efficiency of algorithm is measured by

a. Counting microseconds c. Counting the number of statements

b. Counting the number of key d. Counting the kilobytes of algorithm

operations

Ans : Counting the number of key operations

182. The space factor when determining the efficiency of algorithm is measured by

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 Ans: Counting the maximum memory needed by

the algorithm

183. Which of the following case does not exist in complexity theory

a. Best case c. Average case

b. Worst case d. Null case

Ans : Null Case

184. The Worst case occur in linear search algorithm when

a. Item is somewhere in the middle of c. Item is the last element in the array

the array d. Item is the last element in the array

b. Item is not in the array at all or is not there at all

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

185. The Average case occur in linear search algorithm

a. When Item is somewhere in the c. When Item is the last element in the

middle of the array array

b. WhenItem is not in the array at all d. When Item is the last element in the

array or is not there at all

Ans:When Item is somewhere in the middle of the array

186. The complexity of the average case of an algorithm is

a. Much more complicated to analyze c. Sometimes more complicated and

than that of worst case some other times simpler than that of

b. Much more simpler to analyze than worst case

that of worst case d. None or above

Ans: Much more complicated to analyze than that of worst case

187. The complexity of linear search algorithm is

a. O(n) c. O(n2)

b. O(log n) d. O(n log n)

Ans : O(n)

188. The complexity of Binary search algorithm is

a. O(n) c. O(n2)

b. O(logn) d. O(n log n)

Ans: O(log n)

189. The complexity of Bubble sort algorithm is

a. O(n) c. O(n2)

b. O(log n) d. O(n log n)

Ans : O(n2)

190. The complexity of merge sort algorithm is

a. O(n) c. O(n2)

b. O(log n) d. O(n log n)

Ans : O(n log n)

191. Which of thefollowing sorting algorithm is of divide-and-conquer type?

a. Bubble sort c. Quick sort

b. Insertion sort d. All of above

Ans : Quick Sort

192. An algorithm that calls itself directly or indirectly is known as

a. Sub algorithm c. Polish notation

b. Recursion d. Traversal algorithm

Ans : Recursion

193. The running time of quick sort depends heavily on the selection of

a. No of inputs c. Size o elements

b. Arrangement of elements in array d. Pivot element

Ans : Pivot Element

194. In stable sorting algorithm

a. One array is used c. More then one arrays are required.

b. In which duplicating elements are d. Duplicating elements remain in

not handled. same relative position after sorting.

Ans:Duplicating elements remain in same relative position after sorting.

195. Which sorting algorithn is faster :

a. O(n^2) c. O(n+k)

b. O(nlogn) d. O(n^3)

Ans :O(n+k)

196. In Quick sort algorithm,constants hidden in T(n lg n) are

a. Large c. Not known

b. Medium d. Small

Ans : Small

197. Quick sort is based on divide and conquer paradigm; we divide the problem on base

of pivotelementand:

a. There is explicit combine process as well to conquer the solution.

b. No work is needed to combine the sub-arrays, the array is already sorted

c. Merging the subarrays

d. None of above.

Ans:There is explicit combine process as well to conquer the solution.

198. Dijkstra’s algorithm :

a. Has greedy approach to find all shortest paths

b. Has both greedy and Dynamic approach to find all shortest paths

c. Has greedy approach to compute single source shortest paths to all other vertices

d. Has both greedy and dynamic approach to compute single source shortest paths to all

other vertices. 

Ans:Has greedy approach to compute single source shortest paths to all other vertices

199. What algorithm technique is used in the implementation of Kruskal’ssolution for

theMST?

a. Greedy Technique

b. Divide-and-ConquerTechnique

c. Dynamic Programming Technique

d. The algorithm combines more than one of the above techniques

Ans:Greedy Technique

200. Which is true statement in the following?

a. Kruskal’salgorithm is multiple source technique for finding MST.

b. Kruskal’s algorithm is used to find minimum spanning tree of a graph,

time complexity of this algorithm is O(EV)

c. Both of above

d. Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best

Tree edge) when the graph has relatively few edges )

Ans:Kruskal's algorithm (choose best non-cycle edge) is better than Prim's (choose best

Tree edge) when the graph hasrelatively few edges )

---------------------------Congratulations on solving 200+ MCQs----------------------------------

Bonus 25 MCQs:

Given a binary search tree, which traversal type would print the values in the nodes in

sorted order?

A. Preorder

B. Postorder

C. Inorder

D. None of the above

What is the running time of the following code fragment?

 for(int i=0; i<10; i++)

 for(int j=0; j<N; j++)

 for(int k=N-2; k<N+2; k++)

 cout << i << " " << j << endl;

A. O(log N)

B. O(N log N)

C. O(N)

D. O(N2)

E. O(N3)

Suppose we’re debugging a quicksort implementation that is supposed to sort an array in

ascending order. After the first partition step has been completed, the contents of the array

are in the following order:

 3 9 1 14 17 24 22 20

Which of the following statements is correct about the partition step?

A. The pivot could have been either 14 or 17

B. The pivot could have been 14, but could not have been 17

C. The pivot could have been 17, but could not have been 14

D. Neither 14 nor 17 could have been the pivot 

Which of the following statements about binary trees is NOT true?

A. Every binary tree has at least one node.

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

C. Every node has at most two children.

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

Which of the following will be the likely result of failing properly to fill in your name,

student ID, section number, and EXAM VERSION on your scantron form?

A. A score of 0 will be recorded for the multiple choice portion of the final exam,

regardless of how many questions you answer correctly.

B. Your grade in the course will be lower than it might otherwise be since a 0 will be

recorded for the multiple choice portion of the final exam.

C. You will earn the gratitude of your classmates by helping to lower the curve, since a 0

will be recorded for the multiple choice portion of the final exam.

D. You will need to do exceptionally well on the programming portion of this exam to help

offset the 0 that you will earn for the multiple choice portion.

E. All of the above

Suppose we have two classes, one of which extends the other:

class Base { … };

 class Derived: public Base { … };

Now suppose we execute the following program:

 line 1 int main( ) {

 line 2 Base* b;

 line 3 Derived* d = new Derived;

 line 4 b = d;

 line 5 delete d;

 line 6 return 0;

 line 7 }

What is the static type of variable b after line 4 has been executed and before line 5 is

executed?

A. Base *

B. Base &

C. Derived *

D. Derived &

E. Derived

[The dynamic type of a variable can change as the result of an assignment, but the static type is

fixed – it’s the one given in the variable’s declaration.]

How many times is the symbol ’#’ printed by the call foo(4)?

 void foo (int i) {

 if (i > 1) {

 foo (i/2);

 foo (i/2);

 }

 cout << "#";

 }

A. 3

B. 4

C. 7

7.

D. 8

E. Something else

A class template in C++ has the following structure

 template <class T> class TemplatedClass {

 …

 };

What is the meaning of T in the above declaration?

A. It is a placeholder for a pointer value

B. It is a placeholder for a type name

C. It is a string variable

D. It must be an integer constant

E. It must be a function name

Are there any dynamic memory management errors in the following code?

 int *p = new int;

 int *q = new int;

 int *r;

 *p = 17;

 r = q;

 *q = 42;

 p = q;

 delete r;

A. No, there are no errors

B. Yes, a memory leak

C. Yes, misuse of a dangling pointer

D. Yes, both a memory leak and misuse of a dangling pointer

E. Yes, a dangling chad 

Suppose we have the following pair of class definitions, along with implementations of some

functions of the derived class.

 class Odd {

 public:

 virtual void setName(string name);

 virtual void setID(int id) = 0;

 protected:

 int id;

 private:

 string name;

 };

 class Deranged: public Odd {

 public:

 virtual void setName(string name);

 virtual void setID(int id);

 };

 Deranged::setName(string name) {

 this->name = name; // this is statement A

 }

 Deranged::setID(int id) {

 this->id = id; // this is statement B

 }

The question concerns whether the two statements labeled A and B are legal (i.e., will be

accepted by a standard C++ compiler).

A. Both statements are legal

B. A is legal, B is not

C. B is legal, A is not

10.

D. Neither statement is legal 

5 of 17

Suppose we have the following class whose underlying data structure is a linked list of

ListNodes.

 class List {

 public:

 // other public functions

 ~List();

 private:

 struct ListNode {

 int item;

 ListNode *next;

 };

 ListNode *head;

 };

Which of the following sequences of code could be used in the destructor ~List() to correctly

delete all of the nodes in the list? (Which ones are legal, even if the style is atrocious?)

 I. for (ListNode *n = head; head != NULL; head = n) {

 n = head->next;

 delete head;

 }

 II. for (ListNode *n = head; n != NULL; n->next) {

 delete n;

 }

 III. ListNode* n;

 while (head != NULL) {

 n = head->next;

 delete head;

 head = n;

 }

A I and II only

B. II and III only

C. I and III only

11.

D. III only

E. I, II, and III 

6 of 17

Suppose you were implementing a data structure to store information about the paintings

on display at an art dealer’s showroom. Of the following data structures, which one is the

right one to use?

A. Unordered array

B. Sorted array

C. Linked list

12.

D. Binary search tree

E. It depends

[This was a recurring theme in our discussions of data structures. You have to know how the

data structure will be used and which operations need to be efficient to make an intelligent

choice. The question doesn’t provide enough information to do this without additional guesses

or assumptions.]

In lecture we defined a class IntStack to implement a stack of integers:

 class IntStack {

 public:

 IntStack( );

 bool isEmpty( );

 void push(int item);

 int pop( );

 int top( );

 }

What happens if we execute the following statements?

 IntStack s;

 int n1, n2, n3;

 s.push(17);

 s.push(143);

 s.push(42);

 n1 = s.pop( );

 n2 = s.top( );

 s.push(n1);

 n3 = s.pop( );

 n1 = s.top( );

A. Stack contains 143 (top), 17 (bottom); n1=42, n2=42, n3=42

B. Stack contains 42 (top), 42, 143, 17 (bottom); n1=42, n2=42; n3=42

C. Stack is empty; n1=17, n2=143, n3=42

D. Stack contains 42 (top), 17 (bottom); n1=42, n2=143, n3=143

13.

E. Stack contains 143 (top), 17 (bottom); n1=143, n2=143, n3=42 

7 of 17

Is this a binary search tree?

 55

 / \

17 60

 / \ / \

 5 20 42 105

 / \ \

 3 9 55

A. Yes

14.

B. No

What is the expected time required to search for a value in a binary search tree containing n

nodes? (You should make reasonable assumptions about the structure of the tree.)

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

15.

E. O(n2

)

If we use mergesort to sort an array with n elements, what is the worst case time required

for the sort?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

E. O(n2

)

There are several factors that affect the efficiency of lookup operations in a hash table.

Which of the following is not one of those factors?

A. Number of elements stored in the hash table

B. Size of elements stored in the hash table

C. Number of buckets in the hash table

D. Quality of the hash function

17.

E. All of the above factors affect the efficiency of hash table lookups 

8 of 17

What is the complexity of the following code expressed in O( ) notation? If more than one

answer is correct, choose the smallest one.

 for (int j = n; j > 0; j--) {

 for (int k = 1; k < j; k = k+k) {

 cout << j+k << “ ”;

 }

 cout << endl;

 }

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n2

)

18.

E. O(2n

)

What is the infix version of the following postfix expression?

 x 12 + z 17 y + 42 * / +

Hint: Try using a stack to evaluate the postfix expression and see what happens.

A. (x + 12 + z) / (17 + y * 42)

B. x + 12 + z / 17 + y * 42

C. x + 12 + z / (17 + y) * 42

D. x + 12 + z / ((17 + y) * 42)

19.

E. x + (12 + z) / (17 + y * 42) 

What is printed when we execute the following program?

 class FloridaBallot {

 public:

 FloridaBallot( ) { cout << “Welcome to Florida” << endl; }

 virtual ~FloridaBallot( ) { cout << “Come back soon!” << endl; }

 virtual void vote(string who);

 private:

 …

 };

 class PalmBeachBallot: public FloridaBallot {

 public:

 PalmBeachBallot( ) { cout << “Entering Palm Beach” << endl; }

 ~ PalmBeachBallot( ) { cout << “Leaving Palm Beach” << endl; }

 };

 int main( ) {

 FloridaBallot* b = new PalmBeachBallot;

 …

 b->vote(“Mickey Mouse”);

 …

 delete b;

 return 0;

 }

A. Welcome to Florida

Come back soon!

Entering Palm Beach

Leaving Palm Beach

B. Welcome to Florida

Entering Palm Beach

Come back soon!

Leaving Palm Beach

C. Welcome to Florida

Entering Palm Beach

Leaving Palm Beach

Come back soon!

D. Entering Palm Beach

Welcome to Florida

Come back soon!

Leaving Palm Beach

20.

E. Entering Palm Beach

Welcome to Florida

Leaving Palm Beach

Come back soon! 

Part II: 2 Short Answer Questions (10 points)

[Remember to answer question 20 on the back of the previous page. Don’t skip it!]

21. (6 points) Quicksort is claimed to have an expected running time of O(n log n), but it could

be as slow as O(n2

).

(a) Briefly explain why Quicksort could use O(n2

) time instead of always running in time

O(n log n).

Quicksort will use O(n2

) time if the partition function always picks as the pivot the largest or

smallest element of the array section being sorted. That will cause the depth of the

recursion to be O(n) instead of O(log n).

(b) How can you fix Quicksort so the expected time is O(n log n), if it can be done? You

should give a specific suggestion (don’t just say something like “be clever and careful”).

Explain why your solution will change the expected time to O(n log n).

Use a partition algorithm that partitions the array section into two equal-sized halves. One

way to do this is to pick the pivot element randomly; another is to use an algorithm that

estimates the median value in the array by, say, picking the median of the first, last, and a

few intermediate elements of the array section. This will limit the depth of the recursive

calls to O(log n) and, since each level does O(n) work, the total time will be O(n log n). 

22. (4 points) One of your colleagues is trying to debug a list class that uses an array to hold the

list elements. Something is wrong somewhere in this code. Where are the bug(s)?

Circle the bug(s) in the code and give a brief explanation of what’s wrong.

To save space, the implementations of the functions are given in the class definition, not in a

separate implementation file.

const int MAXSIZE = 1234; // max # elements that can be stored in a list

class List {

public:

 // construct empty list

 List( ) { size = 0; }

 // insert item at end of list; do nothing if list is already full

 void Insert(string item) {

 if (size < MAXSIZE) {

 size++; These statements are in the wrong order. size++

 data[size] = item; needs to be executed after the assignment, or

 } something similar needs to be done

 }

 // = # of elements in this list

 int sizeOf( ) {

 return size;

 }

 // = location of item in the list, or –1 if not found

 int find(string item) {

 int k = 0;

 while (data[k] != item && k < size) This needs to test k<size before accessing

 k++; data[k]. Reverse the condition so it is

 if (k < size) return k; else return –1; k < size && data[k] != item. Otherwise

 } searching for an element not in the list

 will reference data[size], which is out of

private: bounds

 int size; // # of elements currently stored in this list

 string data[MAXSIZE]; // list elements are stored in data[0..size-1]

};

 key to both bugs

Part III: Programming Questions (50 points)

23. (10 points) The nodes of a binary tree containing strings can be represented in C++ as

follows:

 struct BTNode { // binary tree node

 string data; // node data

 BTNode * left; // left subtree

 BTNode * right; // right subtree

 };

An internal node in a binary tree is one that is not a leaf, i.e., an internal node is one that has

at least one child.

Complete the following function so it returns the number of internal nodes in a binary tree.

Hint: Recursion is your friend.

 // = # of internal nodes in tree with given root

 int nInternal(BTNode *root) {

 // handle empty tree or leaf node

 if ((root == NULL) || (root->left == NULL && root->right == NULL))

 return 0;

 // internal node

 return 1 + nInternal(root->left) + nInternal(root->right);

 }

A couple of CSE grad students (including one of the TAs) were getting a bit punchy late one

night and came up with the following solution. The style is definitely something to be

avoided, unless you’re entering the Obfuscated C coding contest.

// = # of internal nodes in tree with root r

 int nInternal(BTNode *r) {

 return (r) ? (r->left || r->right) + nInternal(r->left) + nInternal(r->right) : 0;

 }

24. (25 points) Recall from lecture that a fixed-size queue can be implemented using an array, a

variable holding the number of items currently in the queue, and two variables indicating

where in the array the front and rear of the queue can be found.

The main complication is that the front and rear indicators need to wrap around to the

beginning of the array after they run off the end.

Here is the declaration of a CircularQueue class for a queue of integers. The comments on

the queue variables (data, front, and rear) are incomplete or missing – part of your task is to

figure out precise descriptions of these variables.

 const int QUEUESIZE = 100; // max # elements in the queue

 Class CircularQueue {

 public:

 // construct empty CircularQueue

 CircularQueue( );

 // = “this queue is empty”

 bool isEmpty( );

 // = “this queue is full”

 bool isFull( );

 // add item to the end of the queue (enqueue)

 // do nothing if the queue is already full

 void insert(int item);

 // return item at the front of this queue and remove it (dequeue)

 // precondition: this queue is not empty

 int remove( );

 private:

 int size; // # of items currently in the queue

 int data[QUEUESIZE]; // queue elements

 int front; // Queue elements are stored in data[front..rear-1]

 int rear; // modulo QUEUESIZE. data[front] is the first element

 // in the queue if it is non-empty. data[rear] is the next

// available element in the array where a new queue item

// can be stored, if the queue is not full.

 };

(a) Complete the comments to the right of variables front and rear to specify exactly how

they are used, i.e., which elements of array data they describe – first and last elements in the

queue? Next available slot in the queue? etc. (You may find it helpful to sketch your

implementation of the queue operations before you finish this part of the question.)

[There are many possible ways to define the queue pointers. Your answer did not have to

use the definitions given here, but it is important that the comments make clear whether the

front and rear indices point to queue elements, or the next unused array slot, or whatever.

The reader should not have to examine implementations of the queue operations to figure

that out. The code in your answer to part (b) should use these variables in a way that is

consistent with the comments in your solution to part (a).] 

(b) Complete the implementation of the CircularQueue member functions below. Your

implementations must be consistent with the definitions of front and rear that you gave in your

answer to part (a).

[You probably won’t need all of the space given, particularly for the first few functions.]

// construct empty queue

CircularQueue::CircularQueue( ) {

 size = 0;

 front = rear = 0;

}

// = “this queue is empty”

bool CircularQueue::isEmpty( ) {

 return (size == 0);

}

// = “this queue is full”

bool CircularQueue::isFull( ) {

 return (size == QUEUESIZE);

} 

// add item to the end of the queue (enqueue)

// do nothing if the queue is already full

void CircularQueue::insert(int item) {

 if ( isFull( ) )

 return;

 data[rear] = item;

 rear = (rear + 1) % QUEUESIZE;

 size++;

}

// return item at the front of this queue and remove it (dequeue)

// precondition: this queue is not empty

int CircularQueue::remove( ) {

 int item = data[front];

 front = (front + 1) % QUEUESIZE;

 size--;

 return item;

} 

25. (15 points) Suppose we have an application where we need to store a list of words, and we

need to efficiently support insert, delete, and lookup operations. Because insert and delete

need to be efficient, we decide to use a linked list. Unfortunately, that means that lookup

(search) operations have to scan the linked list – we can’t use binary search.

However, one of your colleagues has observed that, in practice, the words on the list are not

accessed randomly. In this particular application, if a word is accessed, then it is likely to be

accessed again sometime soon.

That suggests a strategy for speeding up searches. When we search for a word, if we find it,

we move the node containing that word to the front of the list. Then if we search for the

same word again, it is likely to be found near the front of the list.

Example: Suppose we have the following list of words

 elephant zebra aardvark platypus moose duck

and the user searches for “platypus”. The lookup function should return true (the word is

in the list) and should also rearrange the list so the node containing platypus has been

moved to the front of the list.

 platypus elephant zebra aardvark moose duck

If lookup searches for a word that is not in the list, it should return false and not change the

order of the nodes in the list.

Here are the key parts of the FancyList class definition.

 class FancyList {

 public:

 …

 // = “word was found in this FancyList”

 // (side effect – the node containing word is moved to the front of the list)

 bool lookup (string word);

 …

 private:

 struct LNode { // list node

 string word; // word stored in this node

 LNode *next; // pointer to next node in the list or null if no next node

 };

 LNode *head; // pointer to first node in the list, or null if list is empty

 };

Complete the implementation of the function lookup on the next page. For full credit, you

must rearrange the nodes in the list by updating the appropriate pointers. You MAY NOT

copy or swap the string values stored in the nodes. 

// = “word was found in this FancyList”

// (side effect – the node containing word is moved to the front of the list)

bool FancyList:: lookup(string word) {

 // if list is empty, word is not found

 if (head == NULL)

 return false;

 // if first node contains word, then we found it, and no rearrangement is needed

 if (head->word == word)

 return true;

 // General case: search for word.

 // At this point, the list is non-empty and the first node does not contain the desired word.

 LNode *prev = head;

 LNode *curr = head->next;

 while (curr != NULL && curr->word != word) {

 prev = curr;

 curr = curr ->next;

 }

 // either we found word or we reached the end of the list without finding it

 // return if we didn’t find it

 if (curr == NULL)

 return false;

 // word found – move that node to the front of the list and return

 prev->next = curr->next;

 curr->next = head;

 head = curr;

 return true;

}

---------------------Congratulations on solving 250+ MCQs-------------------

Champ you need More Bonus 50+ questions Mug it up !:

1.  Which of the following arrangements of general-purpose data structures is  from slowest to fastest for the purpose of finding objects according to a key value: 

1. sorted arrays,  unsorted linked lists, hash tables, binary search trees
2. sorted arrays, binary search trees, linked lists,   hash tables
3. hash tables, binary search trees, unsorted arrays, sorted linked lists
4. sorted linked lists, sorted arrays, binary search trees, hash tables

2.  Which of the following arrangements of general-purpose data structures is  from slowest to fastest for the purpose of storing objects by key value (not necessarily in order): 

1. unsorted arrays,  sorted linked lists, hash tables, binary search trees
2. sorted arrays, binary search trees, linked lists,   hash tables
3. hash tables, binary search trees, sorted arrays, sorted linked lists
4. unsorted arrays, linked lists, binary search trees, hash tables

1. In an abstract data type, access is often limited to certain items.  Which of the following is not such an abstract data type?

1. binary search tree
2. priority queue
3. queue
4. stack

1. Which of the following is not a basic data structure that could be used to implement an abstract data type?

a.   array b.  linked list c.  hash table d.  heap

1. Which of the following statements is true?

1. An abstract data type can be conveniently searched for an item by key.
2. An abstract data type can be conveniently traversed.
3. An abstract data type is an interface within a program that simplifies problems.
4. An abstract data type is a database for direct user-accessible data. 

1. Which of the following methods of implementing a priority queue is best when both insertion and deletion need to be reasonably fast?

a.  ordered array b.  ordered linked list c.  heap d.  binary search tree

1. If the amount of data to be stored in a stack cannot be predicted, the best data structure to implement the stack is:

a.  hash table b.  binary search tree c.  linked list d. unordered array

1. Which of the following statements is true regarding a queue?

1. It may be implemented either by an array or a linked list.
2. It may be implemented by a heap because first in is first out.
3. It may be implemented by a linked list because insertions and deletions may be from the same end.
4. It may be implemented by an array without providing for wrap-around.

1. Which of the following sort algorithms is not an O(n²) sort?

a.  shell sort b.  insertion sort c.  selection sort d.  bubble sort

1. Which of the following is true regarding the efficiency of the shell sort ?

1. It is slower than O(n²).
2. It is faster than O(n*log₂ n).
3. It is not as efficient as the insertion sort.
4. It has not been established theoretically, i.e. as a single function of n.

11. The __________________ sort is good for almost-sorted files, operating in O(n) time if not too many items are out of place.

a.  insertion b.  bubble c. selection quicksort

12.  Which of the following sorts does not operate in O(n*log₂ n) time?

a.  quicksort b.  mergesort c.  heapsort d.  hashsort

13.  Which of the following sorts is not efficient in use of storage because it requires an extra array?

a.  quicksort b.  mergesort c.  heapsort d.  insertion sort

14.  Which of the following sorts may deteriorate to O(n²) time if the data is partitioned into a subarray  of 1 element and a subarray of n-1 elements?

a.  insertion sort b.  mergesort c.  heapsort d.  quicksort

15.  Which of the following sorts is efficient in time but requires a considerable amount of extra storage space?

        a.  shell sort b.  mergesort c.  heapsort d.  quicksort

16.  If the rightmost element is selected as the pivot in the quicksort

a.  when the data is truly random, that value is a good choice.

b.  when the data is sorted, that value is a good choice.

c.  when the data is in reverse order, that value is a good choice.

d.  that value is never a good choice.

                       (left) 44 _ _ _ _ ..._ _ _ _ 86 _ _ _ _ --- _ _ _ _ 29 (right)

17.  Applying the median-of-three method to the above array in the quicksort, which of the following would be selected as the pivot to partition the array.

a.  44 b.  86 c.  29 d.  53

18.                   90  100  20  60  80  110  120  40  10  30   50   70

                         0      1     2    3    4     5     6      7    8   9    10   11

Apply one partition to the above array in the quicksort with 70 as the pivot and 

            show the position of each item in the array immediately after that partition.

19.       Arrange the following functions, often used to represent complexity of algorithms 

in order from slowest to fastest.

                  O(1), O(n), O(n*log₂ n), O(log₂ n), O(n²), O(2ⁿ)

20.  public void mergeSort()           // called by main()

      {                              // provides workspace

      double[] workSpace = new double[nElems];

      recMergeSort(workSpace, 0, nElems-1);

      }

   //-----------------------------------------------------------

   private void recMergeSort(double[] workSpace, int lowerBound,

                                                 int upperBound)

      {

      if(lowerBound == upperBound)            // if range is 1,

         return;                              // no use sorting

      else

         {                                    

         int mid = (lowerBound+upperBound) / 2;

         recMergeSort(workSpace, lowerBound, mid);

         recMergeSort(workSpace, mid+1, upperBound);

         merge(workSpace, lowerBound, mid+1, upperBound);

         }  // end else

      }  // end recMergeSort()

Apply the above sort to this array:     64   21   33   70   12   85   44   3   97   24   51   40

                                                            0      1     2     3     4     5     6    7    8     9    10   11

Show each subarray as it is ordered.  (Hint:  10 subarrays of lengths 2,3 and 6 are sorted and merged.)

21.  Starting with h = 1, generate the gap sequence for the shellsort using the recursive

       expression:  h = 3*h + 1, for an array of 1000 elements.

22.                               12   13   11   16   14   15   18  19   17   20  

0      1     2     3     4     5     6    7    8     9    

The shellsort has been applied to the above array but is not completed!

Has the array been "4-sorted"?  If yes, prove your answer by exhaustion.

If no, prove your answer by counterexample.

23.  In computer science a graph is a data structure where vertices (nodes) represent objects which in turn represent real world data, and edges represent references to objects:  how objects are related.  T/F

 Refer to this graph for nos. 24 - 27

24.  What is the degree of vertex 'a' ?

25.  Does an Eulerian path exist for this graph?  If yes, show one.  If no, explain why.

26.  Show a depth-first search of this graph starting at vertex b.

27.  Show a breadth-first search of this graph starting at vertex b.

28.  A rooted tree is a directed graph in which each node is referenced by at 

       most ___ node(s).

29.  A binary tree is a tree in which each node references at most _____ node(s).

30.  A binary search tree is a binary tree in which the data in the left subtree of a node is 

       greater than the data in the node and the data in the right subtree is greater than the 

       data in the node.  T/F

31.  A binary expression tree is a binary tree in which the data in the left subtree of a 

       node is greater than the data in the node and the data in the right subtree is greater 

       than the data in the node.  T/F

32.  What is the minimum height of a binary tree with 31 nodes?

33.  If  a binary search tree containing 31 nodes is balanced, what is the maximum number of comparisons needed to find any key value?

Refer to this binary tree for questions 34 -  36                                 

                    20

          30                  10

   5             15      25       35

 8   1      12   18

34.  A preorder traversal of this tree is ______________________________________.

35   An inorder traversal of this tree is ______________________________________.

36.  A postorder traversal of this tree is ______________________________________.

Refer to this binary tree for questions 37 - 40

         25

15 35

    10         20          30      40

37.  Redraw the tree after the value 18 is inserted.

38.  Redraw the tree after the value 18 is inserted and 25  is removed.

39.  Which of the following is the result of a postorder traversal of the original tree?

a.  10 15 20 30 35 40 25 b.  10 20 15 30 40 35 25

c.  10 15 20 25 30 35 40 d.  40 35 30 25 20 15 10

40.  Which of the following is the result of a preorder traversal of the original tree?

a.  25 10 15 20 30 35 40 b.  25 15 10 20 35 30 40 

c.  10 15 20 25 30 35 40 d.  40 35 30 25 20 15 10

Refer to this binary expression tree for questions 41 - 

+

/ *

    -           c             d       e

                       a      b

41.  Choose the algebraic expression stored in the above tree.

a.  * + / - a b c d e b.  - a b / c + * d e

c.  + / a b - c * d e d.  + / - a b c * d e

42.  Choose the algebraic expression stored in the above tree.

a.  ((a - b / c) + d * e) b. (((a - b) / (c + d) ) + d * e)

c.  ((a - b / c) + (d * e) ) d. (((a - b) / c) + (d * e))

43.  Draw a binary expression tree that stores the expression:  (((a - b) / c) + (d * e))

44.  Which of the following is not true about a binary expression tree?

a.  All the internal nodes are operators.

b.  All operands are leaves.

c.  All data is stored following the rule:  left subtree < root < right subtree.

d.  All nodes have exactly 0 or 2 children.

45.  The minimum height of a binary search tree containing   n   nodes is: 

a.      n - 1 b.  (int) log₂ n c.  n d. no. levels + 1

46.  Which of the following statements concerning binary search trees is always true?

a.  The search time is O(log₂ n).

b.  They are always balanced.

c.   The delete time is O(log₂ n).

d.  The insert time depends on how well balanced they are.

47.  Which of the following statements concerning heaps is not true?

a.  A heap can be stored in a binary search tree.

b.  A heap can be stored in an array.

c.  A heap can be used to implement a priority queue.

d.  A heap can be used to sort data.

48.  Which of the following statements concerning heaps is not true?

a.  Traversing a  heap in order provides access to the data in numeric or

     alphabetical order

b.  Removing the item at the top provides immediate access to the key value 

     with highest (or lowest) priority.

c.  Inserting an item is always done at the end of the array, but requires

     trickleup() to maintain the heap rule.

d.  A heap may be stored in an array.

49.  A heapsort -

a.  is impossible because the data is not in order, except that the highest is first.

b.  requires a second array, making it space inefficient.

c.  has O(n²) complexity.

d.  is almost as efficient as the quicksort.

Answers:

1 d  

2 b  

3 a  

4 c  

5 c  

6 c  

7 c  

8 a  

9 a  

10 d  

11 a  

12 d

13 b 14 d 15 b 16 a 17 a

18.  50 30 20 60 10 40 70 110 80 100 90 120

19. 2ⁿ   n²   n*log n   n     log n    1

20  see p.234

21. 1  4  13  40  121  364

22  yes:  12<14<17     13<15<20      11<18      16<19

23 true

24.  3 25. no - more than 2 odd vertices 26.  baecd or bcdae or others

27. baced  or bcade or others 28. 1 29. 2 30. false   31 false     32. 4      33. 5

34.  20 30 5 8 1 15 12 18 10 25 35

35.  8 5 1 30 12 15 18 20 25 10 35

36.  8 1 5 12 18 15 30 25 35 10 20

37 25

             15 35

          10   20           30    40

               18

38 20 or 30

             15 35 15 35

          10   18           30    40       10       20                     40

                 18

39. b 40. b 41. d 42. d

43 +

  /                  *

                       -      c           d      e

                    a   b

44 c

45 b  

46 d  

47 a  

48 a  

49 d