1. Let G be a graph and let u and v be two distinct vertices of G. Assume that G has two different walks between u and v. Choose the correct answer between the following (10 marks) two. (a) G has a cycle. (b) G does not necessarily have a cycle. 42. Let G be a graph and suppose that G has a trail with repeated vertices. Choose the correct answer between the following two. (a) G has a cycle. (b) G does not necessarily have a cycle. 3. Choose the correct between the following two. 4. (a) MergeSort is not an O(n) algorithm. (b) MergeSort is an O(n) algorithm. (10 marks) (10 marks) Let n 3 be an integer and let A = [n-1,1,2,3...,0]. (For instance, for n = 5, A = [4,1,2,3,0].) Choose the correct statement between the following two. (10 marks) (a) The Insertion Sort does not sort A in O(n). (b) The Insertion Sort sorts A in O(n).