CSP-J 第一轮仿真测试卷2

你的姓名：

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

1.今有一空栈s,对下列待进栈的数据元素序列1,2,3,4,5,6,7,.....直进行进栈，进栈，出栈，进栈，进栈，进栈，出栈为一次的操作，那么在2019次操作后，S栈的栈顶元素为（） 。

2.对有序数组{5, 13，19, 21, 37, 56，64, 75，88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度(平均比较次数)是（）。

3.下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（）。

4.将(2,6,10, 17)分别储存到某个地址区间为0~10的哈希表中，如果哈希函数h(x)= （）, 将不会产生冲突.，其中a mod b表示a除以b的余数。

5.二分图是指能将定点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12个顶点的二分图至多有（） 条边。

6.有一个含有k个不同的数的数组S=<x1,x2,. ... .,xn>。在S中有这样一个数xi (1<i<n)使x1<x2<x3<. ... <xi-1<xi>xi+1>....>xn-1>xn ，则称这个数xi为数组S的“峰顶”，S就为单峰的。
下面有几行代码，请将a-e五处代码补全到算法之中，使得算法正确找到S的峰顶。
a. S[mid]<S[mid+1]      b.S[mid]>S[mid+1]
c. Search(1, mid-1)        d. Search(mid+1,k)
e.return S[mid]



正确的填空顺序是( )。

7.如果不在快速排序中引入随机化，有可能导致的后果是（）。

8.二进制数-1101010的补码是（）。

9.设二进制数x的值是11001101。若想通过x&y运算使x中的低度4位不变，高4位清零，则y的二进制数是（）

10.循环链表的主要优点是（）。

11.某算法计算时间表示为递推关系式: T(N)=N+T(N/2) , 则该算法时间复杂度为（）。

把7个相同苹果放入到4个相同的篮子里，允许有篮子空着不放，共有多少种放法？

13.6个顶点的连通图的最小生成树，其边数为（ ）

14. 若逻辑变量A、C为真，B为假，以下逻辑运算表达式为真的是（ ）

15.一张有9个节点的简单无向图最多有（）条边.

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

1. 本程序会把几行输入的句子的首字母输出（如果首字母是大写的话）。

如果输入不含大写字母，那么程序就会进入死循环。

把第10句的n++改成++n程序的输出结果一定和原来不同。

如果去掉第13行，程序依然能正常运行。

（2分）若输入的总字符数（包括空格）为50个，n最大是多少?

（2分）若输入的总字符数（包括空格）为50个，n最小是多少?

2.



判断题：

1)结果的数字个数为2n。

2)输入1时，结果为1。

选择题：

3)如果输入3，输出是（）。

4)如果输入5，输出的个数有（）

5)如果输入4时，输出结果的和是（）

6)如果输入2，输出（）

3.

如果i==0且s==0，那么函数的返回值为1。

i=n时的go函数的返回值一定大于等于i=n-1时的go函数的返回值。

如果m>1，且所有的a[i]都等于0，那么最终会输出（ ）。

如果n=1，且a[1]=m，那么输出（ ）。

本体的时间复杂度可以被优化为（ ）。

三、完善程序(单选题，每小题3分，共计15分)
1. (循环比赛日程表)设有N个选手进行循环比赛，其中N=2^M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次， 循环赛共进行N-1天，要求每天没有选手轮空。



1)①处应填（）

2)②处应填（）

3)③处应填（）

4)④处应填（）

5)⑤处应填（）

2.



判断题：

1)若将19行“(degree[b]++);"改为“( degree[a]++);"则运行结果不变。

2)该程序的时间复杂度是0(n)。

3)将代码删除11至15行，值不变。

4)若输入数据为:

则输出3。

选择题：

5)(4分)第5行定义的意义是（）

6)这个程序是用了（）