2012年408真题答案解析
一、单项选择题
1．  B  2．  A  3．  A  4．  B  5．  C  6．  C  7．  C  8．  A  9．  D  10．  A  11．  D  12．  D  13．  B  14．  D  15．  D  16．  A  17．  C  18．  C  19．  C  20．  D  21．  D  22．  B  23．  C  24．  B  25．  B  26．  A  27．  D  28．  A  29．  B  30．  C  31．  A  32．  B  33．  B
34．  C
英语四级查询网站35．  A
36．  B
37．  C
38．  A
39．  D
40．  D
1.【参考答案】B 【解析】考查时间复杂度的计算。该程序中使用了递归运算。本题中递归的边界条件是n<=1，每调用一次fact()，传入该层fact()的参数值减1（注意不是n 减1），因此执行频率最高的语句是return n*fact(n-1)，一共执行了n-1次，而每一层fact(i)运算只包含一次乘法。如果采用递归式来表示时间复杂度，则：
(1)1()(n 1)1
1
O n T n T n ≤
=
−+>  时间复杂度为O(n)。 2.【参考答案】A
【解析】考查栈的应用、表达式求值。表达式求值是栈的典型应用。通常涉及中缀表达式和后缀表达式。中缀表达式不仅依赖运算符的优先级，还要处理括号。后缀表达式的运算符在表达式的后面且没有括号，其形式已经包含了运算符的优先级。所以从中缀表达式转换到后缀表达式需要用运算符栈对中缀表达式进行处理，使其包含运算法优先级的信息，从而转换为后缀表达式的形式。转换过程如下表：
运算符栈  中缀未处理部分 后缀生成部分 #  a+b-a*((c+d)/e-f)+g  #  +b-a*((c+d)/e-f)+g    a  +  b-a*((c+d)/e-f)+g    a  +  -a*((c+d)/e-f)+g  ab  -  a*((c+d)/e-f)+g  ab+  -  *((c+d)/e-f)+g  ab+a  -*  ((c+d)/e-f)+g  ab+a  -*((  c+d)/e-f)+g  ab+a  -*((  +d)/e-f)+g  ab+ac  -*((+  d)/e-f)+g  ab+ac  -*((+  )/e-f)+g  ab+acd  -*(
/e-f)+g
ab+acd+
-*(/ e-f)+g ab+acd+
-*(/ -f)+g ab+acd+e
-*(- f)+g ab+acd+e/
-*(- )+g ab+acd+e/f国家职业技能鉴定中心
-* +g ab+acd+e/f-
- +g ab+acd+e/f-*
国考职位表2022时间
# +g ab+acd+e/f-*-
+ g ab+acd+e/f-*-
# ab+acd+e/f-*-g
可知，栈中的操作符的最大个数为5。
3.【参考答案】A
【解析】考查树的遍历、及由遍历序列确定二叉树的树形。前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为XY与后序序列为YX时，则X为Y的祖先。考虑前序序列a,e,b,d,c、后序序列b,c,d,e,a，可知a为根结点，e为a的孩子结点；此外，a的孩子结点的前序序列e,b,d,c、后序序列b,c,d,e，可知e是bcd的祖先，故根结点的孩子结点只有e。本题答案为A。
【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。
显然选A，最终得到的二叉树满足题设中前序序列和后序序列的要求。
4.【参考答案】B
【解析】考查平衡二叉树的最少结点情况。所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况，如图所示。画图时，先画出T1和T2；然后新建一个根结点，连接T2、T1构成T3；新建一个根结点，连接T3、T2构成T4；……依此类推，直到画出T6，可知T6的结点数为20。对于高度为N的题述的平衡二叉树，它的左、右子树分别为高度为N-1和N-2的所有非叶结点的平衡因子均为1的平衡二叉树。二叉树的结点总数公式为：C N=C N-1+C N-+1，C2=2，C3=4，递推可得C6=20。
2
【排除法】对于选项A ，高度为6、结点数为10的树怎么也无法达到平衡。对于选项C ，结点较多时，考虑较极端情形，即第6层只有最左叶子的完全二叉树刚好有32个结点，虽然满足平衡的条件，但显然再删去部分结点，依然不影响平衡，不是最少结点的情况。同理D 错误。只可能选B 。 5.【参考答案】C
【解析】考查不同存储结构的图遍历算法的时间复杂度。广度优先遍历需要借助队列实现。邻接表的结构包括：顶点表；边表（有向图为出边表）。当采用邻接表存储方式时，在对图进行广度优先遍历时每个顶点均需入队一次（顶点表遍历），故时间复杂度为O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历），故时间复杂度为O(e)，算法总的时间复杂度为O(n+e)。 6.
【参考答案】C
【解析】考查拓扑排序、与存储结构和图性质的关系。对角线以下元素均为零，表明该有向图是一个无环图，因此一定存在拓扑序列。对于拓扑序列是否唯一，我们试举一例：设有向图的邻接矩阵
000000110，则存在两个拓扑序列。所以该图存在可能不唯一的拓扑排序。
结论：对于任一有向图，如果它的邻接矩阵中对角线以下（或以上）的元素均为零，则存在拓
扑序列（可能不唯一）。反正，若图存在拓扑序列，却不一定能满足邻接矩阵中主对角线以下的元素均为零，但是可以通过适当地调整结点编号，使其邻接矩阵满足前述性质。 7.【参考答案】C
【解析】考查Dijkstra 算法求最短路径。 从a 到各顶点的最短路径的求解过程：
顶点 第1趟 第2趟
第3趟
2024年国考报名时间及条件表第
4趟
对5 趟
b (a,b) 2
c (a,c) 5 (a,b,c) 3
d ∞ (a,b,d) 5
(a,b,d) 5 (a,b,d) 5
f ∞ ∞ (a,b,c,f) 4  e ∞ ∞ (a,b,c,e) 7 (a,b,c,e) 7 (a,b,d,e) 6 集合S
{a,b}
{a,b,c}
{a,b,c,f}
宜昌人力资源和社会保障局{a,b,c,f,d}
{a,b,c,f,d,e}
后续目标顶点依次为f,d,e 。
【排除法】对于A ，若下一个顶点为d ，路径a,b,d 的长度5，而a,b,c,f 的长度仅为4，显然
错误。同理可以排除B 。将f 加入集合S 后，采用上述的方法也可以排除D 。 8.【参考答案】A
【解析】考查最小生成树、及最小生成树算法的性质。对于Ⅰ，最小生成树的树形可能不唯一（这是因为可能存在权值相同的边），但是代价一定是唯一的，Ⅰ正确。对于Ⅱ，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，Ⅱ错误。对于Ⅲ，设N 个结点构成环，N-1条边权值相等，则从不同的顶点开始普里姆算法会得到N-1中不同的最小生成树，Ⅲ错误。对于Ⅳ，当最小生成树唯一时（各边的权值不同），普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，Ⅳ错误。 9.【参考答案】D
【解析】考查B-树的删除操作。
对于上图所示的3阶B-树，被删关键字78所在结点在删除前的关键字个数=1=3/2-1    ，且其左兄弟结点的关键字个数=2≥3/2    ，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。
10.【参考答案】A
【解析】考查各种内部排序算法的性质。对于Ⅰ，简单选择排序每次选择未排序列中的最小元素放入其最终位置。对于Ⅱ，希尔排序每次是对划分的子表进行排序，得到局部有序的结果，所以不能保证每一趟排序结束都能确定一个元素的最终位置。对于Ⅲ，快速排序每一趟排序结束后都将枢轴元素放到最终位置。对于Ⅳ，堆排序属于选择排序，每次都将大根堆的根结点与表尾结点交换，确定其最终位置。对于Ⅴ，二路归并排序每趟对子表进行两两归并从而得到若干个局部有序的结果，但无法确定最终位置。 11.【参考答案】D
【解析】考查折半插入和直接插入的区别。折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查法，而折半插入排序是采用折半查法。排序的总趟数取决于元素个数n ，两者都是n-1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是O(1)。折半插入排序的比较次数与序列初态无关，为O(nlog 2n)；而直接插入排序的比较次数与序列初态有关，为O(n)~O(n 2)。 12.【参考答案】D
【解析】考查计算机性能指标的计算。程序A 的运行时间为100秒，除去CPU 运行时间90秒，剩余10秒为I/O 时间。CPU 提速后运行基准程序A 所耗费的时间是T=90/1.5+10=70秒。【误区】CPU 速度提高50%，则CPU 运行时间减少一半。错误！
13.【参考答案】B
【解析】考查C语言中的类型转换。将一个16位unsigned short转换成一个32位的unsigned int，新表示形式的所有附加位都用0进行填充。X的16进制表示为FFFA，所以y的十六进制表示为0000 FFFA。
14.【参考答案】D
【解析】考查IEEE754浮点数的性质。IEEE 754标准的单精度浮点数，是尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短浮点数的真值为：(-1)S×1.f×2E-127，S为符号位，E的取值为1～254（8位表示），f为23位；故float类型能表示的最大整数是1.111…1×2254-127=2127×(2-2-23) = 2128-2104。
15.【参考答案】D
【解析】考查字符串的存储方式。计算机存储器按字节编址，采用小端方式存放数据，即以数据的最低有效字节地址表示数据地址。在存储器中，数据结构按边界对齐方式顺序存储，因此int型数据的地址必须是4的倍数，short型数据地址必须是2的倍数。所以record.c的地址不可能为0xC00D。而273的十六进制表示为0x00000111，故地址0xC008中内容应为低字节0x11，如下表所示。
地址0xC008 0xC009 0xC00A 0xC00B
内容record.a (0x11) record.a (0x01) record.a (0x00) record.a (0x00)
地址0xC00C 0xC00D 0xC00E 0xC00F
内容record.b - record.c record.c
16.【参考答案】A
【解析】考查闪存（Flash Memory）的性质。闪存是EEPROM的进一步发展，可读可写，用MOS管的浮栅上有无电荷来存储信息，它依然是ROM的一种，故写速度比读速度要慢不少（硬件常识）。闪存是一种非易失性存储器，它采用随机访问方式。现在常见的SSD固态硬盘，即由Flash芯片组成。
17.【参考答案】C
【解析】考查组相联映射的Cache置换过程。地址映射采用2路组相联，则主存地址为0~1、4~5、8~9可映射到第0组Cache中，主存地址为2~3、6~7可映射到第1组Cache中。Cache置换过程如下表所示。
走向0    4 8    2 0    6 8    6    4 8
第0组块0 0    4    4 8 8 0 0 8    4 块1 0    4 8 8 0 0 8* 8    4 8*
第1组块2    2    2    2    2    2 块3    2    2    6    6 6*    6    6
考研计算机真题注：“_”表示当前访问块，“*”表示本次访问命中。
18.【参考答案】C
【解析】考查微指令的编码方式。操作控制字段采用字段直接编码法，将微命令字段分成若干个小字段，互斥类微命令可组合在同一字段。根据微命令字段分段的原则：①互斥性微命令分在同一段内，相容性微命令分在不同段内；②一般每个小段要留出一个状态，表示本字段不发出任何微命令。5个互斥类分别需要3、2、4、3、3共15位。