NOIP2011-17届NOIP（C语言）普及组初赛试题

17届NOIP（C语言）普组初赛试题

单项选择题（20题题15分计30分题仅正确选项）
1．二进制1101001 + （ ） 1110110
A 1011 B 1101 C 1010 D 1111
2．字符0ASCII码48字符9ASCII码（ ）
A 39 B 57 C 120 D 视具体计算机定
3．片容量8GBSD卡存储约（ ）张2MB数码片
A 1600 B 2000 C 4000 D 16000
4．摩尔定律（Moore＇s law）英特尔创始戈登•摩尔（Gordon Moore）提出根摩尔定律十年预测未年单块集成电路集成度约（ ）月翻番
A 1 B 6 C 18 D 36

5．完全图图中顶点间恰条边简单图已知完全图G7顶点（ ）条边
A 7 B 21 C 42 D 49

6．寄存器（ ）重组成部分
A 硬盘 B 高速缓存 C 存 D 中央处理器（CPU）

7．果根结点深度记1棵恰2011叶结点二叉树深度少（ ）
A 10 B 11 C 12 D 13

8 体育课铃声响学陆续奔操场老师求高矮站成排学序操场时排尾走排头找第高学站面种站队方法类似（ ）算法
A 快速排序 B 插入排序 C 泡排序 D 排序

9．正整数二进制100位十六进制（ ）位
A 7 B 13 C 25 D 确定

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．现段文言文通二进制哈夫曼编码进行压缩简单起见假设段文言文4汉字者组成出现次数分700600300200字编码长度（ ）
A 1 B 2 C 3 D 4

16．关汇编语言列说法错误（ ）
A 种具体硬件相关程序设计语言
B 编写复杂程序时相高级语言言代码量较易调试
C 直接访问寄存器存单元IO端口
D 着高级语言诞生已完全淘汰

17．（ ）种选优搜索法选优条件前搜索达目标探索某步时发现原先选择优达目标退回步重新选择
A 回溯法 B 枚举法 C 动态规划 D 贪心法

18．1956年（ ）授予肖克利（William Shockley）巴丁（John Bardeen）布拉顿（Walter Brattain）表彰半导体研究晶体效应发现
A 诺贝尔物理学奖
B 约翰•冯•诺曼奖
C 图灵奖
D 高德纳奖（Donald E Knuth Prize）

19．图言果节点存达节点路径称强连通例右图强连通图事实删掉边（ ）然强连通
A a B b C c D d

20．ENIAC前先进计算机冯•诺曼体系结构始终占重位冯•诺曼体系结构核心容（ ）
A 采开关电路 B 采半导体器件
C 采存储程序程序控制原理 D 采键盘输入

二问题求解（2题题5分计10分）

1．份考卷8位二进制序列号仅序列号含偶数1时效例0000000001010011效序列号11111110效序列号________

2．定义字符串基操作：删字符插入字符字符修改成字符三种操作字符串A变成字符串B少操作步数称字符串A字符串B编辑距离字符串ABCDEFG字符串BADECG编辑距离________

三阅读程序写结果（4题题8分计32分）

1
#include
int main() {
int i n m ans

scanf(dd &n &m)
i n
ans 0
while (i < m) {
ans + i
i++
}
printf(d＼n ans)
return 0
}
输入：10 20
输出：_________

2．
#include
#include
#define SIZE 20

int main()
{
char map[] 22233344455566677778889999
char tel[SIZE]
int i

scanf(s tel)
for (i 0 i < strlen(tel) i++)
if ((tel[i] > ＇0＇) && (tel[i] < ＇9＇))
printf(c tel[i])
else if ((tel[i] > ＇A＇) && (tel[i] < ＇Z＇))
printf(c map[tel[i] ＇A＇])
return 0
}

输入：CCFNOIP2011
输出：_________

3．
#include
#include
#define SIZE 100

int main()
{
int n i sum x a[SIZE]

scanf(d &n)
memset(a 0 sizeof(a))
for (i 1 i < n i++) {
scanf(d &x)
a[x]++
}

i 0
sum 0
while (sum < (n 2 + 1)) {
i++
sum + a[i]
}
printf(d＼n i)
return 0
}

输入：
11
4 5 6 6 4 3 3 2 3 2 1
输出：_________

4．
#include

int solve(int n int m)
{
int i sum

if (m 1)
return 1
sum 0
for (i 1 i < n i++)
sum + solve(i m 1)
return sum
}

int main()
{
int n m

scanf(d d &n &m)
printf(d＼n solve(n m))
return 0
}

输入：7 4
输出：_________

四完善程序（前11空空2分2空空3分计28分）

1．（子矩阵）输入n1*m1矩阵an2*m2矩阵b问a中否存子矩阵b相等存输出子矩阵左角坐标存输出There is no answer

#include
#define SIZE 50

int n1 m1 n2 m2 a[SIZE][SIZE] b[SIZE][SIZE]

int main()
{
int i j k1 k2 good haveAns

scanf(d d &n1 &m1)
for (i 1 i < n1 i++)
for (j 1 j < m1 j++)
scanf(d &a[i][j])
scanf(d d &n2 &m2)
for (i 1 i < n2 i++)
for (j 1 j < m2 j++)
①

haveAns 0
for (i 1 i < n1 n2 + 1 i++)
for (j 1 j < ② j++) {
③
for (k1 1 k1 < n2 k1++)
for (k2 1 k2 < ④ k2++) {
if (a[i + k1 1][j + k2 1] b[k1][k2])
good 0
}
if (good 1) {
printf(d d＼n i j)
⑤
}
}
if (haveAns 0)
printf(There is no answer＼n)
return 0
}

2．（整数开方）输入正整数n（1≤n<10100）试二分法计算方根整数部分

#include
#include
#define SIZE 200

typedef struct node {
int len num[SIZE]
} hugeint
中len表示整数位数num[1]表示位num[2]表示十位类推

hugeint times(hugeint a hugeint b)
计算整数ab积
{
int i j
hugeint ans

memset(ansnum 0 sizeof(ansnum))
for (i 1 i < alen i++)
for (j 1 j < blen j++)
① + anum[i] * bnum[j]
for (i 1 i < alen + blen i++) {
ansnum[i + 1] + ansnum[i] 10
②
}
if (ansnum[alen + blen] > 0)
anslen alen + blen
else
anslen alen + blen 1
return ans
}

hugeint add(hugeint a hugeint b)
计算整数ab
{
int i
hugeint ans

memset(ansnum 0 sizeof(ansnum))
if (alen > blen)
anslen alen
else
anslen blen
for (i 1 i < anslen i++) {
ansnum[i] + ③
ansnum[i + 1] + ansnum[i] 10
ansnum[i] 10
}
if (ansnum[anslen + 1] > 0)
anslen++
return ans
}

hugeint average(hugeint a hugeint b)
计算整数ab均数整数部分
{
int i
hugeint ans

ans add(a b)
for (i anslen i > 2 i) {
ansnum[i 1] + ( ④ ) * 10
ansnum[i] 2
}
ansnum[1] 2
if (ansnum[anslen] 0)
anslen
return ans
}

hugeint plustwo(hugeint a)
计算整数a加2结果
{
int i
hugeint ans

ans a
ansnum[1] + 2
i 1
while ((i < anslen) && (ansnum[i] > 10)) {
ansnum[i + 1] + ansnum[i] 10
ansnum[i] 10
i++
}
if (ansnum[anslen + 1] > 0)
⑤
return ans
}

int over(hugeint a hugeint b)
整数a>b返回1否返回0
{
int i

if ( ⑥ )
return 0
if (alen > blen)
return 1
for (i alen i > 1 i) {
if (anum[i] < bnum[i])
return 0
if (anum[i] > bnum[i])
return 1
}
return 0
}

int main()
{
char s[SIZE]
int i
hugeint target left middle right

scanf(s s)
memset(targetnum 0 sizeof(targetnum))
targetlen strlen(s)
for (i 1 i < targetlen i++)
targetnum[i] s[targetlen i] ⑦
memset(leftnum 0 sizeof(leftnum))
leftlen 1
leftnum[1] 1
right target
do {
middle average(left right)
if (over( ⑧ ) 1)
right middle
else
left middle
} while (over(plustwo(left) right) 0)
for (i leftlen i > 1 i)
printf(d leftnum[i])
printf(＼n)
return 0
}

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档