数据结构习题集与参考答案重要Word文档下载推荐.docx
《数据结构习题集与参考答案重要Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构习题集与参考答案重要Word文档下载推荐.docx（55页珍藏版）》请在冰点文库上搜索。
二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。
1.A=（K，R），其中：
K={a，b，c，d，e，f，g，h}，R={r}，r={<
a，b>
b，c>
c，d>
d，e>
e，f>
f，g>
g，h>
2.B=（K，R），其中：
d，b>
d，g>
d，a>
g，e>
3.C=（K，R），其中：
K={a，b，c，d，e}，R={r}，r={<
a，d>
c，f>
4.D=（K，R），其中：
K={48，25，64，57，82，36，75}，R={r1，r2}，r1={<
25，36>
36，48>
48，57>
57，64>
64，75>
75，82>
}；
r2={<
48，25>
48，64>
64，57>
64，82>
25，75>
5.E=（K，R），其中：
K={1，2，3，4，5，6，7}，R={r}，r={<
1，2>
2，1>
1，4>
4，1>
2，3>
3，2>
3，4>
4，3>
1，3>
3，1>
三、指出下列各函数的功能并求出其时间复杂度。
1.voidprime（intn）
{
inti;
for（i=2;
i<
=sqrt（n）;
i++）if（n%i==0）break;
if（i>
sqrt（n））printf（“yes”）;
elseprintf（“no”）;
}
2.longsum1（intn）
{
longsum,w,i;
for（sum=0,i=1;
=n;
i++）{w=1;
for（j=1;
j<
=i;
j++）w=w×
i;
sum=sum+w;
}
return（sum）;
3.longsum2（intn）
for（sum=0,w=1,i=1;
i++）{w=w×
4.voidsort（intr[],intn）
inti,j;
for（i=1;
i<
n;
i++）for（j=0;
n-i;
j++）
if（r[j]>
r[j+1]）{temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
第一章参考答案
1．数据元素，数据项，结构
2．数据，关系
3．树型
4．O
（1），O（n），O（log2n），O（n2）
5．线性结构，非线性结构，顺序结构，链式结构
6．无，一，无，一
7．前驱，一，无，任意
8．任意
9．O（n1/2）
分析：
设程序段中的循环体执行k次，则有不等式
成立，解此不等式得到不等式
，因此
。
10．O
（1）<
O（log2n）<
O（n）<
O（nlog2n）<
O（n2）<
O（n3）<
O（2n）
1．线性结构
2．树型结构
3．图型结构
4．图型结构
数据结构D中的关系集合R有两个关系r1和r2。
如果只考虑关系r1，则为线性结构；
如果只考虑关系r2，则为树型结构；
如果把关系r1和r2联合起来考虑，则为图型结构。
5．图型结构
若用图形来表示则可以看出r是E上的对称关系，为了简化起见，我们通常把<
x，y>
和<
y，x>
这两个有序偶对用一个无序偶对（x，y）或（y，x）来代替。
在用图形表示时，我们把x结点和y结点之间两条相反的弧用一条无向边来代替。
1．函数的功能是判断n是否是一个素数，其时间复杂度为O（n1/2）。
函数prime中出现的库函数sqrt为平方根函数，因此
2．函数的计算
的值，其时间复杂度为O（n2）。
3．函数的计算
的值，其时间复杂度为O（n）。
4．函数的功能是对数组r中的n个元素进行冒泡排序，其时间复杂度为O（n2）。
第二章线性表
1．设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动_______个元素，删除一个元素时平均需要移动______个元素。
2．在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要________移动一个位置。
3．在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要__________移动一个位置。
4．线性表的链式存储结构中，元素之间的线性关系是通过结点中的________来实现的。
5．线性表的顺序存储结构中逻辑上相邻的元素，物理位置__________相邻；
线性表的链式存储结构中逻辑上相邻的元素，物理位置____________相邻。
6．已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为__________。
7．已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为__________。
8．在单链表中设置头结点的作用是________________________________。
9．双向链表中每个结点含有两个指针域，其中一个指针域指向_______结点，另一个指针域指向______结点。
10．在长度为n的线性表中顺序查找某个结点值为X的时间复杂度为______________。
二、选择题
1．在长度为n的顺序线性表中删除第i个元素（1<
=i<
=n），则需要向前移动的元素个数为（）。
⑴n-i⑵n+1-i⑶n-1-i⑷i
2．建立一个长度为n的单链表的时间复杂度为（）。
⑴O（n）⑵O
（1）⑶O（n2）⑷（（log2n）
3．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（）。
⑴p->
next=p⑵p=p->
next
⑶p=p->
next->
next⑷p->
next=p->
4．设指针p指向单链表中结点A，指针q指向单链表中结点A的前驱结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（）。
⑴s->
next；
p->
next=s；
⑵q->
s->
next=p；
⑶p->
next=s->
⑷p->
next=q；
5．在长度为n的顺序线性表中的第i个元素（1<
=n+1）之前插入一个新元素时，则需要向后移动的元素个数为（）。
6．在长度为n的有序线性表中插入一个元素后仍然保持有序的平均时间复杂度为（）。
⑴O（log2n）⑵O
（1）⑶O（n2）⑷O（n）
7．设指针p指向双向链表中的结点A，指针s指向被插入的结点X，则在结点A之后插入结点X的操作为（）。
rlink=s；
llink=p；
rlink->
llink=s；
rlink=p->
rlink；
⑵s->
p->
⑷s->
8．指针p指向双向链表中的结点A，则删除结点A的操作是（）。
llink->
llink=p->
llink；
⑵p->
⑷p->
9．线性表采用链式存储结构时，要求存储单元的地址（）。
⑴必须是连续的⑵部分地址必须是连续的
⑶一定是不连续的⑷连续不连续都可以
10．设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（）。
⑴head==NULL⑵head->
next==NULL
⑶head->
next==head⑷head!
=NULL
11．设head为单链表的头指针，则带头结点的单链表为空的判定条件是（）。
12．设head和tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（）。
⑴head==tail⑵head->
next==tail
⑶tail->
next==head⑷head->
next==tail->
三、算法设计题
顺序存储结构的类型定义：
typedefstruct{inta[m];
intn;
}sqlist;
链式存储结构的类型定义：
typedefstructnode{intdata;
structnode*next;
}lklist;
1.建立一个有n个结点的单链表，要求从尾部进行插入。
2.建立一个有n个结点的单链表，要求从头部进行插入。
3.用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，an）逆置为（an，an-1，……，a1）。
4.用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，……，an）逆置为（an，an-1，……，a1）。
5.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。
6.已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。
7.设计在带有头结点的单向链表中删除值为X的结点算法。
第二章参考答案
1．n/2，（n-1）/2
当在顺序线性表中的第i（1<
=n+1）个位置之前插入一个新元素时，从第i个元素起向后的n+1-i个元素均要向后移动一个位置。
因此在等概率情况下，插入操作中元素的平均移动次数为
；
当在顺序线性表中删除第i（1<
=n）个位置上的元素，从第i+1个元素起向后的n-i个元素均要向前移动一个位置。
因此在等概率情况下，删除操作中元素的平均移动次数为
2．向后
3．向前
4．指针域
5．一定，不一定
6．O（n）
7．O（n）
8．消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。
9．前驱，后继
10．O（n）
二、填空题
1．
（1）
2．
（1）
建立一个单链表的过程实际上就是在空链表的基础之上从单链表的头部或从单链表的尾部不断插入新结点的过程，因此建立单链表的时间复杂度为O（n）。
3．（4）
4．
（2）
5．
（2）
6．（4）
在有序的线性表中插入一个元素后仍然保持有序的过程分为两步：
第一步查找插入位置，第二步插入新元素。
在线性表中查找插入位置的平均时间复杂度为f1（n）=O（n），在顺序线性表中插入新元素的平均时间复杂度为f2（n）=O（n），而在链式线性表中插入新元素的平均时间复杂度为f2（n）=O
（1），因此本题中的平均时间复杂度f（n）=O（n）+O
（1）=O（n）或f（n）=O（n）+O（n）=O（n）。
7．（4）
在双向链表或双向循环链表中插入一个新结点的操作比较繁琐，通常需要修改4个指针域，根据排列公式可知共有4!
=24种方案。
在这24种方案中，有些方案是可行的，有些方案是不可行的。
我们的通常做法是先连接哪些不破坏有用信息的指针域，然后再根据需要连接其余的指针域，在操作过程中注意修改有关结点指针域的操作顺序，以免丢失链域信息而造成链表中断的错误。
8．
（1）
在双向链表或双向循环链表中删除一个结点的操作比较相对插入一个新结点而言稍微简单一些，只需要修改两个指针域。
首先找到指向前驱结点的指针（p->
left）和指向后继结点的指针（p->
right），然后再分别表示出前驱结点中的右指针域（p->
left->
right）和后继结点的左指针域（p->
right->
left），最后分别修改前驱结点中的右指针域和后继结点的左指针域。
9．（4）
10．
（1）
11．
（2）
12．（3）
本题的算法思想是设置指针变量q始终指向当前链表中的最后一个结点，新生成的结点直接在尾部进行插入。
这种设置指针变量q的方法使得操作比较简单，否则每次在尾部插入新结点时需要用一个临时指针变量从链表头部移到链表尾部。
voidcreatelklistfromtail（lklist*&
head）
inti;
lklist*p,*q;
for（i=1,head=0;
i++）
p=（lklist*）malloc（sizeof（lklist））;
scanf（"
%d"
&
（p->
data））;
next=0;
if（i==1）head=q=p;
else{q->
next=p;
q=p;
提示：
以下形式参数表中出现在形式参数名前加符号“&
”的现象，这种现象在我们常见的TurboC2.0版本中不能使用，但在BorlandC3.1及其以后版本中可以使用，它的作用是使得对形式参数的修改可以影响到对应的实在参数。
以后算法设计题中经常用到。
voidcreatelklistfromhead（lklist*&
head）
for（i=1,q=head=0;
scanf（"
next=head;
head=p;
不断从头部插入新结点的方法来构造单向链表比不断从尾部插入新结点的方法来构造单向链表稍微操作简单一些。
但顺序打印从尾部插入建立的单向链表所得到的序列与建立单向链表输入的序列一样，而顺序打印从头部插入建立的单向链表所得到的序列与建立单向链表输入的序列正好相反。
voidinvertsqlist（sqlist&
list）
inti,temp,n=list.n;
=n/2;
i++）{temp=list.a[i-1];
list.a[i-1]=list.a[n-i];
list.a[n-i]=temp;
本题中的循环次数只能是顺序线性表的长度一半，如果循环次数是顺序线性表的长度，则经过逆置后再逆置而还原到初始状态。
本题的算法思想是依次将单链表中的结点取出来并用指针q指向它，然后再用从头部插入的方法建立一个新的单链表。
voidinvertlklist（lklist*&
head）
lklist*p=head,*q;
head=0;
while（p!
=0）{q=p;
p=p->
next;
q->
head=q;
本题的算法思想是顺序取出集合A中的元素A[i]，然后再在集合B中从前向后进行顺序查找，如果找到等于该元素的结点则将其放入集合C中，否则什么也不做。
本题算法思想同样适用于其后的第6题。
voidintersectionsqlist（sqlistlista,sqlistlistb,sqlist&
listc）
for（listc.n=0,i=0;
=lista.n-1;
i++）
for（j=0;
=listb.n-1;
j++）if（listb.a[j]==lista.a[i]）break;
if（j<
=listb.n-1）{listc.a[listc.n]=lista.a[i];
listc.n++;
voidintersectionlklist（lklist*lista,lklist*listb,lklist*&
lklist*p,*q,*s;
for（listc=0,p=lista;
p!
=0;
next）
for（q=listb;
q!
q=q->
next）if（p->
data==q->
data）break;
if（q!
=0）{s=（lklist*）malloc（sizeof（lklist））;
data=p->
data;
next=listc;
listc=s;
本题的算法思想是首先在单链表中查找值为x的结点，如果单链表为空或在单链表中找不到值为x的结点则给出相应的提示信息，否则进行删除操作。
为了便于删除操作的实现而设置指针变量p指向被删除的结点，指针变量q始终指向其前驱结点。
voiddeletelklist（lklist*&
head,intx）
lklist*q,*p;
if（head->
next==0）printf（“Thislinklistisempty\n”）;
elsefor（q=head,p=head->
p!
q=p,p=p->
data==x）break;
if（p==0）printf（“Notfound%dinthislinklist\n”,x）;
else{q->
free（p）;
在链表中引入头结点后可以消除空表的特殊性，统一表示和处理空表和非空表的情形，从而简化插入和删除等操作的某些细节。
具体涉及到本题中，如果没有引入头结点，则在找到值为x的结点后要区分该结点是第一个结点还是其它结点，而引入头结点后，则这两种情况就可以统一处理。
如果本题中的单链表没有带头结点，则需要将上述黑体中的代码改为代码if（p==head）head=p->
elseq->
第三章栈和队列
1.线性表、栈和队列从逻辑上来说都是____________结构。
可以在线性表的_______位置插入和删除元素；
对于栈只能在__________插入和删除元素；
对于队列只能在___________插入元素和在_________删除元素。
2.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；
队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做__________，进行删除的一端叫做___________，先进队的元素必定先出队，所以又把队列称为____________表。
3.假设用向量S[1：
m]来存储顺序栈，指针top指向当前栈顶的位置。
则当栈为空时满足的条件是____________；
当栈为满时满足的条件是_____________。
4.设有一个空栈，现有输入序列1、2、3、4、5，经过push、push、pop、push、pop、push、push、pop、pop、pop后，输出序列为__________________。
5.在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front指向实际队头元素的____________，尾指针rear指向当前实际队尾元素的____________。
若该顺序循环队列有m个存储单元，则队列满时共有__________个元素。
6.设有一个顺序循环队列如上题中的约定，则该队列满的条件是__
升级会员 