noip2014普及组复赛试题_大一高数期末考试试题

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

T1

考察计算机基础知识，所谓集成电路是将大量的晶体管和电子线路组合在一块硅片上，故又称为芯片。故选 $A$ 。

T2

$H T M L$ 超文本标记语言阅读方式是浏览器，浏览器主要用于显示网页服务器。

T3

英特尔公司是全球最大的个人计算机零件和CPU制造商。

T4

TCP/IP模型

在这里插入图片描述
$A$ 项最符合该图形式。

T5

快速排序的期望复杂度是 $O (n l o g n)$ 的，最坏情况（已经排好序的序列）是 $O(n^2)$ 的。

T6

第一代：电子管计算机
第二代：晶体管计算机
第三代：中小规模集成电路计算机
第四代：大规模和超大规模集成电路计算机

$E N I A C$ 则属于第一代。

T7

递归过程就是函数不断压栈的过程，所以可能引起的是栈空间溢出。

T8

$2^{32}$ $=$ $2^{30}$ $*$ $2^2$ = $1 G B$ $*$ $4$ $=$ $4 G B$

T9

$3 G$ 系统的三大主流标准分别是 $W C D M A$ （宽带 $C D M A$ ）和 $C D M A 2000$ 和 $T D - S C D M A$ （时分双工同步）。

T10

蜘蛛网与因特网除了模型相似，其他没有任何必然联系。

T11

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。在考虑时间复杂度时，忽略这个函数的低阶项和首项系数，主要看最高阶项。
$2^{n+1}$ $=$ $2$ $*$ $2^n$ ，故选 $A$ 。

T12

广搜相对于树上的层次遍历，要按照队列的进队出队完成操作

$B$ 项中 $A_2$ 节点因为回溯，所以不能在第三位被访问到。
$C$ 项中 $A_3$ 节点一定是最后被访问到的，故不对。

T13

这道题考验了栈的性质，栈里面的三个元素的相对入栈顺序应是 $a, b, c$ ，结合选项， $A$ 项与 $D$ 项符合题意。

T14

三原色指红色，蓝色与绿色

三基色指红色，蓝色与黄色

故选 $B$ 项与 $D$ 项。

T15

一棵任意形态的 $n$ 个节点的数的二叉树的叶子数范围是 $1$ $\sim$ $\left\lfloor\dfrac{n+1}{2}\right\rfloor$ 。 $1$ 指的是一条链的情况， $\left\lfloor\dfrac{n+1}{2}\right\rfloor$ 指的是二叉哈夫曼树的情况。

T16

因为边权均为正整数，所以如果两点之间的最短路径包含了一个环，那么这条最短路径就不是最短的，因为可以把这个环去掉，所以选项 $A$ 不正确。因为是有向图，所以正向与反向的最短路径不一定相同，所以选项 $B$ 不正确。选项 $C$ 符合最短路径要求，选项 $D$ 通过反证法即可证得正确。

T17

题目给的异或运算表：
请添加图片描述
代入计算发现选项 $A$ 和选项 $B$ 一定对；选项 $C$ 和选项 $D$ 在 $a$ $=$ $T r u e$ ， $b$ $=$ $T r u e$ ， $c$ $=$ $F a l s e$ 时不成立。
另外，选项 $C$ 和选项 $D$ 中 $\land$ 是逻辑与， $\lor$ 是逻辑或。

T18

小数转化为二进制用乘法，先排除整数和有限小数，因为是十进制循环小数，每次乘 $2$ 取整后的数都一样，一直循环再下去就成了无限循环小数。故选 $A$ 。

T19

$H T T P$ ：超文本传输协议
$F T P$ ：文件传输协议
$P O P 3$ ：邮局协议版本3
$S M T P$ ：简单邮件传输协议

故选选项 $C$ 与选项 $D$ 。

T20

$N P$ 问题是指存在多项式算法能够验证的非决定性问题，而其中NP完全问题又是最有可能不是P问题的问题类型。所有的 $N P$ 问题都可以用多项式时间归约到他们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的 $N P - 完全问题$ 也可以在多项式时间内求解。

$P$ 问题是具有多项式算法的判定问题。这里的 $P$ 代表 $P o l y n o m i a l$ 。 $P$ 问题就是可以有一个确定型图灵机在多项式时间内解决的问题。即那些存在 $O (n)$ ， $O (n k)$ ， $O (n l o g n)$ 等多项式时间复杂度解法的问题。比如排序问题、最小生成树、单源最短路径。直观的讲，我们将 $P$ 问题视为可以较快解决的问题。

所以选项 $B$ 和选项 $D$ 正确，选项 $A$ 和选项 $C$ 错误。

T21

对于 $p, q, r$ 三个变量，每个变量可取 $0$ 和 $1$ 两种值，可以得到有 $8$ 种组合。对于每种组合，带入表达式只有 $0$ 和 $1$ 两种答案。因此两两不等价的表达式只有 $2^8=256$ 种。

T22

这道题考察 $D P$ ，可以发现题目给出的是一棵二叉树，那么可以做一遍树形 $D P$ ：
设 $g [i]$ 表示以 $i$ 为根的子树的独立集数；
$f [i] [0]$ 表示不选 $i$ 号节点，以 $i$ 为根的子树的独立集数；
$f [i] [1]$ 表示选 $i$ 号节点，以 $i$ 为根的子树的独立集数；
显然有 $g [i] = f [i] [0] + f [i] [1]$ ， $l c$ 为左儿子， $r c$ 为右儿子，那么有 $f [i] [0] = g [r c], f [i] [1] = f [l c] [0] * f [r c] [0]$ 。
最后答案为 $g [r o o t]$ 。

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$ 。

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$ 的约数个数， $120=2^3*3*5$ ，所以约数个数为 $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]$ ，自己写几个数据后归纳出最后 $d a t a []$ 数组中的数据为： $1024, 512, 256, 128, 64, 16, 8, 4$ 。即： $2012 = 1024 + 512 + 256 + 128 + 64 + 16 + 8 + 4$ ，即最终的结果是将输入的一个数通过归并的方式拆分成若干个 $2$ 的整数次方的和，而 $2^m$ 需要 $2^{m-1}$ 合并，所以最终结果为 $1023 + 511 + 255 + 127 + 63 + 15 + 7 + 3 = 2004$ ，故答案为 $2004$ 。另一个输入 $8$ 自然也就输出 $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$ 基本值对应 $123456$ ，求出的是各个节点基本值乘以该节点深度的和。
这得注意的是，在构造二叉树的时候是严格按照先序遍历的方式进行 $d f s$ ， $x$ 相当于作为判断的节点， $t h$ 相当于要插入的节点，如果 $x$ 没有左右子树，就可以尝试往 $x$ 的两个子树分别添加 $t h$ 节点进行判断；如果 $x$ 有左子树，就只能往右子树插；如果 $x$ 有右子树，那么就插不进去了；如果在这个节点插入是不行的，那么就往根节点跳。
按照上述方法来做，即可得到答案为 $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$ 表示数字 $i$ 还没有被使用过，每次倒着找到第一个能变大的数字，然后变大，接着把后面的数字直接从小到大排列，就生成了一个新的组合。 $f l a g$ 是标记能不能找到一个新的排列，第一层的循环意义是把排列中的第 $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$ 个数用循环队列来维护，用 $d i r e c t i o n$ 来记录这个队列的方向，如果需要翻转，就在这个队列里翻转即可。 $p u s h$ 就是看队列里有没有满，满了就先让一个数到 $s$ 这个栈里，再加入队列，否则直接加入。而 $p o p$ 则只需要看队列里还有没有数，有就直接输出，否则 $E R R O R$ 。那弹出之后如果队列不满且 $s$ 中还有数，就可以将 $s$ 中的数弹出放入队列中。
所以：

第一空：return (k%c)+1
第二空：s[n]=q[tail]
第三空：q[head]
第四空：q[head]
第五空：q[tail]
第六空：next(head)

完结撒花~~

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/172069.html原文链接：https://javaforall.net

noip2014普及组复赛试题_大一高数期末考试试题

T1

T2

T3

T4

T5

T6

T7

T8

T9

T10

T11

T12

T13

T14

T15

T16

T17

T18

T19

T20

T21

T22

T23

T24

T25

T26

T27

T28

相关推荐

解决win10状态栏的搜索框无法搜索本地应用或无反应

validate bootstrap 方法「建议收藏」

二叉树的性质及其创建

vue webpak版本 查看_vue版本以及webpack版本

iphone4装android,iPhone4可安装Android实现双系统启动.pdf

硬阈值(Hard Thresholding)函数解读[通俗易懂]

发表回复

vue webpak版本查看_vue版本以及webpack版本