数据结构 习题Word下载.docx
《数据结构 习题Word下载.docx》由会员分享，可在线阅读，更多相关《数据结构 习题Word下载.docx（48页珍藏版）》请在冰点文库上搜索。
）
A.p=p->
B、p->
next->
C.p->
D.p=p->
12．在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->
next=head,则（
A.p指向头结点
B.p指向尾结点
C.*p的直接后继是头结点
D、*P的直接后继是尾
13.为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（）方式。
A、顺序存储B.链式存储
C.索引存储D.散列存储
答案：
1-5BDACB6-10DBABC11-13BDA
二、判断题（判断下列各小题，正确的在题后括号内打“√”，错的打“╳”。
）
1、单链表中的头结点就是单链表的第一个结点。
（╳）
2、所谓数据的逻辑结构指的是数据元素之间的逻辑关系。
（√）
3、在线性结构中，每个结点都有一个直接前驱和一个直接后继。
三、填空题
1、在单链表中设置头结点的作用_。
2、.设head为带有头结点的单链表的头指针，则判断单链表为空的条件是：
_________。
3、.带头结点的循环链表L为空表的条件是____。
带头结点的双循环链表L为空表的条件是_。
4、在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_______和_______。
5、.通常单链表的头结点指的是________；
单链表的首结点指的是________。
6、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为。
7、从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。
1、简化插入删除算法.
2、head->
next==NULL_____。
3、L->
next=L___。
L->
next=L->
prior=L
4、__s->
next______和_p->
next=s_______。
5、_在单链表第一个结点之前增设的一个类型相同的结点_______；
__表结点中的第一个结点______。
6、p－＞next－＞next=head。
7、__向前移动__
四、算法阅读题
1、阅读下面的算法
LinkListmynote（LinkListL）
{//L是不带头结点的单链表的头指针
if（L&
&
next）{
q=L；
L=L－>
next；
p=L；
S1：
while（p－>
next）p=p－>
S2：
p－>
next=q；
q－>
next=NULL；
}
returnL；
请回答下列问题：
（1）说明语句S1的功能；
（2）说明语句组S2的功能；
（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。
（1）查询表的尾节点
（2）将第一个节点链接到表的尾部成为新的尾节点
（3）（a2,a3,….an,a1）
2、以下函数中，h是带头结点的双向循环链表的头指针。
（1）说明程序的功能；
（2）当链表中结点数分别为1和6（不包括头结点）时，请写出程序中while循环体的执行次数。
intf（DListNode*h）
{
DListNode*p,*q;
intj=1;
p=h->
q=h->
prior;
while（（p!
=q||p->
prior!
=q）&
（j!
=0））
if（p->
data==q->
data）
p=p->
q=q->
}
elsej=0;
returnj;
（1）是否对称
（2）1----0；
6---3
五、应用题
1、假定在学生的档案中含有：
姓名、学号、年龄、性别。
如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。
2.假设以带头结点的单循环链表作非递减有序线性表的存储结构。
请设计一个时间复杂度为O（n）的算法，删除表中所有数值相同的多余元素，并释放结点空间。
例如：
（7，10，10，21，30，42，42，42，51，70）
经算法操作后变为
（7，10，21，30，42，51，70）
参考答案：
typedefstructnode{
intdata;
structnode*next;
}LinkList;
Delete_Eq（LinkList*head）
{
LinkList*p,*q,*s;
p=head;
do{
q=p->
if（p->
data==q->
data）
{s=q;
free（s）;
q=q->
else
p=q;
}while（p->
next!
=head）;
}
2、线性表逆置
voidConvers（LinkList*head）
LinkList*p,*q,*r;
p=head;
q=p->
next=NULL;
while（q!
=NULL）
{
r=q->
q->
q=r;
head=p;
栈和队列习题
1.简述下面所给算法的功能是什么？
（假设栈元素为整数类型）
（1）voidex31（SeqStack*S）
intA[80],i,n;
n=0;
while（!
empty（S））
{A[n]=pop[S];
n++;
for（i=0;
i<
n;
i++）
push（S,A[i]）;
此算法功能是通过一个数组将一个栈中的所有元素逆置存放。
例如原来栈S中存放5个元素abcde，经过算法执行后，变为edcba。
（2）voidex32（SeqStack*s,intc）
SeqStackT;
intd;
StackEmpty（S））
{d=pop（S）;
if（d!
=c）push（T,d）;
while（!
StackEmpty（T））
{d=pop（T）;
=c）push（S,d）;
通过一个中间栈T，达到删除栈S中所有与变量c相同的元素。
2：
算法设计题
试利用循环队列（长度为k）存储,编写求斐波那契的前n（n>
k）项（f0,f1,f2,…）的算法，其函数定义如下：
0n=0
f（n）=1n=1
f（n-2）+f（n-1）n>
=2
算法如下：
因为循环队列长度为K，所以在执行算法结束时，留在队列中的元素应是所求序列中的最后k项。
由于只有k个元素空间，则在计算fi时，队列总是处在头尾相接的状态，因此只须一个指针rear指向当前的队尾。
每次求得一个fi之后即送入（rear%k）的位置上，冲掉原来对头元素。
#definemmaxlen
typedefstruct{
intrear;
intdata[m];
}CirQueue;
intFibonacci（inti）//求序列的前n项算法
{if（i==0）
return0;
elseif（i==1）
return1;
elsereturn（Fibonacci（i-2）+Fibonacci（i-1））;
voidFibonacci（CirQueue*Q,intk）
inti,n;
Q->
rear=0;
scanf（“%d”,&
n）;
for（i=0;
i<
n;
i++）
{Q->
rear=i;
if（i>
=k）Q->
rear=Q->
rear%k;
data[Q->
rear]=Fibonacci（i）;
3．算法阅读
假设两个队列共享一个循环向量空间（参见右下图），
其类型Queue2定义如下：
typedefstruct{
DateTypedata[MaxSize]；
intfront[2],rear[2]；
}Queue2；
对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。
请对以下算法填空，实现第i个队列的入队操作。
intEnQueue（Queue2*Q,inti,DateTypex）
{//若第i个队列不满，则元素x入队列，并返回1；
否则返回0
if（i<
0||i>
1）return0；
if（Q－>
rear[i]==Q－>
front[①]return0；
Q－>
data[②]=x；
rear[i]=[③];
return1；
①（i＋1）%2（或1－i）
②Q－>
rear[i]
③（Q－>
rear[i]＋1）%Maxsize
4、假定在一个链队列中只设置队列为指针，不设置对首指针，并且让队尾节点的指针域指向队首节点（称此微循环队列），试分别写出在循环链队上进行插入和删除操作的算法。
插入算法：
voidQInsert（LNode*&
Rear,constElemtype&
item）
LNode*newptr=newLNode;
if（newptr==NULL）{
printf（“wrong”）;
exit
（1）;
newptr->
data=item;
if（Rear==NULL）
Rear=newptr->
next=newptr;
else{
newptr->
next=Rear->
Rear->
Rear=newptr;
删除算法：
ElemTypeQDelte（LNode*&
Rear）
if（Rear==NULL）{
printf（“Linkedqueueisempty！
”）；
LNode*p=Rear->
if（p==Rear）
Rear=NULL;
next=p->
ElemTypetemp=p->
data;
free（p）;
returntemp;
第四章串习题
练习：
1、串长度的定义是（）
A.串中不同字母的个数B.串中不同字符的个数
C.串中所含字符的个数，且大于0
D.串中所含字符的个数
2、如下陈述中正确的式（）。
A、串是一种特殊的线性表B、串的长度必须大于0
C、串中元素只能是字母D、空串就是空白串
3、设字符串s1=”abcdefg”,s2=”pqrst”,则运算s=strcat（substr（s1,2,length（s2））,substr（s1,length（s2）,2））后串值为（）。
A.“bsdefef”B.“bcpqrst”C.“bsdefg”D.“bcdef”
4、设有两个串s和t,求t在s中首次出现的位置的运算是（）
A.连接B.模式匹配C.求子串D.求串长
一、例子
例1：
从串s1（为顺序存储结构）中第k个字符起求出首次与字符串s2相同的子串的起始位置。
分析：
从第k个元素开始扫描s1，当其元素值与s2第一个元素值相同时，判断它们之后的元素值是否依次相同，直到s2结束为止。
若都相同则返回当前位置值，否则继续上述过程直到s1扫描完为止。
#defineMaxStrSize256
typedefstruct{
charch[MaxStrSize];
intLen;
}SeqString;
intPartPosition（SeqString*s1,SeqString*s2,intk）
inti,j;
i=k;
/*作为扫描s1的下标*/
j=1；
/*作为扫描s2的下标*/
while（i<
=s1->
len&
j<
=s2->
len）
if（s1->
ch[i]==s2->
ch[j]）
{i++;
j++;
else
{i=i-j+2;
j=1;
if（j>
s2->
{returni-s2->
len;
{return0;
例2：
从串s中删除所有与串t相同的子串。
分析：
可利用前面题目的函数。
从位置1开始调用函数PartPosition（）,若找到了相同的子串，则调用删除子串函数DelSubstring（）将其删除，再查找后面位置的相同子串，方法与前同。
voidDelSubstring（SeqString*s,SeqString*t）
intj,k,i=1;
k=1;
while（（i<
=s->
len）&
（k!
=0））
{if（k=PartPosition（s,t,i）>
0）
{for（j=k+t->
j++）
s->
ch[j-t->
len]=s->
ch[j];
/*删除从k开始的子串*/
len=s->
len-t->
len
/*修改s串的长度*/
i=k;
s->
ch[s->
len]=’\0’;
/*赋一个串结束符*/
例3：
已知S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。
根据题意，要用到两重循环，从S中取出第一个字符，与T串中的每个字符依次进行比较，如果一直没有遇到相等的字符，则S中取出的字符就是要求的字符，退出循环；
若遇到相同的字符，则再从S中取出第二个字符与T中的字符进行比较，依次进行下去。
算法如下：
chardata;
structnode*next;
}LinkStrNode;
typedefLinkStrNode*LinkString;
charFindChar（LinkStringS,LinkStringT）
LinkStrNode*p,*q;
P=S;
While（p!
=NULL）
{q=T;
while（q!
{if（p->
data!
=q->
//继续下一个字符的比较
break;
//若有相同的字符，跳出内循环
if（q==NULL）
{returnp->
//返回要求的字符
p=p->
return“#”;
//没有要求的字符
二、算法设计题
1、试写一算法，实现顺序串的比较运算strcmp（S,T）,当S>
T时，函数值为1，当S=T时，函数值为0，当S<
T时，函数值为-1。
算法：
intstrcmp（SeqStringS,SeqStringT）
inti=0;
S.len&
T.len）
if（S.ch[i]>
T.ch[i]）
else
if（S.ch[i]<
return-1;
i++;
if（S.len==T.len）
if（S.len>
return1
2、已知采用顺序存储结构的串S，试写一个算法删除S中第i个字符开始的j个字符。
先判断i和j是否在有效范围内（即i+j<
S.len）,若已查超出范围，则显示出错信息。
否则从i+j-1开始到S.len-1前移j个字符位置。
voiddele（SeqString*s,inti,intj）
intk;
if（i+j-1>
S->
printf（“i或j超出有效范围”）;
for（k=i+j-1;
k<
k++）
S->
ch[k-j]=S->
ch[k];
//移位删除j个字符。
len=S->
len-j;
//串长度减1
3、设S和T是两个采用顺序结构存储的串，试写一个算法将串S中的第i个字符开始的j个字符用串T替换。
SeqSAtring*replace（SeqString*S,SeqString*T,inti,intj）
intk,l;
k=T->
if（k>
0）//说明T的长度大于被替换的串的长度，因此S串需要后移
for（l=S->
len-1;
l>
=i+T->
l--）
ch[l+k]=S->
ch[l];
for（l=i+T->
l<
=S->
l++）
//说明T的长度小于被替换的串的长度，因此S串需要前移
for（l=0;
T->
ch[i+l-1]=T->
//插入串T
len+T->
//修改串S的串长度
ReturnS;
//返回串S
第五章多维数组和广义表
一、应用题
（1）已知二维数组Am*n按“行优先顺序”存储在内存中，假设每个元素占d个存储单元，第一个元素的存储地址表示为LOC（A[0][0]）,那么计算数组A的任意元素A[i][j]的存储地址公式是什么？
LOC（aij）=LOC（a00）+（i*n+j）*d
（2）已知二维数组A[5][10]按“行优先顺序”存储在内存中，假设每个元素占3个存储单元，第一个元素的存储地址表示为1000,那么计算数组A的A[3][4]的存储地址。
LOC（A[23][4]=LOC（A[0][0]）+（3*10+4）*3
（3）已知一个10阶对称矩阵A,采用压缩存储方式存储（以行序为主，每个元素占一个单元），起始地址为1100，则A[4][5]的地址多少？
因为A是对称矩阵，A[4][5]又在上三角，所以存储位置k=j*（j-1）/2+i-1=,因此，A[4][5]的存储地址为LOC（SA）+k*d=
二、自测题
1、一维数组和线性表区别是：
（）
A。
前者长度固定，后者长度可变B.长度均可变
C.无区别D.长度均固定
2、稀疏矩阵一般存储方法有两种（）和（）
3、N是一个5*8的二维数组，当M按行序方式存储时，表示该数组的第十个元素是（）。
N[2][2]B、N[2][1]C、N[1][1]D、N[1][2]
树习题
一、
1.深度为K的完全二叉树至少有_________个结点，至多有_________个结点。
.
（1）2k-1
（2）2k-1。
2.树的三种常用存储结构是：
孩子链表表示法、_________和_________。
（1）孩子兄弟链表示法
（2）双亲表示法。
3.在有n个结点的二叉链表中，值为非空的链域的个数为（）
A.n-1B.2n-1
C.n+1D.2n+1
4.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为（）
A.0B.1
C.2D.不确定
5.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。
2.左右子树空
6.有64个结点的完全二叉树的深度为（）（根的层次为1）。
A.8B.7
C.6D.5
7.二叉树在线索化后，仍不能有效求解的问题是（）
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前趋
D.后序线索二叉树中求后序后继
8．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为（）
A．4B．5C．6D．7
9.具有N个结点的完全二叉树的深度
升级会员 