1. Let G be a graph and let u and v be two distinct vertices of...

Transcribed Image Text:

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

Answer rating: 100% (QA)

Answer 1 The correct answer is b G does not necessarily have a cycle Explanation Having two differen... View the full answer