admin 管理员组文章数量: 1184232
2024年3月14日发(作者：constellation 意思)
1章 答案
1.
简述数据与数据元素的关系与区别。
解：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单
位，是数据的个体。数据与元素之间的关系是元素与集合之间的关系。
2.
数据结构和数据类型有什么区别？
解：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，
即数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和定义在这个集合上的一组运
算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组
成。
3.
设3个表示算法频度的函数f、g和h分别为：
f（n）=100n
3
+n
2
+1000 g（n）
=25n
3
+5000n
2
h（n）
=n
1.5
+5000nlog
2
n
求它们对应的时间复杂度。
解：f（n）=100n
3
+n
2
+1000=O（n
3
），g（n）=25n
3
+5000n
2
=O（n
3
）， 当
n→∞时，√n>log
2
n，所以h（n）=n
1.5
+5000nlog
2
n= O（n
1.5
）。
4.
用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）
求一个n阶方阵的所有元素之和。
（2）
对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）
对于输入的任意n个整数，输出其中的最大和最小元素。
解：（1）算法如下：
本算法的时间复杂度为O（n
2
）。
（2）
算法如下：
本算法的时间复杂度为O（1）。
（3）
算法如下：
本算法的时间复杂度为O（n）。
5.
设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）
（2）
（3）
解：（1）设while循环语句执行次数为T（n），则：
（2）
算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：
（3）
设while循环语句执行次数为T（n），则：
则
6.
有以下递归算法用于对数组a[i．．j]的元素进行归并排序：
求mergesort（a，0，n－1）的时间复杂度。其中，merge（a，i，j，m）用于两个有序子序列
a[i．．m]和a[m+l．．j]的合并，是一个非递归函数，它的时间复杂度为O（合并的元素个数）。
解：设mergesort（a，0，n-1）的执行次数为T（n），分析得到以下递归关系：
O（n）为merge（）所需的时间，设为cn（c为常量）。因此：
由于 趋近于1，则k=log
2
n。所以
上机实验题1
实验题1设计一个程序，输出所有小于等于n（n为一个大于2的正整数）的素数。要求：
（1）
每行输出10个素数；（2）尽可能采用较优的算法。’
实验题2编写一个程序，计算任一输入的正整数的各位数字之和，并分析算法的时间复杂
度。
实验题3编写一个程序，判断一个字符串是否为“回文”（顺读和倒读都一样的字符串称
为“回文”），并分析算法的时间复杂度。
2章 答案
1.
叙述线性表两种存储结构各自的主要特点。
解：线性表的两种存储结构分别是顺序存储结构和链式存储结构。顺序存储结构的主要特点如下：
（1）
节点中只有自身的数据域，没有指针域。因此，顺序存储结构的存储密度大，存储空间利用率
高；
（2）
可以通过序号直接访问任何数据元素，即可以随机存取；
（3）
插入和删除操作会引起大量元素的移动。
链式存储结构的主要特点如下：
（1）
节点中除自身的数据域还有表示关联信息的指针域。因此链式存储结构比顺序存储结构的存储
密度小，存储空间利用率较低；
（2）
在逻辑上相邻的节点在物理上不比相邻，因此不可以随机存取，只能顺序存取；
（3）
插入和删除操作方便灵活。不必移动节点，只需修改节点中的指针域即可。
2.
设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置
上，并保持线性表的有序性。
解：通过比较在顺序表L中找到插入x的位置i，将该位置及后面的元素后移一个位置，将x插入到位
置i中，最后将L的长度增1。对应的算法如下：
3.
假设一个顺序表L中所有元素为整数，设计一个算法调整该顺序表，使其中所有小于零的元素放
在所有大于等于零的元素的前面。
解：i、j分别置初值为0和L．1ength-1，当i 素，j从后向前扫描顺序表L，找小于0的元素，当i 4. 设计一个算法，将一个带头节点的数据域依次为a 1 ，a 2 ，…，a n （n≥3）的单链表的所有节点逆 置，即第一个节点的数据域变为a n ，……，最后一个节点的数据域变为a 1 。
版权声明：本文标题：李春葆数据结构教程第4版习题答案 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1710383998a570645.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论