數(shù)據(jù)結(jié)構(gòu)（遞歸、數(shù)組、矩陣）練習(xí)題與答案

1、有一個(gè)三維數(shù)組A[-2..2][-4..5][2..6],其中元素個(gè)數(shù)是

()O

A.144

B.250

C.396

D.60

正確答案：B

解析：B、A的第1維長度為5,第2維長度為10,第3維長度為

5,元素個(gè)數(shù)=5義10X5=250。

2、設(shè)C/C++二維數(shù)組每個(gè)數(shù)組元素占用k個(gè)存儲單元，

第一個(gè)數(shù)組元素的存儲地址是L0C(a[0][0]),求按行優(yōu)先順序存放

的數(shù)組元素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行，計(jì)iXn個(gè)元素，第i行前

面有j個(gè)元素，則a[i][j]前面有iXm+j個(gè)元素，所以的

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

3、設(shè)二維數(shù)組若按行優(yōu)先的順序存放數(shù)組的元素,

則a[4][6]元素的前面有()個(gè)元素。

A.6

B.40

C.28

D.29

正確答案：D

解析：D、m=5,n=8,a[4][6]元素的前面的元素個(gè)數(shù)=(4T)X

8+(6-l)=29o

4、設(shè)C/C++二維數(shù)組a[6][10],每個(gè)數(shù)組元素占用4個(gè)存儲單元，

若按行優(yōu)先順序存放所有數(shù)組元素，a[3][5]的存儲地址為1000,

則a[0][0]的存儲地址是()。

A.864

B.868

C.860

D.872

正確答案：C

解析：C、C/C++二維數(shù)組下標(biāo)從0開始。a[3][5]前面的元素個(gè)數(shù)

=(3-0)X10+(5-0)=35o所以1000=L0C(a[0][0])+35X4,

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

5、一個(gè)n階對稱矩陣A采用壓縮存儲方式，將其下三角部分(含主

對角線元素)按行優(yōu)先存儲到一維數(shù)組B中，則B中元素個(gè)數(shù)是

()O

A.n(n+l)/2

B.n*n

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

D.n

正確答案：A

6、一個(gè)n階對稱矩陣A[L.n,l..n]采用壓縮存儲方式，將其下三

角部分按行優(yōu)先存儲到一維數(shù)組中，則(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),對

應(yīng)的k=j(j-D/2+i.

7、一個(gè)n階上三角矩陣A按行優(yōu)先順序壓縮存放在一維數(shù)組B,則

B中元素個(gè)數(shù)是()。

A.n

B.n*n

C.n(n+l)/2

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

正確答案：D

8、一個(gè)n(n>3)階三對角矩陣A按行優(yōu)先順序壓縮存放在一維數(shù)組B,

則B中元素個(gè)數(shù)是()。

A.n*n

B.3n-2

C.3n

D.2n

正確答案：B

9、稀疏矩陣常用的壓縮存儲方法有()。

A.哈希表和十字鏈表

B.二維數(shù)組

C.三元組和哈希表

D.三元組和十字鏈表

正確答案：D

10、稀疏矩陣采用壓縮存儲后的缺點(diǎn)之一是()。

A.無法由行、列值查找某個(gè)矩陣元素

B.使矩陣元素之間的邏輯關(guān)系更加復(fù)雜

C.無法判斷矩陣的行列數(shù)

D.喪失隨機(jī)存取特性

正確答案：D

11、一個(gè)正確的遞歸算法通常包含()。

A.遞歸出口

B.遞歸體

C.遞歸出口和遞歸體

D.以上都不包含

正確答案：C

解析：正確的遞歸算法應(yīng)包含遞歸出口和遞歸體兩部分，缺一不可。

12、遞歸函數(shù)f(x,y)定義如下：

f(x,y)=f(x-1,y)+f(x,y-1)當(dāng)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、某遞歸算法的執(zhí)行時(shí)間的遞推關(guān)系如下：

T(n)=l當(dāng)n=l時(shí)

T(n)=T(n/2)+l當(dāng)n>l時(shí)

則該算法的時(shí)間復(fù)雜度為()。

A.0(1)

B.0(log2n)

C.0(n)

D.0(nlog2n)

正確答案：B

解析：不妨設(shè)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、某遞歸算法的執(zhí)行時(shí)間的遞推關(guān)系如下：

T(n)=l當(dāng)n=l時(shí)

T(n)=2T(n/2)+l當(dāng)n>l時(shí)

則該算法的時(shí)間復(fù)雜度為()。

A.0(1)

B.0(log2n)

C.0(n)

D.0(nlog2n)

正確答案：C

解析：不妨設(shè)n=2~k,k=log2n0

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