CSPS初赛模拟题笔记（二）

　　CSP-S 2019 RP++！

　　众所周知，NOIP尸体尚热，亡魂未散，CCF开办了CSP-S 2019初赛模拟赛。

　　这是我瞎写的第二份试卷题解，顺便复习。（什么？第一份？好难的！）

单选题（1）某计算机的 CPU 和内存之间的地址总线宽度是 32 位（bit），这台计算机最多可以使用（　　）的内存。

A. 2GB　　B. 4GB　　C. 8GB　　D. 16GB

[解析]　32位(bit)，即$2^{30}$字节(byte)。

　　　　$1 GB=1024 MB=1024*1024 KB=1024*1024*1024 byte=2^{30} byte$

　　　　$32 bit=2^{30} byte=2^2*2^{30} byte=4GB$

[答案]　B

单选题（2）下面属于解释执行的程序设计语言是（　　）

A. C　　B. C++　　C. Pascal　　D. Python

[解析]　解释执行语言：Python，Javascript，C#，PHP，Basic，Vbscript……

　　　　编译执行语言：C，C++，Objective-C……

[答案]　D

单选题（3）二进制数 00101100 和 01010101 异或的结果是（　　）

A. 00101000

B. 01111001

C. 01000100

D. 00111000

[解析]　根据二进制异或“相同为1，不同为0”的规则，进行异或：

　　　　　　$00101100$

　　　　　　$01010101$

　　　　得：$01111001$

[答案]　B

单选题（4）与二进制小数0.1相等的八进制数是（　　）

A. 0.8　　B. 0.4　　C. 0.2　　D. 0.1

[解析]　由二进制的特点可知，$(0.1)_2=(0.5)_10=(0.4)_8$。

[答案]　B

单选题（5）设某算法的时间复杂度函数的递推方程是$T(n)=T(n-1)+n$（$n$为正整数）及$T(0)=1$，则该算法的时间复杂度为（　　）

A. $O(log n)$　　B. $O(n log n)$　　C. $O(n)$　　D. $O(n^2)$

[解析]　显然，$T(n)=T(n-1)+n$

　　　　　　　　　 $=n+(n-1)+(n-2)+……+1$

　　　　所以复杂度为$O(n^2)$

[答案]　D

单选（6）表达式$a*(b+c)-d$的后缀表达形式为（　　）

A. abcd*+-　　B. abc+*d-　　C. abc*+d-　　D. -+*abcd

[解析]　关于中缀表达式转后缀表达式的方法，我读过很多人的做法，几乎都需要用到栈，在初赛中这种步骤较为繁琐。

　　　　这里有一种不用栈的手算方法，比较简单，可以详见这篇dalao的博文：中缀表达式转后缀表达式

　　　　概括一下，方法就是：先按运算符优先级对每个式子加括号，然后将运算符移到它后面的括号后面就行了。

[答案]　C

单选（7）一棵二叉树如下图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）

A. 6　　B. 7　　C. 12　　D. 14

[解析]　这题我们只需要会数数外加认真作答就可以答对。图中有3个点没有儿子，有1个点只有1个儿子。所以空指针数目：$3*2+1*1=7$。

[答案]　B

单选题（8）以比较作为基本运算，在$N$个数中找最小数的最少运算次数为（　　）

A. $N$　　B. $N^2$　　C. $N-1$　　D. $log N$

[解析]　众所周知，要找$N$个数的最小数，是必须得遍历一遍这$N$个数的（否则拿异能感应最小数吗）。

　　　　而此题“以比较作为基本运算”，找最小数只需要比较$N-1$次，因为自己和自己不必比较。

[答案]　C

单选题（9）在有$n$个子叶节点的哈夫曼树中，其节点总数为（　　）

A. $2^{n-1}$　　B. $2n-1$　　C. $2n+1$　　D. $2n$

[解析]　哈夫曼树是一种特殊树形（是二叉树，至少可以看得出来，本题出题人希望我们认为这是一种二叉树），这种树只存在出度为$0$或$2$的节点。

　　　　可以长这样，也可以长成其他模样：

　　　　很显然，叶子节点为$n$，即为出度为$0$的节点数为$n$，根据哈夫曼树的特性，可以知道出度为$1$的节点数为$n-1$。所以总数为$2n-1$

[答案]　B

单选题（10）G是一个非连通简单无向图，共有28条边，则该图至少有（　　）个顶点。

A. 10　　B. 9　　C. 8　　D. 7

[解析]　因为题目要求求最少顶点数，而完全连通图顶点最少，所以先假设28条边构成一个完全连通图。

　　　　设该完全连通图顶点数为$n$。${n*(n-1)}/{2}=28$，解之得，$n=8$。

　　　　又因为这是“非联通简单无向图”，所以再加一个游离在外的点，则该图至少有$9$个顶点。

[答案]　B

(未完待续……甚至不知道什么时候能续)