数据结构习题参考答案文档格式.docx
- 文档编号:7682933
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:65
- 大小:202.21KB
数据结构习题参考答案文档格式.docx
《数据结构习题参考答案文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构习题参考答案文档格式.docx(65页珍藏版)》请在冰点文库上搜索。
(3)单链表——单链表的每个结点都有两个域,一个数据域和一个指针域,称之为单链表。
(4)双链表——以链表形式存储的线性表,其结点包含一个数据域和两个指针域,称之为双链表。
(5)循环链表——若线性链表的最后一个结点的指针指向头结点,使得链表头尾结点相连,就构成了循环链表。
(6)存储密度——存储密度定义为结点数据本身所占的存储量与结点结构实际分配的存储量的比值。
顺序表的存储密度等于1;
链表结构存储密度小于1。
二.判断题(下列各题,正确的请在前面的括号内打√;
(1)ㄨ
(2)ㄨ(3)√(4)ㄨ(5)ㄨ
(6)√(7)ㄨ(8)ㄨ(9)√(10)√
1.一定
2.不必
3.有限的一对一关系
4.节省存储随机存取
5.插入删除小
6.n/2表长n和插入位置
7.(n-1)/2表长n和删除位置
8.O
(1)
9.直接前驱
10.的直接前趋结点的地址O(n)
11.O
(1)
12.*P的直接前驱结点的地址O(n)O
(1)
13.头指针
(1)B
(2)A(3)B(4)C(5)A
(6)A(7)B(8)B(9)D(10)B
五.简答题
1.顺序存储结构的长处是节约存储空间,可以随机存取。
(缺点是插入、删除要作大量移动,不易扩充);
链表存储结构优点是插入、删除操作容易,表的扩充方便。
(缺点是存储密度低)。
2.头指针——指向链表中第一个结点(头结点或无头结点时的开始结点)的指针。
头结点——在开始结点之前附加的一个结点。
开始结点——在链表中,存储第一个数据元素的结点。
3.主要是简化操作。
由于表的操作常在表的两端进行,所以对单循环链表,当知道其尾指针rear后,其另一端的头指针是rear->
next->
next(表中代头结点),仅改变两个指针值即可,运算时间为O
(1)。
六.
(1)返回结点*p的直接前趋结点地址。
(2)交换结点*p和结点*q(p和q的值不变)。
七.程序设计题
1.解:
voidShow(ListNode*P)
{ListNode*t=P;
do
{printf("
%c"
t->
data);
t=t->
rear;
}
while(t!
=P);
}
2.解:
voiddelete(ListNode*L)
{ListNode*p=L,*q;
if(L->
data==X)
{printf(“值为x的结点是第一个结点,没有直接前趋结点可以删除”);
return;
for(;
p->
data!
=X;
q=p,p=p->
next);
//删除指针p所指向的结点
q->
next=p->
next;
deletep;
3.解voidDel(SeqList*L,inti,intk)
{intj=i-1+k;
for(j=0;
j<
k;
j++)
{L->
data[i-1+j]=L->
data[i+k-2+j];
if(i+k-2+j>
L->
last)
break;
}
4.解:
本题是遍历该链表的每个结点,每遇到一个结点,结点个数加1,结点个数存储在变量n中。
实现本题功能的函数如下:
intcounter(head)
node*head;
{node*p;
intn=0;
p=head;
while(p!
=NULL)
{if(p->
data==x)n++;
p=p->
return(n);
5.解:
本题的算法思想是:
先找到两链表的尾指针,将第一个链表的尾指针与第二个链表的头结点链接起来,使之成为循环的。
函数如下:
node*link(head1,head2)
node*head1,*head2;
{node*p,*q;
p=head1;
while(p->
next!
=head1)p=p->
q=head2;
while(q->
=head2)q=q->
p->
next=head2;
next=head1;
return(head1);
6.解:
假设输入一组多项式的系数和指数,以输入系数为标志结束,在建立多项式链表时,总是按照指数从大到小顺序排列的。
两个多项式链表A和B,其头指针分别是heada和headb,这两个多项的多项式链表为C,其头指针为headc。
structpnode*padd(heada,headb)
structpnode*heada,*headb;
{structpnode*headc,*p,*q,*s;
intx;
p=heada;
q=headb;
headc=(structpnode*)malloc(sizeof(structpndoe));
r=headc;
while(p!
=NULL&
&
q!
{if(p->
exp==q->
exp)//两结点指数相等时,将两系数相加生成新结点插入C中
{x=p->
coef+q->
coef;
if(x!
=0)
{s=(structpnode*)malloc(sizeof(structpnode));
s->
coef=s;
exp=p->
exp;
r->
link=s;
r=s;
p=p->
link;
q=q->
else//两结点的指数不相等时,将其中较小系数的结点复制成一新结点插入C中
if(p->
exp<
q->
exp)
{
s=(structpnode*)malloc(sizeof(structpnode));
coef=q->
exp=q->
link=s;
q=q->
else
s=(structpnode*)malloc(sizeof(structpnode));
coef=p->
p=p->
=NULL)//复制A的余下部分
{
s=(structpnode*)malloc(sizeof(structpnode));
//复制一个结点s
//把s链接到C中
}
while(q!
=NULL)//复制B的余下部分
//把s链接到C中
r->
link=NULL;
//最后结点的link域置空
s=headc;
//删除C的头结点
headc=headc->
free(s);
return(headc);
习题3
一.名词解释
(1)栈——只允许在一端进行插入或删除操作的线性表称为栈。
其最大的特点是“后进先出”。
(2)顺序栈——采用顺序存储结构的栈称为顺序栈。
(3)链栈——采用链式存储结构的栈称为链栈。
(1)√
(2)√(3)ㄨ(4)ㄨ(5)ㄨ(6)ㄨ
三.填空题
(1)后进先出
(2)栈顶栈底
(3)栈空栈满
(4)O
(1)O
(1)
(5)必须一致
(6)栈
(7)栈空
(8)p->
next=toptop=p
(9)--++
(10)LS->
next首
四.单选题
(1)B
(2)C(3)A(4)D(5)B
(6)C(7)D(8)B(9)A(10)A
五.求下列表达式的后缀表达式(要求写出过程)
(1)AB^C^D/
(2)0A–BC*+DE/+
(3)ABC+*D*E-
(4)AB+C*EFGH/+/-D-
(5)852+/6-
六.算法设计题
用一整型变量top表示栈顶指针,top为0时表示栈为空。
栈中元素从S[1]开始存放元素。
(1)入栈算法:
voidpush(charx)
if((top+M)>
MAXLEN-1)
printf(“堆栈溢出!
”);
if(top==0)
top++;
S[top]=x;
top=top+M;
(2)出栈算法:
voidpop(charx)
printf(“堆栈为空栈!
if(top==1)
x=S[top];
top––;
top=top–M;
设表达式在字符数组a[]中,使用一堆栈S来帮助判断。
intcorrect(chara[])
stacks;
InitStack(s);
//调用初始化栈函数
for(i=0;
i<
strlen(a);
i++)
if(a[i]==’(’)
Push(s,’(’);
elseif(a[i]==’)’)
ifStackEmpty(s)//调用判栈空函数
return0;
//若栈为空返回0;
否则出栈
else
Pop(s);
if(StackEmpty(s))//调用判栈空函数
printf(“配对正确!
//若栈空,说明配对正确,并返回1
printf(“配对错误!
//配对错误返回0
习题4
一.名词解释
(1)队列——只允许在一端进行插入,另一端进行删除操作的线性表称为队列。
其最大的特点是“先进先出”。
(2)顺序队列——采用顺序存储结构的队列称为顺序队列。
(3)链队列——采用链式存储结构的称队列为链队列。
(4)循环队列——为了解决顺序队列中“假溢出”现象,将队列的存储空间想象为一个首尾相链的环(即把队头元素与对尾元素链结起来),存储在其中的队列称为循环队列。
(1)√
(2)√(3)ㄨ(4)√(5)ㄨ(6)ㄨ
1.先进先出
2.队尾队头
3.队列是否为空队列是否为满
4.可变的
5.-1NULL
6.O(n)O
(1)O
(1)O
(1)
7.front==rearfront==(rear+1)%MAXLENMAXLEN-front
8.空只含有一个结点
9.front==rear&
front<
>
NULL
10.队尾指针写入
四、单项选择题
(1)A
(2)C(3)A(4)D(5)A
(6)A(7)B(8)A(9)C(10)A
答:
n个(同类)数据元素的有限序列称为线性表。
线性表的特点是数据元素之间存在“一对一”的关系。
栈和队列都是操作受限制的线性表,它们和线性表一样,数据元素之间都存在“一对一”的关系。
不同之处是:
栈是只允许在一端进行插入或删除操作的线性表,其最大的特点是“后进先出”;
队列是只允许在一端进行插入,另一端进行删除操作的线性表,其最大的特点是“先进先出”。
用一个循环数组Queue[0,n-1]表示该循环队列,头指针为front,计数器count用来记录队列中结点的个数。
(1)入队算法:
voidinqueqe(intx)
{inttemp;
if(count==n)
printf(“队列上溢出\n”);
else
{count++
temp=(front+count)%n;
Queue[temp]=x
(2)出队算法:
intoutqueue()
if(count==0)
printf(“队列下溢出\n”);
{temp=Queue[front];
front=(front+1)%n;
count--;
returntemp;
队列为空:
count==0,front==1
队列为满:
count=MAXLEN
队列尾的第一个元素位置==(front+count)%MAXLEN
队列首的第一个元素位置==(front+1)%MAXLEN
constMAXLEN=100;
intqueue[MAXLEN];
intfront,count;
//定义队头和计算器
voidinit()//初始化队列
front=1;
count=0;
intempty()//判定队列是否为空
if(count==0)return
(1);
elsereturn(0);
voidoutqueue(intqueue[],x)//取队列头元素给x
if(count==0)printf(“下溢出\n”);
front=(front+1)%MAXLEN;
x=queue[front];
voidinqueue(intqueue[],intx)//x入队列
intplace;
if(count==MAXLEN)printf(“上溢出\n”);
count++;
place=(front+count)%MAXLEN;
queue[MAXLEN]=x;
voidoutqueue(intqueue[])//删除队列头元素
if(count==0)printf(“队列下溢出\n”);
front=(front+1)%MAXLEN;
count--;
3.
(1)解:
定义本题队列的结点类型如下:
typedefstructlinknode
intdata;
structlinknode*next;
}qu;
qu*rear;
inqueue(intx)//向队列插入结点x
qu*head,*s;
s=(qu*)malloc(size(qu));
//创建一个新结点
data=x;
if(rear==NUlL)//循环队列为空,则建立一个结点的循环队列
rear=s;
rear->
next=s;
else//循环队列不为空,则将s插到后面
head=rear->
next;
rear=s;
//rear始终指向最后一个结点
next=head;
(2)解:
voiddelqueue(rear)
{
if(rear==NULL)printf(“下溢出!
\n”);
else
{head=rear->
//head指向队首结点
if(head==rear)rear=NULL//只有—个结点,则直接删除该结点
elserear->
next=head->
next//否则删除第一个结点
free(head);
//释放队首结点
}
习题5
串:
串(string)是由零个或多个字符组成的有限序列。
一般记为
S=“a1a2...an”(n≥0)
其中,S是串名,用双引号或单引号括起来的字符序列是串的值,ai(1≤i≤n)称为串的元素,它可以是字母、数字、空格或其他字符。
串中字符的个数n称为串的长度。
广义表:
广义表(GeneralizedLists)是n(n≥0)个数据元素a1,a2,…,ai…,an的有序序列,一般记作:
ls=(a1,a2,…,ai,…,an)
其中:
ls是广义表的名称,n是它的长度。
每个ai(1≤i≤n)是ls的成员,它可以是单个元素,称为广义表ls的原子,也可以是一个广义表,称为广义表的子表。
当广义表ls非空时,称第一个元素a1为ls的表头(head),称其余元素组成的表(a2,…,ai,…,an)为ls的表尾(tail)。
广义表的定义是递归的。
(1)ㄨ
(2)√(3)ㄨ(4)ㄨ(5)√(6)√(7)ㄨ(8)√(9)ㄨ(10)√
三.填空题(10个)
1.长度
2.空串零
3.顺序存储
4.数据指针数据指针
5.模式匹配
6.顺序存储和链式存储
7.(a)(((b),c),(((d))))
8.广义表
1.B2.D3.B4.C5.C6.A7.B8.A
1.简述串的存储结构及各自的特点。
串的存储方式有主要有顺序存储、堆分配存储和链式存储。
顺序结构:
用一组地址连续的存储单元存储串的字符序列,构成串的顺序存储,简称为顺序串。
特点:
这种结构是按照预设大小,为每个定义的串变量分配一个固定长度的存储区。
因此存在存储空间的越界或浪费的问题。
对于操作如查找但是操作简单方便。
堆分配存储结构:
在内存中开辟地址连续的存储空间作为串的可利用存储空间,称为堆空间,根据每个串的长度,动态地为每个串在堆空间里申请相应大小的存储区域的一种存储结构。
以一组地址连续的存储单元存放串的字符序列,但其存储空间是在算法执行过程中动态分配得到的,串也是顺序存储在所申请的存储区域中。
由于堆分配存储结构的串既有顺序存储结构的特点,又没有造成对存储空间的浪费和对串长加以限制,使用非常灵活。
链式存储结构:
是将存储区域分成一系列大小相同的结点,每个结点有两个域即数据域data和指针域next。
其中数据域用于存放字符串元素,指针域用于存放下一个结点的地址。
在串中使用链式存储结构同样是在插入、删除等操作中没有移动元素所带来的时间耗费,存储空间的扩展容易;
但结点的容量会带来存储空间的利用率降低。
2.广义表具有哪些性质?
(1)广义表是一种多层次的数据结构。
广义表的元素可以是原子,也可以是子表,而子表的元素还可以是子表。
(2)广义表可以是递归的表。
广义表的定义并没有限制元素的递归,即广义表也可以是其自身的子表。
例如表E就是一个递归的表。
(3)广义表可以为其他表所共享。
例如D=(A,B,C)时,表A、B、C是表D的共享子表。
在D中可以不必列出子表的值,而用子表的名称来引用。
六.下述算法的功能是什么
(1)实现串S和串T的连接运算。
(2)返回串S中从第n1个字符开始取n2个字符组成的子串。
七.程序设计题
1.写一个递归算法来实现字符的逆序存储,要求不另设存储空间。
#include"
stdio.h"
#includeMAXSIZE80
charnext[MAXSIZE80];
/*串的最大长度*/
voidreverse(intn)/*递归函数实现逆置*/
if(n<
=1)
next[n]=getchar();
putchar(next[n]);
next[n]=getchar();
reverse(n-1);
putchar(next[n]);
main()
{inti;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题 参考答案