填空：
1.
以下哪一种设备属于输出设备：（ D）
解析：计算
机基本知识：A,B,C属于输入设备，D是输出设备
2.
下列四个不同进制的数中，与其它三项数值上不相等的是（D ）。
解析：计算机储存单位：
PB>TB>GB>MB>KB>B>bit(位）
每相邻之间进率1024特殊的是B转bit进率是8。一字节=一B
4.
广域网的英文缩写是（B ）。
解析：网络常识，可以用排除法。
5.
中国计算机学会于（ B）年创办全国青少年计算机程序设计竞赛。
解析：必须要背过的，记住1984就行。
6.
如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、
字母键A、字母键 S、字母键D、字母键 F 的顺序循环按键，即 CapsLock、A、S、D、F、CapsLock、A、S、D、F、……，屏幕上输出的第 81 个字符是字母
（A ）。
解析：逻辑题，每四个为一组，每八个为一大组，81除2等余40余1保证是大写，余1说明是小组的第一个
7.
设根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何
子节点外，每一层上的所有结点都有 k 个子结点的树，共有（A ）个结点。
解析：
对于k叉树，每一层的节点数依次为1，k，k^2，k^3，k^4，k^h，根据等比数列公式
(kh+1-1)/(k-1)。
8.
以下排序算法中，不需要进行关键字比较操作的算法是（A ）。
解析：基数排序其实是桶排序，基础算法。
9.
给定一个含N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的
数，至少需要 N - 1 次比较操作。则最坏情况下，在该数组中同时找最大与
最小的数至少需要（A ）次比较操作。（⌈ ⌉表示向上取整，⌊ ⌋表示向下取整）
解析：
算法思路：选定数组第一个元素为最大值max和最小值min，对剩余的n-1个元素按照每两个元素进行分组，首先对每个分组里面的两个元素进行对比，得到当前分组中最大值temp_max和最小值temp_min，然后用最大值max与当前分组中最大值temp_max做对比，用最小值min与当前分组中最小值temp_min做对比，分别更新最大值max和最小值min,按照步长为2，向后推进，直到遍历完数组
比较次数=3*(n-1)/2，解释：每个分组两个元素进行对比，对比次数为n-1/2,得到n-1/2个最大值temp_max和最小值temp_min，再用最小值min与所有的temp_min，最大值max和所有的temp_max做对比得到最后的最大值和最小值，次数都为n-1/2,所以最后总的次数为3*（n-1)/2。
10.
下面的故事与（B ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座
山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里
有座庙，庙里有个老和尚给小和尚讲故事……’”
解析：这道题的故事是在自身中调用自身，所以是递归。
11.
由四个没有区别的点构成的简单无向连通图的个数是（A ）。
解析：用公式3*4/2就行
12.
设含有10 个元素的集合的全部子集数为 S，其中由 7 个元素组成的子集数为
T，则 T / S 的值为（B ）。
解析：
- 子集总数S为 2的10次方= 1024
- 7个元素集合数T为C（10,7）=10!/（3!7!）= 120
- T/S = 120/1024 = 15/128 13. 10000 以内，与 10000 互质的正整数有（ B）个。 a.2000 b.4000 c.6000 d.8000 解析：这是一个简单的容斥原理，首先如果一个数a与10000有大于1的公因数x，那么x必然可以被质因数分解为一些质数的乘积，也就是说只有当a和10000有至少一个相同的质因子的时候，他们之间才会有大于1的公因数。 之后，我们可以对10000分解质因数，分解出来只有2和5。与10000互质的数的个数=数的总数-不与10000互质的数的个数 再考虑1-10000有多少个数里面有2这个质因子，显然有10000/2=5000个（可以举几个例子如1-15,1-20来理解），以此类推，有10000/5=2000个数里面有5这个质因子。 但是答案并不是10000-2000-5000=3000，为什么？因为像10、20这样既有2这个质因子也有5这个质因子的数既被2统计到又被5统计到了。也就是有10这个因子的数被统计到了两次，加上这些数的个数10000/10=1000，就是最后的答案4000 14. C++： 1 2 3 4 5 6 7 8 9 10 intCountBit(intx) { intret = 0; while(x) { ret++; ___________; } returnret; } 则空格内要填入的语句是（ B）。 a.x := x shr 1或者 x >>= 1 b.x := x and (x - 1) 或 x &= x - 1 c.x := x or (x shr 1) 或 x |= x >> 1 d.x := x shl 1 或 x <<= 1 15. 下图中所使用的数据结构是（B ）。 a.哈希表 b.栈 c.队列 d.二叉树 题解：满足先进后出的都是栈
京公网安备 11010502036488号