1.2.2 真题解析
1.【答案】D。
【解析】考查计算机系统中数据表示的基础知识。
对阶是指将两个进行运算的浮点数的阶码对齐的操作。对阶的目的是使两个浮点数的尾数能够进行加减运算。对阶的原则是小阶对大阶，采用补码表示的尾数右移时，符号位保持不变。之所以是小阶对大阶，是因为若大阶对小阶，则尾数的数值部分的高位需移出，而小阶对大阶移出的是尾数的数值部分的低位，这样损失的精度更小。采用补码表示的尾数右移时，符号位保持不变，是因为尾数右移时是将最低位移出，会损失一定的精度，为减少误差，可先保留若干移出的位，供以后舍入处理用。
2.【答案】A。
【解析】考查计算机系统中数据表示的基础知识。
69可分解为69=64+4+1，用二进制形式表示为1000101，偶校验是指数据编码（包括校验位）中1的个数应该是偶数。因此，若除去校验位，编码中1的个数是奇数时，校验位应设置为1；否则，校验位应设置为0。本题1000101中有3个1，所以最高位增加一个偶校验位后为11000101。故答案是A。
3.【答案】（1）B；（2）C。
【解析】考查计算机系统中数据表示的基础知识。
计算机中的有符号数有三种表示方法，即原码、反码和补码。三种表示方法均有符号位和数值位两部分，符号位都是用0表示“正”，用1表示“负”，而对于数值位，三种表示方法各不相同。
已知一个数的补码，求原码的操作其实就是对该补码再求补码：①如果补码的符号位为0，表示是一个正数，它的原码就是补码。②如果补码的符号位为1，表示是一个负数，那么求给定的这个补码的补码就是所要求的原码。
反码为10101011，为负数，所以将它的数值位取反，末位再加1即可得到它的原码，为11010100，将它转化为十进制为-(26+24+22)=-(64+16+4)=-84。
10101100转化为无符号整数：27+25+23+22=128+32+8+4=172。
4.【答案】D。
【解析】考查常用排序算法的基础知识。
快速排序：通过一趟扫描将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列的目的。
选择排序：顾名思义，就是直接从待排序数组里选择一个最小（或最大）的数字，每次都拿一个最小数字出来，顺序放入新数组，直到全部拿完。
冒泡排序：原理是邻近的数字两两进行比较，按照从小到大或者从大到小的顺序进行交换，这样一趟过去后，最大或最小的数字被交换到了最后一位；然后再从头开始进行两两比较交换，直到倒数第二位时结束；以此类推，直到全部比较完。
归并排序：原理是把原始数组分成若干子数组，对每一个子数组进行排序，然后把子数组与子数组合并，合并后仍然有序，直到全部合并完，形成有序的数组。
冒泡排序是通过相邻元素的比较和交换，将最大元素（或最小元素）交换至序列末端（或前端），对{18，12，10，11，23，2，7}进行一次冒泡排序，就可以得到{12，10，11，18，2，7，23}，故答案选D。
5.【答案】C。
【解析】考查数据结构中二叉树的基础知识。
由先序遍历（即前序遍历）看，E为根结点，F为根结点的左孩子。再看中序遍历，则E的左子树中F结点有H和I两个子结点，那么E的右孩子结点为G，它的二叉树如下图所示。
6.【答案】A。
【解析】考查数据结构中栈的基础知识。
出入栈的基本原则为：先进后出，后进先出。若第一个出栈的元素是1，对应的操作就是入栈后又出栈的操作，此后，每个入栈的元素都可能有两种情况，此时不确定2，…，n出入栈的情况，如果2进栈，2出栈，3进栈，3出栈……在i进栈后，以序列i+1，i+2，…，n依次进栈后再依次出栈，则最后出栈的是i(2≤i≤n)。
7.【答案】B。
【解析】考查数据结构中栈的基础知识。
栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这类信息常被称为堆栈帧或者活动记录。
8.【答案】C。
【解析】考查数据结构的二维数组的基础知识。
一个数组占8字节，那么二维数组A[7][8]的元素在逻辑上分7行、每行8列，即共含有7×8=56个数组元素，共占用56×8=448字节的存储空间。
9.【答案】D。
【解析】考查数据结构中字符串的基础知识。
由于S是长度为n的非空字符串，其中的字符各不相同，因此其长度为1的子串有n个，长度为2的子串有n-1个，长度为3的子串有n-2个，以此类推，则长度为n-1的子串为2个，合计为n+n-1+…+2，即为(n+2)(n-1)/2。这里再以字符串"abcde"为例来说明。该字符串长度为1的子串为"a"，"b"，"c"，"d"和"e"，共5个；长度为2的子串为"ab"，"bc"，"cd"和"de”，共4个；长度为3的子串为"abc"，"bcd"和"cde"，共3个；长度为4的子串为"abcd"和"bcde"，共2个；长度为5的子串为"abcde"，共1个；空串是任何字符串的子串。在本题中，空串和等于自身的字符串不算，因此子串数目共14（5+4+3+2）个。
10.【答案】C。
【解析】考查常用算法中二分查找的基础知识。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键码有序排列。
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x进行比较，如果x=a[n/2]，则找到x时算法中止；如果x＜a[n/2]，则只需在数组a的左半部分继续搜索x；如果x＞a[n/2]，则只需在数组a的右半部分搜索x。
二分查找法要求：①必须采用顺序存储结构；②必须按关键码大小有序排列。
11.【答案】B。
【解析】考查数据结构中图的基础知识。
在一个无向图G中，若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径），则称vi和vj是连通的。如果图中任意两点都是连通的，那么该图被称作连通图。任意两个顶点之间都有边的图是完全图，完全图是连通图，反之不一定，也就是说不是任意两顶点之间都存在边。
12.【答案】B。
【解析】考查数学应用的相关知识。
按原计划，在正常的情况下，完成10%的工作量需要2天和0.4万元。工作量为1，正常速度为1/20，现在还剩60%，因此还需要60%÷(1/20)=12天，原计划是10天，因此要推迟2天完工。正常花费为4万元，现在还有60%未完成，因此还需要0.6×4=2.4万元，2+2.4-4=0.4万元，即需要增加费用4000元。
13.【答案】C。
【解析】考查数学应用的基础知识。
代入法：如果是区域的一个顶点，那么满足题干的五个条件，同时也会使x+y=6，2x+y=7，x+2y=8中的三个等式成立。因此可以考虑把四个点的坐标代入以上条件进行检验：A选项满足x+y=6和2x+y=7，但是不满足x+2y≤8；B选项不满足三个等式；C选项满足2x+y=7和x+2y=8，也满足其他条件；D选项只满足2x+y=7。
14.【答案】C。
【解析】考查矩阵相关的数学基础知识。
可以把A作为一个直角坐标系的原点，X轴是从左到右递增，Y轴是从上到下递增。如果E大于A，那么E应该在A的右侧或者A的下侧。因此，可能在子矩阵B、C或者D中。
15.【答案】B。
【解析】考查计算机系统中数据表示的基础知识。
数字0～15用十六进制表示依次为0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F。本题可以将二进制序列1011011从右向左每四位分为一组，分为0101和1011。按照不同进制的转换，(0101)2=(5)10=(5)16，(1011)2=(11)10=(B)16，因此答案应为5B。
16.【答案】C。
【解析】考查数据表示的基础知识。
原码表示是用最左边的位（即最高位）表示符号，其中“0”表示正号，“1”表示负号，其余7位表示数的绝对值，-128的绝对值为128，用二进制表示时需要8位，所以机器字长为8位时采用原码是不能表示-128的。
对于负数，反码表示是用最左边的位（即最高位）表示符号，“0”表示正号，“1”表示负号，其余7位是将数的绝对值的各位取反。-128的绝对值是128，用二进制表示时需要8位，所以机器字长为8位时，采用反码也不能表示-128。
补码表示与原码和反码的相同之处是最高位用“0”表示正号，“1”表示负号，不同的是补码10000000的最高位的1既表示其为负数，也表示数字1，从而使得它可以表示出-128。
17.【答案】A。
【解析】考查数据校验的基础知识。
CRC表示循环冗余校验码，是通过在要发送的数据后面加n位的冗余码来构造的。模2除法与算术除法类似，但每一位除的结果不影响其他位，即不向上一位借位，所以实际上就是异或运算。在CRC的计算中用到了模2除法。
18.【答案】D。
【解析】考查数据表示的基础知识。
海明码可以通过在传输码列中加入冗余位（也称纠错位）实现前向纠错，但这种方法比重传协议的成本要高。编码方式为：假设数据有n位，校验码为x位，则校验码一共有2x种取值方式，其中需要一种取值方式表示数据正确，剩下2x-1种取值方式表示数据出错。因为编码后二进制串有n+x位，因此x应满足2x-1≥n+x。校验码在二进制串中的位置为2的整数幂，剩下的位置为数据。
19.【答案】A。
【解析】考查数据结构的基础知识。
在递归调用中，需要在前期存储某些数据，并在后面以存储的逆序恢复这些数据，以供之后使用，因此，需要用到栈来实现递归。简单地说，就是在递归的前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在递归退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用不同层次中执行代码的其余部分，也就是恢复了调用时的状态。
20.【答案】A。
【解析】考查数据结构的基础知识。
入栈序列为a、b、c、d时，若第一个出栈的元素为d，则说明a、b、c都还在栈中，而且a位于栈底，其次是b和c。因此，合法的出栈序列只能是d、c、b、a。
21.【答案】C。
【解析】考查数据结构的基础知识。
在该关键码序列中进行二分查找时，首先与中间元素24进行比较，若相等则结束；若小于24，则继续在前4个元素中进行二分查找；否则在后4个元素中进行查找。具体的过程可以用如下的判定树来表示。
所以查找15时，需要与24、12和15依次进行比较。
22.【答案】B。
【解析】考查数据结构的基础知识。
散列函数为H(Key)=Key%11（%表示整除取余运算），因此只需要将数据分别与11进行取余运算。按顺序计算各关键码的散列（哈希）地址：H(12)=12%11=1，H(24)=24%11=2，H(15)=15%11=4，H(56)=56%11=1，H(20)=20%11=9，H(87)=87%11=10，H(69)=69%11=3，H(9)=9%11=9。即与11取余分别得到1，2，4，1，9，10，3，9。按照序列依次存储到相应位置，若出现冲突则往后顺延。这里需要注意的是，当存储到关键码序列最后一位的9时，因其取余得到的散列地址是9，与前面的20相同，也就是这个地址单元已存入了20，所以应往后顺延，但最后一位地址第10号单元也已存入了87，仍然冲突，就需要继续往后顺延，这就又需要从0号开始探查，此时探查到散列地址为0的单元为空，因此在0号单元存入9。
23.【答案】D。
【解析】考查数据结构的基础知识。
前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。
后序遍历：先遍历左子树，然后遍历右子树，最后遍历根结点。
层序遍历：从上往下逐层遍历。
二叉树进行中序遍历的过程是：中序遍历左子树、访问根结点、中序遍历右子树，因此此题中二叉树的中序遍历序列是2 5 4 3 6 1。
24.【答案】（1）D；（2）C。
【解析】考查数据结构中矩阵的基础知识。
图的邻接矩阵中，每个元素表示行对应的顶点与列对应的顶点之间是否有弧（1有，0没有），题目所示的邻接矩阵如下所示。
邻接链表存储是将关联同一顶点的边用线性链表存储，对于有向图，每个表结点表示从头结点所示顶点出发的一条弧关联的另一个顶点，从顶点1出发的弧有＜1，2＞和＜1，5＞，采用邻接链表存储的有向图邻接表如下所示。
25.【答案】A。
【解析】考查数据结构的基础知识。
以4个元素（10,20,30,40）为例说明直接插入排序的特点。
若元素已经按照升序排列，即K1=10，K2=20，K3=30，K4=40，那么各趟排列结果如下：
第一趟将20插入仅含元素10的子序列，20与10比较1次，得到10 20。
第二趟将30插入含有元素10、20的子序列，30与20比较1次，得到10 20 30。
第三趟将40插入含有元素10、20、30的子序列，40与30比较1次，得到10 20 30 40。
在上述过程中，由于待插入的元素比有序子序列的最大元素都要大，因此总共进行了3次比较，不需要移动元素。推广到有n个元素的序列，则要进行n-1次比较。
若元素已经按照降序排列，即K1=40，K2=30，K3=20，K4=10，那么各趟排列结果如下：
第一趟将30插入仅含元素40的子序列，30与40比较1次，将40后移，再将30插入40之前，得到30 40。
第二趟将20插入30、40构成的子序列，20与40比较1次，将40后移，再与30比较1次，将30后移，再将20插入30之前，得到20 30 40。
第三趟将10插入20、30、40构成的子序列，10与40比较1次，将40后移，再与30比较1次，将30后移，再与20比较1次，将20后移，再将10插入20之前，得到10 20 30 40。
在上述过程中，由于待插入的元素比有序子序列的所有元素都要小，所以总共进行1+2+3次比较，每次插入时有序子序列的所有元素都要移动。推广到有n个元素的序列，则总共进行1+2+…+n-1次比较。
因此，题目选项中A选项正确。
若初始序列为30 20 10 40，则第一趟排序完成后得到的有序子序列为20 30，此时并没有得到整个序列的最小元素或最大元素，所以选项C和D的说法错误。
26.【答案】A。
【解析】考查关系代数方面的基础知识。
在关系代数中，“并”运算是一个二元运算，要求参与运算的两个关系结构必须相同，运算结果的结构与原关系模式的结构相同。而笛卡儿积和自然连接尽管也是二元运算，但参与运算的两个关系结构不必相同。投影运算是向关系的垂直方向运算，运算的结果是去除某些属性列，所以运算的结果与原关系模式不同。也就是说：若关系R与S具有相同的关系模式，即关系R与S的结构相同，则关系R与S可以进行并、交、差运算。
27.【答案】B。
【解析】考査应用数学的基础知识。
MN＜2(M+N)等价于(M-2)(N-2)＜4，而M-2和N-2都是正整数。
M-2=1时，N-2可以是1、2、3；M-2=2时，N-2只能是1；M-2=3时，N-2只能是1，所以(M,N)只有（3,3），（3,4），（3,5），（4,3），（5,3）五对。
28.【答案】D。
【解析】考查应用数学的基础知识。
用行号（1～4）与列号（1～7）表示一个单元格的坐标，用左上角和右下角两个单元坐标表示一个矩形块。四角上都是1的矩形块是满足题目要求的矩形块。
左上角为11，右下角分別为25, 32, 35, 36，共有4个满足要求的矩形块。
左上角为12，右下角分别为35, 36, 45，共有3个满足要求的矩形块。
左上角为15，右下角为36，共有1个满足要求的矩形块。
左上角为21，右下角分別为33, 35，共有2个满足要求的矩形块。
左上角为23，右下角为35，共有1个满足要求的矩形块。
左上角为32，右下角为45，共有1个满足要求的矩形块。
因此，共有12个满足要求的矩形块。
29.【答案】A。
【解析】考查应用数学的基础知识。
从题目中的图可以分析得到，诊所不应设在D、G两村，其他5村中选择两村的可能性共10种，用列表表示如下：
因此，选择在A、E或C、E两村设立诊所，可使最远的村去诊所的距离最短为3km。
30.【答案】A。
【解析】考查计算机系统基础知识中原码、反码和补码相关的知识。
长度为n的情况下，补码能够表示的范围为[-2n-1,2n-1）。因此，当补码字长为32时，表示的范围为[-231,231）。
31.【答案】A。
【解析】考查数据表示基础知识中的八进制、二进制相互转换。
每个八进制数字转化为二进制表示如下：
将二进制从小数点位置开始从右向左，每3位一组转化为对应的一个八进制数字即可。因此0011011的八进制表示为033。
32.【答案】D。
【解析】考查计算机逻辑运算的基础知识。
各逻辑表达式的真值表表示如下：
从上表可知，当且仅当X和Y同时为1时Z=
为0，其他情况下Z为1。因此应选D。
33.【答案】B。
【解析】考查计算机数据校验的基础知识。
三种常见的校验是奇偶校验、海明校验和循环冗余校验。海明校验是利用奇偶性来检错和纠错的校验方法。海明码的构成方法是：在数据位之间插入k个校验位，通过扩大码距来实现检错和纠错。海明码的校验位位于2的幂次方的位置（例如1，2，4，8等位置），其余位为数据位，因此海明码中数据信息位与校验位需要满足一定的位置关系。
34.【答案】A。
【解析】考查数据结构中栈和队列的基础知识。
当有多个函数构成嵌套调用（如递归调用）时，按照“后调用先返回”的原则，函数之间的信息传递和控制转移可以用“栈”来实现。
35.【答案】C。
【解析】考查数据结构中链表的基础知识。
在单向链表存储结构中，不管是有头指针还是有尾指针，遍历链表（即遍访链表中的所有元素）的时间复杂度都是O(n)。
在单向链表的任何位置插入或删除结点，首先需要找到插入位置（该算法的时间复杂度不确定），然后修改指针即可（该时间复杂度为O(1)）。循环链表仅设头指针时，在表尾插入一个新元素时，因为要找到表尾位置，需从头结点遍历到尾结点，因此其时间复杂度是O(n)。循环链表仅设尾指针时，在表头插入一个新元素时，因为有尾指针且是循环链表，尾指针所指向结点的下一个结点就是头结点，因此在表头插入的时间复杂度是O(1)。
36.【答案】A。
【解析】考查数据结构的基础知识。
在有序顺序表中进行二分查找时，总是先与表中间位置的元素进行比较，若相等，则查找成功并结束，若比中间元素小，则进一步到前半区（由不大于中间元素者构成）进行二分查找，否则到后半区（由不小于中间元素者构成）继续进行二分查找。二分查找（折半查找）的操作步骤如下（设R[low,…,high]是当前的查找区）：
①确定该区间的中点位置：mid=[(low+high)/2]。
②将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下：
●若R[mid].key＞k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键码等于k的结点，则该结点必定是在位置mid左边的子表R[low,…,mid-1]中。因此，新的查找区间是左子表R[low,…,high]，其中high=mid-1。
●若R[mid].key＜k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，其中low=mid+1。
●若R[mid].key=k，则查找成功，算法结束。
③下一次查找是针对新的查找区间进行，重复步骤①和②。
④在查找过程中，low逐步增加，而high逐步减小。如果high＜low，则查找失败，算法结束。
37.【答案】B。
【解析】考查数据结构中哈希查找的基础知识。
在哈希表（散列表）中，通过把关键码映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数叫作哈希函数（散列函数），存放记录的数组叫作哈希表（散列表）。哈希查找的操作步骤如下：
①用给定的哈希函数构造哈希表。
②根据选择的冲突处理方法解决地址冲突。
③在哈希表的基础上执行哈希查找。
38.【答案】C。
【解析】考查数据结构中图的基础知识。
可以根据选项进行判断：
A.G的邻接矩阵是对称矩阵，错误，对称矩阵满足aij=aji，因此当存在i→j的有向边时，一定存在j→i的有向边，此时图不满足。
B.G的邻接矩阵是三角矩阵，错误，三角矩阵中的非0元素一定要在矩阵对角线的一侧，而根据图有a41=a24=1，其中一个a41在对角线下方，另一个a24在对角线上方。
C.G是强连通图，正确。
D.G是完全图，错误，完全图要求任意两个顶点之间都有边（弧），显然G不是完全图。
该题也可以将图转化为邻接矩阵，如下：
39.【答案】D。
【解析】考查树的遍历基础知识。
根据先序遍历（即前序遍历）序列可以确定树（及子树）的根结点，根据中序遍历序列可以分割左、右子树上的结点，据此逐步确定每个结点的位置。判断如下：
①已知先序遍历序列是ABDCE，则根结点为A；然后中序遍历序列是BDACE，则BD是左子树中的元素，CE是右子树中的元素。可排除A、B选项。
②然后看左子树BD，在先序遍历中先访问B结点，B作为该子树的树根。回到中序遍历，先访问的是B，然后访问的是D，则D是B的右孩子结点。
③然后看右子树CE，在先序遍历中先访问C结点，C作为该子树的树根。回到中序遍历，先访问的是C，然后访问的是E，则E是C的右孩子结点。
因此答案应选D。
该题也可以对每个二叉树进行先序遍历和中序遍历运算，根据所得序列确定正确选项，即
选项A所示二叉树的先序遍历序列为ABDEC，中序遍历序列为DBEAC。
选项B所示二叉树的先序遍历序列为ABCDE，中序遍历序列为BADCE。
选项C所示二叉树的先序遍历序列为ABDCE，中序遍历序列为BDAEC。
选项D所示二叉树的先序遍历序列为ABDCE，中序遍历序列为BDACE。
综合判断后选择D选项。
40.【答案】B。
【解析】考查数据结构中堆排序的基础知识。
根据题目要求，满足所有父结点小于或等于其所有子结点的关键码序列为小根堆。因此可以将关键码序列的元素按顺序放入一个完全二叉树中，方便地确定父结点和子结点的大小关系。将题中关键码序列用完全二叉树表示，如下图所示，显然将14、20互换后，满足小根堆的定义。
41.【答案】A。
【解析】考查数据结构中简单选择排序的基础知识。
根据题目描述，简单选择排序第一趟经过n-1次关键码之间的比较，第二趟经过n-2次关键码之间的比较，第三趟经过n-3次关键码之间的比较……第n-1趟经过1次关键码之间的比较，总的比较次数为n-1+n-2+…+1=n(n-1)/2。
42.【答案】B。
【解析】考查软件工程基础知识和数据结构、算法特性及复杂度。
正确性（准确性）：正确实现算法功能，最重要的指标是能否得到正确或者相符的结果或效果的软件。
可靠性：元件、产品、系统在一定时间内和一定条件下无故障地执行指定功能的能力或可能性。
友好性：具有良好的使用性。
可读性：可读的、可以理解的，方便分析、修改和移植。
健壮性：能对不合理的数据或非法的操作进行检查、纠正。
效率：对计算机资源的消耗，包括计算机内存和运行时间的消耗。
可移植性：软件从一个计算机系统或环境转移到另一个计算机系统或环境的难易程度。
43.【答案】B。
【解析】考查软件工程基础知识中的算法特性和复杂度。
正确性（准确性）：正确实现算法功能，最重要的指标是能否得到正确或者相符的结果或效果的软件。
可用性：是在某个考察时间，系统能够正常运行的概率或时间占有率期望值。系统的可用性取决于MTTF（平均无故障时间，表示系统的可靠性）及MTTR（平均修复故障时间，表示系统的可维护性）。
可靠性：元件、产品、系统在一定时间内和一定条件下无故障地执行指定功能的能力或可能性。
友好性：具有良好的使用性。
可读性：可读的、可以理解的，方便分析、修改和移植。
健壮性：能对不合理的数据或非法的操作进行检查、纠正。
效率：对计算机资源的消耗，包括计算机内存和运行时间的消耗。
44.【答案】C。
【解析】考查应用数学基础知识。
因为0＜r＜1，则0＜2r＜2，同时加3后，则有3＜3+2r＜5。线性的3+2r仍能保证在区间（3，5）内均匀分布。
45.【答案】B。
【解析】考查应用数学基础知识。
系统的可用性（System Availability）是指系统服务不中断运行时间占实际运行时间的比例。如果系统的可用性达到99.99%，则表示10000分钟停机时间为1分钟，停机时间占比为0.01%。一年按365天算，每年有365×24=8760小时，则8760×0.0001=0.876小时=52.56分钟≈53分钟。
46.【答案】B。
【解析】考查应用数学基础知识。
从题目中的表格可以看出，工作2只能由工人C来做（表示成C2），工人A只能分配A1或A4。如果分配A1，B只能分配B5。由A1、B5、C2可知，余下3、4项工作只能分配给D、E，可得分配结果为D3、E4。因此，分配A1后，只有A1、B5、C2、D3、E4一种分配方案。
如果分配A4，则B有两种可能：B1或B5。如果分配B1，则在A4、B1、C2后，剩余3、5项工作应由D、E完成，可以有两种分配方案：A4、B1、C2、D3、E5和A4、B1、C2、D5、E3。如果分配B5，则在A4、B5、C2后，剩余1、3项工作由D、E完成，只能分配D1、E3。
综上，共有四种分配方案：A1、B5、C2、D3、E4；A4、B1、C2、D3、E5；A4、B1、C2、D5、E3；A4、B5、C2、D1、E3。
47.【答案】A。
【解析】考查计算机系统中数据表示的基础知识，二进制、十六进制的相互转换。
二进制与十六进制的转换是将每四位二进制转换成一位十六进制，所以二进制1011011转换成十六进制为5B。
48.【答案】B。
【解析】考查计算机系统中的数据表示（原码、反码和补码）的基础知识。
原码、反码和补码是数值数据的三种基本编码方法，对于正数，三种编码是相同的，而对于负数，这三种编码是不同的。码长为8即用8位二进制形式来表示数值，最左边的位是符号位，0表示是正数，1表示是负数，剩余的7位表示数值部分，原码表示的规则是直接表示出数值的绝对值。本题中10000000的最高位为1，表示是负数。数值部分为0，即绝对值为0的数值。在原码表示中，0由于符号部分不同占用00000000和10000000两个编码。
49.【答案】C。
【解析】考查计算机系统中浮点数运算的基础知识。
在机器中表示一个浮点数时，一是要给出尾数，用定点小数形式表示，尾数部分给出有效数字的位数，因而决定了浮点数的精度；二是要给出指数，用整数形式表示，常称为阶码，阶码指明小数点在数据中的位置，因而决定了浮点数的表示范围。例如，浮点数X=1101.0101，Y=10.0111，按照浮点格式（忽略标准格式要求）表示为X=0.11010101×24，Y=0.100111×22。若进行加减运算，需要先对阶，也就是在阶码一致的情况下对尾数部分进行加减运算；若进行乘除运算，则不要求阶码一致。相乘时阶码部分为两个浮点数的阶码相加，尾数部分直接相乘，之后再按照规格化等要求进行处理。
50.【答案】B。
【解析】考查计算机系统中的数据表示基础知识：原码、反码和补码。
用原码表示数据时，是在数值位部分表示出相应数值的绝对值。如果符号位相同，则减法运算是用绝对值较大者减去绝对值较小者；若符号位不同，则减法运算实质是两者的绝对值部分进行相加。用补码表示数据时，可以将减法转化为加法，运算时符号位和数值位用相同的规则处理，统一进行二进制相加运算即可。
51.【答案】A。
【解析】考查数据结构基础知识中栈的用途。
栈的基本操作有入栈、出栈、取栈顶及判断栈是否为空。入栈和出栈分别是指在栈顶加入及删除元素，取栈顶操作仅读取栈顶元素的值而不删除元素。从栈底删除元素不是栈的基本操作。
52.【答案】B。
【解析】考查数据结构中顺序表之一链表的基础知识。
对单向链表中的结点只能进行顺序访问，不能随机访问。在表尾插入元素时，必须从表头遍历至表尾，时间复杂度为O(n)，而在表头插入元素时，可以直接定位至插入位置，时间复杂度为O(1)。
53.【答案】D。
【解析】考查数据结构中二叉排序树的基础知识。
先序遍历二叉树的操作定义如下：若二叉树为空，则进行空操作，否则访问根结点、先序遍历根的左子树、先序遍历根的右子树。题中所示二叉树的先序遍历序列为23, 15, 12, 18, 56, 29, 34, 71。
54.【答案】B。
【解析】考查数据结构中数组的基础知识。
三对角矩阵是一种特殊矩阵，矩阵中的非零元素都分布在主对角线及邻近主对角线的次对角线上，三对角矩阵如下图所示。
按行排列，元素A[56,55]之前有164个元素((56-1)×3-1+(55-56+1))，因此该元素对应着B[165]。
55.【答案】C。
【解析】考查数据结构中树的基础知识。
在一棵高度为h的完全二叉树中，除了第h层（即最底下一层），其余各层都是满的。第h层上的结点必须从左到右依次放置，不能留空，例如，高度为3的完全二叉树有如下图所示的4种，其中图a是完全二叉树也是满二叉树。
对完全二叉树中的结点从1开始编号，自上而下、从左到右依次进行。即根结点的编号为1，它的左孩子结点编号为2，右孩子结点编号为3，以此类推，编号为i的结点的左孩子（存在时）编号为2i、右孩子（存在时）编号为2i+1。
56.【答案】D。
【解析】考查数据结构中字符串的基础知识。
字符串是一种线性表，它的特殊性在于表中的每个元素为字符，同时具有特别的基本运算，如字符串比较、求子串、字符串连接等。选项A是错误的，字符串的长度不受限制。选项B是错误的，字符串可采用链表存储，只是这种存储方式在大多数情况下不利于支持字符串的基本运算。选项C是错误的，字符串属于线性数据结构。
57.【答案】A。
【解析】考查数据结构中堆排序的基础知识。
根据堆的定义，将序列表示为完全二叉树更容易判定相应元素之间的大小关系是否满足堆的定义。
选项A的序列如下图所示，k(131)、k(158)、k(288)显然满足ki≤k2i且ki≤k2i+1，因为父结点k(131)小于它的左、右子结点，三者中最小；k(158)、k(325)、k(763)同样满足k(158)最小；k(288)、k(522)、k(451)中父结点k(288)最小；k(325)、k(617)中父结点k(325)最小（k(325)的右子结点不存在，因而不予考虑），因此，该序列满足小根堆的定义。
对于选项B，将它用一棵完全二叉树来表示，如下图所示。k(131)、k(325)、k(451)满足ki≤k2i且ki≤k2i+1，因为父结点k(131)小于它的左、右子结点，三者中最小；k(325)、k(617)、k(522)中父结点k(325)最小，符合小根堆的定义；而k(451)、k(288)、k(158)中则是父结点k(451)最大，不符合小根堆的定义。因此整个序列不是小根堆。
对于选项C和D采用相同方式加以判断，可得知它们都不是小根堆。
58.【答案】C。
【解析】考查数据结构中图的基础知识。
邻接矩阵和邻接链表是图的两种基本存储结构，矩阵的每行和每列都对应图中的一个顶点，矩阵元素则表示行对应的顶点和列对应的顶点之间是否有边（弧），如下图所示。
邻接链表是为图的每个顶点建立一个单向链表，单向链表中第i个结点表示依附于顶点v的边（对于有向图是以v为尾的边）。邻接链表中的结点有表结点和表头结点两种类型，例如下面图a所示的无向图和图b所示的邻接表表示。
本题正确选项为C，图中顶点数确定的情况下，邻接矩阵的阶（行、列数）就确定了，与边数无关。稀疏图的边数很少，它的邻接矩阵为稀疏矩阵，零元素较多，存储空间利用率降低。对于边数较多的稠密图，采用邻接矩阵更为合适。
59.【答案】C。
【解析】考查应用数学的基础知识。
前几天，甲、乙合作种了1/6，甲和乙的工作量都为1/12；后来，乙、丙合作种了余下5/6的2/5，即1/3，因此乙和丙的工作量都为1/6；最后，由甲、乙、丙三人完成了其余的1-1/6-1/3=1/2，甲、乙、丙三人的工作量都为1/6。综上所述，甲的工作量为1/12+1/6=3/12，乙的工作量为1/12+1/6+1/6=5/12，丙的工作量为1/6+1/6=4/12，因此，甲、乙、丙三人工作量之比为3:5:4。
60.【答案】B。
【解析】考查应用数学的基础知识。
设该班级共有n人，这次考试实际总分应为86.3×n分，但两次错误录入导致总分变成86.7×n分，使总分增加了(86.7-86.3)×n=0.4×n分。其中对一个学生错误地增加了96-69=27分，对另一个学生错误地减少了98-89=9分，即两次错误导致总分增加了27-9=18分。0.4×n=18，所以解得n=45。
61.【答案】C。
【解析】考查应用数学的基础知识。
如下图所示，区域S的面积为2，区域P的面积为1/2。因此，P对S的占比为1/4=25%。
