CSP-J 练习D卷

基本信息：

姓名：
姓名：
班级：
班级：

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

1. 在编程的时候，使用一个4个字节的数据类型定义了1024×2048=2097152个变量，请问大致使用了多少内存？ ( )。

A. 1MB

B. 2MB

C. 4MB

D. 8MB

2. 2 个 10 进制数 1111 和 1010 的与运算结果的 10 进制表示是 ( )。

A. 82

B. 56

C. 100

D. 1111

3. 假设A=true，B=false，C=true，以下为真的是 ( )。

A. A^B^C

B. A^(B^C)

C. A&B&C

D. A&(B^C)

4. 下列排序算法中，哪种排序算法是稳定的( )。

A. 选择排序

B. 冒泡排序

C. 堆排序

D. 快速排序

5. 甲箱中有 200 个螺杆,其中有 160 个 A 型螺杆;乙箱中有 240 个螺母,其中有 180 个 A型的。现从甲乙两箱中各任取一个，则能配成 A 型螺栓的概率为多少 ( )。

A. 3/5

B. 15/16

C. 1/20

D. 19/20

6. 已知有序表(13,18,24,35,47,50,62,83 ,90,115,134)，当折半查找值为 90 的元素时,查找成功的比较次数为( )。

A.2

B.3

C.4

D.5

7. 一棵完全二叉树,共有 1234 个节点，其叶子结点的个数为()。

A.615

B.616

C.617

D.210

8. 已知一棵二叉树前序遍历为 ABCDEFGI,后序遍历为 CEDBIGFA,则其中序遍历可能为( )。

A. ABCDEFGI

B. CBDEAGFI

C. CBEDAIFG

D. CBEDAFIG

9. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的( )。

A. 3 4 6 5 2 1

B. 5 4 3 6 1 2

C. 4 5 3 1 2 6

D. 2 3 4 1 5 6

10. 链表和数组的区别包括( )。

A. 数组不能排序，链表可以

B. 数组大小固定，链表大小可动态调整

C. 链表比数组能存储更多的信息

D. 以上均正确

11. 对表达式a+(b-c)*d的前缀表达式为（），其中+、-、*是运算符。

A. *+a-bcd

B. +a*-bcd

C. abc-d*+

D. abc-+d

12. 十进制小数 8.125 对应的二进制数是( )。

A. 1000.001

B. 1001.010

C. 1001.0111

D. 1101.011

13. 考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在( )。

A. N

B. N+1

C. N^2

D. N-1

14. int类型变量占用( )个比特位。

A. 1

B. 4

C. 8

D. 32

15. 以下哪组操作能完成在双向循环链表结点p之后插入结点s的效果（其中，next域为结点的直接后继，prev域为结点的直接前驱）()。

A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;

B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;

C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;

D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

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

16. (1 分)如果输入的数大于等于10^100，会出现数组越界的情况。 ( )

对

错

17. (1 分) 如果输入一个long long范围以内的数字，那么输出的数字相当于将输入的数字翻转后输出。 ( )

对

错

18. 将第7行“while(x)”改成“while(x>0)”，并在第11行之前加上一句“x=0;”，程序运行的结果不会改变。 ( )

对

错

19. 假设输入的数字在long long范围以内，如果输出的数字为0，那么输入的数字只能是0。( )

对

错

20. (3 分) 若输出的数字为“998244353”，则下列说法正确的是()

A. 输入可以是99824435300

B. 输入可以是3534428991

C. 输入可以是3534428990000

D. 输入只能是353442899

21. 若输入的数字为-1234567 ，则输出的结果是 ( )。

A.-7654321

B.7654321

C.1234567

D.-1234567

程序二

22. 不管输入什么值,程序的输出值一定比输入值大。( )

对

错

23. 若输入 n 是一个质数，则输出值 result 也可能是一个质数。( )

对

错

24. 若输入 n 是一个质数,程序执行到第 29 行时，i 的值等于刚开始输入的 n。 ( )

对

错

25. 若输入 n 的值等于正整数 c 的正整数 d 次方 c^d(c,d>=2),程序的第 15 行循环执行完成后,m 的值为 1,a[1]的值为 c。 ( )

对

错

26. 若输入 n=2400,则输出 result 为( )

A. 1200

B. 640

C. 2400

D. 960

27. 若输出 result=2400,则输入 n 可能为

A. 3200

B. 9000

C. 6400

D. 7200

程序三

28. 若输入的N的大小为10^6，会发生数组越界的情况。 ( )

对

错

29. 假设输入的N是不超过10^5的正整数，输入的a[i].val都是int范围以内的正整数。输出N时，N一定大于sum。 ( )

对

错

30. 假设输入的N是不超过10^5的正整数，输入的a[i].val都是int范围以内的正整数。输出的ans值一定是小于n值的。 ( )

对

错

31. 该程序最后可以建立一棵二叉树。 ( )

对

错

32. 输入的a[i].val都是int范围以内的正整数。若输入的N的值等于10^5，输入的a[1].val=1，输入的a[i].val(1≤i≤N-1)等于a[1].val+a[2].val+......+a[i–1].val，则输出的ans值等于 ()

A.10^5

B.10^5 - 1

C.2 * 10^5

D. 2 * 10^5 - 1

33. 假定内存空间无限大的时候，如果将第7行的maxn改成maxn=2e9，现在第一行输入536870912(=2^29)，第二行输入536870912个1，最后输出的ans值等于

A.29

B. 536870912

C.30

D. 536870911

三、完善程序
1. (有序数组合并)给出正整数 n,m与两个有序数组a,b(从小到大排序)请输出将合并后的结果。
例如:输入 n=3,m=5,a=[1,3,5],b=[2,4,6,8,10],程序应该输出 1 2 3 4 5 6 8 10，表示两个数组合并后的数组。
输入保证 1<=n,m<=100000。
试补全程序

34. ①处应填( )

A. n

B. j

C. i

D.m

35. ②处应填( )

A. n

B. j

C. i

D. m

36. ③处应填( )

A.＜

B.>

C.==

D.!=

37. ④处应填( )

A.while(l ＜= n)

B. while(l ＜ n)

C. while(l ＜= m)

D. while(l ＜ n)

38. ⑤处应填( )

A.n

B.cnt

C.m

D.l

2.(遍历树) 请完善下面的程序，使用 DFS统计从树根到每个点的距离，1为根节点，输入n表示树有n个结点，接下来n-1行输入树上的边与边权。

39. 上述程序 ①中应该填写()

A.x;

B.i

C.fa;

D.p[x].size();

40. 上述程序 ②中应该填写()

A. v == x

B. v == 0

C. v == fa

D. v != 0

41. 上述程序 ③ 中应该填写()

A. dis[x]

B. dis[fa] + dis[x]

C. dis[x] + p[x][i].val

D.dis[fa] + p[x][i].val

42. 上述程序 ④ 中应该填写()

A．p[v].push_back(node{u,w})

B.p[v].insert(node{u,w})

C.p[v][u]=w

D.p[v].push(node{u,w})

43. 上述程序 ⑤中应该填写()

A. n

B. 1

C. n - 1

D. 0