代写CSCI2100D程序、代做C++编程语言、c/c++设计程序调试

日期：2021-03-16 10:15

CSCI2100D 2018-19: Midterm Exam

Time allowed: 105 minutes Student No.:

Q1. [10 marks] Sort the functions below in ascending order of growth rate and justify

your answer briefly. [12 marks] Fill in the C language code from line 7 to 9 in the function below and

analyze 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 not

divisive by other numbers except 1 and itself. For example, 2, 3, and 17 are three prime

numbers. 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 to

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

– Algorithm1

1 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 prime

5 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 prime

5 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 i

7 }

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 integers

in 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 A

but 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 ;

6

7 List SetDifference ( List headA , List headB ){

8 List head = NULL ;

9

10 return head ;

11 }

– Implement the function SetDifference in C language efficiently and analyze the

time complexity of your algorithm. For your time complexity analysis, you can

assume 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 an

algorithm 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 can

assume that the input sequence is stored in a character array Seq of size n, and print

“valid” or “invalid” as the output.

Q6. [20 marks] Binary Tree Traversal. An Inorder traversal of a binary tree visits the

left subtree, the root, and the right subtree. A Preorder traversal visits the root, the left

subtree, and the right subtree. A Postorder traversal visits the left subtree, the right

subtree, and the root.

– Write down the tree node sequence by Inorder, Preorder and Postorder traversal of

the given tree, respectively.

– For one binary tree, we perform Inorder and Preorder traversal on it and obtain the

tree node sequences shown below. Reconstruct and draw the binary tree.

Inorder : ADEFGHMZ

Preorder: GDAFEMHZ