搜索
1第二章线性表一．名词解释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来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________2和________。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.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________，其它结点称为________。21.在单链表中，表结点中的第一个和最后一个分别称为________和________。头结点的数据域可以不存储________，也可以存放一个________或________。22.单链表INITIATE（L）的功能是建立一个空表。空表由一个________和一个________组成。23.INITIATE()的功能是建立一个空表。请在________处填上正确的语句。lklistinitiate_lklist()/*建立一个空表*/{________________;________________;return(t);}24.以下为求单链表表长的运算，分析算法，请在________处填上正确的语句。intlength_lklist(lklisthead)/*求表head的长度*/{________;j=0;while(p-next!=NULL){________________;j++;}return(j);/*回传表长*/}25.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。pointerfind_lklist(lklisthead,inti){p=head;j=0;while(________________){p=p-next;j++;}if(i==j)return(p);3elsereturn(NULL);}26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。intlocate_lklist(lklisthead,datatypex)/*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/{p=head;j=0;while(________________________________){p=p-next;j++;}if(p-data==x)return(j);elsereturn(0);}27.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。voiddelete_lklist(lklisthead,inti){p=find_lklist(head,i-1);if(____________________________){q=________________;p-next=p-next;free(q);}elseerror(“不存在第i个结点”)}28.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。voidinsert_lklist(lklisthead,datatypex,inti)/*在表head的第i个位置上插入一个以x为值的新结点*/{p=find_lklist(head,i-1);if(p==NULL)error(“不存在第i个位置”)；else{s=________________;s-data=x;s-next=________________;p-next=s;}}29.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。lklistcreate_lklist1()/*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/{ininiate_lklist(head);i=1;scanf(“%f”,&x);while(x!=’$’){________________;________________;scanf(“%f”,&x);}return(head);}该建表算法的时间复杂性约等于____________，其量级为____________。430.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。lklistcreate_lklist2()/*直接实现的建表算法。*/{head=malloc(size);p=head;scanf(“%f”,&x);while(x!=’$’){q=malloc(size);q-data=x;p-next=q;________________;scanf(“%f”,&x);}________________;return(head);}此算法的量级为________________。31．除单链表之外，线性表的链式存储结构还有_________和_________等。32．循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________，而是一个指向_________的指针。33．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为______。34．C语言规定，字符串常量按______处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由______语句对其赋值。35．含零个字符的串称为______串，用______表示。其他串称为______串。任何串中所含______的个数称为该串的长度。36．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为______格式，另一种是每个单元存放多个字符，称为______格式。38．通常将链串中每个存储结点所存储的字符个数称为______。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上______。三、单向选择题1．对于线性表基本运算，以下结果是正确的是()①初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф.②求表长LENGTH(L)，引用型运算，其结果是线性表L的长度③读表元GET(L,i),引用型运算。若1=i=LENGTH(L),其结果是线性表L的第i个结点；否则，结果为0④定位LOCATE(L,X),引用型运算.若L中存在一个或多个值与X相等的结点，运算结果为这些结点的序号的最大值；否则运算结果为0⑤插入INSERT(L,X,i),加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X为值的新结点⑥删除DELETE(L,i),引用型运算.其作用是撤销线性表L的第i个结点Ai52.线性结构中的一个结点代表一个（）①数据元素②数据项③数据④数据结构3．顺序表的一个存储结点仅仅存储线性表的一个（）①数据元素②数据项③数据④数据结构4．顺序表是线性表的（）①链式存储结构②顺序存储结构③索引存储结构④散列存储结构5.对于顺序表，以下说法错误的是（）①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作①条件判断②结点移动③算术表达式④赋值语句7.对于顺序表的优缺点，以下说法错误的是（）①无需为表示结点间的逻辑关系而增加额外的存储空间②可以方便地随机存取表中的任一结点③插人和删除运算较方便④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)⑤容易造成一部分空间长期闲置而得不到充分利用8.指针的全部作用就是（）①指向某常量②指向某变量③指向某结点④存储某数据9.除了()，其它任何指针都不能在算法中作为常量出现，也无法显示。①头指针②尾指针③指针型变量④空指针10.单链表表示法的基本思想是