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

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+1B。是编写一个比较A和B的算法,当AB是分别输出-1,0或者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)&&(jnext!=NULL)&&(p->data!=x) 27、(p!=NULL)&&(p->next!=NULL) p->next 28、mailloc(size) p->next 29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n2) 30、p=q p->next=NULL O(n) 11

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