一, 单项选择题
- 1 B
- 1 1 0 0 1 1 0
- - 1 0 1 1 0 0 1
- ------------------------
- = 0 0 0 1 1 0 1
- 2 B
- 48 + 9 = 57
- 3 C
- 8G = 8 * 1024 M
8 * 1024 / 2 = 4096 张
注意, 题目说的是 "大约", 不要求精确.
4 C
摩尔定律是由英特尔 (Intel) 创始人之一戈登. 摩尔 (Gordon Moore) 提出来的. 其内容为: 当价格不变时, 集成电路上可容纳的元器件的数目, 约每隔 18-24 个月便会增加一倍, 性能也将提升一倍. 换言之, 每一美元所能买到的电脑性能, 将每隔 18-24 个月翻一倍以上. 这一定律揭示了信息技术进步的速度.
1965 年 4 月 19 日,《电子学》杂志 (Electronics Magazine) 第 114 页发表了摩尔 (时任仙童半导体公司工程师) 撰写的文章〈让集成电路填满更多的组件〉, 文中预言半导体芯片上集成的晶体管和电阻数量将每年增加一倍.
1975 年, 摩尔在 IEEE 国际电子组件大会上提交了一篇论文, 根据当时的实际情况对摩尔定律进行了修正, 把 "每年增加一倍" 改为 "每两年增加一倍", 而普遍流行的说法是 "每 18 个月增加一倍". 但 1997 年 9 月, 摩尔在接受一次采访时声明, 他从来没有说过 "每 18 个月增加一倍", 而且 SEMATECH 路线图跟随 24 个月的周期.
5 B
每对顶点之间都恰巧有一条边:
对于两个顶点来说, 边数 C(2, 2) = 1;
对于三个顶点来说, 边数 C(3, 2) = 3;
对于四个顶点来说, 边数 C(4, 2) = 6;
对于七个顶点来说, 边数 C(7, 2) = 21.
6 D
CPU 包括运算逻辑部件, 寄存器部件和控制部件等
(1)运算逻辑部件
英文 Logic components; 运算逻辑部件, 也叫运算器. 可以执行定点或浮点算术运算操作, 移位操作以及逻辑操作, 也可执行地址运算和转换.
(2)寄存器
寄存器部件, 包括寄存器, 专用寄存器和控制寄存器. 通用寄存器又可分定点数和浮点数两类, 它们用来保存指令执行过程中临时存放的寄存器操作数和中间 (或最终) 的操作结果. 通用寄存器是中央处理器的重要部件之一.
(3)控制部件
英文 Control unit ; 控制部件, 主要是负责对指令译码, 并且发出为完成每条指令所要执行的各个操作的控制信号.
其结构有两种: 一种是以微存储为核心的微程序控制方式; 一种是以逻辑硬布线结构为主的控制方式.
微存储中保持微码, 每一个微码对应于一个最基本的微操作, 又称微指令; 各条指令是由不同序列的微码组成, 这种微码序列构成微程序. 中央处理器在对指令译码以后, 即发出一定时序的控制信号, 按给定序列的顺序以微周期为节拍执行由这些微码确定的若干个微操作, 即可完成某条指令的执行.
简单指令是由 ( 3 ~ 5 ) 个微操作组成, 复杂指令则要由几十个微操作甚至几百个微操作组成.
7 B
完全二叉树的深度最小.
一层可以容纳 1 个节点; 1 = 21 - 1
两层可以容纳 3 个节点; 3 = 22 - 1
三层可以容纳 7 个节点; 7 = 23 - 1
十层可以容纳 1023 个节点; 1023 = 210 - 1
十一层可以容纳 2047 个节点; 2047 = 211 - 1
8 B
先比较后插入, 是插入排序. 具体可参考《大话数据结构》9.5 节.
9 C
三位二进制数, 可以写成一位八进制数.
四位二进制数, 可以写成一位十六进制数.
例 1: 二进制的 10100001 = 十六进制的 a1 = 十进制的 161
例 2: 二进制的 01111000 = 十六进制的 78 = 十进制的 120
例 3: 二进制的 11111111 = 十六进制的 ff = 十进制的 255
10 C
将回收站清空后, 肉眼看不见文件了. 但是对于操作系统来说, 只是将这件文件占用的硬盘空间标记为 "删除", 并且让肉眼不可见而已.
只有等这块硬盘空间被别的文件占用时, 原先的文件才被新数据所覆盖, 此时原先的文件才无法再恢复.
11 B
深度优先遍历, 不需要额外的数据结构, 递归即可.
广度优先遍历, 需要使用队列做辅助. 每个队首元素出队时, 需要把下一层的顶点入队. 入队或出队的顺序, 即是遍历的顺序.
具体可参考: https://www.jianshu.com/p/ded75497a056
12 A
时间复杂度指的是运行次数, 空间复杂度指的是占用内存大小.
13 C
双向链表只是查找前驱节点方便而已. 假如链表长度为 n, 待查找的节点在链表的尾部, 和单向链表一样要查 n 次才能查到.
14 C
ATM 自动取款机密码跟生物特征没有关系.
15 C
哈夫曼编码, 也叫赫夫曼编码.
哈夫曼编码的方法是将权重最小的两个结点构成一棵树, 树的根结点的权重即为这两个结点之和. 如此类推.
1-15.PNG
如上图所示, 最小的节点是 "也", 权重值 200, 第二小的节点是 "者", 权重值 300, 所以先将这两个节点构造成一棵树, 根结点为 N1, 权重值为 200 + 300 = 500.
构造出节点 N1 后, 忽略掉 "也" 和 "者" 两个节点. 在 N1,"乎" 和 "之" 三个节点中, 最小的节点是 N1, 权重值为 500, 第二小的节点为 "乎", 权重值为 600, 将这两个节点构成一棵二叉树, 根结点为 N2, 权重值为 500 + 600 = 1100.
构造出节点 N2 后, 忽略掉 N1 和 "乎" 两个节点, 剩余 N2 和 "之" 两个节点. 将这两个节点构造成一棵树, 要节点为 N3, 权重值为 700 + 1100 = 1800.
因为已经没有其他的结点了, 所以哈夫曼树已经构造完成. 从 N3 节点到 "也" 节点, 需要经过三段路径, 即编码长度是 3.
16 D
"完全淘汰" 说得太绝对了. 在系统级的程序里还会被少量使用到.
17 A
回溯法 (探索与回溯法) 是一种选优搜索法, 又称为试探法, 按选优条件向前搜索, 以达到目标. 但当探索到某一步时, 发现原先选择并不优或达不到目标, 就退回一步重新选择, 这种走不通就退回再走的技术为回溯法, 而满足回溯条件的某个状态的点称为 "回溯点".
回溯法与穷举法有某些联系, 它们都是基于试探的. 穷举法要将一个解的各个部分全部生成后, 才检查是否满足条件, 若不满足, 则直接放弃该完整解, 然后再尝试另一个可能的完整解, 它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程. 而对于回溯法, 一个解的各个部分是逐步生成的, 当发现当前生成的某部分不满足约束条件时, 就放弃该步所做的工作, 退到上一步进行新的尝试, 而不是放弃整个解重来.
八皇后问题, 是回溯算法的典型案例. 具体可参考:
- https://www.jianshu.com/p/797b2499b9f4
- 18 A
诺贝尔有五大奖项: 物理, 化学, 生物与医疗, 文学, 和平, 经济.
图灵奖是计算机的最高奖.
艾伦. 麦席森. 图灵(Alan Mathison Turing,1912 年 6 月 23 日 - 1954 年 6 月 7 日), 英国数学家, 逻辑学家, 被称为计算机科学之父, 人工智能之父.
约翰. 冯. 诺依曼奖章 (英语: IEEE John von Neumann Medal) 由 IEEE 成立于于 1990 年, 目的是表扬在计算机科学和技术上具有杰出成就的科学家. 该奖项以对计算机科学具有重大贡献的现代计算机创始人之一约翰. 冯. 诺伊曼命名. 约翰. 冯. 诺依曼奖的影响力略逊于图灵奖.
冯. 诺伊曼 (1903~1957) 是一位全才, 参加过 "曼哈顿计划". 他在数学上的成就比计算机上的成就要高.
高德纳于 1995 年获得约翰. 冯. 诺依曼奖.
高德纳奖 (Donald E. Knuth Prize), 授予为计算机科学基础做出杰出贡献的人, 以计算机科学家高德纳(Donald E. Knuth) 命名.
高德纳奖始于 1996 年, 每 1.5 年颁发一次, 包括 5000 美元奖金. 现在奖项由 ACM 计算机理论研讨会和 IEEE 计算机科学基础研讨会交替颁发.
高德纳 (1938-) 是算法和程序设计技术的先驱者, 计算机排版系统 TEX 和 METAFONT 的发明者, 他因这些成就和大量创造性的影响深远的著作而誉满全球
华人计算机科学家姚期智 (1946-) 于 1996 年获得高德纳奖, 2000 年获得图灵奖.
19 A
1-19.PNG
1-2 之间的 a 线, 可以由 1-5 之间的 b 线和 5-2 之间的线来替代. 去掉 a 线后仍然强连通.
去掉 b 后, 1 无法到达 5.
去掉 c 后, 4 无法到达 1.
去掉 d 后, 3 无法到达 4.
20 C
冯. 诺依曼结构也称普林斯顿结构, 是一种将程序指令存储器和数据存储器合并在一起的存储器结构. 程序指令存储地址和数据存储地址指向同一个存储器的不同物理位置, 因此程序指令和数据的宽度相同, 如英特尔公司的 8086 中央处理器的程序指令和数据都是 16 位宽.
说到计算机的发展, 就不能不提到美国科学家冯. 诺依曼. 从 20 世纪初, 物理学和电子学科学家们就在争论制造可以进行数值计算的机器应该采用什么样的结构. 人们被十进制这个人类习惯的计数方法所困扰. 所以, 那时以研制模拟计算机的呼声更为响亮和有力. 20 世纪 30 年代中期, 美国科学家冯. 诺依曼大胆的提出: 抛弃十进制, 采用二进制作为数字计算机的数制基础. 同时, 他还说预先编制计算程序, 然后由计算机来按照人们事前制定的计算顺序来执行数值计算工作.
人们把冯. 诺依曼的这个理论称为冯. 诺依曼体系结构. 从 EDVAC 到当前最先进的计算机都采用的是冯诺依曼体系结构. 所以冯. 诺依曼是当之无愧的数字计算机之父.
人们把利用这种概念和原理设计的电子计算机系统统称为 "冯. 诺曼型结构" 计算机. 冯. 诺曼结构的处理器使用同一个存储器, 经由同一个总线传输.
来源: http://www.jianshu.com/p/499121938385