NOIP2017提高组初赛模拟题

1、第二十三届全国青少年信息学奥林匹克联赛初赛 提高组PASCAL语言模拟试题 竞赛时间：2017年10月14日14:3016:30 选手注意： 试题纸共有13页，答题纸共有 2页，满分100分。请在答题纸上作答 ，写 在试题纸上的一律无效。 不得使用任何电子设备 （如计算器、手机、电子词典等 ）或查阅任何书籍资料。 、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正 确选项） 1. 1956 年（ ）授予肖克利（William Shockley ）、巴丁（ John Bardeen ） 和布拉顿（Walter Brattain ），以表彰他们对半导体的研究和晶体管效应的发

2、现。 A 诺贝尔物理学奖B. 约翰冯诺依曼奖 C.图灵奖D.高德纳奖（Donald E. Knuth Prize ） 2.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、 字母键A、字母键S和字母键D的顺序来回按键，即CapsLock A、S、D、 S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、， 屏幕上输出的第81个字符是字母（）。 A . AB . SC . DD . A 3. 二进制数 00101100和01010101异或的结果是（） A . 00101000 B . 01111001 C . 01000100 D .

3、00111000 4.与二进制小数 0.1相等的八进进制数是（ )0 A . 0.8 B . 0.4 C . 0.2 D . 0.1 5. 以比较作为基本运算，在N个数中找最小数的最少运算次数为（） A . NB . N-1C . N2D . log N 6. 表达式a*（b+c）-d的后缀表达形式为（）。 A . abcd*+- B . abc+*d-C . abc*+d- D . -+*abcd 7. 一棵二叉树如右图所示，若采用二叉树链表存储该二叉 树（各个结点包括结点的数据、左孩子指针、右孩子指 针）。如果没有左孩子或者右孩子，则对应的为空指针 那么该链表中空指针的数目为 （）。 A.

4、 6B. 7C. 12 D . 14 1 8. G是一个非连通简单无向图，共有28条边，则该图至少有（）个顶点 A. 10B . 9C .8D .7 9. 某计算机的CPU和内存之间的地址总线宽度是32位（bit）,这台计算机 最多可以使用（）的内存。 A. 2GBB. 4GBC. 8GBD. 16GB 10无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络 协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最 恰当的是（）。 A.中国公司的经理与波兰公司的经理交互商业文件 策4层 中国公司经理 独兰公司经理 t 4 t + 皮兰公司舉理翹书 十1 牛1

5、 寢层 波兰公司翻译 f 1 中国爵逮员 波兰邮递员 B.军队发布命令 第4层 司令 4 第3层 军长1 1 1 第2层 师长1 师长 师长3 师底斗 1 第1层 团怪1团按 团3团长 团长5团长：6 团长:T团长 C.国际会议中，每个人都与他国地位对等的人直接进行会谈 第4展 英国汝壬 减- 瑞典国王 第3层 英国首相 瑞典首相 第2层 英園外交犬臣 瑞典外空大臣 第1层 英国左施芙土婆 坯蕤左英三丈性 D.体育比赛中，每一级比赛的优胜者晋级上一级比赛 第q层 奥运会 t 第3层 全运会 t 第2层 省运会 策1层 市运会 11. 有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法

6、 A . 7 B .8 C . 21 D . 3 7 12. Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们 之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表 不是朋友。这个社交网站的规则是：如果某人A向他（她）的朋友B分享了 某张照片，那么B就可以对该照片进行评论；如果B评论了该照片，那么他 （她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照 10 片进行评论(除非A也向他(她)分享了该照片)。现在Lucia已经上传了 一张照片，但是她不想让Jacob看见这张照片，那么她可以向以下朋友()分 享该照片。 A. Dana, Micha

7、el, EveB . Dana, Eve, Monica C . Michael, Eve, JacobD. Micheal, Peter, Monica 13. 周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切 菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜10分钟，然后切菜10 分钟，最后炒菜10分钟。那么做一道菜需要 30分钟。注意：两道不 同的菜 的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗， 也不能同时切。那么做完三道菜的最短时间需要()分钟。 A. 90B. 60C. 50D. 40 14. 假设某算法的计算时间表示为递推关系式 T(n) =

8、2T( -)+ . n 4 T(1) = 1 则算法的时间复杂度为()。 2 A.O(n)B. O(、n )C. O( . n logn)D. 0( n ) 15.给定含有n个不同的数的数组 L=。如果L中存在x i (1 i n )使 得x1 x2 . xi-1 xi+1 . xn，则称L是单峰的，并称xi是L的“峰 顶”。现在已知L是单峰的，请把a-c三行代码补全到算法中使得算法 正确 找到L的峰顶。 a. Search(k+1, n) b. Search(1, k-1) c. return Lk Search（1, n） 1. k qn/2 2. if Lk Lk-1 a nd Lk L

9、k+1 3. then 4. else if Lk Lk-1 a nd Lk Lk+1 5. then 6. else 正确的填空顺序是 （）。 A. c, a, bB. c, b, aC. a, b, cD. b, a, c 二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个 正确选项，多选或少选均不得分） 1.以下属于无线通信技术的有（）。 有水 果树 B. AB都打开，CD都关上 D. D打开，其他都关上 A.蓝牙B. WiFiC. GPRSD.以太网 2.可以将单个计算机接入到计算机网络中的网络接入通讯设备有（） A. 网卡 B. 光驱 C.鼠标 D. 显卡 3.下

10、列算法中运用分治思想的有（ ）。 A.快速排序 B.归并排序 C.冒泡排序 D.计数排序 4.下图表示一个果园灌溉系统，有A、B、C、D四个阀门，每个阀门可以打开 或 关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的 有（）。 A. B打开，其他都关上 C. A打开，其他都关上 5.参加NOI比赛，以下能带入考场的有（） D. 铅笔 A. 钢笔B.适量的衣服C. U盘 三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没 有部分分） 1. 在1和2015之间（包括1和2015在内）不能被4、5、6三个数任意一个 数整除的数有 。 2. 结点数为5的不同形态的二叉树

11、一共有 中。（结点数为2的二 叉树一共有2种：一种是根结点和左儿子，另一种是根结点和右儿子。） 四、阅读程序写结果（共4题，每题8分，共计32分） 1 . Co nst SIZE = 100; var n, i, sum, x : in teger; a : array1.SIZE of i nteger; begin readl n(n); fillchar(a, sizeof(a), 0); for i:= 1 to n do begin read(x); in c(ax); en d; i := 0; sum := 0; while sum (n div 2 + 1) do begin

12、in c(i); sum :=sum + ai; en d; writel n(i); end . 输入： 11 4 5 6 6 4 3 3 2 3 2 1 输岀： 2. var n : in teger; procedure f2(x, y : in teger); forward; procedure f1(x, y : in teger); begin if x ans the n ans := len; for i := 1 to n do if (not visitedi) and (ex, i -1) the n dfs(i, le n + ex, i); visitedx :=

13、false; end; begin read ln(n, m); for i := 1 to n do for j := 1 to n do eij := -1; for i := 1 to m do begin read ln(a, b, c); eab := c; eba := c; en d; for i := 1 to n do visitedi := false; ans := 0; for i := 1 to n do dfs(i, 0); write ln(an s); end. 输入： 4 6 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50 2 4 60

14、输岀： 4. con st SIZE = 10000; LENGTH = 10; var sum : longint; n, m, i, j : in teger; a : array1.SIZE, 1. LENGTH of i nteger; fun cti on h(u, v : in teger) : in teger; var an s, i : in teger; begin ans := 0; for i := 1 to n do if aui avi the n in c(a ns); h := ans; end; begin readl n(n); filichar(a, si

15、zeof(a), 0); m := 1; repeat i := 1; while (i n the n break; in c(m); ami :=1; for j := i + 1 to n do amj := am - 1j; un til false; sum :=0; for i := 1 to m do for j := 1 to m do sum := sum + h(i, j); write ln (sum); end. 输入：7 输岀： 五、完善程序(共2题，每题14分，共计28分) 1.(双子序列最大和)给定一个长度为n (3 n 1000)的整数序列，要求从 中选出两个连

16、续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个 最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序 列长度至少为1,且两个连续子序列之间至少间隔1个数。(第五空4分，其余2.5分) co nst MAXN = 1000; var n, i, ans, sum: longint; x: array 1.MAXN of lo ngint; lmax: array 1.MAXN of lo ngint; / lmaxi 为仅含xi及xi左侧整数的连续子序列的序列和中，最大的序列和rmax: ar ray 1.MAXN of lo ngi nt; / rma

17、xi 为仅含xi及xi右侧整数的连续子序列的序列和中，最大的序列和 begin read( n); fori := 1 to n do read(xi); lmax1 := x1; fori := 2 to n do if lmaxi - 1 = 0 then lmaxi := xi else lmaxi := lmaxi - 1 + xi; fori := 2 to n do if lmaxi lmaxi - 1 then lmaxi := lmaxi - 1; (1) fori := n -1 downto 1 do if rmaxi + 1 = 0 the n Else fori :=

18、n - 1 dow nto 1 do if rmaxi ans the n ans := sum; en d; write ln (a ns); en d. 2.(最短路径问题)无向连通图G有n个结点，依次编号为1,2,3,n。用邻接 矩阵的形式给出每条边的边长，要求输出以结点1为起点出发，到各结点的最短路径长 度。使用Dijkstra算法解决该问题：利用dist数组记录当前各结点与起点的已找到的 最短路径长度；每次从未扩展的结点中选取dist值最小的结点v进行扩展，更新与v相 邻的结点的dist值；不断进行上述操作直至所有结点均被扩展，此时dist数据中记录 的值即为各结点与起点的最短路径长度。(第五空2分，其余3分) con