数据结构（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–;}
else x++;
答案：
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;
for i=0; i<n; i++)
for(j=0; j<n; j++)
s+=B[i][j];
sum=s;
答案：
O(n
2
)
解释：语句s+=B[i][j];的执行次数为n
2
。
（
4）i=1;
while(i<=n)
i=i*3;
答案：
O(log
3
n
)
解释：语句i=i*3;的执行次数为 ëlog
3
n
û。
（
5）x=0;
for(i=1; i<n; i++)
for (j=1; j<=n-i; j++)
x++;
答案：
O(n
2
)
解释：语句
x++;的执行次数为n-1+n-2+……＋1= n(n-1)/2。
第
2
章 线性表
1
．
选择题
（
1
）
顺序表中第一个元素的存储地址是
100
，每个元素的长度为
2
，则第
5
个元素的地址是
（
B
）。
A．110 B
．
108 C．100 D．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(n
2
)
或
O(nlog
2
n
)？）。
（
3
）
向一个有
127
个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动
的元素个数为
（
B
）。
A
．
8 B
．
63.5 C
．
63 D
．
7
解释：平均移动元素个数为n/2
（
4
）
链接存储的存储结构所占存储空间
（
A
）。
A
．
分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B
．
只有一部分，存放结点值
C
．
只有一部分，存储表示结点间关系的指针
D
．
分两部分，一部分存放结点值，另一部分存放结点所占单元数
（
5
）
线性表若采用链式存储结构时，要求内存中可用存储单元的地址
（
D
）。
A
．
必须是连续的
B．部分地址必须是连续的
C．
一定是不连续的
D．连续或不连续都可以
（
6
）
线性表Ｌ在
（
B
）
情况下适用于使用链式结构实现。
A
．
需经常修改Ｌ中的结点值
Ｂ
．
需不断对Ｌ进行删除插入
C．
Ｌ中含有大量的结点
Ｄ
．Ｌ中结点结构复杂
解释：链表插入/删除数据只需修改指针不需要移动表中数据，链表
适用长度变化大、频繁进行插入
/
删除操作
。
（
7
）
单链表的存储密度
（
C
）。
A
．
大于
1 B
．
等于
1 C
．
小于
1 D
．
不能确定
解释：
存储密度是指一个结点数据
本身
所占的存储
空间
和整个结点所占的存储
空间
之比
，假设单链表一个结点本身
所占的
空间为
D