第二章线性表
一．名词解释
1线性结构2数据结构的顺序实现3顺序表4链表5数据结构的链接实现
6建表
7字符串
8串9顺序串10链串
二、填空题
1为了便于讨论，有时将含
0个结点的线性结构表示成a1，a2……a
，其中每
个ai代表一个______。a1称为______结点，a
称为______结点，i称为ai在线性表中的________
或______。对任意一对相邻结点ai、ai┼11i
ai称为ai┼1的直接______ai┼1称为ai的直
接______。
2为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何
结点的线性结构记为______或______。
3线性结构的基本特征是若至少含有一个结点，则除起始结点没有直接______外，其他
结点有且仅有一个直接______除终端结点没有直接______外，其它结点有且仅有一个直接
______
4所有结点按1对1的邻接关系构成的整体就是______结构。
5线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称
______
6表长为O的线性表称为______
7线性表典型的基本运算包括______、______、______、______、______、______等六
种。
8顺序表的特点是______。
9顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用kk1
个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个
结点ai的存储地址为______。
10以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。
Voidi
sert_sqlistsqlistL，datatypex，i
ti
将X插入到顺序表L的第i1个位置
ifLlastmaxsizeerror“表满”；
ifi1iLlast1error“非法位置”
forjLlastjij______
Ldatai1x
LlastLlast1

11对于顺序表的插入算法i
sert_sqlist来说，若以结点移动为标准操作，则插入算法
的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，
平均时间复杂性量级是________。
12以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。
voiddelete_sqlistsqlistLi
ti删除顺序表L中的第i1个位置上的结点
ifi1iLlasterror“非法位置”；
forji1jLlastj________
LlastLlast1

13对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时
间复杂性及其量级分别是________和________其平均时间复杂性及其量级分别为________
1
f和________。
14以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。
i
tlocate_sqlistsqlistLdatatypeX
在顺序表L中查找第一值等于X的结点。若r