1.3.2 练习精解

1.【答案】（1）B；（2）A；（3）D。

【解析】二进制数11001100为原码，最高位为1，所以它为负数。后面7位数据代表的是该数的绝对值76，所以它的真值为-76。

若二进制数11001100为补码，则可以知道它对应的原码为10110100，所以它对应的真值为-52。

-1的补码用8位二进制数表示为11111111。

2.【答案】B。

【解析】在逻辑运算中，“与”运算：只要一个逻辑变量为0，运算结果就为0。“或”运算：只要一个逻辑变量为1，运算结果为1。所以答案为B。

3.【答案】D。

【解析】堆的定义：k_i≥k_2i且k_i≥k_2i+1或k_i≤k_2i且k_i≤k_2i+1，即父结点均不大于其孩子结点，或均不小于其孩子结点。

由此定义即可判断出，D中100大于85和40，而40小于60和66，所以D不是堆。

4.【答案】B。

【解析】必须从n/2开始建堆，n为10，所以要从第5个元素即60处开始建堆。

5.【答案】A。

【解析】在逻辑运算中，运算结果只有两种情况，结果为1或0。逻辑“与”运算中，只要一个逻辑变量为0，结果就为0；逻辑“或”运算中，只要一个逻辑变量为1，结果就为1。所以答案为A。

6.【答案】C。

【解析】堆栈将插入和删除操作限制在线性表的一端进行，而队列将插入和删除操作分别限制在线性表的两端进行。它们实际上都是操作受限的线性表，它们的共同点就是只允许在线性表的端点处进行插入和删除操作。

7.【答案】D。

【解析】由于主机将要输出的数据依次写入缓冲区，而打印机则依次从缓冲区取出数据打印，数据写入缓冲区的次序与从缓冲区取数据打印的次序是一致的，因此该缓冲区是一个队列结构。

8.【答案】D。

【解析】浮点数编码表示中符号、阶码和尾数均有体现，只有基数是固定的，无须出现。

9.【答案】B。

【解析】本题主要考查十进制数据与十六进制数据之间的转换。十进制数33对应的十六进制数为21H。

10.【答案】A。

【解析】卡诺图是化简逻辑表达式的有效手段，使用它化简逻辑表达式时，合并图中的1还是合并图中的0，可以根据需要进行。只是使用它合并图中的0时，应该使合并的结果取反才能得到正确的结果。

11.【答案】D。

【解析】考查的是计算机数据表示范围方面的基础知识。

由于28=256，可以表示0～255，因此对于无符号数可以表示256个数据，如果是有符号数或高位用作奇偶校验，可以表示128个数据。

12.【答案】C。

【解析】在关系数据库中，关系演算的基础是数理逻辑中的谓词演算。

13.【答案】D。

【解析】如果不考虑结点数据信息的组合情况，具有3个结点的二叉树有5种形态，其中，只有一棵二叉树具有度数为2的结点（即为一棵有左、右子树的二叉树，一个根节点具有两个叶节点，共3个结点），其余4棵二叉树的度数均为1（没有一个根结点具有左、右子树）。

14.【答案】A。

【解析】深度为h且具有最大结点数目的二叉树被称为满二叉树，而深度为h的二叉树所具有的最大结点数为2h-1。

15.【答案】C。

【解析】根据二叉树的性质，具有2000个结点的非空二叉树的最小深度为log₂ 2000+1=11。

16.【答案】C。

【解析】第一次与数组下标为5的元素比较，不匹配；第二次与下标为8的元素比较，不匹配；第三次与下标为6的元素比较，匹配，查找成功。

17.【答案】C。

【解析】操作数(A5)₁₆即(10100101)₂进行一次算术右移后为(11010010)₂，再进行一次算术右移后为(11101001)₂，即(E9)₁₆，因此答案为C。

18.【答案】B。

【解析】根据二叉树产生的前序序列和中序序列可以唯一地恢复二叉树，原则是：在前序序列中确定根结点，到中序序列中分出根结点的左、右子树。因此本题先根据前序序列将二叉树恢复出来，然后对二叉树进行后序遍历，即可得到后序序列。

具体由前序序列“A,B,D,C,E,F,G”可以确定树的根结点A，在中序序列中以A为界，“D,B,C”是它的左子树中的结点，“F,E,G”是它的右子树中的结点；接下来，由前序序列确定每棵子树的根，再在中序序列中分出它的左、右子树中的结点，以此类推，故本题选B。

19.【答案】B。

【解析】根据计算哈夫曼树的带权路径长度的公式可算出：7×1+5×2+(2+4)×3=35。

20.【答案】A。

【解析】在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网，简称AOE图。用AOE图表示一项工程计划时，对于一项工程来说，一般有一个开始状态和一个结束状态，所以在AOE图中至少有一个入度为0的开始顶点，称其为源点。另外，应有一个出度为0的结束顶点，称其为汇点。AOE中不应存在有向回路，否则整个工程无法完成。从源点到汇点的路径中，长度最长的路径称为关键路径，所以应选A。

21.【答案】B。

【解析】栈的特点是后进先出，从此题可得出结论：像此种进出栈方法，如果某个数NUM后面存在K个比它小的数，那么这K个数出现的顺序一定是从大到小排序。（因为这K个数是从小到大进栈，并且它们出栈的顺序比NUM晚，所以它们一定是按从大到小的顺序出栈。）

进一个元素马上又出一个元素的出栈序列即为A；先进1、2、3、4，然后4出栈，再进5出5，然后出3、2、1，再进6出6就得到序列C；进1、2、3、4、5，然后出5，进6出6，然后依次出4、3、2、1就得到序列D。只有B中在6的后面有两个比6小的元素4和5，但是4和5在序列中按从小到大的顺序排列，这是不可能的，所以应选B。

22.【答案】（1）C；（2）C。

【解析】根据题意，已知一个线性表（38,25,74,63,52,48），根据散列函数H(Key)=Key mod 7和线性探测的开放定址法解决冲突所构造的哈希表如下表所示，那么等概率成功查找的平均查找长度ASL=(1+3+1+1+2+4)/6=2.0。

根据散列函数H(Key)=Key mod 7和拉链法解决冲突所构造的哈希表如下图所示，那么等概率成功查找的平均查找长度ASL=(1+1+1+1+2+2)/6=8/6=4/3。

所以（1）题答案为C，（2）题答案为C。

23.【答案】B。

【解析】考查数据结构中二叉树的基本概念。

根据二叉树的定义，一棵二叉树的每个结点至多有两棵子树，并且，二叉树的子树有左、右之分，其次序不能颠倒。

设任意一棵非空的二叉树中有两棵子树的结点的数目为n₂，有一棵子树的结点的数目为n₁，没有子树的数目为n₀。

若设这棵二叉树中的结点总数为n，那么有n=n₀+n₁+n₂。另外，再观察该二叉树的分支数，除了根结点外，其余结点都有且仅有一个分支进入，若令分支总数为B，则n=B+1。由于这些分支是由子树数目为1和子树数目为2的结点分出的，因此又有B=n₁+2n₂，于是又得到n=n₁+2n₂+1。

显然n=n₀+n₁+n₂=n₁+2n₂+1，因此n₀=n₂+1。

题目中给定的二叉树中不存在只有一棵子树的结点，所以整棵树中的结点数目为n₀+n₂个。由于n₀=n₂+1，因此树中结点数为2n₀-1个。

依据题意，题中m即是叶子结点的个数，故二叉树上的结点总数为2m-1。

24.【答案】B。

【解析】用n个二进制位表示带符号纯整数时，其中一个二进制位用于表示数的符号，习惯上用0表示正号，用1表示负号，而其余的n-1个二进制位则用来表示数值部分。一般形式如下图所示(n=16)。

n-1个二进制位可以表示出00…0～11…1共2n-1个不同数值，对应的十进制值记为0～2n-1-1，若再加上一个符号位，则可以表示的数据的取值范围为[-(2n-1-1),2n-1-1]。在补码表示中，0表示形式为100…0（n-1个0），其符号位上的1既表示该数为负数，又表示一位数值，因此可能表示出2n-1。所以，补码表示法中可以表示[-2n-1,2n-1-1]范围内的数据，超出该范围的数据是不能正确表示的。

已知[X]_补、[Y]_补，那么X和Y是[-2n-1,2n-1-1]区间的数据，而X+Y有可能超出该范围。例如，当n=16时，这个数据范围是[-32768,32767]，若X=32766，Y=2，那么X与Y的和为32768，运算所得结果为-32768，超出范围的数据是不能被正确表示的，如下所示：

[32766]_补=011111111111111110，[2]_补=0000000000000010

[32768]_补=011111111111111110+0000000000000010=1000000000000000

如果X与Y之和不超过这个表示范围，则运算结果可正确表示。

25.【答案】（1）C；（2）C。

【解析】海明码是由贝尔实验室的Richard Hamming设计的，它利用奇偶性进行校验和纠错。该校验码通过在数据位之间插入k个校验位来扩大数据编码的码距，从而不但可以检测出错误，还能纠正错误。

若要能纠正1位错误，k个校验位可以有2k个编码，其中一个编码用来表示数据无差错，剩余的2k-1个编码则可用来指示是哪一位数据出错了。由于n个数据位和k个校验位都可能出错，因此k必须满足：2k-1≥n+k。

海明码的编码规则是：设k个校验位为P_kP_k-1…P₁，n个数据位为D_n-1D_n-2…D₉，则产生的海明码为H_k+nH_k+n-1…H₁。其中，P_i在海明码的第2i-1位置，即P_i=H_j，j=2i-1；数据位则依次从低到高占据海明码中的剩余位置。

海明码中的任一位都是由若干个校验位来校验的，它的对应关系如下：被校验的海明位的下标等于所有参与校验位的下标之和，而校验位则由其自身来校验。因此：

D₉D₈D₇D₆D₅D₄P₄D₃D₂D₁P₃D₀P₂P₁=H₁₄H₁₃H₁₂H₁₁H₁₀H₉H₈H₇H₆H₅H₄H₃H₂H₁

故数据位D₉由校验位P₄、P₃和P₂校验，因为D₉海明码中的下标为14，P₄、P₃和P₂的下标之和为8+4+2=14。数据位D₈由校验位P₄、P₃和P₁校验，因为D₈在海明码中的下标为13，P₄、P₃和P₁的下标之和为8+4+1=13。

26.【答案】B。

【解析】

那么，

27.【答案】A。

【解析】本题目是将三对角矩阵进行压缩存储。三对角矩阵中第一行和最后一行中各有2个元素，其他行均有3个元素。矩阵元素a_ij以行为主序存储在一维数组中，则该矩阵元素存储在数组中的第k个位置，其对应关系是k=2(i-1)+j。注意，这里矩阵的行、列及数组的下标均从1开始。

28.【答案】B。

【解析】对于具有n个元素的线性表，采用顺序存储结构，可插入的位置共有n+1个。等概率下，在任何一个位置上插入的概率为，在第i(1≤i≤n+1)个位置插入需要移动的元素个数为n-i+1。平均移动元素的个数是各种插入情况下移动元素的数学期望（概率），即E_insert=。

29.【答案】C。

【解析】队列是一种先进先出（FIFO）的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾（rear），允许删除元素的一端称为队头（front）。

30.【答案】A。

【解析】本题要求插入和删除一个元素的运算时间都要最短。对于链表上的运算，首先要从链表的头指针或尾指针沿着指针方向顺序查找以确定插入或删除操作的位置，然后对指针进行修改来实现插入或删除操作，所以移动指针是花费时间的所在。若链表中有n个元素；对于“仅有尾指针的单向循环链表”，插入和删除一个元素需要的时间分别是O(1)和O(1)；对于“仅有头指针的单向循环链表”，所需的时间分别为O(n)和O(1)；对于“单向链表”，所需的时间也分别为O(n)和O(1)；对于“双向链表”，所需的时间同样分别为O(n)和O(1)。

31.【答案】D。

【解析】二维数组中元素可以用两种方式存储：以行为主序（按行存储）和以列为主序（按列存储）。对于一个m行n列的二维数组，当数组元素以行为主序存储时，先存储第一行上的所有元素，第二行上的元素存储在第一行的元素之后，第三行上的所有元素存储在第二行的元素之后，以此类推，第m行的元素存储在最后。每行上的元素按列下标从低到高依次存储。同理，以列为主序存储时，先存储第一列上的元素，然后是第二列上的元素，以此类推，最后是第n列上的元素。

设有二维数组A[L1..H1,L2..H2]，无论采用哪一种存储方式，都可以采用以下通式计算数组中元素A[i,j]在存储空间中的位置：

loc(A[i,j])=loc(A[L1,L2])+k×d

其中，k表示数组中存储在A[i,j]之前的元素数目，d表示每个数组元素占用的存储单元个数。当数组的元素以列为主序存储时，存储在A[i,j]之前的元素数目为

k=(i-L2)×(H1-L1+1)+(i-L1)

因此对于题目中定义的数组A[3..16，5..20]，A[i,j]（3≤i≤16，5≤j≤20）的地址计算公式为loc(A[i,j])=loc(A[L1,L2])+((j-5)×14+(i-3))×2=a-146+2i+28j。

32.【答案】A。

【解析】考查的是计算机数制转换方面的基础知识。十进制数254等值的二进制数是11111110。故答案为A。

33.【答案】B。

【解析】考查的是计算机数值运算方面的基础知识。

当两个无符号数相减时，若被减数小而减数大，肯定有借位。这时，进位标志CF会置1；反之，若被减数大而减数小，就不会有借位。这时，进位标志CF会清0。所以，当无符号数A减去无符号数B，它的结果为进位标志CF=1时，就表明A＜B。

34.【答案】A。

【解析】考查的是数据结构中线性表存储方面的基础知识。

线性表的链式存储是用结点来存储数据元素的，结点的空间可以是连续的，也可以是不连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。结点空间只在有需要的时候才动态申请，无须事先分配。最基本的结点结构如下所示：

其中，数据字段（或称为数据域）用于存储数据元素的值，指针字段则存储当前元素的直接前驱或直接后继信息，指针字段中的信息被称为指针（或链）。n个结点通过指针连成一个链表，若结点中只有一个指针字段，则称为线性链表（或单向链表）。

线性表采用链表作为存储结构时，不能进行数据元素的随机访问，它的优点是插入和删除操作不需要移动元素。与顺序存储相比，链表的缺点主要有两个：每个元素增加了一个后继指针字段，要占用更多存储空间；不便于随机地直接访问线性表的任一结点。

35.【答案】B。

【解析】考查的是数据结构方面的基础知识。

矩阵压缩存储是指为多个相同的非零元素分配一个存储空间，对零元素不分配存储空间。因此，这种方法可以节省大量的内存空间。

36.【答案】C。

【解析】考查的是数据结构中队列方面的基础知识。

队列是限定只能在表的一端进行插入，而在表的另一端进行删除操作的线性表。在队列中，我们把允许插入的一端称为队尾（rear），通过队尾指针指明队尾的位置；把允许删除的一端称为队头（front），通过队头指针指明队头的位置。队头指针和队尾指针将随着队列的动态变化而移动。

链表的末尾是队列的队尾结点，队尾结点的链接指针值为NULL。如果是带头结点的队列，则空队列的情形如图a所示；若是带头结点的循环队列，则空队列的情形如图b所示；若不带头结点，则空队列的情形如图c所示。因此，当front==rear时表示队列为空。

队列的链式存储结构（简称链式队列）是指队列中的各个数据元素独立存储，依靠指针链接建立相邻的逻辑关系。一个链式队列显然需要两个分别指向队头和队尾的指针（指向队头的指针称为头指针front，指向队尾的指针称为尾指针rear）才能唯一确定。这里，和线性表的单向链结构一样，也给链式队列添加一个头结点，并令头指针指向头结点。因此，空的链式队列判决条件为头指针和尾指针均指向头结点。

37.【答案】A。

【解析】选项A“字符串是一种特殊的线性表”和选项C“字符串不属于线性表的一种”是一对矛盾体，因此，分析时很容易想到正确答案应该在选项A和选项C中，而无须考虑选项B和选项D。根据学过的知识可知，字符串是一种特殊的线性表，是由某字符集上的字符所组成的任何有限字符序列。当一个字符串不包含任何字符时，称它为空字符串。仅由一个或多个空格组成的字符串称为空白串（Blank String）。空串和空白串不同。字符串通常存储于足够大的字符数组中。

38.【答案】C。

【解析】在树中，除了根结点外，其他的所有结点都是其父结点通过一条边连接出来的，所以设T=＜V,E＞为一棵树，|V|=n，|E|=m，则m=n-1。例如，5个结点和6个结点的树分别如图a、图b所示。由此可知，100个结点的树有99条边。

39.【答案】B。

【解析】栈是一种只能通过访问它的一端来实现数据存储和检索的线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO）或后进先出（LIFO）的线性表。栈的这种特征正好适用于函数嵌套调用的过程。

当调用函数时，系统将为调用者构造一个由参数表和返回地址等信息组成的活动记录，并将活动记录压入由系统提供的运行时栈的栈顶，然后将程序的控制权交给被调函数。若被调函数有局部变量，则在它的活动记录中还包括为局部变量分配的存储空间。当被调函数执行完毕，系统将运行时栈顶的活动记录弹出栈，并根据活动记录中保存的返回地址，将程序的控制权交给调用者。

40.【答案】A。

【解析】可以利用归纳法求解。由题可知，B[1]=T[(1-1)×n]，B[2]=T[(2-1)×n]，B[3]=T[(3-1)×n]，…，根据归纳法可得B[k]=T[(k-1)×n]。

41.【答案】C。

【解析】在试题中，递归函数f(n)的功能是解决1+2+3+…+n的累加问题，可用下面的递归公式表示f(n)。

因此可知，f(n)应采用的代码段为：

42.【答案】（1）C；（2）D。

【解析】定点整数原码的定义如下：

由定义可知，正整数的原码就是其自身，而负整数的原码只需把它的绝对值的原码的符号位置为1即可（0表示正号，1表示负号）。

因此，原码FFH的真值为：-1111111B=-127。

定点整数补码的定义如下：

由定义可知，正整数的补码就是其自身，负整数的补码可以通过对它的绝对值逐位求反，并在最低位加1求得，即求反加1。

可以把补码11111111B减1再取反（除符号位，其余按位取反）得原码100000001B，即-1。