一、单项选择题（共 15 题，每题 2 分，共计 30 分）

1. 以下哪种功能没有涉及 C++ 语言的面向对象特性支持：（） {{ select(1) }}

• C++ 中调用 printf 函数
• C++ 中调用用户定义的类成员函数
• C++ 中构造一个 class 或 struct
• C++ 中构造来源于同一基类的多个派生类

2. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的？（） {{ select(2) }}

• 5 4 3 6 1 2
• 4 5 3 1 2 6
• 3 4 6 5 2 1
• 2 3 4 1 5 6

3. 运行以下代码片段的行为是（）。

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

{{ select(3) }}

• 将 x 的值赋为 201
• 将 y 的值赋为 101
• 将 q 指向 x 的地址
• 将 p 指向 y 的地址

4. 链表和数组的区别包括（）。 {{ select(4) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可动态调整
• 以上均正确

5. 假设栈 S 和队列 Q 的初始状态为空。已知栈入栈顺序 e1~e6，出栈顺序为 e2、e4、e3、e6、e5、e1，则栈 S 的容量至少是（）个数据。 {{ select(5) }}

• 2
• 3
• 4
• 6

6. 表达式 a+(b-c)*d 的前缀表达式为（）。 {{ select(6) }}

• *+a-bcd
• +a*-bcd
• abc-d*+
• abc-+d

7. 字母频率 a:10%、b:15%、c:30%、d:16%、e:29%，哈夫曼编码中字母 d 的编码长度为（）位。 {{ select(7) }}

• 1
• 2
• 2 或 3
• 3

8. 完全二叉树数组存储，第 9 号结点的兄弟结点和右子结点位置分别是（）。 {{ select(8) }}

• 8、18
• 10、18
• 8、19
• 10、19

9. N 个顶点有向连通图的邻接矩阵中至少存在（）个非零元素。 {{ select(9) }}

• N-1
• N
• N+1
• N²

10. 以下对数据结构的表述不恰当的一项为（）。 {{ select(10) }}

• 图的深度优先遍历算法常使用的数据结构为栈
• 栈的访问原则为后进先出，队列的访问原则是先进先出
• 队列常常被用于广度优先搜索算法
• 栈与队列存在本质不同，无法用栈实现队列

11. 在双向循环链表结点 p 之后插入 s，正确的操作是（）。 {{ select(11) }}

• p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
• p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
• s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
• s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

12. 以下排序算法说法错误的是（）。 {{ select(12) }}

• 冒泡排序算法是稳定的
• 简单选择排序是稳定的
• 简单插入排序是稳定的
• 归并排序算法是稳定的

13. 八进制数 32.1 对应的十进制数是（）。 {{ select(13) }}

• 24.125
• 24.250
• 26.125
• 26.250

14. 字符串 abcab 有（）个互不相同的子串。 {{ select(14) }}

• 12
• 13
• 14
• 15

15. 以下对递归方法的描述中，正确的是（） {{ select(15) }}

• 递归是允许使用多组参数调用函数的编程技术
• 递归是通过调用自身来求解问题的编程技术
• 递归是面向对象和数据而不是功能和逻辑的编程语言模型
• 递归是将用某种高级语言转换为机器代码的编程技术

---

二、阅读程序（判断题 1.5 分，选择题 3 分，共计 40 分）

（1）位运算程序

#include <iostream>
using namespace std;
int main() {
    unsigned short x,y;
    cin >>x>>y;
    x=(x|x<<2) &0x33;
    x=(x|x<<1) & 0x55;
    y =(y|y << 2) & 0x33;
    y =(y|y <<1) & 0x55;
    unsigned short z= x|y <<1;
    cout <<z <<endl;
    return 0;
}

16. 删去第 7 行与第 13 行的 unsigned，程序行为不变。（） {{ select(16) }}

• 对
• 错

17. 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（） {{ select(17) }}

• 对
• 错

18. 程序总是输出一个整数 "0"。（） {{ select(18) }}

• 对
• 错

19. 当输入为 "22" 时，输出为 "10"。（） {{ select(19) }}

• 对
• 错

20. 当输入为 "22" 时，输出为 "59"。（） {{ select(20) }}

• 对
• 错

21. 当输入为 "13 8" 时，输出为（）。 {{ select(21) }}

• "0"
• "209"
• "197"
• "226"

---

（2）鸡蛋问题 DP

#include <algorithm>
#include <iostream>
#include <limits>
using namespace std;
const int MAXN=105;
const int MAXK = 105;
int h[MAXN][MAXK];
int f(int n, int m) {
    if (m == 1) return n;
    if(n==0) return 0;
    int ret = numeric_limits<int>::max();
    for (int i=1;i<= n; i++)
        ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);
    return ret;
}
int g(int n, int m) {
    for (int i=1;i<= n; i++) h[i][1]=i;
    for (int j=1;j<= m; j++) h[0][j]=0;
    for (int i=1;i<= n;i++) {
        for (int j=2; j<= m; j++) {
            h[i][j] = numeric_limits<int>::max();
            for (int k=1;k <=i; k++)
                h[i][j]=min(h[i][j],max(h[i - k][j], h[k - 1][j - 1]) + 1);
        }
    }
    return h[n][m];
}
int main() {
    int n,m; cin >>n>>m;
    cout << f(n,m) << endl << g(n,m) << endl;
    return 0;
}

22. 当输入为 "7 3" 时，第 19 行 min 执行了 449 次。（） {{ select(22) }}

• 对
• 错

23. 输出的两行整数总是相同的。（） {{ select(23) }}

• 对
• 错

24. 当 m 为 1 时，输出的第一行总为 n。（） {{ select(24) }}

• 对
• 错

25. 算法 g(n,m) 时间复杂度为（）。 {{ select(25) }}

• O(n^(3/2)m)
• O(nm)
• O(n²m)
• O(nm²)

26. 当输入为 "20 2" 时，输出第一行为（）。 {{ select(26) }}

• "4"
• "5"
• "6"
• "20"

27. 当输入为 "18 1" 时，输出第一行为（）。 {{ select(27) }}

• "6"
• "7"
• "18"
• "1"

---

（3）二分 + 牛顿迭代

#include <iostream>
using namespace std;
int n,k;
int solve1() {
    int l=1,r=n;
    while (l<= r){
        int mid=(l+r)/2;
        if (mid * mid <= n) l= mid +1;
        else r = mid -1;
    }
    return l -1;
}
double solve2(double x) {
    if(x==0) return x;
    for (int i=0;i<k;i++)
        x=(x+n/x)/2;
    return x;
}
int main() {
    cin >>n>>k;
    double ans = solve2(solve1());
    cout << ans << " " << (ans *ans == n)<< endl;
    return 0;
}

28. 时间复杂度为 O(logn + k)。（） {{ select(28) }}

• 对
• 错

29. 输入 "9801 1"，输出第一个数为 "99"。（） {{ select(29) }}

• 对
• 错

30. 输入 n 固定，k 增大，第二个数一定会变成 1。（） {{ select(30) }}

• 对
• 错

31. 程序有缺陷，mid*mid 可能溢出。（） {{ select(31) }}

• 对
• 错

32. 输入 "2 1"，输出第一个数最接近（）。 {{ select(32) }}

• 1
• 1.414
• 1.5
• 2

33. 输入 "3 10"，输出第一个数最接近（）。 {{ select(33) }}

• 1.7
• 1.732
• 1.75
• 2

34. 输入 "256 11"，输出第一个数（）。 {{ select(34) }}

• 等于 16
• 接近但小于 16
• 接近但大于 16
• 前三种都有可能

---

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）枚举因数

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> fac;
    fac.reserve((int)ceil(sqrt(n)));
    int i;
    for (i=1;i*i<n; ++i){
        if(①){
            fac.push_back(i);
        }
    }
    for (int k = 0; k < fac.size(); ++k) {
        cout <<②<<" ";
    }
    if(③){
        cout <<④<<" ";
    }
    for (int k = fac.size()-1; k >=0; --k) {
        cout <<⑤<<" ";
    }
}

35. ①处应填（） {{ select(35) }}

• n%i==0
• n%i!=0
• n%(i-1)==0
• n%(i-1)==1

36. ②处应填（） {{ select(36) }}

• n/fac[k]
• fac[k]
• fac[k]-1
• n/(fac[k]-1)

37. ③处应填（） {{ select(37) }}

• (i-1)*(i-1)==n
• (i-1)*i==n
• i*i==n
• i*(i-1)==n

38. ④处应填（） {{ select(38) }}

• n-i
• n-i+1
• i
• i-1

39. ⑤处应填（） {{ select(39) }}

• n/fac[k]
• fac[k]
• fac[k]-1
• n/(fac[k]-1)

---

（2）洪水填充

#include <bits/stdc++.h>
using namespace std;
const int ROWS = 8;
const int COLS = 8;
struct Point{
    int r,c;
    Point(int r, int c): r(r), c(c){}
};
bool is_valid(char image[ROWS][COLS], Point pt, int prev_color, int new_color) {
    int r = pt.r;
    int c=pt.c;
    return (0 <= r && r < ROWS && 0 <= c && c < COLS && ① && image[r][c]!= new_color);
}
void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;
    queue.push(cur);
    int prev_color = image[cur.r][cur.c];
    ②;
    while (!queue.empty()){
        Point pt = queue.front();
        queue.pop();
        Point points[4] = {③, Point(pt.r - 1, pt.c), Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
        for (auto p: points) {
            if (is_valid(image, p, prev_color, new_color)) {
                ④;
                ⑤;
            }
        }
    }
}

40. ①处应填（） {{ select(40) }}

• image[r][c] == prev_color
• image[r][c] != prev_color
• image[r][c] == new_color
• image[r][c] != new_color

41. ②处应填（） {{ select(41) }}

• image[cur.r+1][cur.c] = new_color
• image[cur.r][cur.c] = new_color
• image[cur.r][cur.c+1] = new_color
• image[cur.r][cur.c] = prev_color

42. ③处应填（） {{ select(42) }}

• Point(pt.r,pt.c)
• Point(pt.r, pt.c+1)
• Point(pt.r+1, pt.c)
• Point(pt.r+1, pt.c+1)

43. ④处应填（） {{ select(43) }}

• prev_color = image[p.r][p.c]
• new_color = image[p.r][p.c]
• image[p.r][p.c] = prev_color
• image[p.r][p.c] = new_color

44. ⑤处应填（） {{ select(44) }}

• queue.push(p)
• queue.push(pt)
• queue.push(cur)
• queue.push(Point(ROWS, COLS))