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

《第1章习题解答数据结构概论.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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、am.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++;}(2)

5、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)=11

6、n。解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+=10*j被执行的次数，应满足条件，解得，因此，可取。2一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别。其中：n是问题的规模，为简单起见，可设n是2的整数幂。解：