第十五届信息学奥赛普及组初赛试题(p)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“第十五届niop初赛试题”。
一.单项选择题（共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位带符号整数的二进制补码为
***1。其对应的十进制整数应该是：
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算法求最小生成树。则依次加 入最小生成树的顶点集合的顶点序列为：
V0，V1，V2，V3，V5，V4 V0，V1，V5，V4，V3，V3 V1，V2，V3，V0，V5，V4
V1，V2，V3，V0，V4，V5 答案（A）
10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息 和资源，请问全国信息学奥林匹克官方网站的网址是：
http://下面哪些说法是正确的： A）HTML全称超文本标记语言，实现了文本、图形、声音、乃至视频信息的统一编码。
B）HTML不单包含有网页内容信息的描述，同时也包含对网页格式信息的定义。
C）网页上的超链接只能指向外部的网络资源，本网站网页间的联系通过设置标签来实现。
D）点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符（URL）请求网络资源或者网络服务。
答案（BD）
6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}{1，0，1}{0，1，0}}，假定在具体存储中顶点依次为：v1，v2，v3 关于该图，下面的说法哪些是正确的：
A）该图是有向图。
B）该图是强联通的。
C）该图所有顶点的入度之和减所有顶点的出度之和等于1。
D）从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。
答案（ABD）
7、在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有了2个以上的结点。下面哪些说法是正确的：
A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：
p^.next:=clist^.next;clist^.next:=p;
B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：
p^.next:=clist;clist^.next:=p;
C）在头部删除一个结点的语句序列为：
p:=clist^.next;clist^.next:=clist^.next^.next;dispose(p);D）在尾部删除一个结点的语句序列为：
p:=clist;clist:=clist^.next;dispose(p);答案（AC）
8、散列表的地址区间为0-10，散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将关键字序列26，25，72，38，8，18，59存储到散列表中，这些元素存入散列表的顺序并不确定。假 定之前散列表为空，则元素59存放在散列表中的可能地址有：
A）5 B）7 C）9 D）10 答案（ABC）
9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪些排序算法是稳定的：
A）插入排序 B）基数排序 C）归并排序 D）冒泡排序
答案（ABCD）
10、在参加NOI系列竞赛过程中，下面哪些行为是被严格禁止的：
A）携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B）在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C）通过互联网搜索取得解题思路。
D）在提交的程序中启动多个进程以提高程序的执行效率。
三.、问题求解（共2题，每空5分，共计10分）
1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若∈E(G)，则u在线性序列 中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为__432____。
2、某个国家的钱币面值有1，7，7^2，7^3共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通____35__张钱币。
四、.阅读程序写结果（共4题，每题8分，共计32分）
1.var
a,b:integer;
function work(a,b:integer):integer;begin
if a mod b 0 then
work := work(b,a mod b)else
work := b;end;
begin read(a,b);
writeln(work(a,b));end.输入：123 321 输出：__3___
2.var
a,b:array[0..3]of integer;i,j,tmp:integer;begin
for i := 0 to 3 do
read(b[i]);for i := 0 to 3 do begin
a[i] := 0;
for j := 0 to i do
begin
inc(a[i],b[j]);
inc(b[a[i] mod 4],a[j]);
end;end;tmp:=1;
for i := 0 to 3 do begin
a[i] := a[i] mod 10;
b[i] := b[i] mod 10;
tmp := tmp *(a[i] + b[i]);end;
writeln(tmp);end.输入：2 3 5 7
输出：__5850____
3.const y = 2009;maxn = 50;var
n,i,j,s:longint;
c:array[0..maxn,0..maxn]of longint;begin s := 0;read(n);c[0,0] := 1;for i := 1 to n do
begin
c[i,0] := 1;
for j := 1 to i1 do
if a[i] = a[j] then
begin
p := i;
k := j;
break;
end;
if p 0 then
break;
b[i] := a[i] div m;
a[i+1] :=(a[i] mod m)* 10;
inc(i);until a[i] = 0
NOIP2009初赛普及组（PASCAL语言）参考答案与评分标准
一、单项选择题：（每题1.5分）
1.D
2.B
3.A
4.A
5.B
6.D
7.C
8.B
9.C
10.D
11.C
12.C
13.B
14.D
15.D
16.B
17.D
18.A
19.C
20.B
二、问题求解：（共2题，每空5分，共计10分）
1．70
2．5
三、阅读程序写结果（共4题，每题8分，共计32分）
1.4 2.416 3.782
4.NPOI
四．完善程序(前8空，每空3分，后2空，每空2分，共28分)
1.① 0
② tmp+a[i]=ans或者 a[i]+tmp=ans 或者ans=a[i]+tmp等
③
⑤ inc(tmp, a[i])或者tmp := tmp+a[i] 2.① 0
② inc(hash[i, j])或者 hash[i][j]:= hash[i][j]+1
③ work(x,y,tot+1)
④ dec(hash[i, j])或者 hash[i][j]:= hash[i][j]-1
⑤ work(0,0,0)
注意：② ④ 两空，不一定要+1 或者-1。也可以是④-1 , ② +1.也可以是 + k , 也可以-k, 甚至任何加标记的操作(如位运算)都可以，只要相互撤销。（所以答案非常多）。
