>LLink-Rlink=Q ->LLink=Q 40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用() 存储方式最节省时间 ①顺序表 ②单链表 ③双链表 ④单循环链表 串是任意有限个 ①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用 1.请用类C语言描述顺序表,并予以解释说明 请用类C语言描述单链表的类型定义,并予以解释说明 3.请用类C语言描述双链表的类型定义,并予以解释说明 4.请用类C语言描述顺序串的类型定义。 5.请用类C语言描述链串的类型定义 6.叙述以下概念的区别:头指针变量、头指针、头结点、首结点,并说明头指针变量和头结 点的作用。 7.有哪些链表可仅由一个尾指针来惟一确定,即从尾指针出发能访问到链表上任何一个结点 8.简述下列每对术语的区别: 空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9.设有A B="mule",C="old",D="my",试计算下列运算的结果(注:A+B是 CONCAT(A,B) 的简写,A=”"的""含有两个空格) a)A+B (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, d") (i) INSERT(D, 2, C) (k) INSERT(B, 1, A) (1)DELETE (B, 2, 2) (m) DELETE (B, 2. 0) 10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算,将S转换为T。 五、算法设计 1.设A=(a,a,a, an)和B=(b,b,..,b)是两个线性表(假定所含数据元素均为 整数)。若n=m且a:=b;(i=1,,,n),则称A=B;若a=b;(i )且a1<b1(j<n<=m),则 称AB;在其他情况下均称A>B。是编写一个比较A和B的算法,当A<B,A书或AB是分别输 出-1,0或者1。 2,试编写在无头结点的单链表上实现线性表基本运算 LOCATE(L,Xx、 INSERT(L,X,i和 DELETE(L,ⅱ)的算法,并和在带头结点的单链表上实现相的算法进行比较。 3.试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法 4.假设有两个按数据元素值递增有序排列的线性表A和B,均以单链表作存储结构。编写算 99 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="mule"，C="old"，D="my",试计算下列运算的结果(注: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,"d") (j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0) 10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算，将 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<bj+1（j<n<=m）, 则 称 A<B;在其他情况下均称 A>B。是编写一个比较 A 和 B 的算法，当 A<B,A=B 或 A>B 是分别输 出-1，0 或者 1。 2，试编写在无头结点的单链表上实现线性表基本运算 LOCATE(L,X)、INSERT(L,X，i)和 DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算 LENGTH(L)的算法。 4．假设有两个按数据元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构。编写算