没有合适的资源?快使用搜索试试~ 我知道了~
数据结构(C语言版 第2版)课后习题答案 严蔚敏 编著
需积分: 13 26 下载量 5 浏览量
2021-01-21
20:24:16
上传
评论 5
收藏 221KB DOCX 举报
温馨提示
试读
14页
数据结构(C语言版 第2版)课后习题答案 严蔚敏 编著
资源推荐
资源详情
资源评论
数据结构(C 语言版 第 2 版)课后习题答案 严蔚敏 编著
置顶 就是
217 2018-09-1117:09:52 116555 收藏 377
转自 hps://blog.csdn.net/Bamboo_shui/ar#cle/details/72433523(原文没第八章答案)
数据结构(C 语言版 第 2 版)课后习题答案 严蔚敏 等 编著,仅供参考,还是自己认真做
了再看
第 1 章 绪论
5.选择题
(1)在数据结构中,从逻辑上可以把数据结构分成( C)。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的( C)。
A.存储结构 B.存储实现
C.逻辑结构 D.运算实现
(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着( B)。
A.数据具有同一特点
B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致
C.每个数据元素都一样
D.数据元素所包含的数据项的个数要相等
(4)以下说法正确的是( D)。
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
解释:数据元素是数据的基本单位,数据项是数据的最小单位,数据结构是带有结构的各
数据元素的集合。
(5)算法的时间复杂度取决于( D)。
A.问题的规模 B.待处理数据的初态
C.计算机的配置 D.A 和 B
解释:算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序
的算法,其执行时间与待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以
及平均时间复杂度的评价。
(6)以下数据结构中,( A)是非线性数据结构
A.树 B.字符串 C.队列 D.栈
6.试分析下面各程序段的时间复杂度。
(1)x=90;y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
elsex++;
答案:O(1)
解释:程序的执行次数为常数阶。
(2)for(i=0;i<n;i++)
for(j=0;j<m;j++)
a[i][j]=0;
答案:O(m*n)
解释:语句 a[i][j]=0;的执行次数为 m*n。
(3)s=0;
fori=0;i<n;i++)
for(j=0;j<n;j++)
s+=B[i][j];
sum=s;
答案:O(n2)
解释:语句 s+=B[i][j];的执行次数为 n2。
(4)i=1;
while(i<=n)
i=i*3;
答案:O(log3n)
解释:语句 i=i*3;的执行次数为 ëlog3nû。
(5)x=0;
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
x++;
答案:O(n2)
解释:语句 x++;的执行次数为 n-1+n-2+……+1=n(n-1)/2。
第 2 章 线性表
1.选择题
(1)顺序表中第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址
是( B)。
A.110B.108C.100D.120
解释:因为顺序表是连续存储的,所以第 5 个元素的地址为:100+2*(5-1)=108。
(2)在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是( A)。
A.访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n)
B.在第 i 个结点后插入一个新结点(1≤i≤n)
C.删除第 i 个结点(1≤i≤n)
D.将 n 个结点从小到大排序
解释:在顺序表中插入、删除一个结点,平均约移动表中一半元素,时间复杂度为 O(n);
顺序表是一种随机存取结构,按位置访问元素可通过数组下标直接定位,时间复杂度是
O(1);(排序的时间复杂度为 O(n2)或 O(nlog2n)?)。
(3) 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动
的元素个数为( B)。
A.8B.63.5C.63D.7
解释:平均移动元素个数为 n/2
(4)链接存储的存储结构所占存储空间( A)。
A.分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
B.只有一部分,存放结点值
C.只有一部分,存储表示结点间关系的指针
D.分两部分,一部分存放结点值,另一部分存放结点所占单元数
(5)线性表若采用链式存储结构时,要求内存中可用存储单元的地址( D)。
A.必须是连续的 B.部分地址必须是连续的
C.一定是不连续的 D.连续或不连续都可以
(6)线性表L在( B)情况下适用于使用链式结构实现。
A.需经常修改L中的结点值 B.需不断对L进行删除插入
C.L中含有大量的结点 D.L中结点结构复杂
解释:链表插入/删除数据只需修改指针不需要移动表中数据,链表适用长度变化大、频繁
进行插入/删除操作。
(7)单链表的存储密度( C)。
A.大于 1B.等于 1C.小于 1D.不能确定
解释:存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比,
假设单链表一个结点本身所占的空间为 D,指针域所占的空间为 N,则存储密度为 D/
(D+N),即一定小于 1。
(8)将两个各有 n 个元素的有序表归并成一个有序表,其最少的比较次数是( )。
A.nB.2n-1C.2nD.n-1
答案:A
解释:当第一个有序表中所有的元素都小于(或大于)第二个表中的元素,只需要用第二
个表中的第一个元素依次与第一个表的元素比较,总计比较 n 次,最多比较 2n-1 次。
(9)在一个长度为 n 的顺序表中,在第 i 个元素(1≤i≤n+1)之前插入一个新元素时须向后
移动( B)个元素。
A.n-iB.n-i+1C.n-i-1D.I
(10)线性表 L=(a1,a2,……an),下列说法正确的是(D)。
A.每个元素都有一个直接前驱和一个直接后继
B.线性表中至少有一个元素
C.表中诸元素的排列必须是由小到大或由大到小
D.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。
剩余13页未读,继续阅读
资源评论
fish8245
- 粉丝: 8
- 资源: 7
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功