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.2h-1
B.2h
C.2h-1
D.2h
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)16进行两位算术右移的结果是______。
A.(D2)16
B.(52)16
C.(E9)16
D.(69)16
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.2m+1
B.2m-1
C.2(m-1)
D.2(m+1)
24.用n个二进制位表示带符号纯整数时，已知[X]补、[Y]补，则当______时，等式[X]补+[Y]补=[X+Y]补成立。
A.-2n≤(X+Y)≤2n-1
B.-2n-1≤(X+Y)＜2n-1
C.-2n-1≤(X+Y)≤2n-1
D.-2n-1≤(X+Y)＜2n
25.对于16位的数据，需要（1）个校验位才能构成海明码。
在某个海明码的排列方式D9D8D7D6D5D4P4D3D2D1P3D0P2P1中，Di(0≤i≤9)表示数据位，Pj(1≤j≤4)表示校验位，数据位D8由（2）进行校验。
（1）A.3
B.4
C.5
D.6
（2）A.P4P2P1
B.P4P3P2
C.P4P3P1
D.P3P2P1
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+2i+28j
B.a-116+2i+28j
C.a-144+2i+28j
D.a-146+2i+28j
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