当前位置:首页 » 数据结构练习题 » 正文

数据结构-绪论-练习题

2965 人参与  2018年09月10日 21:51  分类 : 数据结构练习题  评论

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

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

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

答案:C

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

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

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

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

1A=KR),其中:

K={abcdefg}

R={r}

r={ab〉,〈bc〉,〈cd〉,〈de〉,〈ef〉,〈fg}

2B=KR),其中:

K={abcdefgh}

R={r}

r={db〉,〈dg〉,〈da〉,〈bc〉,〈ge〉,〈gh〉,〈af}

3C=KR),其中:

K={123456}

R={r}

r={12),(23),(24),(34),(35),(36),(45),(46}

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

解:

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

image.png 

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

image.png 

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

image.png 

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

a=0b=1

fori=2i=ni++

{s=a+b

 b=a

 a=S

}

解:

因为,语句的频度是2

语句的频度是n

语句的频度是n-1

语句的频度是n-1

语句的频度是n-1

故,该程序段的时间复杂度Tn=2+n+3*n-1=4n-1=On)。

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

intijk

Fori=0ini++

Forj=0jnj++

{

c[i][j]=0

fork=0knk++

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

}

解:

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

语句作为语句循环体内的语句应该执行n次,但语句本身要执行n+1次,故语句的频度是nn+1);

同理可得语句的频度分别是n2n2n+1)和n3

该程序段所有语句的频度之和为:Tn=2n3+3n2+2n+1其复杂度为On3

来源:我是码农,转载请保留出处和链接!

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

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!