CS203 2017秋 期中 答案

一、填空题

1-1

array

1-2

342*+3*63/-

1-3

45

1-4

queue、stack

1-5

SSSXSXXX

1-6

4

1-7

0, 3

二、简答题

2-1

n/2

2-2

-1 0 0 1 2 3 4

2-3

public class DoublyLinkedList<E> {
    int size;
    Node<E> first;
    Node<E> last;
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
    public void add(int index, E element) {
        if (!(index >= 0 && index <= size)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, element, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
        } else {
            Node<E> succ = node(index);
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, element, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
        }
    }
    public E delete(int index) {
        if (!(index >= 0 && index < size)) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> x = node(index);
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        return element;
    }
}

2-4

for(int i = 0; i < n / 2; i++) {
    if (s[i] != s[n - i - 1]) {
        return false;
    }
}
return true;

三、算法与程序设计

3-1

int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

3-2

1. Find the lengths of the two linked lists, say n and m, assume n >= m.
2. Advance the longer list by (n - m) steps.
3. Then move both pointers together until they meet; the meeting node is the first common node.

3-3\

Postfix notation is easier to calculate than other notation. With two simple operations, stack push and stack pop, any normal expression can be handled:

• If the current character is a digit, push to stack.
• If it is an operator, pop the top two elements, perform the operation, and push the result back.
• When all characters are processed, the stack should contain only one element, which is the final result.

3-4

Binary search:

• The maximum possible value: $mvp=(x_n-x_1)/(m-1)$
• Binary search from 0 to mvp (begin = 0, end = mvp), each time check whether the distance can be satisfied.

fakecode:

current value = 0
If check returns true:
  if mid is bigger than current value:
    update current value from mid+1 to end
  else if check return false
    adjust the range from begin to mid-1