全国自考数据结构导论（绪论）模拟试卷1

28． 求两个n阶矩阵的乘法C=A×B，其算法如下：

void maXtrixmult(int n，floata[N][N]，b[N][N]，float c[N][N])

   {

   int i，J，k；

   float X：

   for(i=1；i＜=nji++)   ①

   {

   for(j=1;j＜=n；j++)   ②

   {

   x=0；   ③

   for(k=1；k＜=n；k++)   ④

   X+=a[i][k]*b[k][J]；   ⑤

   c[i][j]=x；   ⑥

   }

   }

   }

分析该算法的时间复杂度。

27． 指出下列各算法的时间复杂度。

(1)prime(int n)   ／*n为一个正整数*／

   {

   int i=2：

   while((n%i)!=0&&i*1．0＜sqrt(n))i++;

   if(i*1．0＞sqrt(n))

   print f(”％d是一个素数＼n”，n);

   else

   print f(”％d不是一个素数＼n”，n);

   }

 (2)s uml (int n)   ／*n为一个正整数*／

   {

   int P=1，sum=0，i；

for(i=1；i＜=n；i++)

   {

   P*=i；

   sum+=p；

   }

   return(sum)；

 }

(3)sum2(int n)   ／*n为一个正整数*／

 {

   int sum=0，i，j；

   for(i=1；i＜=n；i++)

   {

   P=1；

   for(j=l;j＜=i;j++)P*=j；

   sum+=p；

   }

   return(sum)；

 }

26． 有如下递归函数fact(n)，分析其时间复杂度。

fact(int n)

{

if(n＜=1)return(1)；   ①

   elsereturn(n*fact(n一1))； ②

   }

24． 设有数据逻辑结构为：

B=(K，R) K={k1，k2，…，k9} 

R={，，，，，，，，，，} 

画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点?

23． 运算与运算的实现是什么关系?有哪些相同点和不同点?

25． 设有如下图所示的逻辑结构，给出它的逻辑结构。

22． 逻辑结构与存储结构是什么关系?

21． 为什么说数据元素之间的逻辑关系是数据内部组织的主要方面?

20． 数据与数据元素有何区别?

19． 下面程序段的时间复杂度是______。

i=s=0;

while(s＜n) { 

i++；  ／*i=i+1*／

s+=i；  /*s=s+i*/ 

}

18． 下面程序段的时间复杂度是________。

for(i=0；i＜n;i++)

for(j=0；j＜m;j++) 

A[i][j]=0;

16． 常见时间复杂度有：常数阶O(____)、线性阶O(____)、对数阶O(______)、平方阶O(________)和指数阶O(_______)。通常认为，具有______量级的算法是好算法，而具有______量级的算法是差算法。

17． 以下时间复杂度由大到小的排列次序为_______。 2ⁿ⁺²(n+2)! (n+2)⁴100 000 nlog₂n

14． 线性结构中元素之间存在_________关系，树形结构中元素之间存在_________关系，图形结构中元素之间存在________关系。

15． 在一般情况下，一个算法的时间复杂度是_______的函数。

13． 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是______、_________和_______。

12． 常见的数据存储结构一般有四种类型，它们分别是________、_______、______和________。

11． 数据元素是数据的______，数据项是数据的__________。

9． 有实现同一功能的四个算法F1、F2、鹞和F4，其中F1的时间复杂度为T1=O(2ⁿ)，F2的时间复杂度为T2=O(n²)，F3的时间复杂度为T3=O(log₂n)，F4的时间复杂度为T4=O(n!)。仅从时间复杂度来看，较好的算法是_______。

10． 所谓数据的逻辑结构指的是数据元素之间的______。

8． 分析下列程序段的时间复杂度是______。

i=1;

while(i<=n)

i=i*2;

7． 以下有关抽象数据类型的描述中，正确的是________。

6． 算法是指________。

4． 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_______。

5． 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着_______。

1． 以下说法中，正确的是________。

3． 在数据结构中，从逻辑上可以把数据结构分成_____。

2． 以下不属于数据的逻辑结构的是_______。