CS203 2017秋 期中

Data Structure and Algorithm Analysis

2017-18 Midterm Examination B

Part I. Please answer the questions (32%)

1. Write down a kind of structure that we can directly locate elements: $\underset{―}{}$.

2. What is the corresponding postfix expression of the infix expression $(3+4\ast 2)\ast 3-6/3$: $\underset{―}{}$.

3. What is the number of non-empty substrings of the string "windows10": $\underset{―}{}$.

4. What is the basic difference between stack and queue? $\underset{―}{}$ is FIFO, $\underset{―}{}$ is LIFO.

5. Suppose there is a stack; when we push an element into the stack it prints "S", and when we pop an element it prints "X". Four integers are pushed in order 1,2,3,4. If we want the pop order 3,4,2,1, what is the corresponding sequence of operations (sequence of S and X)? $\underset{―}{}$.

6. Suppose an empty stack receives pushes $e_1,e_2,e_3,e_4,e_5,e_6$ in that order. If the pop order is $e_4,e_3,e_2,e_6,e_5,e_1$ what is the minimum capacity of the stack? $\underset{―}{}$.

7. Suppose that we use an array (capacity 6) to simulate a queue and when the index value of rear equals front, the queue is empty. Now the index values of rear and front are 4 and 2 respectively, in this case, after we add two elements into the queue, what's the index value of rear? $\underset{―}{}$ After that we remove one element out of the queue, what's the index value of front? $\underset{―}{}$

Part II. Short answer questions (28%)

II-1

A is a linear table $[a_1,a_2,...,a_n]$ and use a sequential storage structure. In the case of equal probability, what's the average number of element needed to move when adding an element to A? Please write a brief description of the calculation process.

II-2

we know a pattern string P = "abababc" and a target string S = "abababababcaba"

II-2-1

You are asked to give the next array of the pattern string P = "abababc"

II-2-2

Please draw the matching process using KMP algorithm

Definition:

$$\mathrm{next}[j]=\{\begin{array}{ll}-1,& j=0,\\ max\{k:0<k<j\text{and}P(0\dots k-1)=P(j-k\dots j-1)\},& \text{if k exists},\\ 0,& \text{otherwise}.\end{array}$$

II-3

write down a class of doubly linked list and describe its process of adding and deleting an element

II-4

Given a string, you are supposed to judge if it is symmetric, For Example, given "abba", you should return 1, given "abbc" ,you should return 0.

Part III. Algorithms and programming (40%)

III-1

Given a nonnegative integer (1<=n<=10), compute n! using recursion. Examples:

$$3!=6,4!=24,5!=120$$

III-2

Suppose we have two singly linked lists. Maybe they have some common nodes. Please design an algorithm to find their first common node.

Assume the lengths of the two linked lists are m and n ,

if your algorithm's time complexity is $\mathrm{O}(m+n)$, you can get 10 marks at most;

if $\mathrm{O}(\mathrm{mn})$, you can get 6 marks at most.

III-3

Using the defined double stack structure as following, please implement how to calculate the result of a postfix expression.

Stack_Double
- capacity : int
- S: double[]
- top: int
+ Stack_Double(int)
+ IsEmpty() : boolean
+ push(double) : void
+ top() : double
+ pop() : double

III-4

Real estate developers plan to build $m(2\le m\le n)$ houses along a river. The houses can be located along a straight line at positions $x_1,\dots ,x_n(2\le x_1<x_2<\dots <x_n\le 10000)$ near the river bank.

As we know, one of the factors that decide the house price is the distance of this house away from its neighbors: the further it is away from its neighbors, price could be higher.

They ask you for help to find the largest minimum distance. Please design and implement an algorithm which time complexity is $\mathrm{O}(n\log n)$.