1843: 入门级 CSP-J第9套初赛模拟试题

一、单项选择题(共15题，每题2分，共计30分；每题有且仅有一个正确选项) 

 1.关于机器翻译，下列选项中正确的是(    )。

A.常见的翻译软件只有金山词霸、金山快译两种

B. 机器翻译的英文全称是Machine Translation,简称MT

C. 百度和谷歌不具有在线翻译功能

D.机器翻译是利用计算机把一种自然语言转变成另一种机器语言 

2.以补码存储的8位有符号整数10100011的十进制表示为(    )。

A.-93                         B.163                      C.-35                       D.-92

3.关于网络协议，下面说法中正确的是(    )。

A.Internet 网络协议采用TCP/IP 协议

B. 我们所说的TCP/IP  协议就是指传输控制协议

C.www浏览器使用的应用协议是 IPX/SPX

D. 没有网络协议，网络也能实现可靠地传输数据 

4.以下程序当执行完毕后，输出的值为(    )。

A.13                 B.21                 C.34                     D.55

5.下列关键字序列中，哪一项是堆(    )。

 A.16,72,31,23,94,53                                         B.94,23,31,72,16,53

C.16,53,23,94,31,72                                         D.16,23,53,31,94,72

6.对n 个不同的排序码进行冒泡排序，在下列哪种情祝下比较的次数最多(    )。

A.从小到大排列好的                  B. 从大到小排列好的

C. 元素无序                        D. 元素基本有序

7.n  为一个两位数，它的数码之和为a, 当 n 分别各乘以3、5、7、9以后得到4个乘积，如果每 一个积的数码之和都为 a, 那么这样的两位数 n 有(    )个。

A.3                                B.4                              C.5                              D.6

8.二叉树第10层的结点数的最大数目为(    )。

A.10                          B.100                        C.512                       D.1024

9.100以内最大的素数是(    )。

A.89                          B.97                         C.91                         D.93

10.15张卡片，每张卡片上写有3个不同的汉字，任意2张上的汉字不完全相同；任意6张 中，一定有2张，它们上面有共同的汉字。问：这15张卡片上最多有多少个不同的汉 字 ? (    )。

A.30                       B.45                        C.35                           D.180

11.仅由数字1,2,3组成的七位数中，相邻数字均不相同的七位数的个数是(    )。

A.128                       B.252                       C.343                          D.192

12.有甲、乙、丙、丁四支球队参加的足球循环赛，每两队都要赛一场，胜得3分，负者得0分，如果踢平，两队各得1分。现在甲、乙、丙分别得了7分、1分和6分，已知甲和乙踢平，那 么丁得(  ) 分 。

A.1                       B.3                         C.4                         D.7

13. 若一组记录的排序码为(46,79,56,38,40,84)则利用快速排序的方法，以第一个记录为 基准得到的一次划分结果为(   )。

A.38,40,46,56,79,84                                    B.40,38,46,79,56,84

C.40,3846,56,79,84                                      D.40,38,46,84,56,79

14. 一棵6节点二叉树的中序遍历为ABDGECF,先序遍历为DBACEGF,后序遍历为(   )。

A.DGBEFAC               B.ABGEFCD                C.GBEACFD               D.ABCDEFG

15.下面哪种图不一定是树(   )。

A.无回路的连通图                    B.有 n 个结点，n-1  条边的连通图

C. 每对结点间都有通路的图            D.连通但删去任意一条边则不连通的图

二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填T,错误填F;除特殊说明外，判断题1.5分，选择题3分，共计40分)

●判断题

(1)输出只能是正整数。(   )

(2)将03行的2e5 改为2e10输出结果不变。(   )

(3)将第09行删除，程序运行结果不会改变。(   )

(4)只要输入 int 数据类型的数据，输出结果就是正确的。(   ) 

●选择题

(5)如输入的531234524,则输出的结果为(   )。

A.6                        B.9                             C.12                           D.15

(6)本题涉及下列哪一项的数据范围偏小(   )。

A.a[N]                   B.s[N]                        C.m                            D.以上都不对

●判断题：

(1)上述代码中，将第13行修改为INF=1<<40, 输出结果一定不变。(   )

(2)上述代码中，将第23行修改为break或 continue 这两种情况后，相同的输入，在这两种 情况，输出结果也一定相同。(   )

(3)上述代码中，将第23行修改为break 后，相同的输入，变量c 的值和未修改前一定相 同。(   )

(4)上述代码中，将第23行修改为break后，相同的输入，输出结果也一定相同。(   )

●选择题：

(5)当输入为：8,输出为(   )。

A.17                       B.19\n over                C.19                          D.23\n over

(6)上述代码中，将第06行的i<n 修改为(   )后功能不变，效率更高。

A.i*i<=n                B.i<n/2                      C.i<n/3                       D.i<n/4

●判断题：

(1)若输入的序列是一个单调递增序列，则ans1 的值为1。(    )

(2)若输入的序列是一个单调递减序列，则ans2 的值为1。(    )

(3)对输入序列数据处理中，ansl  的值越大，ans2 的值将会越小。(    )

(4)输入的数值不能为负数。(    )

●选择题：

(5)若输入38920715530029917015865,输出第一个数为(   )。

A.3                          B.4                              C.5                              D.6

(6)若输入0- 10- 1,则输出(    )。

A.22                        B.41                            C.32                            D.23

三、完善程序(单选题，每题3分，共计30分)

1.(SPFA)   给定一个有n 个顶点(从1到n 编号) ,m条边的有向图(其中某些边权可能为负， 但保证没有负环)。请你计算从1号点到其他点的最短路。试补全程序。

(1)①处应填(   )。

A.1                                                               B.-1

C.h[t]                                                           D.t

(2)②处应填(    )。

A.i=0                       B.i>0                           C.i!=-1                         D.i>-1

(3)③处应填(   )。

A.dis[j]=dis[t]+w[t]                                    B.dis[j]=abs(dis[t]+w[i])

C.dis[j]=dis[t]+w[i]                                     D.dis[j]=dis[i]+w[i]

(4)④处应填(   )。

A.q.push(j)              B.q.push(i)                  C.q.push(st[j])             D.q.push(1)

(5)⑤处应填(   )。

A.spfa()                   B.add()                        C.add(a,b,c)                 D.spfa

2. (01背包)在网友的国度中共有 n 种不同面额的货币，第i 种货币的面额为 a[i],   你可以 假设每一种货币都有无穷多张。为了方便，我们把货币种数为n、面额数组为a[1..n]的 货币系统记作(n,a)。

在一个完善的货币系统中，每一个非负整数的金额x 都应该可以被表示出，即对每一 个非负整数 x, 都存在n 个非负整数t[i]  满足a[i]*t[i]的和为x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额x 不能被该货币系统表示出。例如在货币 系统 n=3,a=[2,5,9]中，金额1,3就无法被表示出来。

两个货币系统(n,a)   和(m,b)   是等价的，当且仅当对于任意非负整数x, 它要么均可 以被两个货币系统表示出，要么不能被其中任何一个表示出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统(m,b),满足(m,b) 与原来的货币系统(n,a)等价，且m 尽可能的小。他们希望你来协助完成这个艰巨的 任务：找到最小的m。

(1)①处应填(   )。

A.T                        B.T--                         C.1                             D.0

(2)②处应填(   )。

A.a[0]                    B.a[n-1]                     C.a[1]                        D.a[n]

(3)③处应填(   )。

A.-1                        B.0                             C.1                             D.n

(4)④处应填(   )。

A.f[j+a[i]]+1         B.f[a[i]]+1                 C.f[j-a[i]]                  D.f[j-a[i]]+1

(5)⑤处应填(   )。

A.f[a[i]]==1          B.f[a[i]]==0              C.f[a[i]]>1                D.f[a[i]]>2