数据结构-绪论-练习题

1. 算法分析的目的是( )。

A. 找出数据结构的合理性 B.研究算法的输入/输出关系 

C.分析算法的效率以求改进 D.分析算法的易读性

答案：C

2. 什么是数据? 它与信息是什么关系?

什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。

什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大 楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。

3. 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种结构。

（1）A=（K，R），其中：

K={a，b，c，d，e，f，g}

R={r}

r={〈a，b〉，〈b，c〉，〈c，d〉，〈d，e〉，〈e，f〉，〈f，g〉}

（2）B=（K，R），其中：

K={a，b，c，d，e，f，g，h}

R={r}

r={〈d，b〉，〈d，g〉，〈d，a〉，〈b，c〉，〈g，e〉，〈g，h〉，〈a，f〉}

（3）C=（K，R），其中：

K={1，2，3，4，5，6}

R={r}

r={（1，2），（2，3），（2，4），（3，4），（3，5），（3，6），（4，5），（4，6）}

这里的圆括号对表示两结点是双向的。

解：

（1）A对应逻辑图形如下，它是一种线性结构。

（2）B对应逻辑图形如下，它是一种树形结构。

（3）C对应逻辑图形如下，它是一种图形结构。

4. 分析以下程序段的时间复杂度。

a=0；b=1；①

for（i=2；i〈=n；i++）②

{s=a+b；③

 b=a；④

 a=S；⑤

}

解：

因为，语句①的频度是2；

语句②的频度是n；

语句③的频度是n-1；

语句④的频度是n-1；

语句⑤的频度是n-1；

故，该程序段的时间复杂度T（n）=2+n+3*（n-1）=4n-1=O（n）。

5. 分析以下程序段的时间复杂度。

inti，j，k；

For（i=0；i〈n；i++〉①

For（j=0；j〈n；j++〉②

{

c[i][j]=0；③

for（k=0；k〈n；k++〉④

c[i][j]=c[i][j]+a[i][k]+b[k][j]；⑤

}

解：

语句①的循环控制变量i要增加到n，测试到i=n成立才会终止，故它的频度为n+1；

语句②作为语句①循环体内的语句应该执行n次，但语句②本身要执行n+1次，故语句②的频度是n（n+1）；

同理可得语句③、④和⑤的频度分别是n2，n2（n+1）和n3。

该程序段所有语句的频度之和为：T（n）=2n3+3n2+2n+1、其复杂度为O（n3）

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=356