第二章 线性表
二、填空题
1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a1，a2,??an)，其中每个ai代表一个结点。a1称为起始结点，an称为终端结点，i称为ai在线性表中的位置或序号。对任意一对相邻结点ai、ai┼1(1<=i 2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为（）或?。 3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前趋外，其他结点有且仅有一个直接前趋;除终端结点没有直接后趋外，其它结点有且仅有一个直接后趋. 4.所有结点按1对1的邻接关系构成的整体就是线性结构。 5.线性表的逻辑结构是线性结构。其所含结点的个数称为线性表的长度，简称表长. 6.表长为O的线性表称为空表 7.线性表典型的基本运算包括:初始化INITLATE(L)、求表长LENGTH(L)、读表长GET(L,i)、定位LOCATE(L,X),插入INSERT(L,X,i)、删除DELETE(L,i)等六种。 8.顺序表的特点是逻辑结构中相邻的结点在存储结构中仍相邻。 9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个结点ai的存储地址为b+(i-1)Xk。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ { if( L.last == maxsize) error(“表满”)； if((i<1)||(i>L.last+1))error(“非法位置”); for(j=L.last;j>=i;j--)L.data[j]=l.data[j-1]; L.data[i-1]=x; L.last=L.last+1; } 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为___n_____，量级是__O(n)_。插入算法的平均时间复杂性为n/2，平均时间复杂性量级是O(n)。 12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ {if((i<1)||(i>L.last))error(“非法位置”)； for(j=i+1;j=L.last;j++)_____L.data[j-2]=L.data[j-1]___; L.last=L.last-1; } 13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是__n-1______和__O(n)______,其平均时间复杂性及其量级分别为__(n-1)/2______和__O(n)______。 14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________; while((i≤L.last)&&(L.data[i-1]!=X))i++; if(__i=1 i<=L.last______)return(i); else return(0); } 15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂性量级为__O(n)______。求表长和读表元算法的时间复杂性为___O(1)_____。 16.在顺序表上，求表长运算LENGTH（L）可通过输出___L.last_____实现，读表元运算 GET（L，i）可通过输出__L.data[i-1]______实现。 17.线性表的常见链式存储结构有_单链表_______、_循环链表_______和___双链表_____。 18.单链表表示法的基本思想是用__指针______表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成_单链表_______。 20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为___头结点_____，其它结点称为___表结点_____。 21.在单链表中，表结点中的第一个和最后一个分别称为__首结点______和_尾结点_______。头结点的数据域可以不存储___任何信息_____，也可以存放一个__特殊标志______或___表长_____。 22.单链表INITIATE（L）的功能是建立一个空表。空表由一个__头结点______和一个___头结点_____组成。 23.INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/ {t=malloc(size); t->next=NULL; return(t); } 24.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ {p=head; j=0; while(p->next!=NULL) {p=p->next; j++; } return(j); /*回传表长*/ } 25.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 pointer find_lklist(lklist head,int i) { p=head;j=0; while((p->next!=NULL)&&(j if(i==j) return(p); else return(NULL); } 26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head;j=0; while((p->next!=NULL)&&(p->data!=x)){p=p->next;j++;} if (p->data==x) return(j); else return(0); } 27.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(lklist head,int i) { p=find_lklist(head,i-1); if((p!=NULL)&&(p->next!=NULL)) { q=p->next; p->next=p->next; free(q); } else error(“不存在第i个结点”) } 28.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ { p=find_lklist(head,i-1); if(p==NULL)error(“不存在第i个位置”)； else {s=malloc(size);s->data=x; s->next=p->next; p->next=s; } } 29.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志*/ { ininiate_lklist(head); i=1; scanf(“%f”,&x); while(x!=’$’) {insert_lklist(head,x,i); i++; scanf(“%f”,&x); } return(head); } 该建表算法的时间复杂性约等于n(n-1)/2，其量级为O(n^2)。 30.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ { head=malloc(size); p=head; scanf(“%f”,&x); while(x!=’$’) { q=malloc(size); q->data=x; p->next=q; p=q; scanf(“%f”,&x); } p->next=NULL; return(head); } 此算法的量级为O(n)。 31．除单链表之外，线性表的链式存储结构还有单项循环链表和双向循环链表等。 32．循环链表与单链表的区别仅仅在于其尾结点的链域值不是NULL，而是一个指向头结点的指针。 33．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为双链表。 34．C语言规定，字符串常量按字符数组处理，它的值在程序的执行过程中是不能改变的。而串变量与其他变量不一样，不能由赋值语句对其赋值。 35．含零个字符的串称为空串，用?表示。其他串称为非空串。任何串中所含字符的个数称为该串的长度。 36．当且仅当两个串的长度相等并且各个对应位置上的字符都相同_时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的子串，该串称为它所有子串的主串。 37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为非紧缩格式，另一种是每个单元存放多个字符，称为紧缩格式。 38．通常将链串中每个存储结点所存储的字符个数称为结点大小。当结点大小大于1时，链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域里补上不属于字符集的特殊符号。 三、单向选择题 1．对于线性表基本运算，以下结果是正确的是 ( 2 ) ①初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф 2 . ② 求表长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个结点Ai 2.线性结构中的一个结点代表一个 （ 1 ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 3．顺序表的一个存储结点仅仅存储线性表的一个 （ 1 ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 4．顺序表是线性表的 （ 2 ） ①链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构 5.对于顺序表，以下说法错误的是 （ 1 ） ①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 ④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ 2 ）为标准操作 ①条件判断 ②结点移动 ③算术表达式 ④赋值语句 7.对于顺序表的优缺点，以下说法错误的是 （ 3 ） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用 8.指针的全部作用就是 （ 3 ） ①指向某常量 ② 指向某变量 ③指向某结点 ④存储某数据 9.除了( 4 ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。 ①头指针 ②尾指针 ③指针型变量 ④空指针 10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是（ 2 ） ①任何指针都不能用打印语句输出一个指针型变量的值 ②如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可 ③若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值 ④对于一个指针型变量P的值。只需知道它指的是哪个结点 ⑤结点*ｐ是由两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针 11.单链表的一个存储结点包含 （ 4 ） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 12.对于单链表表示法，以下说法错误的是 （ 3 ） ①数据域用于存储线性表的一个数据元素 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NULL称为空指针，它不指向任何结点，只起标志作用 13.对于单链表表示法，以下说法错误的是 （ 5 ） ①指向链表的第一个结点的指针，称为头指针 ②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL ⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表 14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ 4 ） ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针” ③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值” 15．设指针P指向双链表的某一结点，则双链表结构的对称性可用（ 3 ）式来刻画 ①p->prior->next->==p->next->next ②p->prior->prior->==p->next->prior ③p->prior->next->==p->next->prior ④p->next->next==p->prior->prior 16.以下说法错误的是 （ 1 ） ①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易 ④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。 17．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ 2 ） ①real和rear->next->next ②rear->next 和real ③rear->next->next和rear ④rear和rear->next 3 18.以下说错误的是 ( 3 ) ①对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n） ②读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构 ③在链表上实现读表元运算的平均时间复杂性为O（1） ④链入、摘除操作在链表上的实现可在O（1）时间内完成 ⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19．在串的基本运算中，属于加工型运算的有 （ 4 ） ①EQAL(S,T) ②LENGTH(S) ③CONCAT(S,T) ④REPLACE(S,T,R) ⑤INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有 （ 4 ） ①ASSIGN(S,T) ②INSERT(S1,i,S2) ③DELETE(S,i,j) ④SUBSTR(S,i,j) ⑤REPLACE(S,T,R) 21．循环链表主要优点是 （ 4 ） ①不再需要头指针了 ②已知某个结点的位置后，能够容易找到它的直接前趋 ③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表 22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ 2 ） ①正确 ②错误 23．以下说法错误的是 （ 2 ） ①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是 3 ①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继 ②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低 ③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动 25．以下说法错误的是 （ 4 ） ①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 ②顺序存储的线性表可以随机存取 ③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构 26．以下说法错误的是 （2 ） ①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 ④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（ 3 ） ①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素 ②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 ③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ 4 ） ①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构 ④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( 1 ) ①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作 ③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作 30.线性表L=(a1,a2,...,ai,...,an),下列说法正确的是( 4 ) ①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素 ③表中诸元素的排列顺序必须是由小到大或由大到小的 ④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( 2 ) ①正确 ②不正确 32.设p,q是指针,若p=q,则*p=*q ,这种说法( 2 ) ①正确 ②不正确 33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( 4 ) ①必需是联系的 ②部分地址必须是连续的 ③一定是不连续的 ④连续不连续都可以 34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( 4 ) ①p=rear; ②rear=rear->next; rear=rear->next; free(rear); free(p) ③rear=rear->next->next; ④ p=rear->next->next; free(rear); rear->next->next=p->next; free(p); 35. 单链表中，增加头结点的目的是为了 ( 3 ) ①使单链表至少有一个结点 ②标示表结点中首结点的位置 4 ③方便运算的实现 ④说明单链表是线性表的链式存储实现 36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着 3 ① 每个结点所代表的数据元素都一样。 ② 每个结点所代表的数据元素包含的数据项的个数要相等 ③ 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④ 结点所代表的数据元素有同一特点 37．带头结点的单链表Head为空的判定条件是 2 ①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足 3 P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下： LLink data RLink 其中：LLink是指向前驱结点的指针域： data是存放数据元素的数据域； Rlink是指向后继结点的指针域。 下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是 2 ①Q->LLink=P->LLink; ②P->LLink=Q; Q->Rlink=P; Q->Rlink=P; P->LLink=Q; P->LLink->Rlink=Q; P->LLink->Rlink=Q; Q->LLink=P->LLink; ③Q->LLink=P->LLink; Q->Rlink=P; P->LLink->Rlink=Q; P->LLink=Q; 40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ 1 ）存储方式最节省时间。 ①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个4 ①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 第三、四章练习题 3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答： (1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 3.2链栈中为何不设置头结点? 答： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答： 当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 3.4指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1 5