第二章线性表
一．名词解释
1线性结构2、数据结构得顺序实现3、顺序表4、链表5、数据结构得链接
实现
6、建表
7、字符串
8、串9、顺序串10、链串
二、填空题
1、为了便于讨论有时将含
0个结点得线性结构表示成a1a2……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_sqlistsqlistLdatatypexi
ti
将X插入到顺序表L得第i1个位置
ifL、lastmaxsizeerror“表满”
ifi1iL、last1error“非法位置”
forjL、lastjij______
L、datai1x
L、lastL、last1

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

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