数据结构练习题-第二章--线性表-习题及答案.doc

数据结构练习题第二章线性表习题及答案

??第二章线性表

??一．名词解释

??1.线性结构2.数据结构的顺序实现3.顺序表4.链表5.数据结构的链接实现

??6.建表7.字符串8.串9.顺序串10.链串

??二、填空题

??1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,??an)，其中每

??个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________

??或______。对任意一对相邻结点ai、ai┼1(1=in),ai称为ai┼1的直接______ai┼1称为ai的直接______。

??2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。

??3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.

??4.所有结点按1对1的邻接关系构成的整体就是______结构。

??5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称______.

??6.表长为O的线性表称为______

??7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。

??8.顺序表的特点是______。

??9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为______。

??10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。

??Voidinsert_sqlist(sqlistL，datatypex，inti)

??/*将X插入到顺序表L的第i-1个位置*/

??{if(L.last==maxsize)error(“表满”)；

??if((i1)||(iL.last+1))error(“非法位置”);

??for(j=L.last;j=i;j--)______;

??L.data[i-1]=x;

??L.last=L.last+1;

??}

??11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。

??12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。

??voiddelete_sqlist(sqlistL,inti)/*删除顺序表L中的第i-1个位置上的结点*/

??{if((i1)||(iL.last))error(“非法位置”)；

??for(j=i+1;j=L.last;j++)________;

??L.last=L.last-1;

??}

??13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________1

??和________。

??14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。intlocate_sqlist(sqlistL,datatypeX)

??/*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/{________;

??while((i≤L.last)(L.data[i-1]!=X))i++;

??if(________)return(i);

??elsereturn(0);

??}

??15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为________。求表长和读表元算法的时间复杂性为________。

??16.在顺序表上，求表长运算LENGTH（L）可通过输出________实现，读表元运算GET（L，i）可通过输出________实现。

??17.线性表的常见链式存储结构有________、________和________。

??18.单链表表示法的基本思想是用________表示结点间的逻辑关系。

??19.所有结点通过指针的链接而组织成________。

??20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________，其它