答案和问题私信发我即可，万分感谢

---

一、单项选择（共 $5$ 题，每题 $2$ 分，共 $10$ 分）

1. 在 Windows 命令提示符 cmd 中，以下哪一个操作和目录有关？（$\qquad$）

• A. RENAME

• B. FC

• C. MD

• D. LS

2. 下面哪一个数最大？（$\qquad$）

• A. $114_{\,(16)}$

• B. $514_{\,(8)}$

• C. $314_{\,(10)}$

• D. $2311_{\,(5)}$

3. 若有 $n$ 个节点要构建 Huffman 树，用一般的贪心算法的平均时间复杂度是（$\qquad$）。

• A. $O(\log n)$

• B. $O(n)$

• C. $O(n\log n)$

• D. $O(n^2)$

4. 在双向链表中,若要删除p所在的结点，以下正确的做法是（$\qquad$）。

• A. p->next->prev=p->prev; p->prev->next=p->next;

• B. p->next=p->next->next; p->next->prev=p;

• C. p->next=p->next->next; p->next->next->prev=p;

• D. p->prev->next=p->next; p->next=p->prev->next;

5. 商家规定：$3$ 个喝完的汽水瓶可以换一瓶新的汽水，并且新汽水喝完后可继续兑换。现在 ltl0825 买了 $114$ 瓶汽水，由于个人 RP 问题， 没人会借给他空瓶子。请求出他最多可以喝多少瓶汽水。（$\qquad$）

• A. $152$

• B. $164$

• C. $169$

• D. $170$

---

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

（多重背包）ltl0825 有一个容量为 $W$（$0\le W\leq 4\times 10^4$）的背包，现在总共有 $n$ （$1\leq n\le 100$）种物品，每种物品的价值为 $v_i$ ，重量为 $w_i$ ，每种物品有 $m_i$ 件。且（$n\leq \sum m_i \leq 10^5$） ltl0825 希望选择一些物品装进背包，使得它们的价值和最大。

试补全程序。

1	#include <bits/stdc++.h>
2	using namespace std;
3	int ans;
4	int cnt = 1;
5	int vi, wi, mi;
6	int n, m;
7	int f[1000100];
8	int w[1000100], v[1000100];
9	int main() {
10		cin >> n >> m;
11		for (int i = 1; i <= n; ++i) {
12			cin >> vi >> wi >> mi;
13			for (int j = 1; j <= mi; j <<= 1) {
14				v[++cnt] = j*vi;
15				w[cnt] = j*wi;
16				___①___
17			}
18			if (mi) v[___②___] = vi * mi, w[cnt] = wi * mi;
19		}
20		for (int i = 1; i <= ___③___; ++i)
21			for (int j = m; j >= ___④___; --j)
22				f[j] = max(f[j], ___⑤___);
23		cout<<f[m]<<endl;
24		return 0;
25	}

6. ①处应填（$\qquad$）。

• A. mi -= j;

• B. wi -= j;

• C. mi /= 2;

• D. wi /= 2;

7. ②处应填（$\qquad$）。

• A. cnt

• B. cnt+1

• C. cnt++

• D. ++cnt

8. ③处应填（$\qquad$）。

• A. n

• B. cnt

• C. n-1

• D. cnt-1

9. ④处应填（$\qquad$）。

• A. 0

• B. 1

• C. m[i]

• D. w[i]

10. ⑤处应填（$\qquad$）。

• A. f[i - w[j]] + v[i]

• B. f[i - w[j]] + v[j]

• C. f[j - w[i]] + v[i]

• D. f[j - w[i]] + v[j]