P->LLink->Rlink=Q;
P->LLink=Q;
40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个
①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用
1． 请用类C语言描述顺序表，并予以解释说明。
2． 请用类C语言描述单链表的类型定义，并予以解释说明。 3． 请用类C语言描述双链表的类型定义，并予以解释说明。 4． 请用类C语言描述顺序串的类型定义。 5． 请用类C语言描述链串的类型定义。
6.叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。
7．有哪些链表可仅由一个尾指针来惟一确定，即从尾指针出发能访问到链表上任何一个结点。 8．简述下列每对术语的区别：
空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9．设有 A=” ”,B=\，C=\，D=\试计算下列运算的结果(注:A+B是CONCAT（A,B）的简写,A=\的 \含有两个空格)。 (a) A+B (b) B+A (c) D+C+B
(d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) (i) INDEX(C,\(j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0)
10.已知:S=\。试利用连接、求子串和置换等基本运算，将S转换为T。 五、算法设计
1． 设A=（a1,a2,a3,......an）和B=(b1,b2,.. .,bm)是两个线性表（假定所含数据元素均为整数）。若n=m且ai=bi(i=1,.. .,n),则称A=B;若ai=bi(i=1,.. .,j)且aj+1
2，试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X，i)和DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。
4．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写算
9
法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C，并要求利用原表(即A表和B表的)结点空间存放表C。
5．设有线性表A=(a1,a2,.. .,am)和B=(b1,b2,.. .,bn).试写合并A、B为线性表C的算法，使得：
?(a1,b1,...,am,bm,bm?1,bn)当m??n;C=? ?(a1,b1,...,an,bn,an?1,...,am)当m?n;假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。
6，设线性表存放在向量A[arrsize]的前elenum分量中，且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L中，使得L仍然有序。
8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,.. .,an)逆置为(an,.. .,a2,a1)。 9．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。
10，已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算： 删去那些既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链式的)编写实现上述运算的算法。
11．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。
12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间(头结点可另辟空间)。
13.(Josephus环)任给正整数n、k，按下述方法可得排列1，2，??,n的一个置换:将数字1，2，.. .,n环形排列(如图算法设计题13.所示)，按顺时针方向从1开始 计数；计满K时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3，6，9，2，7，1，8，5，10，
4。试编写一算法，对输人的任意正整数n、k，输出相应的置换
14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次LOCATEL，X)运算时，令元素值为X的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE运算的算法。 16·若X和Y是用结点大小为1单链表表示的串，设计一个算法找出X中第一个不在y中出
10
现的字符。
17．在顺序串上实现串的判等运算EQUAL(S,T)。 18．在链串上实现判等运算EQUAL(S,T)。
19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。
20．用串的其他运算构造串的子串定位运算index。
第二章 参考答案 一、名词解释 （略） 二、填空题 1、结点 起始 终端 序号 位置 前趋 后趋 2、（） ф 3、前趋 前趋 后趋 后趋 4、线性 5、线性 长度 表长 6、空表 7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） 定位LOCATE （L，X） 插入INSERT（L，X，i） 删除DELETE（L，i） 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+（i-1）x k 10、L．data[j]=L．data[j-1] 11、n O(n) n/2 O(n) 12、L.data[j-2]=l.data[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦L.last 15、O(n) O(1) 16、L.last L.data[i-1] 17、单链表 循环链表 双链表 18、指针 19，单链表 20、头结点 表结点 21、首结点 尾结点 任何信息、特殊标志 表长 22、头结点 头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(j
31、单向循环链表（简称循环链表） 双向循环链表（简称双链表） 32、NULL 头结点 33、双链表 三、单项选择题 1、②2、①3、①4、②5、① 6、②7、③8、③9、④10、② 11、④12、③13、⑤14、④15、③ 16、①17、②18、③19、④20、④ 21、④22、223、②24、③25、④ 26、②27、③28、④29、①30、④ 31、②32、②33、④34、④35、③ 36、③37、②38、③39、②40、① 四、简答及应用 1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表： const maxsize=顺序表的容量； typedef struct { datatype data[maxsize] int last; }sqlist; sqlist L; 数据域data是一个一维数组，线性表的第1，2??，n个元素分别存放在此数组的第0，1，??，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1为顺序表当前的空闲区（或称备用区）。 Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺序表，其表长应写为L.last，而它的终端结点则必须写为 L.data[L.last-1]。 2、假设数据元素的类型为datatype。单链表的类型定义如下： typedef struct node *pointer struct node {datatype data; pointer next; }; typedef pointer lklist; 其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next是 12