noip2014普及组复赛试题_大一高数期末考试试题
noip2014普及组复赛试题_大一高数期末考试试题
大家好，又见面了，我是你们的朋友全栈
T1
考察计算机基础知识，所谓集成电路是将大量的晶体管和电子线路组合在一块硅片上，故又称为芯片。故选 A A A。
T2
H T M L HTML HTML超文本标记语言阅读方式是浏览器，浏览器主要用于显示网页服务器。
T3
英特尔公司是全球最大的个人计算机零件和CPU制造商。
T4
TCP/IP模型
A A A项最符合该图形式。
T5
快速排序的期望复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)的，最坏情况（已经排好序的序列）是 O ( n 2 ) O(n^2) O(n2)的。
T6
- 第一代：电子管计算机
- 第二代：晶体管计算机
- 第三代：中小规模集成电路计算机
- 第四代：大规模和超大规模集成电路计算机
E N I A C ENIAC ENIAC则属于第一代。
T7
递归过程就是函数不断压栈的过程，所以可能引起的是栈空间溢出。
T8
2 32 2^{32} 232 = = = 2 30 2^{30} 230 ∗ * ∗ 2 2 2^2 22= 1 G B 1GB 1GB ∗ * ∗ 4 4 4 = = = 4 G B 4GB 4GB
T9
3 G 3G 3G系统的三大主流标准分别是 W C D M A WCDMA WCDMA （宽带 C D M A CDMA CDMA）和 C D M A 2000 CDMA2000 CDMA2000 和 T D − S C D M A TD-SCDMA TD−SCDMA（时分双工同步）。
T10
蜘蛛网与因特网除了模型相似，其他没有任何必然联系。
T11
在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。在考虑时间复杂度时，忽略这个函数的低阶项和首项系数，主要看最高阶项。 2 n + 1 2^{n+1} 2n+1 = = = 2 2 2 ∗ * ∗ 2 n 2^n 2n，故选 A A A。
T12
广搜相对于树上的层次遍历，要按照队列的进队出队完成操作
B B B项中 A 2 A_2 A2 节点因为回溯，所以不能在第三位被访问到。 C C C项中 A 3 A_3 A3 节点一定是最后被访问到的，故不对。
T13
这道题考验了栈的性质，栈里面的三个元素的相对入栈顺序应是 a , b , c a,b,c a,b,c ，结合选项， A A A项与 D D D项符合题意。
T14
三原色指红色，蓝色与绿色
三基色指红色，蓝色与黄色
故选 B B B 项与 D D D 项。
T15
一棵任意形态的 n n n个节点的数的二叉树的叶子数范围是 1 1 1 ∼ \sim ∼ ⌊ n + 1 2 ⌋ \left\lfloor\dfrac{n+1}{2}\right\rfloor ⌊2n+1⌋。 1 1 1指的是一条链的情况， ⌊ n + 1 2 ⌋ \left\lfloor\dfrac{n+1}{2}\right\rfloor ⌊2n+1⌋指的是二叉哈夫曼树的情况。
T16
因为边权均为正整数，所以如果两点之间的最短路径包含了一个环，那么这条最短路径就不是最短的，因为可以把这个环去掉，所以选项 A A A 不正确。因为是有向图，所以正向与反向的最短路径不一定相同，所以选项 B B B不正确。选项 C C C符合最短路径要求， 选项 D D D通过反证法即可证得正确。
T17
题目给的异或运算表：
代入计算发现选项 A A A和选项 B B B一定对；选项 C C C和选项 D D D在 a a a = = = T r u e True True， b b b = = = T r u e True True， c c c = = = F a l s e False False时不成立。 另外， 选项 C C C和选项 D D D中 ∧ \land ∧ 是逻辑与， ∨ \lor ∨是逻辑或。
T18
小数转化为二进制用乘法，先排除整数和有限小数，因为是十进制循环小数，每次乘 2 2 2取整后的数都一样，一直循环再下去就成了无限循环小数。故选 A A A。
T19
- H T T P HTTP HTTP：超文本传输协议
- F T P FTP FTP：文件传输协议
- P O P 3 POP3 POP3：邮局协议版本3
- S M T P SMTP SMTP：简单邮件传输协议
故选选项 C C C与选项 D D D。
T20
N P NP NP问题是指存在多项式算法能够验证的非决定性问题，而其中NP完全问题又是最有可能不是P问题的问题类型。所有的 N P NP NP问题都可以用多项式时间归约到他们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的 N P − 完 全 问 题 NP-完全问题 NP−完全问题 也可以在多项式时间内求解。
P P P问题是具有多项式算法的判定问题。这里的 P P P代表 P o l y n o m i a l Polynomial Polynomial。 P P P问题就是可以有一个确定型图灵机在多项式时间内解决的问题。即那些存在 O ( n ) O(n) O(n)， O ( n k ) O(nk) O(nk)， O ( n l o g n ) O(nlogn) O(nlogn)等多项式时间复杂度解法的问题。比如排序问题、最小生成树、单源最短路径。直观的讲，我们将 P P P问题视为可以较快解决的问题。
所以选项 B B B和选项 D D D正确，选项 A A A和选项 C C C错误。
T21
对于 p , q , r p,q,r p,q,r三个变量，每个变量可取 0 0 0和 1 1 1两种值，可以得到有 8 8 8种组合。对于每种组合，带入表达式只有 0 0 0和 1 1 1 两种答案。因此两两不等价的表达式只有 2 8 = 256 2^8=256 28=256种。
T22
这道题考察 D P DP DP，可以发现题目给出的是一棵二叉树，那么可以做一遍树形 D P DP DP： 设 g [ i ] g[i] g[i]表示以 i i i为根的子树的独立集数； f [ i ] [ 0 ] f[i][0] f[i][0]表示不选 i i i号节点，以 i i i为根的子树的独立集数； f [ i ] [ 1 ] f[i][1] f[i][1]表示选 i i i号节点，以 i i i为根的子树的独立集数； 显然有 g [ i ] = f [ i ] [ 0 ] + f [ i ] [ 1 ] g[i]=f[i][0]+f[i][1] g[i]=f[i][0]+f[i][1]， l c lc lc为左儿子， r c rc rc为右儿子，那么有 f [ i ] [ 0 ] = g [ r c ] , f [ i ] [ 1 ] = f [ l c ] [ 0 ] ∗ f [ r c ] [ 0 ] f[i][0]=g[rc],f[i][1]=f[lc][0]*f[rc][0] f[i][0]=g[rc],f[i][1]=f[lc][0]∗f[rc][0]。 最后答案为 g [ r o o t ] g[root] g[root]。
T23
#include <iostream>
using namespace std;
int n, i, temp, sum, a[100];
int main() {
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n - 1; i++)
if (a[i] > a[i + 1]) {
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
for (i = n; i >= 2; i--)
if (a[i] < a[i - 1]) {
temp = a[i];
a[i] = a[i - 1];
a[i - 1] = temp;
}
sum = 0;
for (i = 2; i <= n - 1; i++)
sum + = a[i];
cout << sum / (n - 2) << endl;
return 0;
}去除一个最大值和最小值后的平均值，然后向下取整，程序中通过两次擂台比较值，将最大值和最小值放到了尾和首。故答案为 41 41 41。
T24
#include <iostream>
using namespace std;
int n, i, ans;
int gcd(int a, int b)
{
if (a % b == 0) return b;
else
return gcd(b, a%b);
}
int main()
{
cin>>n;
ans = 0;
for (i = 1; i <= n; i++)
if (gcd(n,i) == i)
ans++;
cout<<ans<<endl;
}显然是求 n n n 的约数个数， 120 = 2 3 ∗ 3 ∗ 5 120=2^3*3*5 120=23∗3∗5，所以约数个数为 4 ∗ 2 ∗ 2 = 16 4*2*2=16 4∗2∗2=16个。
T25
#include <iostream>
using namespace std;
const int SIZE = 20;
int data[SIZE];
int n, i, h, ans;
void merge() {
data[h - 1] = data[h - 1] + data[h];
h--;
ans++;
}
int main() {
cin >> n;
h = 1;
data[h] = 1;
ans = 0;
for (i = 2; i <= n; i++) {
h++;
data[h] = 1;
while (h > 1 && data[h] == data[h - 1])
merge();
}
cout << ans << endl;
}本题由代码可知是统计合并的次数，合并的过程执行一次便统计一次。合并的条件是 d a t a [ h ] = d a t a [ h − 1 ] data[h]=data[h-1] data[h]=data[h−1]，自己写几个数据后归纳出最后 d a t a [ ] data[] data[]数组中的数据为： 1024 , 512 , 256 , 128 , 64 , 16 , 8 , 4 1024,512,256,128,64,16,8,4 1024,512,256,128,64,16,8,4。即： 2012 = 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4 2012=1024+512+256+128+64+16+8+4 2012=1024+512+256+128+64+16+8+4，即最终的结果是将输入的一个数通过归并的方式拆分成若干个 2 2 2的整数次方的和，而 2 m 2^m 2m需要 2 m − 1 2^{m-1} 2m−1合并，所以最终结果为 1023 + 511 + 255 + 127 + 63 + 15 + 7 + 3 = 2004 1023+511+255+127+63+15+7+3=2004 1023+511+255+127+63+15+7+3=2004，故答案为 2004 2004 2004。另一个输入 8 8 8自然也就输出 7 7 7了。
T26
#include <iostream>
#include <string>
using namespace std;
int lefts[20], rights[20], father[20];
string s1, s2, s3;
int n, ans;
void calc(int x, int dep)
{
ans = ans + dep*(s1[x] - 'A' + 1);
if (lefts[x] >= 0) calc(lefts[x], dep+1);
if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x)
{
if (lefts[x] >= 0) check(lefts[x]);
s3 = s3 + s1[x];
if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th)
{
if (th == n)
{
s3 = "";
check(0);
if (s3 == s2)
{
ans = 0;
calc(0, 1);
cout<<ans<<endl;
}
return;
}
if (lefts[x] == -1 && rights[x] == -1)
{
lefts[x] = th;
father[th] = x;
dfs(th, th+1);
father[th] = -1;
lefts[x] = -1;
}
if (rights[x] == -1)
{
rights[x] = th;
father[th] = x;
dfs(th, th+1);
father[th] = -1;
rights[x] = -1;
}
if (father[x] >= 0)
dfs(father[x], th);
}
int main()
{
cin>>s1;
cin>>s2;
n = s1.size();
memset(lefts, -1, sizeof(lefts));
memset(rights, -1, sizeof(rights));
memset(father, -1, sizeof(father));
dfs(0, 1);
}由先序遍历，中序遍历的序列构造出二叉树，再求节点对应值的和—— A B C D E F ABCDEF ABCDEF基本值对应 123456 123456 123456，求出的是各个节点基本值乘以该节点深度的和。 这得注意的是，在构造二叉树的时候是严格按照先序遍历的方式进行 d f s dfs dfs， x x x相当于作为判断的节点， t h th th相当于要插入的节点，如果 x x x没有左右子树，就可以尝试往 x x x的两个子树分别添加 t h th th节点进行判断；如果 x x x有左子树，就只能往右子树插；如果 x x x有右子树，那么就插不进去了；如果在这个节点插入是不行的，那么就往根节点跳。 按照上述方法来做，即可得到答案为 55 55 55。
T27
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 25;
bool used[SIZE];
int data[SIZE];
int n, m, i, j, k;
bool flag;
int main() {
cin >> n >> m;
memset( used, false, sizeof(used) );
for ( i = 1; i <= m; i++ ) {
data[i] = i;
used[i] = true;
}
flag = true;
while ( flag ) {
for ( i = 1; i <= m - 1; i++ )
cout << data[i] << " ";
cout << data[m] << endl;
flag = ①;
for ( i = m; i >= 1; i-- ) {
②;
for ( j = data[i] + 1; j <= n; j++ )
if ( !used[j] ) {
used[j] = true;
data[i] = ③;
flag = true;
break;
}
if ( flag ) {
for ( k = i + 1; k <= m; k++ )
for ( j = 1; j <= ④; j++ )
if ( !used[j] ) {
data[k] = j;
used[j] = true;
break;
}
⑤;
}
}
}
}填程序题·。 u s e d [ i ] = = f a l s e used[i]==false used[i]==false表示数字 i i i还没有被使用过，每次倒着找到第一个能变大的数字，然后变大，接着把后面的数字直接从小到大排列，就生成了一个新的组合。 f l a g flag flag是标记能不能找到一个新的排列，第一层的循环意义是把排列中的第 i i i位清零，就是第二个空的作用，如果找到一个排列，就把后面的排列补全（在剩余的元素中找到最小的排列），然后跳出循环，就是第四个空和第五个空的意思。 所以：
- 第一空：
false - 第二空：
used[data[i]]=false - 第三空：
j - 第四空：
n - 第五空：
break
T28
也是道填程序题，题目中给出的：
#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;
}题目说的很清楚，思考一下，本题的思路是前 c c c个数用循环队列来维护，用 d i r e c t i o n direction direction来记录这个队列的方向，如果需要翻转，就在这个队列里翻转即可。 p u s h push push就是看队列里有没有满，满了就先让一个数到 s s s这个栈里，再加入队列，否则直接加入。而 p o p pop pop则只需要看队列里还有没有数，有就直接输出，否则 E R R O R ERROR ERROR。那弹出之后如果队列不满且 s s s中还有数，就可以将 s s s中的数弹出放入队列中。 所以：
- 第一空：
return (k%c)+1 - 第二空：
s[n]=q[tail] - 第三空：
q[head] - 第四空：
q[head] - 第五空：
q[tail] - 第六空：
next(head)
完结撒花~~
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/172069.html原文链接：https://javaforall.cn