数据结构练习题-第二章--线性表-习题及答案.doc
版权申诉
5星 · 超过95%的资源 145 浏览量
2021-10-12
20:18:47
上传
评论
收藏 105KB DOC 举报 
. . . .
第二章 线性表
一． 名词解释
1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的实现
6.建表 7.字符串 8.串 9.顺序串 10.链串
二、填空题
1.为了便于讨论，有时将含 n(n>=0)个结点的线性结构表示成(a
1
，a
2
,……a
n
)，其中
每个 a
i
代表一个______。a
1
称为______结点，a
n
称为______结点，i 称为 a
i
在线性表中的__
______或______。对任意一对相邻结点 a
i
、a
i┼1
(1<=i<n),a
i
称为 a
i┼1
的直接______a
i┼1
称为
a
i
的直接______。
2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何
结点的线性结构记为______或______。
3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其
他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直
接______.
4.所有结点按 1 对 1 的邻接关系构成的整体就是______结构。
5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称____
__.
6.表长为 O 的线性表称为______
7.线性表典型的基本运算包括:______、______、______、______、______、______等
六种。
8.顺序表的特点是______。
9.顺序表的类型定义可经编译转换为机器级。假定每个 datatype 类型的变量占用
k(k>=1)个存单元，其中，b 是顺序表的第一个存储结点的第一个单元的存地址，那么，
第 i 个结点 a
i
的存储地址为______。
10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。
Void insert_sqlist(sqlistL，datatypex，inti)
/*将 X 插入到顺序表 L 的第 i-1 个位置*/
{ if( L.last == maxsize) error(“表满”)；
if((i<1)||(i>L.last+1))error(“非法位置”);
for(j=L.last;j>=i;j--)______;
L.data[i-1]=x;
L.last=L.last+1;
}
11.对于顺序表的插入算法 insert_sqlist 来说，若以结点移动为标准操作，则插入算法
的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，
平均时间复杂性量级是________。
12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。
void delete_sqlist(sqlist L,int i) /*删除顺序表 L 中的第 i-1 个位置上的结点*/
{if((i<1)||(i>L.last))error(“非法位置”)；
for(j=i+1;j=L.last;j++)________;
L.last=L.last-1;
}
13.对于顺序表的删除算法 delete_sqlist 来说，若以结点移动为标准操作，最坏情况
时间复杂性与其量级分别是________和________,其平均时间复杂性与其量级分别为_______
1 / 21
剩余20页未读，继续阅读
beibeidzh
- 粉丝: 8
- 资源: 24万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减5.97元 开通VIP
评论1