第1章习题解答数据结构概论

第1章习题解答数据结构概论

ID:12293524

大小:75.00 KB

页数:3页

时间:2018-07-16

第1章习题解答数据结构概论_第1页
第1章习题解答数据结构概论_第2页
第1章习题解答数据结构概论_第3页
资源描述:

《第1章习题解答数据结构概论》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第1章数据结构概论一、判断题1算法可以没有输入语句。解:对。按照算法定义,它包括输入、输出、确定性、有穷性和有效性这五条。其中,算法允许有零个或多个输入语句,但必须至少有一个输出语句。2数据的逻辑结构按照数据元素前驱的个数划分为线性与非线性两类,线性的数据结构指数据元素只有一个前驱,非线性的则有多个前驱。解:错。正确的表述应为:线性的数据结构是指每个数据元素至多只有一个前驱,至多只有一个后继。3数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。解:对。数据结构的研究内容为:数据的逻辑结构、存储

2、方式与数据运算。二、选择题1算法的时间复杂度取决于。(A).问题的规模(B).待处理数据的初态(C).编码的语言(D).占用内存的大小解:选A。时间复杂度与空间复杂度均取决于问题规模。2算法与程序的主要区别在于程序可以不满足算法的B。(A).确定性(B).有穷性(C).可行性(D).健壮性解:选B。算法包含有五个特性:(1)输入。(2)输出。(3)确定性。(4)有穷性。(5)有效性程序可以不满足有穷性,亦即程序允许无限次地运行。例如,在以下程序中,当不输入-1时,程序将无限次地运行。#include

3、ream.h>voidmain(){intn;cout<<"输入正整数n,输入-1结束"<>n;if(n==-1)break;}}3.算法分析的两个方面是。(A).空间复杂性和时间复杂性(B).正确性和简明性(C).可读性和文档性(D).数据复杂性和程序复杂性解:选A。三、填空题1若算法中语句频度之和为,则算法的时间复杂度为。解:因为,故。2数据的存储结构分为顺序、链接、索引和散列四种。3在线性结构、树结构和图结构中,前驱和后继结点之间分别存在着一对

4、一、一对多和多对多的关系。解:线性结构中,头结点无前驱但仅有一个后继,尾结点有一个前驱但无后继,其中间结点均有一个前驱与一个后继,即前驱与后继结点是一对一的关系。在树结构中,父结点往往有多个子结点,是一对多的关系。在图结构中,结点的对应关系往往是多对多的关系。4算法的计算工作量大小和实现算法所需的存储单元多少,分别称为计算的时间复杂度和空间复杂度。四、应用题1计算带下划线语句的执行次数,n为已知的正整数。(1)x=91,y=n;while(y>0){if(x>100){x=x-10;y--;}elsex++;

5、}(2)j=0,k=0;while(k100)需要执行91>100,92>100,…,101>100次的比较,共11次。而且执行之后的x=91,y=n-1。然后,对于x=91,y=n-1,再重复上述操作,即语句if(x>100)需要执行91>100,92>100,…,101>100次的比较,共11次。而且执行之后的x=91,y=n-2。类似地操作重复进行,直到y=0为止。因此,下划线语句if(x>100)共被执行了11n次,故T(n

6、)=11n。解1(2)对于j=0,k=0,执行循环第1次,有j=1,k=10执行循环第2次,有j=2,k=30执行循环第3次,有j=3,k=60执行循环第4次,有j=4,k=100执行循环第5次,有j=5,k=150…..为了得到j与k之间的关系,我们引入记号,,,,一般地,()因此,语句k+=10j被执行的次数,应满足条件,解得,因此,可取。2一个算法所需时间由下述递归方程表示,试求出该算法的时间复杂度的级别。其中:n是问题的规模,为简单起见,可设n是2的整数幂。解:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。