普及组真题
1.在二进制中，1101+()= 111010。
A.1011 b . 1101 c . 1010d . 1111
2.字符“0”的ASCII码是48，字符“9”的ASCII码是()。
A.39b.57c.120d。这要看具体的电脑。
3.一张8GB容量的SD卡可以存储大约()张2MB大小的数码照片。
A.1600
4.摩尔定律是英特尔的创始人之一戈登创立的。它是由戈登·摩尔提出的。根据摩尔定律，在过去几十年和可预见的未来，单个集成电路的集成度每()个月就会翻一番。
A.1 B. 6 C. 18 D. 36
5.无向完全图是一个简单的图，图中每对顶点之间只有一条边。给定一个无向完全图G有七个顶点，它有()条边。
A.21
6.寄存器是()的重要组成部分。
A.硬盘b .缓存c .内存d .中央处理器(CPU)
7.如果根节点的深度是1，那么恰好有2011个叶节点的二叉树的深度至少是()。
A.10 b . 11c . 12d . 13
8.体育课铃响了，学生们一个接一个地奔向操场，按照老师的要求从高到低站成一排。当每个同学按顺序来到操场后，从排尾走到头，找到第一个比自己高的同学，站在他身后。这种排队方法类似于()算法。
A.快速排序b .插入排序c .冒泡排序d .归并排序
9.如果一个正整数在二进制中有100位，那么在十六进制中有()位。
A.7b.13c.25d .不确定。
10.有人认为，把一个文件放入回收站，就意味着在个人电脑送修之前，这个文件已经被删除了。这个想法是()。
A.没错，把一个文件放入回收站，就意味着它被彻底删除，无法恢复。
B.不正确，只有清空回收站后，才表示完全删除，无法恢复。
C.不正确，即使清空了回收站，并且文件仅被标记为已删除，仍然可以通过恢复软件检索到该文件。
D.不正确的文件，只要出现在硬盘上，就永远无法彻底删除。
11.广度优先搜索需要的数据结构是()。
A.链表b .队列c .栈d .哈希表
12.用高级语言编程时，“空间复杂度”中的“空间”一般指()。
A.程序运行时理论上占用的内存空间。
B.程序运行时理论上占用的数组空间
C.程序运行时理论上占用的硬盘空间
D.程序源文件占用的理论硬盘空间
13.查询在一个包含n个元素的双向链表中是否有一个键为k的元素。在最坏的情况下，运行时间复杂度是()。
A.O(1)b . O(log n)c . O(n)d . O(n log n)
14.生物识别是利用人体的生物特征进行身份认证的技术。目前，指纹识别、虹膜识别、人脸识别等技术已经广泛应用于政府、银行、安防等领域。下列不属于生物识别技术及其应用的是()。
A.手指静脉验证b .步态验证C. ATM密码验证d .语音验证
15.一个已有的文言文文本应该用二进制霍夫曼编码进行压缩。为简单起见，假设这篇文言文仅由四个汉字组成，即直、胡、者、也，分别出现700、600、300、200次。那么，“也”字的编码长度是()。
A.1 B. 2 C. 3 D. 4
16.关于汇编语言，下列说法错误的是()。
是一种与特定硬件相关的编程语言。
B.写复杂程序时，相对于高级语言，代码量大，不容易调试。
直接访问寄存器、存储单元和I/O端口。
d随着高级语言的诞生，已经完全被淘汰，不再使用。
17.()是一种优化搜索方法，根据优化条件向前搜索以达到目标。当你探索到某一步的时候，发现原来的选择并不优秀或者达不到目标，于是退一步重新选择。
A.回溯法b .枚举法c .动态规划d .贪婪法
18.1956()被授予肖克利、约翰·巴丁和布拉顿，以表彰他们对半导体的研究和对晶体管效应的发现。
A.诺贝尔物理学奖
b .约翰？冯？诺伊曼奖
C.图灵奖
D.唐纳德·克努特奖
19.对于一个有向图，如果每个节点都有一条到任何其他节点的路径，则称它是强连通的。例如，右图是一个强连通图。其实删除边()后，还是强连通的。
A.a B. b C. c D. d
20.从ENIAC到目前最先进的计算机，冯？诺依曼建筑始终占据着重要的地位。冯？诺依曼架构的核心内容是()。
A.采用开关电路b .采用半导体器件。
c、采用存储程序和程序控制原理D、采用键盘输入。
二、解题(***2题，每题5分，* * * 10分)
1.每张试卷都有一个8位二进制序列号。当且仅当序列号包含1的偶数时，它才有效。比如0000000000，0101011都是有效的序列号，而1165438+。然后，有_ _ _ _ _ _ _ _ _个有效序列号* *。
2.定义字符串的基本操作是:删除一个字符，插入一个字符，将一个字符修改成另一个字符。将字符串A变为字符串B的最小操作步数称为从字符串A到字符串B的编辑距离..从字符串“ABCDEFG”到字符串“BADECG”的编辑距离是_ _ _ _ _ _ _ _ _。
三、阅读程序写结果(***4题，每题8分，32分***)
1.
# include & ltstdio.h & gt
int main() {
int i，n，m，ans
scanf("%d%d "，& ampn & amp；m)；
I = n；
ans = 0；
while(我& lt= m) {
ans+= I；
i++；
}
printf("%d\n "，ans)；
返回0；
}
输入:10 20
产出:_ _ _ _ _ _ _ _
2.
# include & ltstdio.h & gt
# include & ltstring.h & gt
#定义尺寸20
int main()
{
char map[]= " 222333444555666777889999 "；
char tel[SIZE]；
int I；
scanf("%s "，电话)；
for(I = 0；我& ltstrlen(电话)；i++)
if((tel[I]& gt；= ' 0 ')& amp；& amp(电话[I]& lt；= '9'))
printf("%c "，tel[I])；
else if((tel[I]& gt；= ' A ')& amp；& amp(电话[I]& lt；= 'Z '))
printf("%c "，map[tel[I]-' A '])；
返回0；
}
输入:CCF-NOIP-2011。
产出:_ _ _ _ _ _ _ _
3.
# include & ltstdio.h & gt
# include & ltstring.h & gt
#定义尺寸100
int main()
{
int n，I，sum，x，a[SIZE]；
scanf("%d "，& ampn)；
memset(a，0，sizeof(a))；
for(I = 1；我& lt= n；i++) {
scanf("%d "，& ampx)；
a[x]++；
}
I = 0；
sum = 0；
while(sum & lt；(n / 2 + 1)) {
i++；
sum+= a[I]；
}
printf("%d\n "，I)；
返回0；
}
输入:
11
4 5 6 6 4 3 3 2 3 2 1
产出:_ _ _ _ _ _ _ _
4.
# include & ltstdio.h & gt
int solve(int n，int m)
{
int i，sum
如果(m == 1)
返回1；
sum = 0；
for(I = 1；我& ltn；i++)
sum += solve(i，m-1)；
返回总和；
}
int main()
{
int n，m；
scanf("%d %d "，& ampn & amp；m)；
printf("%d\n "，solve(n，m))；
返回0；
}
输入:7 4
产出:_ _ _ _ _ _ _ _
四、完善方案(11前空，每空2分，2后空，每空3分，28分* * *)。
1.(子矩阵)输入一个n1*m1的矩阵A和一个n2*m2的矩阵B，问A中是否有子矩阵等于B，如果有，输出所有子矩阵的左上角坐标；如果没有输出“没有答案”。
# include & ltstdio.h & gt
#定义尺寸50
int n1，m1，n2，m2，a[SIZE][SIZE]，b[SIZE][SIZE]；
int main()
{
int i，j，k1，k2，good，haveAns
scanf("%d %d "，& ampn 1；m 1)；
for(I = 1；我& lt= n 1；i++)
for(j = 1；j & lt= m 1；j++)
scanf("%d "，& ampa[I][j])；
scanf("%d %d "，& ampn2和ampm2)；
for(I = 1；我& lt= n2i++)
for(j = 1；j & lt= m2j++)
① ;
have ans = 0；
for(I = 1；我& lt= n 1-N2+1；i++)
for(j = 1；j & lt= ② ;j++) {
③ ;
for(k 1 = 1；k 1 & lt；= n2k1++)
for(k2 = 1；k2 & lt= ④ ;k2++) {
if(a[I+k 1-1][j+k2-1]！= b[k1][k2])
好= 0；
}
if (good == 1) {
printf("%d %d\n "，I，j)；
⑤ ;
}
}
if (haveAns == 0)
printf("没有答案\ n ")；
返回0；
}
2.(大整数根)输入一个正整数n (1 ≤ n
# include & ltstdio.h & gt
# include & ltstring.h & gt
#定义尺寸200
typedef结构节点{
int len，num[SIZE]；
} hugeint
//其中len表示大整数的位数；Num[1]表示一位，num[2]表示十位，依此类推。
hugeint次(hugeint a，hugeint b)
//计算大整数A和b的乘积。
{
int i，j；
hugeint ans
memset(ans.num，0，sizeof(ans . num))；
for(I = 1；我& lt= a.leni++)
for(j = 1；j & lt= b.lenj++)
① += a号[i] * b号[j]；
for(I = 1；我& lt= a . len+b . len；i++) {
ans . num[I+1]+= ans . num[I]/10；
② ;
}
if(ans . num[a . len+b . len]& gt；0)
ans . len = a . len+b . len；
其他
ans . len = a . len+b . len-1；
返回ans
}
hugeint add(hugeint a，hugeint b)
//计算大整数A和b的和。
{
int I；
hugeint ans
memset(ans.num，0，sizeof(ans . num))；
if(a . len & gt；文学硕士)
ans . len = a . len；
其他
ans . len = b . len；
for(I = 1；我& lt= ans.leni++) {
ans . num[I]+=③；
ans . num[I+1]+= ans . num[I]/10；
ans . num[I]% = 10；
}
if(ans . num[ans . len+1]& gt；0)
ans . len++；
返回ans
}
hugeint平均值(hugeint a，hugeint b)
//计算大整数A和b的平均值的整数部分。
{
int I；
hugeint ans
ans = add(a，b)；
for(I = ans . len；我& gt= 2;我- ) {
ans . num[I-1]+=(④)* 10；
ans . num[I]/= 2；
}
ans . num[1]/= 2；
if(ans . num[ans . len]= 0)
ans . len-；
返回ans
}
胡根特加二号
//计算大整数a加2的结果。
{
int I；
hugeint ans
ans = a；
ans . num[1]+= 2；
I = 1；
而((i & lt= ans . len)& amp；& amp(ans . num[I]& gt；= 10)) {
ans . num[I+1]+= ans . num[I]/10；
ans . num[I]% = 10；
i++；
}
if(ans . num[ans . len+1]& gt；0)
⑤ ;
返回ans
}
int over(hugeint a，hugeint b)
//如果整数是一个& gtb返回1，否则返回0。
{
int I；
如果(⑥)
返回0；
if(a . len & gt；文学硕士)
返回1；
for(I = a . len；我& gt= 1;我- ) {
if(a . num[I]& lt；编号[i])
返回0；
if(a . num[I]& gt；编号[i])
返回1；
}
返回0；
}
int main()
{
char s[SIZE]；
int I；
hugeint目标，左，中，右；
scanf("%s "，s)；
memset(target.num，0，sizeof(target . num))；
target . len = strlen(s)；
for(I = 1；我& lt= target.leni++)
target . num[I]= s[target . len-I]-⑦；
memset(left.num，0，sizeof(left.num))。
left . len = 1；
left . num[1]= 1；
右=目标；
做{
中间=平均(左，右)；
if (over( ⑧ ) == 1)
右=中；
其他
左=中；
} while (over(plustwo(left)，right)= = 0)；
for(I = left . len；我& gt= 1;我-)
printf("%d "，left . num[I])；
printf(" \ n ")；
返回0；
}