数据结构习题解答Word格式文档下载.docx
- 文档编号:4103417
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:19
- 大小:109.83KB
数据结构习题解答Word格式文档下载.docx
《数据结构习题解答Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构习题解答Word格式文档下载.docx(19页珍藏版)》请在冰点文库上搜索。
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<
t)
{while(A[s]%2!
=0)s++;
//s=s+1
while(A[t]%2==0)t--;
if(s<
t){temp=A[s];
A[s]=A[t];
A[t]=temp;
}
}}
或voidtiaozhen(TA[],intn)
{if(A[s]%2!
elseif(A[t]%2==0)t--;
else{temp=A[s];
s++;
t--;
}}
(3)试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较
voidLinkList_1:
:
Insert(inti,Tx){
if(i<
=0)throw"
输入的插入位置值小于1"
;
if(i==1){s=newNode<
T>
s->
data=x;
next=first;
first=s;
else{p=first;
j=0;
while(p&
&
j<
i-1){p=p->
j++;
if(!
p)throw“插入位置值太大"
else{s=newNode<
next=p->
}
(4)试分别以顺序表和单链表作存储结构,各写一实现线性表就地逆置的算法。
顺序表的程序参见题
(1)的converse.单链表的程序如下,设单链表有表头结点.
voidLinkList:
converse()
{p=first->
first->
next=NULL;
while(p){
q=p->
next=first->
next=p;
p=q;
(5)假设在长度大于1的循环链表中,既无头结点也无头指针,s为指向链表中某个结点的指针,试编写算法删除结点s的前驱结点。
deleteS(Node<
*s)
{p=s;
while(p->
next!
=s)p=p->
{q=p->
}
(6)已知一单链表中的数据元素含有三类字符:
字母、数字和其它字符。
试编写算法,构造三个循环链表,使每个循环链表中只含同一类字符。
1)构造3个带表头结点的循环链表,分别为zifu,shuzi和qita;
2)遍历单链表,按单链表中的当前数据元素的分类插入相应的链表
voidfl(Node<
*zifu,Node<
*shuzi,Node<
*qita)
{s=newNode<
zifu=s;
s=newNode<
shuzi=s;
qita=s;
a=zifu;
b=shuzi;
c=qita;
p=first->
//设单链表带头结点
while(p){q=p;
p=p->
if((q->
data>
='
a'
q->
data<
z'
)||(q->
A'
q->
))
{q->
next=a->
a->
next=q;
a=q;
elseif(q->
0'
&
9'
)
{q->
next=b->
b->
b=q;
else{q->
next=c->
c->
c=q;
deletefirst;
(7)设单链表以非递减有序排列,设计算法实现在单链表中删除相同的多余结点。
解:
voidLinkList:
deleteALL()
//假设单链表带表头结点。
while(p)
{if(p->
=NULL&
data==p->
data)
{q=p->
elsep=p->
(8)判断带头结点的双循环链表是否对称。
解boolLinkList:
equal(DulNode<
*first)
q=first->
prior;
while(p!
=q&
p->
prior!
=q)
if(p->
data==q->
{p=p->
q=q->
else{return0;
return1;
----------------------------------------------------------------------------------------------------------------------------------------
习题三
(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))。
(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)串是一种特殊的线性表,其特殊性体现在(数据元素的类型为字符型)。
(2)两个串相等的充分必要条件是(它们的长度相等且对应位置的字符相同)。
(3)数组通常只有两种运算,分别是(存取)和(修改),这决定了数组通常采用(顺序存储)结构来实现存储。
(4)(1140)
(5)设有一个10阶的对称矩阵A采用压缩存储,第一个元素A[0][0]的存储地址为d,每个元素占用1个地址空间,则元素A[8][5]的存储地址为(d+41)。
(6)稀疏矩阵一般压缩存储方法有两种,分别是(三元组顺序表)和(十字链表)。
(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;
i<
n;
i++){//求第i行的最小值,记入B[i]
B[i]=A[i][0];
for(j=1;
j<
m;
j++)if(B[i]>
A[i][j])B[i]=A[i][j];
for(j=0;
j++){//求第j列的最大值,记入C[j]
C[j]=A[0][j];
for(i=1;
i++)if(C[j]<
A[i][j])C[j]=A[i][j];
i++)//求马鞍点
j++)
if(B[i]==A[i][j]&
C[j]==A[i][j])
cout<
<
A[i][j];
算法复杂度:
O(mn)。
从时间复杂度的幂的角度来说这个算法是最好的,因为你求马鞍点必须要搜索所有的A[i][j]。
习题五
(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)。
(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);
rchild);
其他解法二:
用前序遍历的非递归算法
CountPreOrder(BiNode<
*rt)
{top=-1;
p=rt;
num=0;
//采用顺序栈s,并假定不会发生上溢
while(p!
=NULL||top!
=-1){
=NULL)//找此结点的最左边的后代
{num++;
//访问
s[++top]=p;
//此结点进栈
lchild;
//转移到左儿子子树
if(top!
=-1){p=s[top--];
rchild;
returnnum;
//cout<
num
(2)设计算法按照前序次序打印二叉树中的叶子结点.
注:
其实按照“选择题”的(7)知:
任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序肯定不发生改变
解法思想:
使用任何遍历算法,把“cout<
rt->
data”改成判断此结点是否为叶子结点。
leaf(BiNode<
*rt){
if(rt==NULL)return;
else
{if(rt->
lchild==NULL&
!
rchild)
data;
PostOrder(rt->
(3)设计算法求二叉树的深度.
本算法也可以用二叉树遍历的所有算法。
但是在用前序和中序算法时要注意深度如何来确定。
depth(BiNode<
{if(rt==NULL)return0;
else{
hl=depth(rt->
hr=depth(rt->
return(hl>
hr)?
hl+1:
hr+1;
(4)设计算法:
输出二叉树后序遍历的逆序.
太简单啦!
!
前序遍历是先遍历右子树即可.
PostOrder_1(BiNode<
else{
PostOrder(rt->
(5)以二叉链表为存储结构,编写算法求二叉树中值x的结点的双亲.
PreOrder_Parent(BiNode<
=NULL)
lchild!
lchild->
data==x)
if(rt->
rchild!
rchild->
(6)以二叉链表为存储结构,在二叉树中删除以值x为根结点的子树.
DeleteX(BiNode<
*rt,Tx)
{if(rt==NULL)return;
data==x){Release(rt);
else{
DeleteX(rt->
lchild,x);
rchild,x);
(7)一棵具有n个结点的二叉树采用顺序存储结构,编写算法对该二叉树进行前序遍历.
算法思想:
套用前序遍历的原程序,注意查找左右孩子结点的地址和判别孩子是否存在的方法。
根结点的下标是1。
PreOrder_Seq(intrt)
//采用顺序栈s,并假定不会发生上溢
while((p<
=length)&
(A[p]!
=“”))||top!
(A[p]!
=“”)){
//找此结点的最左边的后代
A[p];
p=2*p;
p=2*p+1;
(8)编写算法交换二叉树中所有结点的左右子树.
data”改成左右孩子指针交换即可。
PostOrderChange(BiNode<
{
{PostOrder(rt->
temp=rt->
rt->
lchild=rt->
rchild=temp;
}}
习题6
1.填空题
⑴设无向图G中顶点数为n,则图G至少有(0)条边,至多有(n(n-1)/2)条边;
若G为有向图,则至少有(0)条边,至多有(n(n-1) )条边。
⑵任何连通图的连通分量只有一个,即是(它本身)。
⑶图的存储结构主要有两种,分别是(邻接矩阵)和(邻接表)。
⑷已知无向图G的顶点数为n,边数为e,其邻接表表示的空间复杂度为(O(n+e))。
⑸已知一个图的邻接矩阵表示,计算第j个顶点的入度的方法是(矩阵中第j-1列的非0元素个数)。
⑹有向图G用邻接矩阵A[n][n]存储,其第i行的所有元素之和等于顶点i的(出度)。
⑺图的深度优先遍历类似于树的(前序)遍历,它所用的数据结构是(栈);
图的广度优先遍历类似于树的(层序)遍历,它所用的数据结构是(队列)。
⑻对于含有n个顶点e条边的连通图,利用Prim算法求最小生成树的时间复杂度为(O(n2)),利用Kruscal算法求最小生成树的时间复杂度为(O(elog2e))。
⑼如果一个有向图不存在(有向回路),则该图的全部顶点可以排成一个拓扑序列。
⑽在一个有向图中,若存在弧<
vi,vj>
、<
vj,vk>
vi,vk>
,则
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题 解答