数据结构（递归、数组、矩阵）练习题与答案

1、有一个三维数组A[-2..2][-4..5][2..6],其中元素个数是

()O

A.144

B.250

C.396

D.60

正确答案：B

解析：B、A的第1维长度为5,第2维长度为10,第3维长度为

5,元素个数=5义10X5=250。

2、设C/C++二维数组每个数组元素占用k个存储单元，

第一个数组元素的存储地址是L0C(a[0][0]),求按行优先顺序存放

的数组元素a[i][j](OWiWmT,OWjWnT)的存储地址为()。

A.LOC(a[O][O])+[(j-DXm+i-1]Xk

B.LOC(a[O][O])+[iXn+j]Xk

C.LOC(a[O][0])+[(i-l)Xn+j-1]Xk

D.LOC(a[O][O])+[jXm+i]Xk

正确答案：B

解析：B、a[i][j]前面有0~i-l行，计iXn个元素，第i行前

面有j个元素，则a[i][j]前面有iXm+j个元素，所以的

存储地址40(；6[0][O])+[iXn+j]Xko

3、设二维数组若按行优先的顺序存放数组的元素,

则a[4][6]元素的前面有()个元素。

A.6

B.40

C.28

D.29

正确答案：D

解析：D、m=5,n=8,a[4][6]元素的前面的元素个数=(4T)X

8+(6-l)=29o

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)X10+(5-0)=35o所以1000=L0C(a[0][0])+35X4,

LOC(a[0][0])=860o

5、一个n阶对称矩阵A采用压缩存储方式，将其下三角部分(含主

对角线元素)按行优先存储到一维数组B中，则B中元素个数是

()O

A.n(n+l)/2

B.n*n

C.n(n+l)/2+l

D.n

正确答案：A

6、一个n阶对称矩阵A[L.n,l..n]采用压缩存储方式，将其下三

角部分按行优先存储到一维数组中，则(i〈j)元

素在B中的位置k是()。

A.i(i-l)/2+j-l

B.j(j-l)/2+i-l

C.j(j-l)/2+i

D.i(i-l)/2+j

正确答案：C

解析：C、对于下三角部分或者主对角线元素它存储在

b[k]中，k=i(i-l)/2+jo对于上三角部分元素(i<j),对

应的k=j(j-D/2+i.

7、一个n阶上三角矩阵A按行优先顺序压缩存放在一维数组B,则

B中元素个数是()。

A.n

B.n*n

C.n(n+l)/2

D.n(n+l)/2+l

正确答案：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)的值是()o

A.1

B.2

C.3

D.4

正确答案：D

解析:f(2,l)=f(l,l)+f(2,0)=f(0,l)+f(l,0)+2=l+l+2=4o

13、某递归算法的执行时间的递推关系如下：

T(n)=l当n=l时

T(n)=T(n/2)+l当n>l时

则该算法的时间复杂度为()。

A.0(1)

B.0(log2n)

C.0(n)

D.0(nlog2n)

正确答案：B

解析：不妨设n=2~k,k=log2no

T(n)=T(n/2)+1=T(n/2"2)+2=-**=T(n/2"k)+k=T(1)+1og2n=0(1og2n)0

14、某递归算法的执行时间的递推关系如下：

T(n)=l当n=l时

T(n)=2T(n/2)+l当n>l时

则该算法的时间复杂度为()。

A.0(1)

B.0(log2n)

C.0(n)

D.0(nlog2n)

正确答案：C

解析：不妨设n=2~k,k=log2n0

T(n)=21*T(n/21)+1=2-2*T(n/2^2)