NOIP2010信息学奥赛初赛普及组模拟试题(二).doc

第 1 页 共 8 页 NOIP2010 初赛模拟试题（六）初赛模拟试题（六） （ 普及普及 Pascal 语言语言 二小时完成二小时完成 ） 全部试题答案均要求写在答卷纸上全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效写在试卷纸上一律无效 一一 单项选择题单项选择题 （共（共 20 题题,每题每题 1.5 分分,共计共计 30 分。每题有且仅有一个正确答案。分。每题有且仅有一个正确答案。 ） 1、.在所有由两个 1 和六个 0 组成的 8 位二进制整数（补码）中，最小的数是：（ ） A-127B-64C-128D-65 2、.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（ ） A都不相同B完全相同 C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同 3、下面有效的 IP 地址是：（ ） A202.280.130.45B5 C192.256.130.45D256 4、一台具有 1024*768 分辨率、可显示 65 536 种颜色的显示器，其显示适配器（显示卡） 上显示存储器容量的配置为：（ ） A512KB1MBC大于 1.6MB，小于 2MB D2MB 5、进行二分法查找，则线性表（ ） A必须顺序方式存储 B必须以链接方式存储，且数据元素已按值排好序 C必须以链接方式存储 D必须以顺序方式存储，且数据元素已按值排好序 6、机器语言是用（ ）编写的。 A二进制码BASCII 码C十六进制码D国标码 7、一棵含有 101 个结点的完全二叉树存储在数组 A1.101中,对 1k101,若 Ak是叶 子结点,则 k 的最小值是：（ ） A51B50C49D48 第 2 页 共 8 页 8、不同的计算机，其指令系统也不相同，这主要取决于 （ ） A. 所用的操作系统 B. 系统的总体结构 C. 所用的 CPU D. 所用的程序设计语言 9、计算机主机是由 CPU 与（ ）构成的。 A控制器 B。输入、输出设备 C运算器 D内存储器 10、计算机系统总线上传送的信号有（ ）。 A地址信号与控制信号 B数据信号、控制信号与地址信号 C控制信号与数据信号 D数据信号与地址信号 11、计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次 能处理的数据量叫字长。已知 64 位的奔腾处理器一次能处理 64 个信息位，相当于（ ） 字节。 A8 个 B1 个 C16 个 D2 个 12、某数列有 1000 个各不相同的单元，由低至高按序排列；現要对该数列進行二分法检索 （binary search），在最坏的情況下，需检视（ ）个单元。 A1000 B10 C100 D500 13、字符串aABaa的最长回文字串是（ ） AaAaa Baabaa Caa DB 14、在一棵具有 n 个结点的二叉树的第 i 层上，最多具有 （ ）个结点 (A)2i (B)2(i+1) (C)2(i-1) (D)2n 15、在一棵完全二叉树中，若编号为 i 的结点存在左儿子，则左儿子的编号是（ ） (A）2i (B）2i-1 (C）2i+1 (D)2i+2 16、链表不具有的特点是（ ） A） 可随机访问任一元素 B）插入删除不需要移动元素 C）不必事先估计存储空间 D）所需空间与线性表长度成正比 17、在以下各项中,（ ）不是操作系统软件。 A. Solaris B. Linux C. Sybase D. Windows Vista E. Symbian 18、微型计算机中,ALU 的基本功能是（ ）。 A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 存储各种控制信息 D. 获取外部信息 E. 存放程序和数据 19、设栈 S 的初始状态为空,元素 a,b,c,d,e,f 依次入栈 S,出栈的序列为 b,d,c,f,e,a,则栈 S 的容 量至少应该是（ ）。 A. 6 B. 5 C. 4 D. 3 E. 2 第 3 页 共 8 页 20、对有序数组5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100进行二分查找,等概率的情况下查找 成功的平均查找长度（平均比较次数）是（ ）。 A. 35/11 B. 34/11 C. 33/11 D. 32/11 E. 34/10 三问题求解（共三问题求解（共 2 题题,每空每空 5 分分,共计共计 10 分）分） 1用 1 个或多个互不相同的正整数之和表示 1511 之间的所有整数 至少要多少个不同的正整数_; 这些正整数是_ 2拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列，使得图中任意一对顶 点 u 和 v，若 E(G)，则 u 在线性序列中出现在 v 之前，这样的线性序列成为拓扑 序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为 。 四阅读程序写结果（共四阅读程序写结果（共 4 题题,每题每题 8 分分,共计共计 32 分）分） 1. program t1; var i,s,max:integer; a:array1.10 of integer; begin for i:=1 to 10 do read(ai); max:=a1;s:=a1; for i:= 2 to 10 do begin if smax then max:=s; end; writeln(max=,max) end. 3 2 1 5 4 7 6 8 9 第 4 页 共 8 页 输入:-2 13 -1 4 7 8 -1 -18 24 6 输出:max= 输入:8 9 -1 24 6 5 11 15 -28 9 输出:max= 1.program t2; const n=5; var i,j,k:integer; a:array1.2*n,1.2*n of integer; begin k:=1; for i:=1 to 2*n-1 do if i0 then begin write(i:4);s:=s+1;end; writeln; writeln(s=,s); readln(x); 第 6 页 共 8 页 writeln(gx) end. 输入: 10 20 65 10 输出: 五完善程序五完善程序 (前前 5 空空,每空每空 2 分分,后后 6 空空,每空每空 3 分分,共共 28 分分) 1【问题描述问题描述】 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。 同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制 点。因此称之为“马拦过河卒”。 棋盘用坐标表示，A 点(0, 0)、B 点(n, m)(n, m 为不超过 15 的整数)，同样马的位置坐标 是需要给出的。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定 不动的，并不是卒走一步马走一步。 【输入输入】 一行四个数据，分别表示 B 点坐标和马的坐标。 【输出输出】 一个数据，表示所有的路径条数。 【输入样例输入样例】 6 6 3 3 【输出样例】 6 const dx:array1.8 of integer=(-2,-1,1,2,2,1,-1,-2); dy:array1.8 of integer=(1,2,2,1,-1,-2,-2,-1); var n,m,x,y,i,j: byte; g:array0.20,0.20 of 0.1; c:longint; procedure sol(x,y:integer); var i:integer; begin if (x=n) and (y=m) then （1） else begin if (ym) and (gx,y+1=0) then （2） ; if (x=0) and (x+dxi=0) and (y+dyi=m) then （4） ; （5） ; writeln(c); end. 2. 【问题描述问题描述】 某乡有 n 个村庄(1n40)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程 s(0s1000)是已知的，且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率，他从商 店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为 1，他不知道选择什 么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 【输入输入】 村庄数 n 和各村之间的路程(均是整数)。 【输出输出】 最短的路程。 【样例样例】 salesman.in salesman.out 3 村庄数3 0 2 l 村庄 1 到各村的路程 1 0 2 村庄 2 到各村的路程 2 1 0 村庄 3 到各村的路程 var a:array1.40,1.40 of byte; n,i,j:byte; min ,m :longint; bj:array1.40 of boolean; procedure init; begin readln(n); for i:=1 to n do for j:=1 to n do （1） ; fillchar(bj,sizeof(bj),true); min:=99999999; m:=0; end; procedure road(step,line:byte); 第 8 页 共 8 页 var i,j,k:by