数据结构习题解答.docx
《数据结构习题解答.docx》由会员分享，可在线阅读，更多相关《数据结构习题解答.docx（19页珍藏版）》请在冰点文库上搜索。
数据结构习题解答
习题一
1填空题
（1）（数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。
（2）（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。
（3）从逻辑关系上讲，数据结构主要分为（集合）、（线性结构）、（树结构）和（图）。
（4）数据的存储结构主要有（顺序存储结构）和（链式存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：
（数据元素）和（它们之间的关系）。
（5）算法具有5个特性，分别是（输入）、（输出）、（有穷性）、（确定性）、（可行性）。
（6）算法的描述方法通常有（自然语言）、（流程图）、（程序设计语言）、（伪代码）4种，其中，（伪代码）被称为算法语言。
（7）一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。
（8）设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（O
（1）），若为n*log25n,则表示成数量级的形式为（O（n*log2n））。
2.选择题:
（1）C,D
（2）B（3）B（4）A（5）D（6）A（7）C（8）C,E
习题二
1.填空题
（1）在顺序表中，等概率情况下，插入和删除一个元素平均需移动（表长的一半）个元素，具体移动元素的个数与（表的长度）和（数据元素所在的位置）有关。
（2）一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是2，则第5个数据元素的存储地址是（108）。
（3）设单链表中指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p->next=（p->next）->next,或者q=p->next;p->next=q->next）。
（4）单链表中设置头结点的作用是（方便运算,减少程序的复杂性，使得空表和非空表处理统一）。
（5）非空的循环单链表由头指针head指示，则其尾结点（由指针p所指）满足（p->next=head）。
（6）在有尾指针rear指示的循环单链表中，在表尾插入一个结点s的操作序列是（s->next=rear->next;rear->next=s;rear=s），删除开始结点的操作序列是（q=rear->next->next;rear->next->next=q->next;deleteq;）。
注：
假设此循环单链表有表头结点
（7）一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（O
（1））；在给定值x的结点后插入一个新结点的时间复杂性为（O（n））。
（8）可由一个尾指针惟一确定的链表有（循环链表）、（双链表）、（双循环链表）。
2.选择题:
（1）A,B
（2）D（3）B（4）A（5）A（6）D（7）B（8）B（9）C（10）B（11）B（12）D（13）A（14）A
5.算法设计
（1）设计一个时间复杂度为O（n）的算法。
实现将数组A[n]中所有元素循环左移k个位置。
算法思想：
要使a1…akak+1…an->ak+1…ana1…ak,可以先让a1…akak+1…an->ak…a1an…ak+1,再让ak…a1an…ak+1->ak+1…ana1…ak，参见第1章16页的思想火花
算法：
voidconverse（Ta[],inti,intj）{
for（s=i;s<=（i+j）/2;s++）//将数组a中从i到j中的元素倒置
{temp=a[s];a[s]=a[j-s+i];a[j-s+i]=temp;}}
voidmove（Ta[],k）
{converse（a,0,k-1）;//3次调用函数converse
converse（a,k,n-1）;
converse（a,0,n-1）;
}
（2）已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O（n）.
解法1：
voidtiaozhen（TA[],intn）
{s=0;t=n-1;
while（s{while（A[s]%2!
=0）s++;//s=s+1
while（A[t]%2==0）t--;
if（s}}
或voidtiaozhen（TA[],intn）
{s=0;t=n-1;
while（s{if（A[s]%2!
=0）s++;//s=s+1
elseif（A[t]%2==0）t--;
else{temp=A[s];A[s]=A[t];A[t]=temp;s++;t--;}
}}
（3）试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较
voidLinkList_1:
:
Insert（inti,Tx）{
if（i<=0）throw"输入的插入位置值小于1";
if（i==1）{s=newNode;s->data=x;s->next=first;first=s;}
else{p=first;j=0;
while（p&&jnext;j++;}
if（!
p）throw“插入位置值太大";
else{s=newNode;s->data=x;s->next=p->next;p->next=s;}
}
}
（4）试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。
算法思想：
顺序表的程序参见题
（1）的converse.单链表的程序如下，设单链表有表头结点.
voidLinkList:
:
converse（）
{p=first->next;
first->next=NULL;
while（p）{
q=p->next;p->next=first->next;
first->next=p;p=q;
}
}
（5）假设在长度大于1的循环链表中，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。
voidLinkList:
:
deleteS（Node*s）
{p=s;
while（p->next->next!
=s）p=p->next;
{q=p->next;p->next=q->next;
deleteq;
}
（6）已知一单链表中的数据元素含有三类字符：
字母、数字和其它字符。
试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。
算法思想：
1）构造3个带表头结点的循环链表，分别为zifu，shuzi和qita；
2）遍历单链表，按单链表中的当前数据元素的分类插入相应的链表
voidfl（Node*zifu,Node*shuzi,Node*qita）
{s=newNode;s->next=s;zifu=s;
s=newNode;s->next=s;shuzi=s;
s=newNode;s->next=s;qita=s;
a=zifu;b=shuzi;c=qita;
p=first->next;//设单链表带头结点
while（p）{q=p;p=p->next;
if（（q->data>='a'&&q->data<='z'）||（q->data>='A'&&q->data<='A'））
{q->next=a->next;a->next=q;a=q;}
elseif（q->data>='0'&&q->data<='9'）
{q->next=b->next;b->next=q;b=q;}
else{q->next=c->next;c->next=q;c=q;}
}
deletefirst;
}
（7）设单链表以非递减有序排列，设计算法实现在单链表中删除相同的多余结点。
解：
voidLinkList:
:
deleteALL（）
{p=first->next;//假设单链表带表头结点。
while（p）
{if（p->next!
=NULL&&p->next->data==p->data）
{q=p->next;p->next=q->next;deleteq;}
elsep=p->next;}
}
（8）判断带头结点的双循环链表是否对称。
解boolLinkList:
:
equal（DulNode*first）
{p=first->next;q=first->prior;
while（p!
=q&&p->prior!
=q）
if（p->data==q->data）
{p=p->next;q=q->prior;}
else{return0;}
return1;
}
----------------------------------------------------------------------------------------------------------------------------------------
习题三
1填空题
（1）设有一个空栈，栈顶指针为1000H，经过push、push、pop、push、pop、push、push后，栈顶指针为（1003H）。
（2）栈结构通常采用的两种存储结构是（顺序存储结构和链接存储结构\顺序栈和链栈），其判定栈空的条件分别是（top=-1,top=NULL）,判断栈满的条件分别是（top=MaxSize-1,内存满/内存无可用空间）。
（3）（栈）可作为实现递归函数调用的一种数据结构。
（4）表达式a*（b+c）-d的后缀表达式是（abc+*d-）。
（5）栈和队列是两种特殊的线性表，栈的操作特性是（后进先出），队列的操作特性是（先进先出），栈和队列的主要区别在于（插入、删除运算的限定不一样）。
（6）循环队列的引入是为了克服（假溢出）。
（7）一维数组Data[n]用来表示循环队，队头指针front和队尾指针rear定义为整型变量，计算队中元素个数的公式是（（rear-front+n）%n）。
（8）用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（O
（1））和（O（n））。
2.选择题:
（1）C
（2）D（3）C（4）B（5）B（6）B（7）D（8）A（9）C
4.解答下列问题
（1）①不可以,因为有序列C,A,B.
②可以,push,push,push,pop,pop,pop,push,pop,push,pop.
（2）见书本
（3）栈顶元素是6,栈底元素是1.
（4）队尾元素是9,队头元素是5.
（5）①③④合法,②不合法.
习题四
1.填空题
（1）串是一种特殊的线性表，其特殊性体现在（数据元素的类型为字符型）。
（2）两个串相等的充分必要条件是（它们的长度相等且对应位置的字符相同）。
（3）数组通常只有两种运算，分别是（存取）和（修改），这决定了数组通常采用（顺序存储）结构来实现存储。
（4）（1140）
（5）设有一个10阶的对称矩阵A采用压缩存储，第一个元素A[0][0]的存储地址为d，每个元素占用1个地址空间，则元素A[8][5]的存储地址为（d+41）。
（6）稀疏矩阵一般压缩存储方法有两种，分别是（三元组顺序表）和（十字链表）。
2.选择题:
（1）B
（2）D,E,K（3）B（4）XXX（5）D（6）C（7）D
5
（2）.设计一个求矩阵A=（aij）nXm所有鞍点的算法，并分析最坏情况下的时间复杂度。
算法思想2：
附加两个数组B[n]和C[m]，B[i]用来存第i行的最小值，C[j]用来存第j列的最小元素值。
如果A[i][j]=B[i]=C[j]，则A[i][j]一定为马鞍点。
viodmaandian2（A[][],intm,intn）{
intB[n],C[m],i,j;
for（i=0;iB[i]=A[i][0];
for（j=1;jA[i][j]）B[i]=A[i][j];}
for（j=0;jC[j]=A[0][j];
for（i=1;ifor（i=0;ifor（j=0;jif（B[i]==A[i][j]&&C[j]==A[i][j]）
cout<}
算法复杂度：
O（mn）。
从时间复杂度的幂的角度来说这个算法是最好的，因为你求马鞍点必须要搜索所有的A[i][j]。
习题五
1填空题
（1）树是n（n≥0）个结点的有限集合。
在一棵非空树中，有（且仅有一个）根结点，其余结点分成m（m>=0）个（互不相交）的有限集合，每个集合又是一棵树。
（2）树中某结点的子树的个数称为该结点的（度），子树的根结点称为这个结点的（孩子结点）,该结点称为其子树根结点的（双亲结点）.
（3）一棵二叉树的第i（i≥1）层上最多有（2i-1）个结点,一棵有n（n>0）个结点的满二叉树共有（（n+1）/2）个叶子结点和（（n-1）/2）个非终端结点。
（4）设高度为h的二叉树只有度为0的和度为2的结点，该二叉树的结点数可能达到的最大值是（2h-1）,最小值是（2h-1）。
（5）深度为k的二叉树中，所含叶子的个数最多为（2k-1）.
（6）具有100个结点的完全二叉树的叶子结点数为（50）。
（7）已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。
则该树有（12）个叶子结点。
（8）某二叉树的前序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE,则其后序遍历序列是（CDBGFEA）。
（9）在具有n个结点的二叉链表中，共有（2n）个指针域，其中（n-1）个指针域用于指向其左右孩子，剩下的（n+1）个指针域则是空的。
（10）在有n个叶子的哈夫曼树中，叶子结点总数为（n）,分支结点总数为（n-1）。
2.选择题:
（1）D
（2）D（3）B（4）C（5）B,C（6）D（7）A（8）A,B（9）D,A（10）B（11）B（12）C（13）D（14）C
4.解答下列问题
（3）已知一棵度为m的树中：
n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，问该树中共有多少个叶子结点？
解：
设该树中共有n0个叶子结点。
则该树中总结点个数为
n=n0+n1+…+nm.
而分支数为n-1=n1+2n2+3n3+…+mnm,所以
n0=1+n2+2n3+…+（m-1）nm
（4）已知一棵二叉树的中序和后序序列为CBEDAFIGH和CEDBIFHGA,试构造该二叉树。
（5）给出叶子结点的权值集合为W={5,2,9,11,8,3,7}的哈夫曼树的构造过程。
5算法设计
（1）设计算法求二叉树的结点个数.
注：
本算法可以用二叉树遍历的所有算法，只要把cout语句换成结点的计数就可以了，但是要注意递归中的计数变量应该是外部变量。
如
intnum=0;
intBiTree:
:
count（BiNode*rt）{countsub（rt）;returnnum;}
voidBiTree:
:
countSub（BiNode*rt）{
if（rt!
=NULL）{num++;countSub（rt->lchild）;countSub（rt->rchild）;}
}
其他解法二：
用前序遍历的非递归算法
intBiTree:
:
CountPreOrder（BiNode*rt）
{top=-1;p=rt;num=0;//采用顺序栈s，并假定不会发生上溢
while（p!
=NULL||top!
=-1）{
while（p!
=NULL）//找此结点的最左边的后代
{num++;//访问
s[++top]=p;//此结点进栈
p=p->lchild;//转移到左儿子子树
}
if（top!
=-1）{p=s[top--];p=p->rchild;}}
returnnum;//cout<}
（2）设计算法按照前序次序打印二叉树中的叶子结点.
注:
其实按照“选择题”的（7）知:
任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序肯定不发生改变
解法思想:
使用任何遍历算法，把“cout<data”改成判断此结点是否为叶子结点。
voidBiTree:
:
leaf（BiNode*rt）{
if（rt==NULL）return;
else
{if（rt->lchild==NULL&&!
rt->rchild）
cout<data;
PostOrder（rt->lchild）;
PostOrder（rt->rchild）;
}}
（3）设计算法求二叉树的深度.
注：
本算法也可以用二叉树遍历的所有算法。
但是在用前序和中序算法时要注意深度如何来确定。
intBiTree:
:
depth（BiNode*rt）
{if（rt==NULL）return0;
else{
hl=depth（rt->lchild）;
hr=depth（rt->rchild）;
return（hl>hr）?
hl+1:
hr+1;
}
（4）设计算法:
输出二叉树后序遍历的逆序.
解法思想:
太简单啦！
！
！
前序遍历是先遍历右子树即可.
voidBiTree:
:
PostOrder_1（BiNode*rt）{
if（rt==NULL）return;
else{
cout<data;
PostOrder（rt->rchild）;
PostOrder（rt->lchild）;
}}
（5）以二叉链表为存储结构，编写算法求二叉树中值x的结点的双亲.
voidBiTree:
:
PreOrder_Parent（BiNode*rt）{
{top=-1;p=rt;//采用顺序栈s，并假定不会发生上溢
while（p!
=NULL||top!
=-1）{
while（p!
=NULL）
{if（rt->lchild!
=NULL&&rt->lchild->data==x）
cout<data;
if（rt->rchild!
=NULL&&rt->rchild->data==x）
cout<data;
s[++top]=p;//此结点进栈
p=p->lchild;//转移到左儿子子树
}
if（top!
=-1）{p=s[top--];p=p->rchild;}}
}
（6）以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树.
voidBiTree:
:
DeleteX（BiNode*rt,Tx）
{if（rt==NULL）return;
if（rt->data==x）{Release（rt）;}
else{
DeleteX（rt->lchild,x）;
DeleteX（rt->rchild,x）;
}}
（7）一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历.
算法思想:
套用前序遍历的原程序，注意查找左右孩子结点的地址和判别孩子是否存在的方法。
注：
根结点的下标是1。
voidBiTree:
:
PreOrder_Seq（intrt）
{top=-1;p=rt;//采用顺序栈s，并假定不会发生上溢
while（（p<=length）&&（A[p]!
=“”））||top!
=-1）{
while（（p<=length）&&（A[p]!
=“”））{
//找此结点的最左边的后代
cout<s[++top]=p;//此结点进栈
p=2*p;//转移到左儿子子树
}
if（top!
=-1）{p=s[top--];p=2*p+1;}
}
}
（8）编写算法交换二叉树中所有结点的左右子树.
解法思想:
使用任何遍历算法，把“cout<data”改成左右孩子指针交换即可。
voidBiTree:
:
PostOrderChange（BiNode*rt）
{
if（rt==NULL）return;
else
{PostOrder（rt->lchild）;
PostOrder（rt->rchild）;
temp=rt->lchild;
rt->lchild=rt->rchild;
rt->rchild=temp;
}}
习题6
1.填空题
⑴设无向图G中顶点数为ｎ，则图G至少有（0）条边，至多有（n（n-1）/2）条边；若G为有向图，则至少有（0）条边，至多有（n（n-1） ）条边。
⑵任何连通图的连通分量只有一个，即是（它本身）。
⑶图的存储结构主要有两种，分别是（邻接矩阵）和（邻接表）。
⑷已知无向图Ｇ的顶点数为ｎ，边数为ｅ，其邻接表表示的空间复杂度为（O（n+e））。
⑸已知一个图的邻接矩阵表示，计算第ｊ个顶点的入度的方法是（矩阵中第j-1列的非0元素个数）。
⑹有向图Ｇ用邻接矩阵Ａ[ｎ][ｎ]存储，其第ｉ行的所有元素之和等于顶点ｉ的（出度）。
⑺图的深度优先遍历类似于树的（前序）遍历，它所用的数据结构是（栈）；图的广度优先遍历类似于树的（层序）遍历，它所用的数据结构是（队列）。
⑻对于含有ｎ个顶点ｅ条边的连通图，利用Ｐrim算法求最小生成树的时间复杂度为（O（n2）），利用Kruscal算法求最小生成树的时间复杂度为（O（elog2e））。
⑼如果一个有向图不存在（有向回路），则该图的全部顶点可以排成一个拓扑序列。
⑽在一个有向图中，若存在弧、、，则
升级会员 