辅导CSCI2100D程序、写作C++编程

” 辅导CSCI2100D程序、写作C++编程CSCI2100D 2018-19: Midterm ExamTime allowed: 105 minutes Student No.:Q1. [10 marks] Sort the functions below in ascending order of growth rate and justifyyour answer briefly. [12 marks] Fill in the C language code from line 7 to 9 in the function below andanalyze the time complexity of the function in O notation. int find(int n, int A[], int Value)Find a given value in a sorted array A of size n. Numbers in A satisfy:A[0] A[1] A[2] A[n 1]If A[i] = value : return i;Otherwise : return -1.1 int find (int n , int A [] , int value ){2 int left , right , mid ;3 left = 0;4 right = n – 1;5 while ( left = right ){6 mid = ( left + right ) / 2;7 if( A [ mid ] == value )Q3. [18 marks] A prime number (or a prime) is a natural number greater than 1 that is notdivisive by other numbers Except 1 and itself. For example, 2, 3, and 17 are three primenumbers. Given a positive integer n as input, the problem is to find all prime numbers in[2, n]. In the following, we provide three valid algorithms implemented in C language tosolve this problem. Give the time complexity of each algorithm in O notation. void algo(int n, int isPrime[])The array isPrime contains the result.isPrime[i] = 0 : i is not a Prime;isPrime[i] = 1 : i is a prime. Algorithm11 void algo1 (int n , int isPrime []){2 int i , j ;3 for ( i =2; i = n ; i ++){4 isPrime [ i ] = 1; // assume i is a prime5 for( j =2; j i ; j ++)6 if( i % j ==0) isPrime [ i ] = 0;7 }8 } Algorithm2: Only line 5 is changed compared to Algorithm 1.1 void algo2 (int n , int isPrime []){2 int i , j ;3 for ( i =2; i = n ; i ++){4 isPrime [ i ] = 1; // assume i is a prime5 for( j =2; j *j = i ; j ++)6 if( i % j ==0) isPrime [ i ] = 0;7 }8 } Algorithm3: For each integer j (j 1), 2j, 3j, 4j, are not prime numbers.1 void algo3 (int n , int isPrime []){2 int i , j ;3 for ( i =2; i = n ; i ++) isPrime [ i ] = 1;4 for ( j =2; j n ; j ++)5 for( i = j *2; i = n ; i += j )6 isPrime [ i ] = 0; // j is a factor of i7 }Q4. [20 marks] Compute the set difference of two linked lists. In this problem, we use a singly linked list to maintain a sequence of distinct integersin ascending order. Now, we have two linked lists denoted as A and B as input,which represent two sets of sorted integers. List SetDifference(List headA, List headB)Create a new sorted list As the set difference A\B, that is, if an integer is in list Abut not in list B, then insert it into the result linked list.1 typedef struct linked_list_node {2 int value ;3 struct linked_list_node * next ;4 } Node ;5 typedef Node * List ;67 List SetDifference ( List headA , List headB ){8 List head = NULL ;910 return head ;11 } Implement the function SetDifference in C language efficiently and analyze thetime complexity of your algorithm. For your time complexity analysis, you canassume that there are n integers in A andm integers in B. An algorithm withO(n m)time complexity is regarded not very efficient, thus cannot get full marks.Q5. [20 marks] Given a sequence of characters composed of (, ), [ and ], design analgorithm to determine whether it is a valid sequence. Definition: An empty sequence is valid; A ( immediately followed by a ) is valid, but is invalid in the reverse order, i.e., () is valid, and ) ( is invalid; A [ immediately Followed by a ] is valid, but is invalid in the reverse order, i.e.,[ ] is valid, and ] [ is invalid; A valid sequence contained in a pair of ( ) or [ ] is still valid; A concatenation of Two valid sequences is still valid; A single character that is unpaired is invalid; A sequence having a pair of ( ) and a pair of [ ] with partial overlap is invalid, e.g.,( [ ) ], and [ ( ] ). Valid Sample 1 : ( )Valid Sample 2 :Valid Sample 3 : ( ( ) [ ] ) [ ( ) ] ( ) Invalid Sample 1 : ( ( ( ( ) ) ) ]Invalid Sample 2 : ( [ ) ]Invalid Sample 3: [ ( ] Show your algorithm in pseudo-code and analyze its time complexity. You canassume that the input sequence is stored in a character array Seq of size n, and printvalid or invalid as the Output.Q6. [20 marks] Binary Tree Traversal. An Inorder traversal of a binary tree visits theleft subtree, the root, and the right subtree. A Preorder traversal visits the root, the leftsubtree, and the right subtree. A Postorder traversal visits the left subtree, the rightsubtree, and the root. Write down the tree node Sequence by Inorder, Preorder and Postorder traversal ofthe given tree, respectively. For one binary tree, we perform Inorder and Preorder traversal on it and obtain thetree node sequences shown below. Reconstruct and draw the binary tree.Inorder : ADEFGHMZPreorder: GDAFEMHZ如有需要，请加QQ：99515681 或WX：codehelp

“