数据结构（递归、数组、矩阵）练习题与答案
1、有一个三维数组A[-2..2][-4..5][2..6]，其中元素个数是
（）。
A.144
B.250
C.396
D.60
正确答案：B
解析： B、A的第1维长度为5，第2维长度为10，第3维长度为5，元素个数=5×10×5=250。
2、设C/C++二维数组a[m][n]，每个数组元素占用k个存储单元，
第一个数组元素的存储地址是LOC(a[0][0])，求按行优先顺序存放
的数组元素a[i][j]（0≤i≤m-1，0≤j≤n-1）的存储地址为（）。
A.LOC(a[0][0])+[(j-1)×m+i-1]×k
B.LOC(a[0][0])+[i×n+j]×k
C.LOC(a[0][0])+[(i-1)×n+j-1]×k
D.LOC(a[0][0])+[j×m+i]×k
正确答案：B
解析： B、a[i][j]前面有0～i-1行，计i×n个元素，第i行前
面有j个元素，则a[i][j]前面有i×m+ j个元素，所以a[i][j]的
存储地址=LOC(a[0][0])+[i×n+j]×k。
3、设二维数组a[1..5][1..8]，若按行优先的顺序存放数组的元素，则a[4][6]元素的前面有（）个元素。
A.6
B.40
C.28
D.29
正确答案：D
解析： D、m=5，n=8，a[4][6]元素的前面的元素个数=(4-1) ×8+(6-1)=29。
数组和链表
4、设C/C++二维数组a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放所有数组元素，a[3][5]的存储地址为1000，则a[0][0]的存储地址是（）。
A.864
B.868
C.860
D.872
正确答案：C
解析： C、C/C++二维数组下标从0开始。a[3][5]前面的元素个数=(3-0)×10+(5-0)=35。所以1000=LOC(a[0][0])+35×4，
LOC(a[0][0])=860。
5、一个n阶对称矩阵A采用压缩存储方式，将其下三角部分（含主对角线元素）按行优先存储到一维数组B中，则B中元素个数是（）。
A.n(n+1)/2
B.n*n
C.n(n+1)/2+1
D.n
正确答案：A
6、一个n阶对称矩阵，1..n]采用压缩存储方式，将其下三
角部分按行优先存储到一维数组]中，则A[i][j]（i<j）元< p="">
素在B中的位置k是（）。
A.i(i-1)/2+j-1
B.j(j-1)/2+i-1
C.j(j-1)/2+i
D. i(i-1)/2+j
正确答案：C
解析： C、对于下三角部分或者主对角线元素a[i][j]，它存储在
b[k]中，k=i(i-1)/2+j。对于上三角部分元素A[i][j]（i<j），对< p="">
应的k=j(j-1)/2+i。
7、一个n阶上三角矩阵A按行优先顺序压缩存放在一维数组B，则
B中元素个数是（）。
A.n
B.n*n
C.n(n+1)/2
D.n(n+1)/2+1
正确答案：D
8、一个n(n>3)阶三对角矩阵A按行优先顺序压缩存放在一维数组B，则B中元素个数是（）。
A.n*n
B.3n-2
C.3n
D.2n
正确答案：B
9、稀疏矩阵常用的压缩存储方法有（）。
A.哈希表和十字链表
B.二维数组
C.三元组和哈希表
D.三元组和十字链表
正确答案：D
10、稀疏矩阵采用压缩存储后的缺点之一是（）。
A.无法由行、列值查某个矩阵元素
B.使矩阵元素之间的逻辑关系更加复杂
C.无法判断矩阵的行列数
D.丧失随机存取特性
正确答案：D
11、一个正确的递归算法通常包含（）。
A.递归出口
B.递归体
C.递归出口和递归体
D.以上都不包含
正确答案：C
解析：正确的递归算法应包含递归出口和递归体两部分，缺一不可。
12、递归函数f(x，y)定义如下：
f(x，y)=f(x-1，y)+f(x，y-1) 当x>0且y>0
f(x，y)=x+y 否则
则f(2，1)的值是（）。
A.1
B.2
C.3
D.4
正确答案：D
解析： f(2,1)=f(1,1)+f(2,0)=f(0,1)+f(1,0)+2=1+1+2=4。
13、某递归算法的执行时间的递推关系如下：
T(n)=1 当n=1时
T(n)=T(n/2)+1 当n>1时
则该算法的时间复杂度为（）。
A. O(1)
B. O(log2n)
C. O(n)
D. O(nlog2n)
正确答案：B
解析：不妨设n=2^k，k=log2n。
T(n)=T(n/2)+1= T(n/2^2)+2=…= T(n/2^k)+k=T(1)+log2n=O(log2n)。
14、某递归算法的执行时间的递推关系如下：
T(n)=1 当n=1时
T(n)=2T(n/2)+1 当n>1时
则该算法的时间复杂度为（）。
A. O(1)
B. O(log2n)
C. O(n)
D. O(nlog2n)
正确答案：C
解析：不妨设n=2^k，k=log2n。
T(n)=2^1*T(n/2^1)+1=2^2*T(n/2^2)+1+2^1=…
=2^kT(n/2^k)+1+2^1+…+2^(k-1)=2^k T(1)+2^k-1=2n-1=O(n)。
15、将递归算法转换成非递归算法时，通常要借助的数据结构是（）。
A.线性表
B.栈
C.队列
D.树
正确答案：B
解析：递归算法转换成非递归算法时通常使用栈。
</j），对<>
</j）元<>

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。