习题2参考答案及数组广义表习题.docx
- 文档编号:16144835
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:28
- 大小:60.99KB
习题2参考答案及数组广义表习题.docx
《习题2参考答案及数组广义表习题.docx》由会员分享,可在线阅读,更多相关《习题2参考答案及数组广义表习题.docx(28页珍藏版)》请在冰点文库上搜索。
习题2参考答案及数组广义表习题
习题2参考答案
一、单项选择题
1.A2.A3.D4.C5.D6.A7.B8.B9.C10.A11.D12.B13.C14.B15.C16.C17.B18.D19.C20.A
二、填空题
1.线性
2.n-i+1
3.相邻
4.前移,前,后
5.物理存储位置,链域的指针值
6.前趋,后继
7.顺序,链接
8.一定,不一定
9.线性,任何,栈顶,队尾,队头
10.单链表,双链表,非循环链表,循环链表
11.使空表和非空表统一;算法处理一致
12.O
(1),O(n)
13.栈满,栈空,m,栈底,两个栈的栈顶在栈空间的某一位置相遇
14.2、3
15.O
(1)
三、简答题
1.头指针是指向链表中第一个结点(即表头结点)的指针;在表头结点之前附设的结点称为头结点;表头结点为链表中存储线性表中第一个数据元素的结点。
若链表中附设头结点,则不管线性表是否为空表,头指针均不为空,否则表示空表的链表的头指针为空。
2.线性表具有两种存储结构即顺序存储结构和链接存储结构。
线性表的顺序存储结构可以直接存取数据元素,方便灵活、效率高,但插入、删除操作时将会引起元素的大量移动,因而降低效率:
而在链接存储结构中内存采用动态分配,利用率高,但需增设指示结点之间关系的指针域,存取数据元素不如顺序存储方便,但结点的插入、删除操作较简单。
3.应选用链接存储结构,因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素,这里存储单元可以是连续的,也可以是不连续的:
这种存储结构对于元素的删除或插入运算是不需要移动元素的,只需修改指针即可,所以很容易实现表的容量的扩充。
4.应选用顺序存储结构,因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。
因此,只要确定了其起始位置,线性表中的任一个数据元素都可随机存取,因此,线性表的顺序存储结构是一种随机存取的存储结构,而链表则是一种顺序存取的存储结构。
5.设尾指针比设头指针好。
尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O
(1)。
若用头指针来表示该链表,则查找终端结点的时间为O(n)。
6.共有14种可能的出栈序列,即为:
ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA
7.在队列的顺序存储结构中,设队头指针为front,队尾指针为rear,队列的容量(即存储的空间大小)为maxnum。
当有元素要加入队列(即入队)时,若rear=maxnum,则会发生队列的上溢现象,此时就不能将该元素加入队列。
对于队列,还有一种“假溢出”现象,队列中尚余有足够的空间,但元素却不能入队,一般是由于队列的存储结构或操作方式的选择不当所致,可以用循环队列解决。
一般地,要解决队列的上溢现象可有以下几种方法:
(1)可建立一个足够大的存储空间以避免溢出,但这样做往往会造成空间使用率低,浪费存储空间。
(2)要避免出现“假溢出”现象可用以下方法解决:
第一种:
采用移动元素的方法。
每当有一个新元素入队,就将队列中已有的元素向队头移动一个位置,假定空余空间足够。
第二种:
每当删去一个队头元素,则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种:
采用循环队列方式。
将队头、队尾看作是一个首尾相接的循环队列,即用循环数组实现,此时队首仍在队尾之前,作插入和删除运算时仍遵循“先进先出”的原则。
8.该算法的功能是:
将开始结点摘下链接到终端结点之后成为新的终端结点,而原来的第二个结点成为新的开始结点,返回新链表的头指针。
四、算法设计题
1.算法思想为:
(1)应判断删除位置的合法性,当i<0或i>n-1时,不允许进行删除操作;
(2)当i=0时,删除第一个结点:
(3)当0
算法描述如下:
delete(LinkList*q,inti)
{//在无头结点的单链表中删除第i个结点
LinkList*p,*s;
intj;
if(i<0)
printf("Can'tdelete");
elseif(i==0)
{s=q;
q=q->next;
free(s);
}
else
{j=0;s=q;
while((j
=NULL))
{p=s;
s=s->next;
j++;
}
if(s==NULL)
printf("Cant'tdelete");
else
{p->next=s->next;
free(s);
}
}
}
2.由于在单链表中只给出一个头指针,所以只能用遍历的方法来数单链表中的结点个数了。
算法描述如下:
intListLength(LinkList*L)
{//求带头结点的单链表的表长
intlen=0;
ListList*p;
p=L;
while(p->next!
=NULL)
{p=p->next;
len++;
}
return(len);
}
3.设单循环链表的头指针为head,类型为LinkList。
逆置时需将每一个结点的指针域作以修改,使其原前趋结点成为后继。
如要更改q结点的指针域时,设s指向其原前趋结点,p指向其原后继结点,则只需进行q->next=s;操作即可,算法描述如下:
voidinvert(LinkList*head)
{//逆置head指针所指向的单循环链表
linklist*p,*q,*s;
q=head;
p=head->next;
while(p!
=head)//当表不为空时,逐个结点逆置
{s=q;
q=p;
p=p->next;
q->next=s;
}
p->next=q;
}
4.定义类型LinkList如下:
typedefstructnode
{intdata;
structnode*next,*prior;
}LinkList;
此题可采用插入排序的方法,设p指向待插入的结点,用q搜索已由prior域链接的有序表找到合适位置将p结点链入。
算法描述如下:
insert(LinkList*head)
{LinkList*p,*s,*q;
p=head->next;//p指向待插入的结点,初始时指向第一个结点
while(p!
=NULL)
{s=head;//s指向q结点的前趋结点
q=head->prior;//q指向由prior域构成的链表中待比较的结点
while((q!
=NULL)&&(p->data>q->data))//查找插入结点p的合适的插入位置
{s=q;
q=q->prior;
}
s->prior=p;
p->prior=q;//结点p插入到结点s和结点q之间
p=p->next;
}
}
5.算法描述如下:
delete(LinkList*head,intmax,intmin)
{linklist*p,*q;
if(head!
=NULL)
{q=head;
p=head->next;
while((p!
=NULL)&&(p->data<=min))
{q=p;
p=p->next;
}
while((p!
=NULL)&&(p->data p=p->next; q->next=p; } } 6.算法描述如下: delete(LinkList*head,intmax,intmin) {LinkList*p,*q; q=head; p=head->next; while(p! =NULL) if((p->data<=min)||(p->data>=max)) {q=p; p=p->next; } else {q->next=p->next; free(p); p=q->next; } } 7.本题是对一个循环链队列做插入和删除运算,假设不需要保留被删结点的值和不需要回收结点,算法描述如下: (1)插入(即入队)算法: insert(LinkList*rear,elemtypex) {//设循环链队列的队尾指针为rear,x为待插入的元素 LinkList*p; p=(LinkList*)malloc(sizeof(LinkList)); if(rear==NULL)//如为空队,建立循环链队列的第一个结点 {rear=p; rear->next=p;//链接成循环链表 } else//否则在队尾插入p结点 {p->next=rear->next; rear->next=p; rear=p; } } (2)删除(即出队)算法: delete(LinkList*rear) {//设循环链队列的队尾指针为rear if(rear==NULL)//空队 printf("underflow\n"); if(rear->next==rear)//队中只有一个结点 rear=NULL; else rear->next=rear->next->next;//rear->next指向的结点为循环链队列的队头结点 } 8.只要从终端结点开始往前找到第一个比x大(或相等)的结点数据,在这个位置插入就可以了。 算法描述如下: intInsertDecreaseList(SqList*L,elemtypex) {inti; if((*L).len>=maxlen) {printf(“overflow"); return(0); } for(i=(*L).len;i>0&&(*L).elem[i-1] (*L).elem[i]=(*L).elem[i-1];//比较并移动元素 (*L).elem[i]=x; (*L).len++; return (1); } 第3章串 讲课提要 【主要内容】 1.串的有关概念及基本操作 2.串的存储结构 3.串操作应用举例 【教学目标】 1.掌握串的有关概念及基本运算 2.熟悉串的存储结构 3.熟悉串操作应用举例 【所需课时】 一次课。 1.串的有关概念及基本运算 2.串的存储结构 3.串操作应用举例 学习指导 1.概念和术语 •串(String)(或字符串): 是由零个或多个字符组成的有限序列。 一般记为 s=“a a …a ”(n≥0) 其中,s是串的名,用双引号括起来的字符序列是串的值。 •串的长度: 串中字符的个数n。 •子串和主串: 串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。 •空串: 不包含任何字符的串,表示为“Ф”。 •空格串: 由一个或多个空格字符组成的串。 例如: “”。 2.串的基本操作 (1)用串变量赋值assign(s,t)和用串常量赋值create(s,ss) (2)判等函数equal(s,t) (3)求长函数length(s) (4)连接函数concat(s,t) (5)求子串函数substring(s,pos,len) (6)定位函数index(s,t) (7)置换函数replace(s,t,v) (8)插入子串insert(s,pos,t) (9)删除子串delete(s,pos,k) (10)串的复制copy(s,t) 【例3-1】已知字符串: a=“anapple”,b=“otherhero”,c=“her”,求: (1)concat(substr(a,1,2),b)。 (2)replace(a,substr(a,5,1),c)。 (3)index(a,c)和index(b,c)。 解: (1)返回值为“anotherhero”,其中substr(a,1,2)的返回值为“an”。 (2)返回值为“anaherherle”,其中sub(a,5,1)的返回值为“p”。 (3)返回值分别为0和3。 3.串的顺序存储结构(顺序串) 串的顺序存储方式类似于线性表的顺序存储方式,其存储结构用C语言描述为: typedefstructstrnode{ chardata[maxlen]; intlen; }SeqString;//定义顺序串类型 【例3-2】设定串采用顺序存储结构,写出对串s1和串s2比较大小的算法。 串值大小按字典排序(升序)方式,返回值等于-1,0和1分别表示s1 解: 算法思想: (1)比较s1和s2共同长度范围内的对应字符: 若s1的字符>s2的字符,返回; 若s1的字符 若s1的字符=s2的字符,按上述规则继续比较; (2)当 (1)中对应字符均相同时,比较和的长度: 两者相等时,返回0; 前者>后者时,返回1; 前者<后者时,返回-1; 算法描述如下: #defineMAXLEN256 structstrnode{ chardata[MAXLEN]; intlen; }SeqString;//定义顺序串类型 intstrcmp(SeqStrings1,SeqStrings2)//比较串s1和串s2的大小 {intcomlen; if(s1.len elsecomlen=s2.len; for(i=0;i if(s1.ch[i] else if(s1.ch[i]>s2.ch[i])return (1);//s1>s2 if(s1.ch[i]==s2.ch[i])return(0);//s1=s2 else if(s1.ch[i] elsereturn (1);//s1>s2 } 4.串的链式存储结构(即链串或块链结构) 使用链式存储结构的字符串,只要存储空间足够大,其长度没有任何限制,但逻辑上的连续性不体现为物理上的邻接性。 每个字符和一个指针域形成一个结点,结点间的关系由链指针实现,即字符逻辑上的连续性由链指针描述。 其存储结构用C语言描述为: typedefstructstrnode{//定义字符串的结点类型 chardata; structstrnode*next; }LinkString; 习题3 一、单项选择题 1.空串与空格字符组成的串的区别在于()。 A.没有区别B.两串的长度不相等 C.两串的长度相等D.两串包含的字符不相同 2.一个子串在包含它的主串中的位置是指()。 A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3.下面的说法中,只有()是正确的。 A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中,则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4.两个字符串相等的条件是()。 A.两串的长度相等 B.两串包含的字符相同 C.两串的长度相等,并且两串包含的字符相同 D.两串的长度相等,并且对应位置上的字符相同 5.若SUBSTR(S,i,k)表示求S中从第i个字符开始的连续k个字符组成的子串的操作,则对于S=“Beijing&Nanjing”,SUBSTR(S,4,5)=()。 A.“ijing”B.“jing&” C.“ingNa”D.“ing&N” 6.若INDEX(S,T)表示求T在S中的位置的操作,则对于S=“Beijing&Nanjing”,T=“jing”,INDEX(S,T)=()。 A.2B.3C.4D.5 7.若REPLACE(S,S1,S2)表示用字符串S2替换字符串S中的子串S1的操作,则对于S=“Beijing&Nanjing”,S1=“Beijing”,S2=“Shanghai”,REPLACE(S,S1,S2)=()。 A.“Nanjing&Shanghai”B.“Nanjing&Nanjing” C.“ShanghaiNanjing”D.“Shanghai&Nanjing” 8.在长度为n的字符串S的第i个位置插入另外一个字符串,i的合法值应该是()。 A.i>0B.i≤n C.1≤i≤nD.1≤i≤n+1 9.字符串采用结点大小为1的链表作为其存储结构,是指()。 A.链表的长度为1 B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 二、填空题 1.计算机软件系统中,有两种处理字符串长度的方法: 一种是___________,第二种是___________________。 2.两个字符串相等的充要条件是_____________________和___________________。 3.设字符串S1=“ABCDEF”,S2=“PQRS”,则运算S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2))后的串值为___________________。 4.串是指___________________。 5.空串是指___________________,空格串是指___________________。 三、算法设计题 1.设有一个长度为s的字符串,其字符顺序存放在一个一维数组的第1至第s个单元中(每个单元存放一个字符)。 现要求从此串的第m个字符以后删除长度为t的子串,m 2.设s和t是表示成单链表的两个串,试编写一个找出s中第1个不在t中出现的字符(假定每个结点只存放1个字符)的算法。 习题3参考答案 一、单项选择题 1.B2.D3.C4.D5.B6.C7.D8.C9.D 二、填空题 1.固定长度,设置长度指针 2.两个串的长度相等,对应位置的字符相等 3.“BCDEDE” 4.含n个字符的有限序列(n≥0) 5.不含任何字符的串,仅含空格字符的字符串 三、算法设计题 1.算法描述为: intdelete(r,s,t,m)//从串的第m个字符以后删除长度为t的子串 charr[]; ints,t,m; {inti,j; for(i=1;i<=m;i++) r[s+i]=r[i]; for(j=m+t-i;j<=s;j++) r[s-t+j]=r[j]; return (1); }//delete 2.算法思想为: (1)链表s中取出一个字符;将该字符与单链表t中的字符依次比较; (2)当t中有与从s中取出的这个字符相等的字符,则从t中取下一个字符重复以上比较; (3)当t中没有与从s中取出的这个字符相等的字符,则算法结束。 设单链表类型为LinkList;注意,此时类型LinkList中的data成分为字符类型。 LinkStringfind(s,t) LinkString*s,*t; {LinkString*ps,*pt; ps=s; while(ps! =NULL) {pt=t; while((pt! =NULL)&&(ps->data! =pt->data)) pt=pt->next; if(pt==NULL) ps=NULL; else {ps=ps->next; s=ps; } } returns; }//find 第4章数组和广义表 讲课提要 【主要内容】 1.多维数组的顺序存储结构 2.特殊矩阵的压缩存储 3.广义表的定义及其与线性表的关系 4.广义表的存储结构 5.广义表运算实现中递归的应用 【教学目标】 1.掌握多维数组的顺序存储结构 2.掌握特殊矩阵的压缩存储方法 3.掌握广义表的定义及其与线性表的关系 4.掌握广义表的存储结构 5.了解广义表运算实现中递归的应用 【所需课时】 二次课。 [第一次课] 1.多维数组的顺序存储结构 2.特殊矩阵的压缩存储方法 3.广义表的定义及其与线性表的关系 [第二次课] 4.广义表的存储结构 5.广义表运算实现中递归的应用 学习指导 1.多维数组的顺序存储结构 对于多维数组,有两种存储方式: 一是以行为主序(或先行后列)的顺序存放,如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配,即一行分配完了接着分配下一行。 另一种是以列为主序(先列后行)的顺序存放,如FORTRAN语言中,用的是以列为主序的分配顺序,即一列一列地分配。 以行为主序的分配规律是: 最右边的下标先变化,即最右下标从小到大,循环一遍后,右边第二个下标再变,…,从右向左,最后是左下标。 以列为主序分配的规律是: 最左边的下标先变化,即最左下标从小到大,循环一遍后,左边第二个下标再变,…,从左向右,最后是右下标。 不论按何种方式存储,只要确定了数组的首地址以及每个数组元素所占用的单元数,就可以将数组元素的存储地址表示为其下标的线性函数。 设有m×n二维数组Amn,以“以行为主序”的分配为例,按照元素的下标确定其地址的计算方法如下。 设数组的基址为LOC(a11),每个数组元素占据L个地址单元,计算aij的物理地址的函数为: LOC(aij)=LOC(a11)+((i-1)*n+j-1)*L 同理,对于三维数组Amnp,即m×n×p数组,对于数组元素aijk其物理地址为: LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1))*L 注意: 在C语言中,数组中每一维的下界定义为0,则: LOC(aij)=LOC(a00)+(i*n+j)*L 【例4-1】二维数组A的每一个元素是由6个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。 若A以行为主序存储元素,A[8][5]的物理地址与当A按列为主序存储时的元素()的物理地址相同。 设每个字符占一个字节。 A.A[8][5]B.A[3][10]C
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 习题 参考答案 数组 广义