Question 7: Sorting [20] Consider the following sequence of numbers 11, 8, 9, 4, 2,5, 3, 12, 6, 10, 7 a) Sort the list using selection sort. Show the state of the list after each call to the swap procedure. b) Sort the list using insertion sort. For each iteration of the outer loop of the algorithm show the state of the list. c) Sort the list using quick sort with the middle element as pivot. For each iteration of the outer loop of the algorithm show the state of the list. You are not required to write code for this question. You need to trace through the different sorting algorithms using the given list. Question 1: Linked Lists [5] Consider a linked list called list depicted below. Assume the node is in the usual info-link form. (list and Ptr are pointers of type nodeType.) per A Suppose calling exchange (2,4) on the list will rearrange the nodes such that the second node is D and the last node is B. Without changing the order of the nodes in the above diagram, adjust the links of this list below to show the results after calling exchange (2,4): A o o o Ptr Note that the exchange () function does not swap the elements of the nodes. Write C++ code to implement (a). Do not provide the complete function. Question 2: Linked Lists [15] 2.1 Add the following operation to the class orderedLinkedList: void mergeLists (orderedLinkedList &listi, orderedLinkedList & list2) //This function creates a new list by merging the elements //of listl and list2. //Postcondition: first points to the merged list; listi and list2 //are empty Example: Consider the following statements: orderedLinkedList newList; orderedLinkedList listi; orderedLinkedList list2; suppose listi points to the list containing the elements 2 6 7 and list2 points to the list containing the elements 3 5 8. The statement: newList.mergeLists (listi, list2); creates a new linked list with the elements in the order 2 3 4 5 7 8 and the object newLists points to this list. After the preceding statement have executed, listi and list2 are empty. 2.2 Write the definition of the function template to implement the operation mergeLists. Write a program to test your function thereafter. Question 3: Recursion [6] Write a recursive function template, identicals that checks whether two stacks provided as parameters are identical. If that is the case, the function should return the Boolean value true otherwise the Boolean value false should be returned. Use the following header: template bool identicals (stackType si, stackType 52); Question 4: Stacks [6] L={abn} where n 21, is a language of all words with the following properties: The words are made up of strings of a's followed by b's. The number of a's is always equal to the number of b's. Examples of words that belong to L are ab, where n=1; aabb, where n=2; aaabbb, where n=3; aaaabbbb, where n=4. One way to test if a word w belong to this language is to use a stack to check if the number of a's balances the number of b's. Use the provided header and write a function isInLanguageL that uses a stack to test if any word belongs to L. bool isInLanguagel (string w); Question 5: Queues [16] a) Write a function reverse that uses a local stack to reverse the contents of a queue. Use the following header: template void reverseQ ( queue Type &q) You can make use of any member function of class queueType. Note that this function is not a member of class queueType. (6) b) Implement question 4 using a queue instead of a string as in the following header: bool isInLanguageLQ (queueType &W) (10) Question 6: Searching [6] Describe how the binary search algorithm will search for 27 in the following list: 5, 6, 8, 12, 15, 21, 25, 31