1.3 难点精练

本节针对重难知识点进行模拟练习并讲解，强化重难知识点及题型。

1.3.1 重难点练习

1.二进制数11001100为原码的时候，它代表的真值为 （1） ；若它是补码，则它代表的真值为 （2） ；十进制数-1的补码用8位二进制数表示为 （3） 。

（1）A.204

B.-76

C.-204

D.76

（2）A.-52

B.-20

C.19

D.148

（3）A.0000001

B.10000001

C.1111110

D.1111111

2.设 X 为逻辑变量，下列逻辑运算中，不正确的是______。

A. X ·1= X

B. X +1= X

C. X ·0=0

D. X +0= X

3.以下序列不是堆的是______。

A.{100，85，98，77，80，60，82，40，20，10，66}

B.{100，98，85，82，80，77，66，60，40，20，10}

C.{10，20，40，60，66，77，80，82，85，98，100}

D.{100，85，40，77，80，60，66，98，82，10，20}

4.对于关键码序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为______的关键码开始。

A.18

B.60

C.15

D.100

5.下列逻辑不正确的是______。

A.1+1=2

B.1+0=1

C.0+0=0

D.1+A=1

6.堆栈和队列的相同之处是______。

A.元素的进出满足先进后出

B.元素的进出满足后进先出

C.只允许在端点进行插入和删除操作

D.无共同点

7.在解决计算机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区取出数据打印，该缓冲区应是一个______结构。

A.线性表

B.数组

C.堆栈

D.队列

8.在浮点数编码表示中，______在机器数中不出现，是隐含的。

A.阶码

B.符号

C.尾数

D.基数

9.十进制数33用十六进制数表示为______。

A.33H

B.21H

C.FFH

D.12H

10.对于卡诺图，下列说法正确的是______。

A.卡诺图是用来化简逻辑表达式的有效手段

B.卡诺图化简逻辑表达式时，只能合并卡诺图中的1

C.卡诺图化简逻辑表达式时，只能合并卡诺图中的0

D.卡诺图能减少逻辑错误

11.8个二进制位至多表示______个数据。

A.8

B.64

C.255

D.256

12.关系演算的基础是______。

A.形式逻辑中的逻辑演算

B.形式逻辑中的关系演算

C.数理逻辑中的谓词演算

D.数理逻辑中的形式演算

13.按照二叉树的定义，具有3个结点的树有______种形态（不考虑数据信息的组合情况）。

A.2

B.3

C.4

D.5

14.深度为 h 且有______个结点的二叉树称为满二叉树。

A.2 ^h -1

B.2 h

C.2 ^{h -1}

D.2 ^h

15.具有2000个结点的非空二叉树的最小深度为______。

A.9

B.10

C.11

D.12

16.将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中，然后采用折半查找方法查找数组元素12，被比较过的数组元素的下标依次为______。

A.10,16,12

B.10,12,16

C.5,8,6

D.5,6,8

17.对8位补码操作数(A5) ₁₆ 进行两位算术右移的结果是______。

A.(D2) ₁₆

B.(52) ₁₆

C.(E9) ₁₆

D.(69) ₁₆

18.二叉树的前序遍历序列为 A , B , D , C , E , F , G ，中序遍历序列为 D , B , C , A , F , E , G ，它的后序遍历序列为______。

A. D , C , F , G , E , B , A

B. D , C , B , F , G , E , A

C. F , G , E , D , C , B , A

D. D , C , F , G , B , E , A

19.与一组权值（7,5,2,4）对应的哈夫曼树的带权路径长度为______。

A.25

B.35

C.45

D.55

20.在AOE图中，关键路径是______。

A.从源点到汇点的最长路径

B.从源点到汇点的最短路径

C.最长的回路

D.最短的回路

21.现在6个元素按1,2,3,4,5,6的顺序进栈，序列______是不可能的出栈序列。

A.1,2,3,4,5,6

B.3,2,1,6,4,5

C.4,5,3,2,1,6

D.5,6,4,3,2,1

22.已知一个线性表（38,25,74,63,52,48），采用的散列函数（哈希函数）为 H (Key)=Key mod 7，将元素散列到表长为7的哈希表中存储。若采用线性探测的开放定址法解决冲突，则在该哈希表上进行等概率成功查找的平均查找长度为 （1） ；若利用拉链法解决冲突，则在该哈希表上进行等概率成功查找的平均查找长度为 （2） 。

（1）A.1.5

B.1.7

C.2.0

D.2.3

（2）A.1.0

B.7/6

C.4/3

D.3/2

23.设某二叉树有如下特点：结点的子树数目若不是2个，则为0个。这样的一棵二叉树中有 m ( m ＞0)个子树为0的结点时，该二叉树上的结点总数为______。

A.2 m +1

B.2 m -1

C.2( m -1)

D.2( m +1)

24.用 n 个二进制位表示带符号纯整数时，已知[ X ] _补 、[ Y ] _补 ，则当______时，等式[ X ] _补 +[ Y ] _补 =[ X + Y ] _补 成立。

A.-2 ⁿ ≤( X + Y )≤2 ⁿ -1

B.-2 ^{n -1} ≤( X + Y )＜2 ^{n -1}

C.-2 ^{n -1} ≤( X + Y )≤2 ^{n -1}

D.-2 ⁿ -1≤( X + Y )＜2 ⁿ

25.对于16位的数据，需要 （1） 个校验位才能构成海明码。

在某个海明码的排列方式 D ₉ D ₈ D ₇ D ₆ D ₅ D ₄ P ₄ D ₃ D ₂ D ₁ P ₃ D ₀ P ₂ P ₁ 中， D _i (0≤ i ≤9)表示数据位， P _j (1≤ j ≤4)表示校验位，数据位 D ₈ 由 （2） 进行校验。

（1）A.3

B.4

C.5

D.6

（2）A. P ₄ P ₂ P ₁

B. P ₄ P ₃ P ₂

C. P ₄ P ₃ P ₁

D. P ₃ P ₂ P ₁

26.( ) S =______。

A.

B.

C.

D.

27.将一个三对角矩阵 A [1..100,1..100]中的元素按行存储在一维数组 B [1..298]中，矩阵 A 中的元素 A [66,65]在数组 B 中的下标为______。

A.195

B.196

C.197

D.198

28.给定一个有 n 个元素的线性表。若采用顺序存储结构，则在等概率前提下，向其插入一个元素需要移动的元素个数平均为______。

A. n +1

B.

C.

D. n

29.______是线性结构的数据结构。

A.列表

B.高维数组

C.双端队列

D.二叉树

30.某线性表最常用的运算是插入和删除，插入运算是指在表尾插入一个新元素，删除运算是指删除表头第一个元素，那么采用______存储方式最节省运算时间。

A.仅有尾指针的单向循环链表

B.仅有头指针的单向循环链表

C.单向链表

D.双向链表

31.设数组 A [3..16,5..20]的元素以列为主序存放，每个元素占用两个存储单元，数组空间的起始地址为 a ，则数组元素 A [ i , j ]（3≤ i ≤16，5≤ j ≤20）的地址计算公式为______。

A. a -118+2 i +28 j

B. a -116+2 i +28 j

C. a -144+2 i +28 j

D. a -146+2 i +28 j

32.与十进制数254等值的二进制数是______。

A.11111110

B.11101111

C.11111011

D.11101110

33.无符号数 A 减去无符号数 B ，结果的进位标志为1表明______。

A. A ≥ B

B. A ＜ B

C. A = B

D. A ＞ B

34.链表不具备的特点是______。

A.可随机访问任何一个元素

B.插入、删除操作不需要移动元素

C.不需要先估计存储空间的大小

D.所需存储空间与线性表长度成正比

35.对矩阵压缩存储的主要目的是______。

A.方便运算

B.节省存储空间

C.降低计算复杂度

D.提高运算速度

36.判断“链式队列为空”的条件是______。（front为头指针，rear为尾指针。）

A.front==NULL

B.rear==NULL

C.front==rear

D.front!=rear

37.以下关于字符串的判定语句中正确的是______。

A.字符串是一种特殊的线性表

B.字符串的长度必须大于零

C.字符串不属于线性表的一种

D.空格字符组成的字符串就是空串

38.在具有100个结点的树中，其边的数目为______。

A.101

B.100

C.99

D.98

39.在程序的执行过程中，用______结构可实现嵌套调用函数的正确返回地址。

A.队列

B.栈

C.树

D.图

40.已知有一维数组 T [0… m × n -1]，其中 m ＞ n 。从数组 T 的第一个元素( T [0])开始，每隔 n 个元素取出一个元素依次存入数组 B [1… m ]中，即 B [1]= T [0]， B [2]= T [ n ]，以此类推，那么放入 B [ k ]（1≤ k ≤ m ）的元素是______。

A. T [( k -1)× n ]

B. T [ k × n ]

C. T [( k -1)× m ]

D. T [ k × m ]

41.已知递归函数 f ( n )的功能是计算1+2+…+ n ，且 n ≥1，应采用的代码段是______。

A.if n＞1 then return1 else return n+f(n-1)

B.if n＞1 then return1 else return n+f(n+1)

C.if n＜1 then return0 else return n+f(n-1)

D.if n＜1 then return0 else return n+f(n+1)

42.若码值FFH是一个整数的原码表示，则该整数的真值为 （1） ；若码值FFH是一个整数的补码表示，则该整数的真值为 （2） 。

（1）A.127

B.0

C.-127

D.-1

（2）A.127

B.0

C.-127

D.-1

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 _{2 i} 且 k _i ≥ k _{2 i +1} 或 k _i ≤ k _{2 i} 且 k _i ≤ k _{2 i +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。

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

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

12.【答案】C。

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

13.【答案】D。

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

14.【答案】A。

【解析】深度为 h 且具有最大结点数目的二叉树被称为满二叉树，而深度为 h 的二叉树所具有的最大结点数为2 ^h -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 ₁ +2 n ₂ ，于是又得到 n = n ₁ +2 n ₂ +1。

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

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

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

24.【答案】B。

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

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

已知[ X ] _补 、[ Y ] _补 ，那么 X 和 Y 是[-2 ^{n -1} ,2 ^{n -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 个校验位可以有2 ^k 个编码，其中一个编码用来表示数据无差错，剩余的2 ^k -1个编码则可用来指示是哪一位数据出错了。由于 n 个数据位和 k 个校验位都可能出错，因此 k 必须满足：2 ^k -1≥ n + k 。

海明码的编码规则是：设 k 个校验位为 P _k P _{k -1} … P ₁ ， n 个数据位为 D _{n -1} D _{n -2} … D ₉ ，则产生的海明码为 H _{k + n} H _{k + n -1} … H ₁ 。其中， P _i 在海明码的第 2 ⁱ -1位置，即 P _i = H _j ， j =2 ⁱ -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 [ L 1.. H 1, L 2.. H 2]，无论采用哪一种存储方式，都可以采用以下通式计算数组中元素 A [ i , j ]在存储空间中的位置：

loc( A [ i , j ])=loc( A [ L 1, L 2])+ k × d

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

k =( i-L 2)×( H 1 -L 1+1)+( i-L 1)

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

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。 78lrBp0AxqsT17ML7B2w01zkWPSp0UVScRTrYerKLuKhgohVyZJj2UN96q9uXVJr