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

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

2、)待处理数据的初态(C)编码的语言 (D)占用内存的大小解：选A。时间复杂度与空间复杂度均取决于问题规模。2 算法与程序的主要区别在于程序可以不满足算法的 B 。(A)确定性 (B)有穷性 (C)可行性 (D)健壮性解：选B。算法包含有五个特性：（1）输入。（2）输出。（3）确定性。（4）有穷性。（5）有效性程序可以不满足有穷性，亦即程序允许无限次地运行。例如，在以下程序中，当不输入-1时，程序将无限次地运行。#includevoid main() int n; cout输入正整数n,输入-1结束endl; while(1) coutn; if(n=-1) break; 3. 算法分析的两个方

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 -; else x +;(2) j =0，k = 0;while ( k 100)需要执行91100,92100,101100次的比较，共11次。而且执行之后的x=91，y=n-1。然后，对于x=91，y=n-1，再重复上述操作，即语句if(x100)需要执行91100,92100,101100次的比较，共11次。而且执行之后的x=91，y=n-2。类似地操作重复进行，直到y=0为止。因此，下划线语句if(x100)共被执行了11n次，故T(n)=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+=10*j被执行的次数，应满足条件，