一、选择题

（共15题，每题2分，共计30 分；未特殊说明，每题有且仅有一个正确选项）

【第 1 题】

下面关于线性表的叙述错误的是（ ）。 {{ select(1) }}

• 线性表采用顺序存储必须占用一片连续的存储空间
• 线性表采用链式存储不必占用一片连续的存储空间
• 线性表采用链式存储便于插入和删除操作的实现
• 线性表采用顺序存储便于插入和删除操作的实现

【第 2 题】

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。 {{ select(2) }}

• 2m-1
• 2m
• 2m+1
• 4m

【第 3 题】

设顺序循环队列 Q[0：M-1] 的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元素的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。

{{ select(3) }}

• R-F
• F-R
• (R-F+M)％M
• (F-R+M)％M

【第 4 题】

在以下各项中，（ ）不是 CPU 的组成部分。 {{ select(4) }}

• 控制器
• 运算器
• 寄存器
• 主板

【第 5 题】

ASCII 码的含义是（ ）。 {{ select(5) }}

• 二—十进制转换码
• 美国信息交换标准代码
• 数字的二进制编码
• 计算机可处理字符的唯一编码

【第 6 题】

C++ 语言中，表达式 23|2^5 的值是（ ）。 {{ select(6) }}

• 23
• 1
• 18
• 32

【第 7 题】

在 C++ 语言中，判断 a 等于 0 或 b 等于 0 或 c 等于 0 的正确的条件表达式是（ ）。 {{ select(7) }}

• !((a!=0) || (b!=0) || (c!=0))
• !((a!=0) && (b!=0) && (c!=0))
• !(a==0 && b==0) || (c!=0)
• (a=0) && (b=0) && (c=0)

【第 8 题】

地面上有标号为 A,B,C 的 3 根细柱，在 A 柱上放有 10 个直径相同中间有孔的圆盘，从上到下依次编号为 1,2,3,…，将 A 柱上的部分盘子经过 B 柱移入 C 柱，也可以在 B 柱上暂存。如果 B 柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在 C 柱上，从下 到上的盘子的编号为（ ）。 {{ select(8) }}

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

【第 9 题】

与十进制数 17.5625 对应的 8 进制数是（ ）。 {{ select(9) }}

• 21.5625
• 21.44
• 21.73
• 21.731

【第 10 题】

欧拉图 G 是指可以构成一个闭回路的图，且图 G 的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中，不一定是欧拉图的是（ ）。 {{ select(10) }}

• 图 G 中没有度为奇数的顶点
• 包含欧拉环的图（欧拉环是指通过图中每边恰好一次的闭路径）
• 包含欧拉闭迹的图（欧拉迹是指通过图中每边恰好一次的路径）
• 存在一条回路，通过每个顶点恰好一次

【第 11 题】

设 A=B=true，C=D=false，以下逻辑运算表达式值为假的有（ ）。 {{ select(11) }}

• (¬ A∧B)∨(C∧D∨A)
• ¬ (((A∧B)∨C)∧D)
• A∧(B∨C∨D)∨D
• (A∧(D∨C)) ∧B

【第 12 题】

一个无法靠自身的控制终止的循环称为“死循环”，例如，在 C++ 语言程序中，语句 while(1) printf("*"); 就是一个死循环，运行时它将无休止地打印 * 号。下面关于死循环的说法中，只有（ ）是正确的。

{{ select(12) }}

• 不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而， 任何编译系统都不做死循环检验
• 有些编译系统可以检测出死循环
• 死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环
• 死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也是可以检测的

【第 13 题】

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

• 24.125
• 24.250
• 26.125
• 26.250

【第 14 题】【多选】

已知 7 个结点的二叉树的先序遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），后根遍历是 4 6 5 2 7 3 1，则该二叉树的可能的中序遍历是（ ）。 {{ multiselect(14) }}

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

【第 15 题】【多选】

关于操作系统下面说法哪些是正确的（ ）。 {{ multiselect(15) }}

• 多任务操作系统专用于多核心或多个 CPU 架构的计算机系统的管理。
• 在操作系统的管理下，一个完整的程序在运行过程中可以被部分存放在内存中。
• 分时系统让多个用户可以共享一台主机的运算能力，为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。
• 为了方便上层应用程序的开发，操作系统都是免费开源的。

二、阅读程序

（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

阅读程序（一）

1. #include <bits/stdc++.h>
2. using namespace std;
3. 
4. const int N = 1e5 + 10;
5.
6. int n;
7. int s[N] = {-1}, tt = 0;
8.
9. int main() {
10.
11.    cin >> n;
12.    
13.    for(int i = 1;i <= n; i++){
14.        int x;
15.        cin >> x;
16.        while(tt && s[tt] >= x) tt--;
17.        if(tt) cout << s[tt] << " ";
18.        else cout << -1 << " ";
19.        s[++tt] = x;
20.    }
21.
22.	return 0;
23. }

输入 n 不超过 $10^5$ 的正整数，x 绝对值不超过 $10^9$。

判断题

16. 程序输出的第一个数一定是 -1。 {{ select(16) }}

• 正确
• 错误

17. 该程序是求每个数右边第一个比其小的数。 {{ select(17) }}

• 正确
• 错误

18. 数组 s 中的数值从左到右是严格单调递增的。 {{ select(18) }}

• 正确
• 错误

19. 如果输入的 n 个数值都相同，则输出都是 -1。 {{ select(19) }}

• 正确
• 错误

单选题

20. 该程序的时间复杂度为（ ）。 {{ select(20) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• $O(n^\frac{3}{2})$

21. 当输入的 n 为 5，a 数组为 3 4 2 7 5 时，输出为（ ）。

{{ select(21) }}

• 1 3 -1 2 2
• -1 3 -1 2 3
• -1 3 -1 2 2
• -1 4 -1 2 2

阅读程序（二）

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 1e6 + 5;
4. int n, a[N], rt[N], lf[N], nx[N];
5. vector<int> stk[N];
6. int main() {
7.    cin >> n;
8.    for (int i = 1; i <= n; i++) cin >> a[i];
9.    long long ans = 0;
10.     for (int i = 0; i <= n + 1; i++) {
11.         lf[i] = i - 1;
12.         rt[i] = i + 1;
13.     }
14.     for (int i = n; i; i--) {
15.         if (!stk[a[i] + 1].empty()) {
16.             nx[i] = stk[a[i] + 1][stk[a[i] + 1].size() - 1];
17.             stk[a[i] + 1].pop_back();
18.         }
19.         stk[a[i]].push_back(i);
20.     }
21.     for (int i = n; i; i--) {
22.         if (a[i] == 1) {
23.             int pos = i;
24.             while (nx[pos]) {
25.                 pos = nx[pos];
26.                 rt[lf[pos]] = rt[pos];
27.                 lf[rt[pos]] = lf[pos];
28.             }
29.             ans += rt[i] - i;
30.             rt[lf[i]] = rt[i];
31.             lf[rt[i]] = lf[i];
32.         }
33.     }
34.     cout << ans << endl;
35.     return 0;
36. }

判断题

22. 若 nx[i]=stk[a[i]+1][stk[a[i]+1].size()-1] 改为 nx[i]=stk[a[i]+1].back()，程序行为不变。

    {{ select(22) }}

• 正确
• 错误

23. 若将 stk[a[i]].push_back(i) 改为 stk[a[i]].emplace_back(i)，程序行为不变。 {{ select(23) }}

• 正确
• 错误

24. 若输入的 n 为 4，a 数组为 1 1 2 3 时，输出为 6。 {{ select(24) }}

• 正确
• 错误

单选题

25. 程序的时间复杂度为（ ）。 {{ select(25) }}

• $O(n^2)$
• $O(nlogn)$
• $O(n)$
• $O(nlog^2n)$

26. 当输入的 n 为 6，a 数组为 1 1 2 2 3 3 时，输出为（ ）。（4 分） {{ select(26) }}

• 6
• 7
• 8
• 9

27. 当输入的 n 为 6，a 数组为 1 2 1 2 1 3 时，输出为（ ）。 {{ select(27) }}

• 10
• 11
• 12
• 13

阅读程序（三）

1. #include <iostream>
2. #include <cstdio>
3. #include <cstring>
4. using namespace std;
5.
6. typedef unsigned long long ULL;
7.
8. const int N = 1e6 + 10, P = 131;
9.
10. ULL hsub[N], hs[N], p[N] = {1};
11.
12. ULL calc(int L, int R, ULL h[]){
13.    return h[R] - h[L - 1] * p[R - L + 1];
14. }
15.
16. int main() {
17.
18.    int T;
19.    scanf("%d", &T);
20.
21.    while(T--){
22.        char sub[N], s[N];
23.
24.        scanf("%s%s", sub + 1, s + 1);
25.
26.        int sublen = strlen(sub +  1), slen = strlen(s + 1);
27.        int len = max(slen, sublen);
28.
29.        for(int i = 1; i <= len; i++){
30.            p[i] = p[i - 1] * P;
31.            hs[i] = hs[i - 1] * P + s[i];
32.            hsub[i] = hsub[i - 1] * P + sub[i];
33.        }
34.
35.        int ans = 0;
36.
37.        ULL x = hsub[sublen];
38.        for(int L = 1; L <= slen - sublen + 1; L++){
39.            int R = L + sublen - 1;
40.            if(x == calc(L, R, hs)) ans++;
41.        }
42.
43.        printf("%d\n", ans);
44.    }
45.    
46.    return 0;
47. }

输入的字符串只有小写字母并且长度不超过 $10^6$，T 不超过 10。

判断题

28. 输入的第一个字符串长度大于第二个字符串长度，程序会报错。 {{ select(28) }}

• 正确
• 错误

29. 将第 6 行的 unsigned 去掉，程序没有影响。 {{ select(29) }}

• 正确
• 错误

30. 若将常量 P 改为其他质数，程序将会出错。 {{ select(30) }}

• 正确
• 错误

31. 程序的结果不会超过第二个字符串长度。 {{ select(31) }}

• 正确
• 错误

选择题

32. 当输入为 1 a aaaaaaaaaa 时，答案为（ ）。 {{ select(32) }}

• 0
• 1
• 2
• 10

33. 输入为 1 abc abcabcd 时，答案为（ ）。 {{ select(33) }}

• 0
• 1
• 2
• 3

34. 输入为 1 aba abababababa 时，答案为（ ）。 {{ select(34) }}

• 3
• 4
• 5
• 6

三、完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序（一）

给出一个长度为 n(n≤100) 的序列，再给出一个序列中的元素 x。求 x 是序列中第几小的数（从 1 开始）不使用排序算法，使用二分算法。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10086;
int A[MAXN], B[MAXN];

int Find_Kth(int L, int R, int k) {
    int key = A[L];
    int low = L, high = R;
    while ( ① ) {
        while ( ② ) high--;
        if (low < high)
            A[low] = A[high];
        while (low < high && A[low] <= key) low++;
        if (low < high)
            A[high] = A[low];
    }
    A[low] = key;
    if (low == k)
        return key;
    if (low < k)
        return ③ ;
    return Find_Kth(L, low - 1, k);
}

int main() {
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> B[i];
    int L = 0, R = n;
    while (R - L > 1) {
        int mid = (L + R) / 2;
        memcpy(A, B, sizeof(B));
        if ( ④ )
            L = mid;
        else
            ⑤;
    }
    cout << R << endl;
}

35. ① 处应填（ ）。

{{ select(35) }}

• low<=high
• low<high
• a[low]<=key
• a[high]>key

36. ② 处应填（ ）。

{{ select(36) }}

• low<=high&&A[high]>=key
• low<=high&&A[low]<key
• low < high&&A[high] >= key
• low<high&&A[low]<key

37. ③ 处应填（ ）。

{{ select(37) }}

• A[low]
• Find_Kth(low + 1, R, k)
• key
• Find_Kth(low R, k)

38. ④ 处应填（ ）。

{{ select(38) }}

• Find_Kth(1, n, mid) < x
• Find_Kth(1, mid, n) < x
• Find_Kth(1, n, mid) <= x
• Find_Kth(1, mid, n) <= x

39. ⑤ 处应填（ ）。

{{ select(39) }}

• R=mid-1
• R=L+1
• R=mid+1
• R=mid

完善程序（二）

双向链表操作：

输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。这一行整数是用来初始化链表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。

第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。如果是“get”或者“delete”，则其后跟着一个整数a，代表获得或者删除第a个元素；如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e；“show”之后没有整数。

数据范围：(1≤n,m≤${10}^5$)

如果获取成功，则输出该元素；如果删除成功则输出“delete OK”；如果获取失败或者删除失败，则输出“get fail”以及“delete fail”。如果插入成功则输出“insert OK”，否则输出“insert fail”。如果是“show”则输出列表中的所有元素，如果列表是空的，则输出“Link list is empty”。

#include <bits/stdc++.h>
using namespace std;

typedef struct ListNode {
	int data;
	ListNode* next;
	ListNode* prior;
}Node, *PNode;


class MyList {
private:
	PNode head, tail;
	int cnt;

public:

	MyList();

	int size();
	void push_back(int x);
	void push_front(int x);
	void insert(int k, int x);

	PNode exist(int k);
	int get(int k);
	void del(int k);

	void traverse();
};

int main() {

	MyList lst;

	int n, m;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
        【 ① 】
	}
	cin >> m;

	while (m--) {
		string op;
		cin >> op;
		int k, x;
		if (op == "show") {
			if (lst.size() > 0) lst.traverse();
			else puts("Link list is empty");
		}
		else if (op == "insert") {

			cin >> k >> x;
			if (k <= lst.size() || (lst.size() == 0 && k == 1)) {
				lst.insert(k, x);
				puts("insert OK");
			}
			else puts("insert fail");
		}
		else if (op == "get") {
			cin >> k;
			if (k <= lst.size()) cout << lst.get(k) << endl;
			else puts("get fail");
		}
		else if (op == "delete") {
			cin >> k;
			if (【 ② 】) {
				lst.del(k);
				puts("delete OK");
			}
			else puts("delete fail");
		}
	}

	
	return 0;
}


MyList::MyList() {
	head = new Node;
	tail = new Node;
	head->next = tail;
	tail->prior = head;

	【 ③ 】
}

int MyList::size() {
	return cnt;
}

PNode MyList::exist(int k) {
	if (k > size() || k <= 0) return NULL;

	PNode p;
	p = head->next;

	while (k > 1) {
		p = p->next;
		k--;
	}

	return p;
}

void MyList::insert(int k, int x) {

	cnt++;

	PNode s = new Node;
	s->data = x;

	PNode p = exist(k);
	PNode q = p->prior;

	s->next = p;
	s->prior = q;

	q->next = s;
	p->prior = s;
}

int MyList::get(int k) {
	return exist(k)->data;
}

void  MyList::del(int k) {

	PNode s = exist(k);
	PNode q, p;
	
	q = s->prior;
	p = s->next;

	p->prior = q;
	q->next = p;

	delete s;
	cnt--;
}

void MyList::push_back(int x) {

	cnt++;

	PNode s = new Node;
	PNode q = new Node;

	s->data = x;
	q = tail->prior;

	s->next = tail;
	q->next = s;
	tail->prior = s;
	s->prior = q;
}

void MyList::push_front(int x) {

	cnt++;

	PNode s = new Node;
	PNode p = new Node;

	s->data = x;
	p = head->next;

	s->next = p;
    【 ④ 】

	p->prior = s;
	s->prior = head;
}

void MyList::traverse() {
	PNode p = new Node;
    【 ⑤ 】
	while (p != tail) {
		cout << p->data << " ";
		p = p->next;
	}
	puts("");
}

40. ① 处应填（ ）。

{{ select(40) }}

• lst.push_front(x);
• lst.push_back(x);
• lst[i]=x
• lst.push(x);

41. ② 处应填（ ）。

{{ select(41) }}

• k = lst.size()
• k < lst.size()
• k <= lst.size()
• k > lst.size()

42. ③ 处应填（ ）。

{{ select(42) }}

• int cnt=1;
• cnt=0;
• cnt=-1;
• int cnt=0;

43. ④ 处应填（ ）。

{{ select(43) }}

• s->next=p;
• s->prior = head;
• head->next->prior = s;
• head->next = s;

44. ⑤ 处应填（ ）。

{{ select(44) }}

• p = head->next;
• p = nullptr;
• p = head;
• p = head->prior;