单项选择

8.$\color{green}{D. 4GB}$

有 $n$ 位就是 $2 ^ {n}B$ 最终换算即可

不定项选择

1. $\color{green}{A.2 ^ {n + 1}}$

质数级别相同的时间复杂度需要保证底数相同

但由于 $D 的 2 ^ {2n}$可以化简为 $4 ^ n$ 性质就与 B 相同了

6. $\color{green}{C.d(v_1, v_2) = d(v_2, v_1)\ D. d(v_1, v_3) <= d(v_1, v_2) + d(v_2, v_3)}$

认真看 $A$ 选项，题目说的是 $dist[a][b]$ 的最短路径，而不是之间

9. $\color{green}{C.POP3\ D.SMTP}$

$\color{red}{SMTP管“发”，POP3/IMAP管“收”}$

SMTP = small mail transfer Protocol
POP3 = Post Office Protocol
IMAP = Post Office Protocol

10. $\color{green}{BD}$

A．如果一个问题不存在多项式时间的算法，那它一定是$NP$类问题
B．如果一个问题不存在多项式时间的算法，那它一定不是$P$类问题
C．如果一个问题不存在多项式空间的算法，那它一定是$NP$类问题
D．如果一个问题不存在多项式空间的算法，那它一定不是$P$类问题

NP问题: 是指还未被证明是否存在多项式算法能够解决的问题，而其中NP完全问题又是最有可能不是P问题的问题类型。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题
P问题: P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出

三、问题求解

1. $\color{green}{256}$

$p, q, r$ 分别有$true 和 false$两种情况，要找出两两不等价的表达式最多有多少种（注意，不是两两不等价的表达式对数），也就是要找出这8个结果(0/1)组成的集合最多可能有多少种不同的。（也可以叫做集合{000, 001, 010, 011, 100, 101, 110, 111}到集合{0, 1}的映射个数）答案：$2 ^ 8 = 256$

也可以这么想，$p, q, r$ 分别有$true 和 false$ 有 $2 ^ 3$种情况，~的出现也会有$2 ^ 3$ 中情况，两个符号 ^ v有$2 ^ 2$, 总和则为$2 ^ 8 == 256$

2. $\color{green}{5536}$

五、完善程序

新壳栈

#include < iostream > 
using namespace std; 
const int
NSIZE = 100000, 
CSIZE = 1000; 
int n, c, r, tail, head, s[NSIZE], q[CSIZE]; 
//数组 s 模拟一个栈，n 为栈的元素个数
//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标 
bool direction, empty; 
int previous(int k) {
    if (direction)
        return ((k + c - 2) % c) + 1; 
    else
        return (k % c) + 1; 
}
int next(int k) {
    if (direction)
        ①; 
    else
        return ((k + c - 2) % c) + 1; 
}
void push() {
    int element; 
    cin >> element; 
    if (next(head) == tail) {
        n++; 
        ②; 
        tail = next(tail); 
    }
    if (empty)
        empty = false; 
    else
        head = next(head); 
    ③ = element; 
}
void pop() {
    if (empty) {
        cout << "Error: the stack is empty!" << endl; return; 
    }
    cout <<     ④ << endl; 
    if (tail == head)
        empty = true; 
    else {
        head = previous(head); 
    if (n > 0) {
        tail = previous(tail); 
        ⑤ = s[n]; 
        n--; 
    }
}
}
void reverse() {
    int temp; 
    if (    ⑥ == tail) {
        direction =  ! direction; 
        temp = head; 
        head = tail; 
        tail = temp; 
    }
    else
        cout << "Error: less than " << c << " elements in the stack!" << endl; 
}
int main() {
    cin >> c; 
    n = 0; 
    tail = 1; 
    head = 1; 
    empty = true; 
    direction = true; 
    do {
        cin >> r; 
        switch (r) {
            case 1:push(); break; 
            case 2:pop(); break; 
            case 3:reverse(); break; 
        }
    }while (r != 0); 
    return 0; 
}

首先分析一下每个变量的作用：
数组 s 模拟一个栈，n 为栈的元素个数, 并且这个栈不会存储 q 的内容
数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标，c 为队列的长度上限
direction 代表当前循环队列的方向, empty 代表循环队列是否为空

函数 $previous(int k)$ 作用是寻找循环队列中第 $k$ 个元素的前一个元素，但是这个前有讲究，当正方向时，前就是前，当反方向时，前就是后

函数 $next(int k)$ 作用是寻找循环队列中第 $k$ 个元素的后一个元素，但是这个后有讲究，当正方向时，后就是后，当反方向时，后就是前

1. $\color{red}{所以第一空照葫芦画瓢虽然我没错}$

• $我$现在才知道$head$和$tail$的位置如下

  $e _ 1\ e _ 2\ e _ 3\ e _ 4\ …\ e _ n$
  tail指向$e _ 1$, head指向$e _ n$

  当然还是$queue$的模拟不熟，$queue$就是个先进先出的数据结构，$head$指向新节点，$tail$指向尾节点
  所以next(head) = tail

  1. 如果循环队列不为空且不满 c 个元素时，head 后移，再将元素进入循环队列 head 指向的位置；
  2. 如果循环队列不为空且满 c 个元素时，队尾元素出队并进入栈中，再将tail 后移，然后head 后移，再将元素进入循环队列的 head 指向的位置。
  3. 如果循环队列为空，元素进入循环队列 head 指向的位置

• $\color{red}{由第 2 条可知，第二个空就是队尾元素放在栈顶}$

• $\color{red}{由第 1 条可知，第三个空就是队头插入元素}$

函数 pop() 作用是弹出“新壳栈”栈顶元素，元素弹出“新壳栈”时：

• 如果循环队列为空，报错 Error；
• 如果循环队列不为空，输出队头元素，即 head 指向的元素；
• 如果 head 和 tail 指向同一个位置，那么循环队列为空，否则 head 前移一位，当 head 前移一位后，判断栈内元素个数，如果栈内存在元素则将该栈顶元素入队尾，并将元素个数-1。

1. $\color{red}{由第 2 条可知，第四个空就是输出队头元素}$

2. $\color{red}{由第 3 条可知，第五个空就是栈顶元素入队尾}$

1. $\color{red}{第五题由上文可知}$