Description

CS203 Data Structure and Algorithm Analysis Quiz 1
Note 1: Write all your solutions in the question paper directly. You can ask additional answer paper if necessary
Note 2: If a question asks you to design an algorithm, full points will be given if your algorithm runs with optimal time complexity
Note 3: If a question asks you to design an algorithm, you should first describe your ideas in general words, then write the pseudocode, and end with time complexity analysis.

Problem 1 [25 points, 5 per points]
1) Which of the following function is not 𝑂(𝑛2.5) ( )
A. 𝑛 2100𝑛 B. (log2 n)98 C. 938593729n2 D. n2.6/log2 n

2) Which of the following functions is 𝑂
A. 358· nlog2 n B. n1.2/log5 n C. (1.01)n D. n · (log2 n)1.0003

3) There are 5 elements, which are pushed into the stack by the order e1, e2, e3, e4, e5. If e3 is the first element be popped and e4 is the second, in this case, please list out all the possible order of pop stack:
A. 𝐞𝟑, 𝐞𝟒, 𝐞𝟓, 𝐞𝟐, 𝐞𝟏 B. 𝐞𝟑, 𝐞𝟒, 𝐞𝟐, 𝐞𝟓, 𝐞𝟏 C. 𝐞𝟑, 𝐞𝟒, 𝐞𝟐, 𝐞𝟏, 𝐞𝟓 D. 𝐞𝟑, 𝐞𝟒, 𝐞𝟓, 𝐞𝟏, 𝐞𝟐
4) Stack s is empty, use s to convert the infix expression 6/2 +(8*9-3*5)/3 to equivalent postfix expression. In the process, when the 5 is scanned, what are the elements in the stack (from stack bottom to top)?
A. +(*- B. +(-* C. /+(*-* D. /+-*

5) Suppose f(1) = 1; f(2) = 2; f(n) = 3 + f(n − 2). f(n) = ___ O(n)____. (in terms of BigO notation).
Problem 2, 25 Let S1 be an unsorted array of 𝑛 integers, and S2 is another sorted array of log2𝑛 integers (𝑛 is a power of 2, S2 is in descending order). Describe an algorithm to output the number of pairs (x, y) satisfying x ∈ S1, y ∈ S2, and x ≤ y. Your algorithm must terminate in 𝑂(𝑛loglog𝑛) time. For example, if S1 = {10, 7, 12, 18} and S2 = {15, 7}, then you should output 4 because 4 pairs satisfy the required conditions: (10, 15),(7, 15),(12, 15),(7, 7).

Problem 3, 20 Method B is a sorting algorithms, please answer questions. The start position of array Arr is 0. Method B:
void sortB(int Arr[], int low, int high){ if(low < high){ int pi = partition (Arr, low, high); print array Arr; // Line Output sortB( Arr, __low__, __pi-1__ ); sortB( Arr, pi+1, high );
}
}
int partition (int Arr[], int low, int high) { pivot = Arr[high]; i = (low – 1) for (j = low; j <= high- 1; j++) { if (Arr[j] <= pivot) { i++; swap (_Arr[i]___, __Arr[j]__)
}
}
swap (Arr[i + 1] , Arr[high]) return (i+1);
}
(1) Please complete the method B then it works as quick sort [6 points]
(2) If the original sequence is “25, 40, 3, 55, 30, 26, 18, 45”, after invoking Method B, please write down the outputs (Line output) step by step. [14 points]

Problem 4, 30 Design a function to check if a linked list is a palindrome. For example:
Linked list A: 1->2->3 is not a palindrome, return No.
Linked list B: 1->2->3->2->1 is a palindrome, return Yes.