15 特殊矩阵
选择题
（1） 对特殊矩阵采用压缩存储的目的主要是为了（ ）。 A．表达变得简单 B．对矩阵元素的存取变得简单 C．去除矩阵中的多余元素 D．减少不必要的存储空间
（2） 下面（ ）不属于特殊矩阵。 A．对角矩阵 B．三角矩阵 C．稀疏矩阵 D．对称矩阵
（3） 一个n×n的对称矩阵，如果以行或列为主序放入内存，则需要（ ）个存
储单元。 A．n(n+1)/2 B．n(n-1)/2 C．n2 D．n2/2
（4） 设A[n，n]是对称矩阵，将其下三角（包括对角线）按行序存储到一维数组
T[n(n+1)/2]中，则上三角元素A[i][j]对应T[k]的下标k是（ ）。 A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1
（5） 设有一个n行n列的对称矩阵A将其下三角部分按行存放在一维数组B中，
A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ ）处。 A．(i+3)*i/2 B．(i+1)*i/2 C．(2n-i+1)*i/2 D．(2n-i-1)*i/2
（6） 若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中。
则存放到B[k]中的非零元素ai,j（1≤i，j≤n）的下标i，j与k的对应关系是（ ）。 A．(i+1)*i/2+j B．(i+1)*i/2+j-1 C．(j+1)*j/2+i D．(j-1)*j/2+i-1
（7） 若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中。
则存放到B[k]中的非零元素ai,j（1≤i，j≤n）的下标i，j与k的对应关系是（ ）。 A．(j-1)(2n-j+1)/2+i-j B．(j-1)(2n-j+2)/2+i-j+1 C．(j-1)(2n-j+2)/2+i-j D．(j-1)(2n-j+2)/2+i-j+1
（8） 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，
则A中元素A66,65在B数组中的位置k为（ ）。 A．198 B．195 C．197 D．196
应用题
（9） 对于一个n行m列的上三角矩阵A，如果以行优先的方式用一维数组B从0
号位置开始存储，求元素ai,j（1≤i≤n，1≤j≤m）在数组B中的存储位置。
（10） 设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐
行存于数组B[3n-2]中，使得B[k]=ai,j，求： ①用i，j表示k的下标变换公式； ②用k表示i，j的下标变换公式。
31
（11） 设有五对角矩阵B=(ai,j)20×20，按特殊矩阵压缩存储的方式将其五条对角线上的
元素存于数组A[-10..m]中，计算元素B[15][16]在数组A中的存储位置。
挑战题
（12） 对于给定的数组a[n][2n-1]，将3个顶点分别为a[0][n-1]、a[n-1][0]和a[n-1][2n-2]
的三角形上的所有元素按行序存放在一维数组B[n×n]中，且元素a[0][n-1]存放在B[0]中。例如当n=3时，数组a[3][5]中三角形如图所示。如果位于三角形上的元素a[i][j]存放于B[k]中，请给出元素a[i][j]的下标i，j和k的对应关系。 a00 a10
a01
a20
a11 a21
a02 a12 a22
a03 a13 a04 a14
a23 a24
（13） 设A和B均为n阶下三角矩阵，另有一个n行n+1列的二维数组C，设计一
个方案将两个矩阵A和B压缩存储于同一个数组C中，并给出A的矩阵元素ai,j和B的矩阵元素bi,j在数组C中的存放位置。
32
16 查找的基本概念
选择题
（1） 静态查找与动态查找的根本区别在于（ ）。 A．它们的逻辑结构不一样 B．施加在其上的操作不同 C．所包含的数据元素的类型不一样 D．存储实现不一样
（2） 以下（ ）方法适合动态查找。 A．顺序查找 B．折半查找 C．散列查找 D．随机查找
（3） 能够实现动态查找的数据结构是（ ）。 A．有序表 B．双链表 C．循环链表 D．二叉排序树
（4） 平均查找长度与查找集合中记录个数n无关的查找方法是（ ）。A．折半查找 B．平衡二叉树的查找 C．散列查找 D．不存在
（5） 在以下数据结构中，（ ）查找效率最低。 A．有序顺序表 B．二叉排序树 C．堆 D．散列表
33
17 顺序查找
选择题
（1） 对线性表进行顺序查找，要求线性表的存储结构为（ ）。 A．散列存储 B．顺序存储 C．链接存储 D．顺序存储或链接存储
（2） 用顺序查找方法在长度为n的线性表中进行查找，在等概率情况下，查找成功
的平均查找长度为（ ）。 A．n B．n/2 C．(n-1)/2 D．(n+1)/2
（3） 假定查找成功与不成功的可能性相同，在查找成功的情况下每个记录的查找概
率相同，则顺序查找的平均查找长度为（ ）。 A．0.5(n+1) B．0.25(n+1) C．0.5(n-1) D．0.75n+0.25
34
18 折半查找
选择题
（1） 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找
与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（ ）；在查找不成功的情况下，s和b的关系是（ ）。 A．s=b B．s>b C．s
（2） 长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，
查找成功的平均长度是（ ），查找失败时的平均查找长度是（ ）。 A．37/12 B．62/13 C．39/12 D．49/13
（3） 已知一个有序表为{12，18，24，35，47，50，62，83，90，115，134}，当折
半查找值为90的元素时，经过（ ）次比较后查找成功。 A．2 B．3 C．4 D．5
（4） 折半查找判定树不属于（ ）。 A．平衡二叉树 B．二叉排序树 C．完全二叉树 D．二叉树
（5） 当n足够大时，在有序顺序表中进行折半查找，假设顺序表中每个元素的查找
概率相同，则查找成功的平均查找长度为（ ）。 A．(n+1)/2 B．n/2 C．log2(n+1)-1 D．log2(n+1)
（6） 对表长为n的有序表进行折半查找，其判定树的高度为（ ）。 A．log2(n+1) B．log2(n+1)-1 C．log2n D．log2(n-1)
（7） 对100个元素进行折半查找，在查找成功的情况下，比较次数最多是（ ）。 A．25 B．50 C．10 D．7
（8） 对具有14个元素的有序表R[]14]进行折半查找，查找R[3]时比较需要比较
（ ）。
A．R[0]R[1]R[2]R[3] B．R[6]R[2]R[4]R[3] C．R[0]R[13]R[2]R[3] D．R[6]R[4]R[2]R[3]
（9） 对有序表A[1..17]进行折半查找，则查找长度为5的元素下标依次是（ ）。 A．8，17 B．5，10，12 C．9，16 D．9，17
应用题
（10） 画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查
找长度。
（11） 对长度为2k-1的有序表进行折半查找，查找成功的情况下最多需要比较多少
次？查找失败的情况下需要比较多少次？
35