历年南京大学计算机考研复试机试真题
本文整理南京大学计算机考研机试真题，并提供详细解析与代码实现，帮助同学们了解保研机试的难度与题型分布
字符串区间翻转
题目描述
小诺有一个由 0 和 1 组成的字符串。现在小诺有一次机会，可以选择一个任意的区间 [L,R]，将该区间内的所有字符串进行翻转（即 0→1，1→0）。
请问小诺经过一次翻转之后字符串中最多会有多少个 1？
输入格式
第一行输入一个正整数 ${n}$，表示字符串长度，${n \leq 10^7}$。接下来一行输入一个 01 字符串。可能有多组测试数据输入。
输出格式
输出题目要求的答案。
输入样例
4
1001
输出样例
4
完全背包问题
题目描述
有 ${n}$ 种（每一种有无数个）重量和价值分别为 ${W_i}$, ${V_i}$ 的物品，现从这些物品中挑选出总量不超过 ${W}$ 的物品，求所有方案中价值总和的最大值。
输入格式
输入包含多组测试用例，每一例的开头为两位整数 ${n}$、${W}$（${1 \leq n \leq 10000}$, ${1 \leq W \leq 1000}$），接下来有 ${n}$ 行，每一行有两位整数 ${W_i}$、${V_i}$（${1 \leq W_i \leq 10000}$, ${1 \leq V_i \leq 100}$）。
输出格式
输出为一行，即所有方案中价值总和的最大值。
输入样例
3 4
1 2
2 5
3 7
3 5
2 3
3 4
4 5
输出样例
10
7
最长连续公共子序列
题目描述
输入两个字符串 ${s1}$, ${s2}$。输出最长连续公共子串长度和最长连续公共子串。
输入格式
多组数据输入。输入两个字符串 ${s1}$, ${s2}$，长度不大于 100，以空格隔开。
输出格式
输出最长连续公共子串长度和最长连续公共子串。
输入样例
abcdefg qwercdefiok
输出样例
4
cdef
子序列
题目描述
一个串的“子序列”是将这个串中的一些字符提取出来得到一个新串，并且不改变它们的相对位置关系。
我们说串 ${t}$ 是串 ${s1}$ 和 ${s2}$ 的公共子序列，当且仅当 ${t}$ 是 ${s1}$ 的子序列且 ${t}$ 是 ${s2}$ 的子序列。定义串 ${s1}$ 和 ${s2}$ 的相似度为它们最长公共子序列的长度。
现在给定一个文本串 ${S}$ 和一组模式串 ${T[1], T[2], \dots, T[n]}$。求 ${T[i]}$ 中和 ${S}$ 具有最高相似度的那个，然后输出最高的相似度。
${S}$ 和所有的 ${T[i]}$ 都只含有小写字母。
输入规则：
先是一行字符串 ${S}$。
第二行是 ${n}$（${1 \leq n \leq 100}$）。
第三行以降的 ${n}$ 行是 ${n}$ 个模式串 ${T[1] \dots T[n]}$。
${S}$ 和所有的 ${T[i]}$ 的长度都不超过 2000。
输入格式
如题
输出格式
如题
输入样例
abcdef
4
acfaff
appont
emmm
bdxeuf
输出样例
bdxeuf
4
二叉树遍历
题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：ABC##DE#G##F###，其中 # 表示的是空格，空格字符代表空树。
建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入格式
输入包括 1 行字符串，长度不超过 100。
输出格式
可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。
输入样例
abc##de#g##f###
输出样例
c b e g d f a