下载文档原格式
第十五届（2009年）信息学奥赛初赛试题及答案一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。
）1 、关于图灵机下面的说法哪个是正确的：图灵机是世界上最早的电子计算机。
由于大量使用磁带操作，图灵机运行速度很慢。
图灵机只是一个理论上的计算模型。
图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
答案（C）2、关于BIOS下面的说法哪个是正确的：BIOS是计算机基本输入输出系统软件的简称。
BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。
BIOS一般由操作系统厂商来开发完成。
BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
答案（A）3 、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：A）48 B）49 C）50 D）以上都不是答案（D）4 、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。
其对应的十进制整数应该是：A）19 B）-19 C）18 D）-18答案（B）5 、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1答案（D）6 、表达式a*(b+c)-d的后缀表达式是：abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd答案（B）7 、最优前缀编码，也称Huffman编码。
这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。
下面编码组合哪一组不是合法的前缀编码：A）（00，01，10，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）答案（B）8 、快速排序平均情况和最坏情况下的算法时间复杂度分别为：平均情况O(nlog(2,n))，最坏情况O(n^2)平均情况O(n)，最坏情况O(n^2)平均情况O(n)，最坏情况O(nlog(2,n))平均情况O(log(2,n))，最坏情况O(n^2)答案（A）9 、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。
第十五届（2009年）信息学奥赛初赛试题及答案一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。
）1 、关于图灵机下面的说法哪个是正确的：图灵机是世界上最早的电子计算机。
由于大量使用磁带操作，图灵机运行速度很慢。
图灵机只是一个理论上的计算模型。
图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
答案（C）2、关于BIOS下面的说法哪个是正确的：BIOS是计算机基本输入输出系统软件的简称。
BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。
BIOS一般由操作系统厂商来开发完成。
BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
答案（A）3 、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：A）48 B）49 C）50 D）以上都不是答案（D）4 、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。
其对应的十进制整数应该是：A）19 B）-19 C）18 D）-18答案（B）5 、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1答案（D）6 、表达式a*(b+c)-d的后缀表达式是：abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd答案（B）7 、最优前缀编码，也称Huffman编码。
这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。
下面编码组合哪一组不是合法的前缀编码：A）（00，01，10，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）答案（B）8 、快速排序平均情况和最坏情况下的算法时间复杂度分别为：平均情况O(nlog(2,n))，最坏情况O(n^2)平均情况O(n)，最坏情况O(n^2)平均情况O(n)，最坏情况O(nlog(2,n))平均情况O(log(2,n))，最坏情况O(n^2)答案（A）9 、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。
第十五届（2009年）信息学奥赛初赛试题答案一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。
）1 、关于图灵机下面的说法哪个是正确的：答案（C）A）图灵机是世界上最早的电子计算机。
B）由于大量使用磁带操作，图灵机运行速度很慢。
C）图灵机只是一个理论上的计算模型。
D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
最早的计算机是ENIAC图灵机是计算机模型，没有运行速度，更谈不上磁带操作图灵机是英国人阿兰图灵提出的理论，阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。
图灵是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。
人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。
1936年，阿兰.图灵提出了一种抽象的计算模型── 图灵机(Turing Machine)。
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。
装置由一个控制器和一根假设两端无界的工作带（起存储器的作用）组成。
工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。
控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。
外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。
“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。
回顾20世纪科学技术的辉煌发展时，不能不提及20世纪最杰出的数学家之一的冯·诺依曼（美籍匈牙利人）。
20世纪40年代，冯·诺依曼在参与世界上第一台计算机-ENIAC的研制小组工作时，发现ENIAC有两个致命的缺陷：一是采用十进制运算，逻辑元件多，结构复杂，可靠性低；二是没有内部存贮器，操纵运算的指令分散存贮在许多电路部件内，这些运算部件如同一副积木，解题时必须像搭积木一样用人工把大量运算部件搭配成各种解题的布局，每算一题都要搭配一次，非常麻烦且费时。
NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项） 1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。
A. 2020B. 2021C. 2022D. 20232.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。
A. 43B. -85C. -43D.-843.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。
A. 2812.5KBB. 4218.75KBC. 4320KBD. 2880KB4. 2017年10月1日是星期日，1949年10月1日是( )。
A. 星期三B. 星期日C. 星期六D. 星期二5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。
A.m–n+1B. m-nC. m+n+1D.n–m+16. 若某算法的计算时间表示为递推关系式：T(N)=2T(N/2)+NlogNT(1)=1则该算法的时间复杂度为( )。
A.O(N)B.O(NlogN)C.O(N log2N)D.O(N2)7. 表达式a * (b + c) * d的后缀形式是()。
A. abcd*+*B. abc+*d*C. a*bc+*dD. b+c*a*d8. 由四个不同的点构成的简单无向连通图的个数是( )。
A. 32B. 35C. 38D. 419. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。
A. 60B. 84C. 96D.12010. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。
A. 1/2B. 2/3D. 111. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。
2017年第十五届绍兴市少儿信息学竞赛复赛试题全文共四篇示例，供读者参考第一篇示例：绍兴市少儿信息学竞赛是绍兴市教育局主办的一项旨在鼓励少儿学习计算机科学知识，提高信息技术应用能力的比赛。
每年都吸引了众多学生参与，展现出了他们在信息学领域的才华和潜力。
今年的第十五届绍兴市少儿信息学竞赛复赛即将举行，以下是部分试题供参赛选手练习。
一、选择题1. 下列哪个是二进制数系统中的最大数字？A. 0B. 1C. 10D. 112. 在计算机领域，HTTP是指什么？A. 超文本传输协议B. 超文本处理器C. 超级传输协议D. 超级处理器3. 在Excel中，下列哪个不是函数？A. SUMB. IFC. MAXD. +-4. 在计算机中，CPU是指什么？A. 控制处理器单元B. 中央处理器单元C. 运算处理器单元D. 计算处理器单元5. 以下哪个不是常见的编程语言？A. JavaB. PythonC. PhotoshopD. C++二、填空题1. 在二进制数系统中，用8个比特表示的最大十进制数是_________。
2. HTML是什么含义？HTML全称为________________。
3. 在Excel中，用于对多个单元格进行求和运算的函数是_________。
5. Python是一种_________编程语言。
三、计算题1. 请计算二进制数1101转换为十进制数的结果。
2. 请计算以下列出的数的和：101、23、45、67。
3. 请编写一个简单的Python程序，输出“Hello, World!”。
四、简答题1. 请简要解释HTTP和HTTPS之间的区别。
2. 请简要介绍一下计算机的工作原理。
3. 请简要介绍一下什么是算法，以及算法在计算机领域的应用。
以上为2017年第十五届绍兴市少儿信息学竞赛复赛试题的部分内容，希望参赛选手能够认真思考，努力完成每一道题目。
祝大家取得好成绩！第二篇示例：绍兴市少儿信息学竞赛是绍兴市教育局主办的一项旨在培养青少年信息技术能力的赛事。
信息奥林匹克竞赛试题一、选择题（每题2分，共20分）1. 在计算机科学中，以下哪个不是基本数据结构？A. 数组B. 链表C. 栈D. 文件系统2. 以下哪个算法是用于解决最短路径问题的？A. 快速排序B. 深度优先搜索C. 迪杰斯特拉算法D. 欧几里得算法3. 在C++语言中，以下哪个关键字用于声明引用类型？A. intB. floatC. &D. *4. 以下哪个排序算法是稳定的？A. 快速排序B. 归并排序C. 堆排序D. 冒泡排序5. 在数据库中，以下哪个操作用于删除表中的记录？A. SELECTB. INSERTC. DELETED. UPDATE二、简答题（每题10分，共20分）1. 描述什么是递归，并给出一个简单的递归算法的例子。
2. 解释什么是时间复杂度，并给出一个算法的时间复杂度分析示例。
三、编程题（每题30分，共60分）1. 编写一个函数，实现对一个整数数组的快速排序算法。
要求：- 输入：一个整数数组及其长度。
- 输出：排序后的数组。
2. 编写一个程序，实现对一个字符串进行模式匹配的KMP算法。
要求：- 输入：主字符串和模式字符串。
- 输出：模式字符串在主字符串中的所有出现位置。
四、算法设计题（每题30分，共30分）设计一个算法，用于在无序数组中找到第k大的元素。
假设数组中没有重复元素。
要求：- 输入：一个无序整数数组及其长度，以及一个整数k。
- 输出：第k大的元素。
结束语：本试题旨在考察参赛者对计算机科学基础知识的掌握程度，以及编程和算法设计的能力。
希望参赛者能够通过练习，提高自己的编程技巧和解决问题的能力。
祝所有参赛者取得优异的成绩！。
信息学奥赛试题及答案信息学奥赛试题一、填空题（共20题，每题1.5分，共计30分。
每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。
1.微型计算机的性能主要取决于（）。
A）内存B）主板C）中央处理器D）硬盘E）显示器2.能将高级语言程序转换为目标程序的是( ).A）调试程序B）解释程序C）编辑程序D）编译程序E）连接程序3．A=B,B=B,C=B,则A∨B∧C=( )A） B） C） D） E)4.计算机设备，既是输入设备，又是输出设备的是( )。
A)键盘B)触摸屏C)扫描仪D)投影仪E)数字化仪5.计较机病毒沾染的需求前提是( )。
A)在内存中运转病毒步伐B)对磁盘举行读写操纵C)在内存中运行含有病毒的可执行程序D)复制文件E)删除文件6．行列(13，2，11，34，4l，77，5，7，18，26，15)，第一个进入行列的元素是13，则第五个出行列的元素是( )。
A)5 B)41 C)77 D)13 E)187.在利用E-mail前，需求对Outlook举行设置，个中ISP 发送电子邮件的效劳器称为( )效劳器。
A)POP3 B)SMTPC)DNS D)FTP E)HTTP8.对给定的整数序列(54,73,21,35,67,78,63,24,89)举行从小到大的排序时,接纳快速排序的第一趟扫描的成效是( ).A)(24,21,35,54,67, 78,63,73,89) B)(24,35,21,54,67, 78,63,73,89)C)(24,21,35,54,67, 63,73,78,89) D)(21,24,35,54,63, 67,73,78,89)E)(24,21,35,54,67, 63,73,78,89)9.编号为1到13的纸牌顺时针排成一圈，有人从编号为1的牌从数字1开始顺时针数下去，1，2，3，……,一圈又一圈,问当数到数字n ,所在的纸牌编号为多少?A) n mod 13 B)1+(n-1) mod 13 C)(n+1) mod 13-1 D)(n+1) mod 13 E) (n-1) mod 1310.对下图进行广度优先拓朴排序得到的顶点序列正确的是( ).A) 1,2,3,4,5,6 B) 1,3,2,4,5,6 C) 1,3,2,4,6,5D) 1,2,3,4,6,5, E) 1,3,2,4,5,611.下列属于冯.诺依曼计算机模型的核心思想是( ).A)采用二进制表示数据和指令; B)采用”存储程序”工作方式C)计算机硬件有五大部件(运算器、控制器、存储器、输入和输出设备)D)结构化程序设计方法E)计算机软件只有系统软件12．CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。
历年noip初赛普及组试题芜湖县实验学校noip初赛复习资料整理：zq多年来noip推广组预赛试题汇编芜湖县实验学校noip初赛复习资料芜湖市实验学校noip初审数据整理：ZQ第十五届全国青少年信息学奥林匹克联赛初赛试题(2021)（通用C++语言组在两小时内完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单选题（共20道题，每道题1.5分，共30分。
每道题有且只有一个正确答案。
）1.关于图灵机，以下哪项陈述是正确的：a)图灵机是世界上最早的电子计算机。
b）由于磁带操作的广泛使用，图灵机运行非常缓慢。
c)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
d)图灵机只是一个理论上的计算模型。
2、关于计算机内存下面的说法哪个是正确的：a）随机存取存储器（RAM）是指当程序运行时，每次分配给程序的特定内存位置是随机的机而不确定的。
b） 1MB内存通常指1024*1024字节的内存。
c）严格来说，计算机内存包括主存、缓存和寄存器三个部分。
d）通常，即使在断电的情况下，内存中的数据也可以保留2小时以上。
3.关于BIOS，以下哪项陈述是正确的：a)bios是计算机基本输入输出系统软件的简称。
b） BIOS包含常用输入和输出设备的驱动程序，如键盘、鼠标、声卡、图形卡和打印机。
c） BIOS通常由操作系统制造商开发。
d)bios能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
4、关于cpu下面哪个说法是正确的：a） CPU被称为中央处理器（CPU）。
b） CPU可以直接运行汇编语言。
c)同样主频下，32位的cpu比16位的cpu运行速度快一倍。
d)cpu最早是由intel 公司发明的。
5、关于ascii，下面哪个说法是正确的：a） ASCII码是键盘上所有键的唯一代码。
b)一个ascii码使用一个字节的内存空间就能够存放。
c）新扩展的ASCII编码方案包括汉字和其他欧洲语言的编码。
第十七届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言两小时完成）●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。
每题有且仅有一个正确选项。
）1、在二进制下，1101001 + （） = 1110110。
A、1011B、1101C、1010D、11112、字符“0”的 ASCII 码为 48，则字符“9”的 ASCII 码为（）。
A、39B、57C、120D、视具体的计算机而定3、一片容量为 8GB 的 SD 卡能存储大约（）张大小为 2MB 的数码照片。
A、1600B、2000C、4000D、160004、摩尔定律（Moore's law）是由英特尔创始人之一戈登·摩尔（Gordon Moore）提出来的。
根据摩尔定律，在过去几十年以及在可预测的未来几年，单块集成电路的集成度大约每（）个月翻一番。
A、1B、6C、18D、365、无向完全图是图中每对顶点之间都恰有一条边的简单图。
已知无向完全图 G 有 7 个顶点，则它共有（）条边。
A、7B、21C、42D、496、寄存器是（）的重要组成部分。
A、硬盘B、高速缓存C、内存D、中央处理器（CPU）7、如果根结点的深度记为 1，则一棵恰有 2011 个叶结点的二叉树的深度最少是（）。
A、10B、11C、12D、138、体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。
每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。
这种站队的方法类似于（）算法。
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、现有一段文言文，要通过二进制哈夫曼编码进行压缩。
简单起见，假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、 200。
那么，“也”字的编码长度是（）。
A、1B、2C、3D、416、关于汇编语言，下列说法错误的是（）。
A、是一种与具体硬件相关的程序设计语言B、在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试C、可以直接访问寄存器、内存单元、以及 I/O 端口D、随着高级语言的诞生，如今已完全被淘汰，不再使用17、（）是一种选优搜索法，按选优条件向前搜索，以达到目标。
当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
A、回溯法B、枚举法C、动态规划D、贪心法18、1956 年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain），以表彰他们对半导体的研究和晶体管效应的发现。
A、诺贝尔物理学奖B、约翰·冯·诺依曼奖C、图灵奖D、高德纳奖（Donald E. Knuth Prize）19、对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。
例如，右图就是一个强连通图。
事实上，在删掉边（）后，它依然是强连通的。
A、aB、bC、cD、d20、从 ENIAC 到当前最先进的计算机，冯·诺依曼体系结构始终占有重要的地位。
冯·诺依曼体系结构的核心内容是（）。
A、采用开关电路B、采用半导体器件C、采用存储程序和程序控制原理D、采用键盘输入二、问题求解（共 2 题，每题 5 分，共计 10 分）1、每份考卷都有一个 8 位二进制序列号。
当且仅当一个序列号含有偶数个 1 时，它才是有效的。
例如，00000000、01010011 都是有效的序列号，而 11111110 不是。
那么，有效的序列号共有________个。
2、定义字符串的基本操作为：删除一个字符、插入一个字符和将一个字符修改成另一个字符这三种操作。
将字符串 A 变成字符串 B 的最少操作步数，称为字符串 A 到字符串 B 的编辑距离。
字符串"ABCDEFG"到字符串"BADECG"的编辑距离为________。
三、阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1、Varn, m, i, ans : Integer;BeginReadln(n, m);ans := 0;i := n;While i <= m DoBeginans := ans + i;Inc(i);End;Writeln(ans);End.输入：10 20输出：__________________2、Varmap, tel : String;i : Integer;Beginmap := '22233344455566677778889999';Readln(tel);For i := 1 To Length(tel) DoIf (tel[i] >= '0') AND (tel[i] <= '9')Then Write(tel[i])ElseIf (tel[i] >= 'A') AND (tel[i] <= 'Z')Then Write(map[Ord(tel[i]) - Ord('A') + 1]); End.输入：CCF-NOIP-2011输出：__________________3、ConstSIZE = 100;Varn, i, sum, x : Integer;a : Array[1..SIZE] Of Integer;BeginReadln(n);FillChar(a, SizeOf(a), 0);For i := 1 To n DoBeginRead(x);Inc(a[x]);End;i := 0;sum := 0;While sum < (n DIV 2 + 1) DoBeginInc(i);sum := sum + a[i];End;Writeln(i);End.输入：114 5 6 6 4 3 3 2 3 2 1输出：__________________4、Var n, m : Integer;Function solve(n, m : Integer) : Integer;Var i, sum : Integer;BeginIf m = 1 ThenBeginsolve := 1;Exit;End;sum := 0;For i := 1 To n - 1 Dosum := sum + solve(i, m - 1);solve := sum;End;BeginReadln(n, m);Writeln(solve(n, m));End.输入：7 4输出：__________________四、完善程序（前 11 空，每空 2 分，后 2 空，每空 3 分，共计 28 分）1、（子矩阵）输入一个n1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和b 相等。
若存在，输出所有子矩阵左上角的坐标；若不存在输出“There is no answer”。
ConstSIZE = 50;Varn1, m1, n2, m2, i, j, k1, k2 : Integer;a, b : Array[1..SIZE, 1..SIZE] Of Integer;good, haveAns : Boolean;BeginReadln(n1, m1);For i := 1 To n1 DoFor j := 1 To m1 DoRead(a[i][j]);Readln(n2, m2);For i := 1 To n2 DoFor j := 1 To m2 Do① ;haveAns := FALSE;For i := 1 To n1 - n2 + 1 DoFor j := 1 To②DoBegin③ ;For k1 := 1 To n2 DoFor k2 := 1 To④DoIf a[i + k1 - 1][j + k2 - 1] <> b[k1][k2] Thengood := FALSE;If good ThenBeginWriteln(i, ' ', j);⑤ ;End;End;If NOT haveAns ThenWriteln('There is no answer');End.2、（大整数开方）输入一个正整数n（1≤n＜10100），试用二分法计算它的平方根的整数部分。
ConstSIZE = 200;Typehugeint = Recordlen : Integer;num : Array[1..SIZE] Of Integer;End;//len表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推Vars : String;i : Integer;target, left, middle, right : hugeint;Function times(a, b : hugeint) : hugeint;// 计算大整数 a 和 b 的乘积Vari, j : Integer;ans : hugeint;BeginFillChar(ans, SizeOf(ans), 0);For i := 1 To a.len DoFor j := 1 To b.len Do① := ans.num[i + j - 1] + a.num[i] * b.num[j];For i := 1 To a.len + b.len DoBeginans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10;② ;If ans.num[a.len + b.len] > 0Then ans.len := a.len + b.lenElse ans.len := a.len + b.len - 1; End;times := ans;End;Function add(a, b : hugeint) : hugeint;// 计算大整数 a 和 b 的和Vari : Integer;ans : hugeint;BeginFillChar(ans.num, SizeOf(ans.num), 0);If a.len > b.lenThen ans.len := a.lenElse ans.len := b.len;For i := 1 To ans.len DoBeginans.num[i] := ③ ;ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ans.num[i] := ans.num[i] MOD 10;End;If ans.num[ans.len + 1] > 0Then Inc(ans.len);add := ans;End;Function average(a, b : hugeint) : hugeint;// 计算大整数 a 和 b 的平均数的整数部分Vari : Integer;ans : hugeint;Beginans := add(a, b);For i := ans.len DownTo 2 DoBeginans.num[i - 1] := ans.num[i - 1] + ( ④ ) * 10; ans.num[i] := ans.num[i] DIV 2;End;ans.num[1] := ans.num[1] DIV 2;If ans.num[ans.len] = 0Then Dec(ans.len);average := ans;End;Function plustwo(a : hugeint) : hugeint;// 计算大整数 a 加 2 后的结果Vari : Integer;ans : hugeint;Beginans := a;ans.num[1] := ans.num[1] + 2;i := 1;While (i <= ans.len) AND (ans.num[i] >= 10) DoBeginans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10;ans.num[i] := ans.num[i] MOD 10;Inc(i);End;If ans.num[ans.len + 1] > 0Then⑤ ;plustwo := ans;End;Function over(a, b : hugeint) : Boolean;// 若大整数 a > b 则返回 1, 否则返回 0Vari : Integer;BeginIf ( ⑥ ) ThenBeginover := FALSE;Exit;End;If a.len > b.len ThenBeginover := TRUE;Exit;End;For i := a.len DownTo 1 DoBeginIf a.num[i] < b.num[i] ThenBeginover := FALSE;Exit;End;If a.num[i] > b.num[i] ThenBeginover := TRUE;Exit;End;End;over := FALSE;End;BeginReadln(s);FillChar(target.num, SizeOf(target.num), 0);target.len := Length(s);For i := 1 To target.len Dotarget.num[i] := Ord(s[target.len - i + 1]) - ⑦;FillChar(left.num, SizeOf(left.num), 0);left.len := 1;left.num[1] := 1;right := target;Repeatmiddle := average(left, right);If over( ⑧ )Then right := middleElse left := middle;Until over(plustwo(left), right);For i := left.len DownTo 1 DoWrite(left.num[i]);Writeln;End.第十六届（2010年）全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题1.与16进制数 A1.2等值的10进制数是（）A.101.2 B.111.4 C.161.125 D.177.252.一个字节（byte）由（）个二进制组成。
