算法导论10.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

10.1-1

可以发现，大矩阵\(m\times n\)的所属块号由行坐标和列坐标的最高比特决定。由于是行坐标优先，因此转化成一维序列是，最高的两位坐标为\(i_{\lg m-1},j_{\lg n-1}\)。块内依旧行优先，因此剩下的\(m-1\)比特行坐标排高位，剩下的\(n-1\)比特行坐标排低位。因此最终答案为

\[\langle i_{\lg m-1},j_{\lg n-1},i_{\lg m-2},i_{\lg m-3},\dots,i_1,i_0,j_{\lg n-2},j_{\lg n-3},\dots,j_1,j_0\rangle\]

10.1-2

\(\begin{array}{|l|} \hline \text{PUSH}(S, 4)\\ \hline \text{PUSH}(S, 1)\\ \hline \text{PUSH}(S, 3)\\ \hline \text{POP}(S)\\ \hline \text{PUSH}(S, 8)\\ \hline \text{POP}(S)\\ \hline \end{array} \quad \begin{array}{|l|l|l|l|l|l|} \hline 4\\ \hline 4&1\\ \hline 4&1&3&\phantom{3}&\phantom{3}&\phantom{3}\\ \hline 4&1\\ \hline 4&1&8\\ \hline 4&1\\ \hline \end{array}\)

10.1-3

数组的左边可以用于栈存储，右边也可以用于栈存储。一开始，左栈顶指针栈空时指向左外侧\(0\)，如果需要入栈那么将左栈顶指针右移，出栈时将左栈顶指针左移；同样的，右栈顶指针栈空时指向右外侧\(n+1\)，如果需要入栈那么将右栈顶指针左移，出栈时将右栈顶指针右移。当这两个栈顶指针恰好相邻时，两个栈都满了（数组\(A\)都占用完成）。可以发现，无论出栈入栈本质上是指针移动一个单位的操作，因此运行时间均为\(O(1)\)。

10.1-4

\(\begin{array}{|l|} \hline \text{ENQUEUE}(Q, 4)\\ \hline \text{ENQUEUE}(Q, 1)\\ \hline \text{ENQUEUE}(Q, 3)\\ \hline \text{DEQUEUE}(Q)\\ \hline \text{ENQUEUE}(Q, 8)\\ \hline \text{DEQUEUE}(Q)\\ \hline \end{array} \quad \begin{array}{|l|l|l|l|l|l|} \hline 4\\ \hline 4&1\\ \hline 4&1&3&\phantom{3}&\phantom{3}&\phantom{3}\\ \hline &1&3\\ \hline &1&3&8\\ \hline & &3&8\\ \hline \end{array}\)

10.1-5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
QUEUE-EMPTY(Q)
  return Q.head == Q.tail

QUEUE-FULL(Q)
  return Q.head == Q.tail + 1 or (Q.head == 1 and Q.tail == Q.size)

ENQUEUE(Q, x)
  if QUEUE-FULL(Q)
    error "overflow"
  Q[Q.tail] = x
  if Q.tail == Q.size
    Q.tail = 1
  else Q.tail = Q.tail + 1

DEQUEUE(Q)
  if QUEUE-EMPTY(Q)
    error "underflow"
  x = Q[Q.head]
  if Q.head == Q.size
    Q.head = 1
  else Q.head = Q.head + 1
  return x

10.1-6

将沿用题目10.1-5的两个子程序QUEUE-EMPTY(Q), QUEUE-FULL(Q)判断双端队列是否为空/满。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
HEAD-ENQUEUE(Q)
  if QUEUE-FULL(Q)
    error "overflow"
  x = Q[Q.head]
  if Q.head == 1
    Q.head = Q.size
  else Q.head = Q.head - 1
  Q[Q.head] = x

HEAD-DEQUEUE(Q)
  if QUEUE-EMPTY(Q)
    error "underflow"
  x = Q[Q.head]
  if Q.head == Q.size
    Q.head = 1
  else Q.head = Q.head + 1
  return x

TAIL-ENQUEUE(Q, x)
  if QUEUE-FULL(Q)
    error "overflow"
  Q[Q.tail] = x
  if Q.tail == Q.size
    Q.tail = 1
  else Q.tail = Q.tail + 1

TAIL-DEQUEUE(Q)
  if QUEUE-EMPTY(Q)
    error "underflow"
  if Q.tail == 1
    Q.tail = Q.size
  else Q.tail = Q.tail - 1
  return Q[Q.tail]

10.1-7

假设有两个栈S1, S2，那么支持队列的两个操作如下进行：

  • ENQUEUE 直接将元素推入栈S2中。此操作时间复杂度为\(\Theta(1)\)。
  • DEQUEUE 将S1栈顶的元素弹出并返回即可。如果S1为空，那么弹出S2中的所有元素，一边弹出，一边将元素推入到S1中，再将元素弹出并返回。这种操作绝大多数时间下都是\(O(1)\)，如果栈S2过于庞大，那么时间开销就是S2的长度。
1
2
3
4
5
6
7
8
9
10
11
// Q.S1和Q.S2表示队列Q内部的两个栈。
ENQUEUE(Q, x)
  PUSH(Q.S2, x)

DEQUEUE(Q)
  if STACK-EMPTY(Q.S1)
    while not STACK-EMPTY(Q.S2)
      x = POP(Q.S2)
      PUSH(Q.S1, x)
  x = POP(Q.S1)
  return x

10.1-8

假设有两个队列Q1, Q2，那么支持栈的两个操作如下进行（一开始令\(p=0\)）：

  • PUSH: 在队列Qp队尾推入元素。此操作时间复杂度为\(\Theta(1)\)。
  • POP:将队列Qp中的所有元素弹出，除了最后一个元素\(x\)，其它元素依次推入到队列Q(3-p)中，然后赋予p=3-p，并且将\(x\)返回。此操作时间复杂度为队列Sp的长度，即\(\Theta(n)\)。