admin 管理员组文章数量: 1184232
2024年3月14日发(作者：googlechrome安卓版)
圣才电子书
十万种考研考证电子书、题库视频学习平台
第二部分课后习题
第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
）。
1
/
116
圣才电子书
十万种考研考证电子书、题库视频学习平台
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：
本算法的时间复杂度为O（n
2
）。
（2）算法如下：
本算法的时间复杂度为O（1）。
（3）算法如下：
2
/
116
圣才电子书
十万种考研考证电子书、题库视频学习平台
本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）
（2）
（3）
3
/
116
圣才电子书
十万种考研考证电子书、题库视频学习平台
答：（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为常量）。因此：
4
/
116
圣才电子书
十万种考研考证电子书、题库视频学习平台
由于趋近于1，则k=log
2
n。所以
上机实验题1
实验题1设计一个程序，输出所有小于等于n（n为一个大于2的正整数）
的素数。要求：（1）每行输出10个素数；（2）尽可能采用较优的算法。’
实验题2编写一个程序，计算任一输入的正整数的各位数字之和，并分析
算法的时间复杂度。
实验题3编写一个程序，判断一个字符串是否为“回文”（顺读和倒读都
一样的字符串称为“回文”），并分析算法的时间复杂度。
5
/
116
圣才电子书
十万种考研考证电子书、题库视频学习平台
第2章线性表
1．叙述线性表两种存储结构各自的主要特点。
答：线性表的两种存储结构分别是顺序存储结构和链式存储结构。顺序存储结构的主要
特点如下：
（1）节点中只有自身的数据域，没有指针域。因此，顺序存储结构的存储密度大，存
储空间利用率高；
（2）可以通过序号直接访问任何数据元素，即可以随机存取；
（3）插入和删除操作会引起大量元素的移动。
链式存储结构的主要特点如下：
（1）节点中除自身的数据域还有表示关联信息的指针域。因此链式存储结构比顺序存
储结构的存储密度小，存储空间利用率较低；
（2）在逻辑上相邻的节点在物理上不比相邻，因此不可以随机存取，只能顺序存取；
（3）插入和删除操作方便灵活。不必移动节点，只需修改节点中的指针域即可。
2．设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）
的适当位置上，并保持线性表的有序性。
答：通过比较在顺序表L中找到插入x的位置i，将该位置及后面的元素后移一个位置，
将x插入到位置i中，最后将L的长度增1。对应的算法如下：
6
/
116
版权声明：本文标题：李春葆《数据结构教程》(第4版)课后习题-第一章至第十二章(圣才出品 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710383551a570627.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论