文档介绍：第二章线性表
一. 名词解释
线性结构 2. 数据结构的顺序实现 3. 顺序表 4.
链表
二、填空题
1. 为了便于讨论,有时将含 n(n>=0) 个结点的线性
结构表示成 (a 1, a2, ,, an) ,其中每个 ai 代表一个 ____
结点 __ 。a1 称为 ___起始 ___结点, an 称为 _终端 _____
结点, i 称为 ai 在线性表中的 _序号 _______或 __ 位置
____。对任意一对相邻结点 ai 、 ai ┼1(1<=i<n),a
i
称为 ai
┼1
的直接 ___前趋 ___ai ┼1 称为 ai 的直接 __后趋 ____。
2. 线性结构的基本特征是 : 若至少含有一个结点, 则
除起始结点没有直接 __前趋 ____外,其他结点有且仅有
一个直接 _前趋 _____; 除终端结点没有直接 __ 后趋 ____
外,其它结点有且仅有一个直接 _后趋 _____.
3. 表长为 O 的线性表称为 _空表 _____
4. 线性表典型的基本运算包括 :_ 初始化 _____ 、 _
求表长 _____、_读表长 _____ 、__插入 ____ 、_删除 _____、
___定位 ___等六种。
5. 顺序表的类型定义可经编译转换为机器级。假定
每个 datatype 类型的变量占用 k(k>=1) 个内存单元,其
中, b 是顺序表的第一个存储结点的第一个单元的内存
地址,那么,第 i 个结点 ai 的存储地址为 __ b+( i-1 )x
k ____ 。
6. 以下为顺序表的插入运算, 分析算法, 请在 ______
处填上正确的语句。
Void insert_sqlist(sqlist L , datatype x ,int i)
/* 将 X 插入到顺序表 L 的第 i-1 个位置 */
{ if(  == maxsize) error( “表满” ) ;
if((i<1)||(i>+1))error( “非法位置” );
for(j=;j>=i;j--)_
L. data[j]=L . data[j-1] _____;
[i-1]=x;
=+1;
}
7. 对于顺序表的插入算法 insert_sqlist 来说,若
以结点移动为标准操作,则插入算法的最坏时间复杂性
为 _ n _______ ,量级是 _ O(n) _______ 。插入算法的平
均时间复杂性为 __ n/2 ______,平均时间复杂性量级是
___ O(n) _____。
8. 以下为顺序表的删除运算 ,分析算法, 请在
________ 处填上正确的语句。
void delete_sqlist(sqlist L,int i) /* 删除顺序
表 L 中的第 i-1 个位置上的结点 */
1
{if((i<1)||(i>))error( “非法位置” ) ;
for(j=i+1;j=;j++)_
[j-2]=[j-1] _______;
=-1;
}
9. 对于顺序