第二十届全国青少年信息学奥林匹克联赛初赛；提高组Pascal语言试题；竞赛时间:日14:30～16；选手注意:；●试题纸共有10页，答题纸共有2页，满分100分；●不得使用任何电子设备(如计算器、手机、电子词典；一、单项选择题(共15题，每题1.5分，共计22；1.以下哪个是面向对象的高级语言()；A.汇编语言B.C++C.FORTRAN
第二十届全国青少年信息学奥林匹克联赛初赛
提高组Pascal语言试题
竞赛时间:日14:30～16:30
试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。
不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。
一、单项选择题(共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项)
1.以下哪个是面向对象的高级语言(
A. 汇编语言
C. FORTRAN D. Basic
2.1TB代表的字节数量是(
A. 2的10次方 B. 2的20次方 C. 2的30次方 D. 2的40次方
3. 二进制数010101的和是(
4. TCP协议属于哪一层协议(
D. 数据链路层
5. 下列几个32位IP地址中，书写错误的是(
A. 162.105.130.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.1
6. 在无向图中，所有顶点的度数之和是边数的(
7. 对长度为n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为(
B. (n+1)/2
C. (n-1)/2
8. 编译器的主要功能是(
A. 将一种高级语言翻译成另一种高级语言
B. 将源程序翻译成指令
C. 将低级语言翻译成高级语言
D. 将源程序重新组合
9. 二进制数111.101所对应的十进制数是(
10. 若有变量var a:integer；x，y:real；，且a:=7，x:=2.5，y:=4.7，则表达式x + a mod 3 * trunc(x + y) mod 2 div 4的值大约是(
A.2.500000 B.2.750000 C.3.500000 D.0.000000
11. 有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个连续结点。
node=record
p,q,r: data
现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是(
A. q^.next:=r^. p^.next:=r; r^.next:=q;
B. p^.next:=r; q^.next:=r^. r^.next:=q;
C. q^.next:=r^. r^.next:=q; p^.next:=r;
D. r^.next:=q; q^.next:=r^. p^.next:=r;
12. 同时查找2n个数中的最大值和最小值，最少比较次数为(
A. 3(n-2)/2
13. 设G是有6个结点的完全图要得到一棵生成树，需要从G中删去(
14. 以下时间复杂度不是O(n2)的排序方法是(
A. 插入排序
B. 归并排序
C. 冒泡排序
D. 选择排序
15. 以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S，输出S中第二小的数SecondMin。在最坏情况下，该算法需要做(
)次比较。 if S[1]&S[2] then
FirstMin:=S[1];
SecondMin:=S[2];
FirstMin:=S[2];
SecondMin:=S[1];
for i:=3 to n dO
if S[i]&SecondMin then
if S[i]&FirstMin then
SecondMin:=FirstM
FirstMin:=S[i];
SecondMin:=S[i];
二、不定项选择题(共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分)
1. 若逻辑变量A、C为真，B、D为假，以下逻辑运算表达式为真的有(
A. (B∨C∨D)∨D∧A
B. ((┐A∧B)∨C)∧┐B D. A∧(D∨┐C)∧B C. (A∧B)∨(C∧D)∨┐A)
)软件属于操作系统软件。
A. Microsoft Word
B. Windows XP
C. Android
3. 在NOI比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容
A. 试图访问网络
B. 打开或创建题目规定的输入/输出文件之外的其他文件
C. 运行其他程序
D. 改变文件系统的访问权限
E. 读写文件系统的管理信息
4. 以下哪些结构可以用来存储图(
A. 邻接矩阵 B. 栈
5. 下列各无符号十进制整数中，能用八位二进制表示的数有(
三、问题求解(共2题，每题5分，共计10分；每题全部答对得5分，没有部分分)
1. 由数字1，1，2，4，8，8所组成的不同的四位数的个数是________。
2. 如图所示，图中每条边上的数字表示该边的长度，则从A到E的最短距离是________。
四、阅读程序写结果(共4题，每题8分，共计32分)
a, b, i, tot, c1, c2:
readln(a,b);
for i:=a to b do
c1:=i div 10;
c2:=i mod 10;
if (c1+c2) mod 3=0 then
writeln(tot);
输出:________
function fun(n, minNum, maxNum : integer):
var tot, i:
if n=0 then
for i:=minNum to maxNum do
tot:=tot + fun(n-1, i+1, maxNum);
exit(tot);
readln(n, m);
writeln(fun(m, 1, n));
输出:________
dict:array[1..SIZE]
包含各类专业文献、应用写作文书、专业论文、行业资料、外语学习资料、高等教育、75NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)等内容。　
　NOIP2013全国青少年信息学奥林匹克联赛初赛参考答案(提高组PASCAL)_学科竞赛_高中教育_教育专区。NOIP2013全国青少年信息学奥林匹克联赛初赛参考答案(提高组PASCAL)第... 　NOIP2014提高组Pascal初赛试题.pdf_IT认证_资格考试/认证_教育专区。第二十届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2014 年 10 月 12... 　NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言... 　第十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)_法律资料_人文...第十届)提高组( 语言) NOIP2004 年(第十届)提高组(Pascal 语言)参考答案 ... 　NOIP2014(第二十届)初赛普及组C语言试题及答案_学科竞赛_初中教育_教育专区。NOIP2014初赛普及组C语言试题及答案; 第二十届全国青少年信息学奥林匹克联赛初赛普及组... 　NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组Pascal试题、整理打印版、答案第十九届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间:2013... 　届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)...16.在下列各软件中,属于 NOIP 竞赛(复赛)推荐使用... 　NOIP2013初赛提高组Pascal试题及答案_学科竞赛_高中教育_教育专区。NOIP2013初赛提高组Pascal试题及答案 完美word版第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pas... 　noip2014初赛普及组Pascal试题_学科竞赛_初中教育_教育专区。noip2014初赛普及组Pascal试题 第二十届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛...近十年的选择题_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
近十年的选择题
上传于|0|0|文档简介
&&noip近十年的选择题汇总
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩26页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢笔试题&面试题：给定n个数，要求比较次数1.5n同时找出最大值和最小值 - 推酷
笔试题&面试题：给定n个数，要求比较次数1.5n同时找出最大值和最小值
写出一个算法,对给定的n个数的序列,返回序列中的最大和最小的数.
设计出一个算法,只需要执行1.5n次比较就能找到序列中最大和最小的数吗？能否再少？
分析：要求比较次数为1.5n，使用一般的逐个遍历每个元素然后判断其是否为最大最小值是需要2n次的比较的，所以这样的方法是行不通的。现在考虑采用，每次从数组中取出两个元素，判断其大小，然后再分别判断其是否是最大或最小值，这样一次处理两个元素，每一次比较3次，最终的比较次数就是n/2*3=1.5n。C语言代码如下：
#include &stdio.h&
#define MIN -1
#define MAX 65535
void find_max_min(int num[], int len)
int max = MIN;
int min = MAX;
int count = 0; /*用来统计比较次数*/
j = len - 1;
while(i &= j)
if(num[i] & num[j])
tmax = num[j];
tmin = num[i];
tmax = num[i];
tmin = num[j];
if(min & tmin)
if(max & tmax)
count += 2; /*上面的两次比较*/
printf(&The max number is: %d.\n&, max);
printf(&The min number is: %d.\n&, min);
printf(&Compare number is: %d.\n&, count);
int main()
int num[10] = {2, 4, 5, 6, 8, 3, 7, 1, 9, 10};
find_max_min(num, 10);
程序运行结果截图：
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致7046人阅读
编程之美（9）
问题描述：给出一个数组，包含N个整数，那么需要比较多少次找到最大值和最小值
注意：要想得到最大值和最小值，遍历一遍数组是不可避免的。我们能减少的就是减少比较次数来提高效率
方法一、遍历一遍数组，同时得到最大值和最小值
具体是，定义一个max 和 min，每遍历一个数，就分别和max 和 min比较一次，直到处理完所有的数据
比较次数： N+N = 2N
方法二、我们可以把数组中的数据两两分组，分组内找出最大值 和 最小值，之后在最大值的那部分找出最大值，在最小值那部分找出最小值
比较次数：
两两比较，较小值放到左边，较大放右边，这时比较N/2次
之后，得到的最大值部分是 N/2个数，最小值部分是N/2个数
之后在 最大值部分 取出最大值。比较次数N/2
& &在 最小值部分 取出最小值。比较次数N/2
比较次数：1.5N
评价：虽然比较次数下降了，但是破坏了原数组，而且由于在比较过程中有数据的交换，效率还是会拖累的。
方法三、引入俩变量min 和 max，每次也是处理两个数据，直到所有的数据全部都处理完
具体思路：
引入两个变量Min 和 Max
取出两个数，比较一次，得出最大值和最小值
最大值和Max比较，最小值和Min比较，如果比最值还要大或小，则进行更新
比较次数：每处理两个数，比较3次，则N/2 *3 = 1.5N次
优点，不会破坏原数组，较好
方法四、使用分治算法，其实和方法三是一样的，分治是一直到两个数的时候才做，且做完了 把结果合并下就好
思路：在N个数中求最大值和最小值，我们只需求出前后N/2个数的Min和Max，然后取较小的Min，较大的Max即可
比较次数：和方法三一样，比较次数没有变化
f(2) = 1;&
f(n) = 2*f(n/2) + 2;&
&第2个2的意思是：递归分成的两部分求出最值后，还有结合下求出一个整体的最值，这时要有两次比较&
可以推出f(n) = 1.5*n -2; &可见总的比较次数仍然没有减少。
找出N个数组中第二大的数，需要比较多少次呢？
是否可以通过类似的分治思想来降低比较次数呢？
方法一、比较笨的方法
先找到本数组中的最大数X，需要n-1次比较，再在剩下的数组中去找最大数X’,需要n-2次比较
则X’就是第二大的数，这需要(n-1) + (n-2)次比较
方法二、我们也可以在数组中，两数结合，分别求出最大值 和 次大值，之后每两个数结合求出的最值 在相互比较，得到最值得最大值 和 次大值
具体思路：
把数组中的每两个元素分为一组，每组中的最大数为F，第二大数为S。
假设相邻两组的最大数和第二大数分别是:Fi,Si 和Fj,Sj,。
则这两组合并为一组后，其中最大数和第二大数可能是：
1、若Fi&& Fj，则最大数是Fi；
& & &若Si &Fj，则第二大数是Si；否则，第二大数是Fj
2、若Fi& Fj，则最大数是Fj
& & &若Fi&Sj，则第二大数是Fi；否则，第二大数是Sj
比较次数：共有N/2组，每组需要比较倆次得出本组的最大数和第二大数；共需比较N/2 * 2次。
方法三、分治法
思路：和上面的思路是一样的
把数组分成两部分，其最大数和第二大数分别是:Fi，Si，Fj，Sj。合并时的情况可能为：
1、Fi & Fj，最大数是Fi；若Si&Fj，则第二大数是Si，否则第二大数是Fj；
2、Fi & Fj，最大数是Fj；若Fi&Sj，则第二大数Fi，否则第二大数是Sj。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：522726次
积分：7015
积分：7015
排名：第2685名
原创：207篇
转载：55篇
评论：203条
Java学习中，求交流，进步。
(10)(1)(7)(18)(32)(45)(29)(13)(1)(5)(7)(14)(14)(5)(1)(2)(3)(8)(2)(29)(16)NOIP2014提高组Pascal初赛试题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
NOIP2014提高组Pascal初赛试题
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢
高中精品题库
最新高考模拟题
名校精品试卷}