Else________;
}
5.递归函数invert(inta[],intk)将指定数组中的前k个元素逆置
Voidinvert(inta[],intk)
{intt;
If(_______){invert(____________);
T=a[0];
A[0]=a[k-1];a[k-1]=t;
}
}
6.intdec(intn)的功能是计算n!
.如调用dec(6)后函数的反回值是120
intdec(intn){if(n<2)_________;
elsereturn(________);
}
7.递归函数intfib(intn)的功能是计算fibonacci数列的第n项
intfib(intn){if(n==0)________;
elseif(_________)return1;
else_________;
}
判断:
1)栈低元素是不能删除的元素。
2)顺序栈中元素值的大小是有序的。
3)在n个元素进栈后,他们的出栈顺序和进栈顺序正好相反。
4)栈顶元素和栈底元素有可能是同一元素。
5)若用s[1]~s[m]表示顺序栈的存储空间,则对栈的进栈,出栈操作最多只能进行m次。
6)栈是一种对进栈,出栈操作总次数做了限制的线性表。
7)对顺序栈进行进栈,出栈操作,不涉及元素的前后移动问题。
8)栈是一种对进栈,出栈操作的次序做了限制的线性表。
9)空栈没有栈顶指针。
10)栈和队列都是限制存取端的线性表。
11)队列是一种对进队列,出队列操作的次序做了限制的线性表。
12)n个元素进队列的顺序和出队列的顺序总是一致的。
13)顺序队中有多少元素,可以根据队首指针的值和队尾指针的值来计算。
14)若用“队首指针的值和队尾指针的值相等”作为环形顺序队为空的标志,则在设置一个空队时,只需给队首指针和队尾指针赋同一个值,不管什么值都可以。
文档收集自网络,仅用于个人学习
15)无论是顺序队还是链队,进队,出队操作的时间复杂度都是O
(1).
解答题:
1)设有一个数列的输入顺序为123456,若采用栈结构,并以A和D分别表示进栈和出栈操作,试问通过进栈和出栈操作的合法序列。
文档收集自网络,仅用于个人学习
(1)能否得到输出序列为325641的序列?
(2)能否得到输出序列为154623的序列?
2)说说线性表,栈和队列的异同。
3)设栈s和队列q的初始状态都为空,元素a,b,c,d,e和f依次通过栈s,一个元素出栈后既进入队列q,若6个元素出队的序列是bdcfea,则栈s的容量至少应该存多少个元素?
文档收集自网络,仅用于个人学习
程序题:
1>写出下列程序字段的输出结果(栈的元素类型SElemType为char)
Voidmain()
{StackS;
Charx,y;
InitStack(S);
X=’c’;y=’k’;
Push(S,x);push(S,’a’);push(S,y);
Pop(S,x);push(S,’t’);push(S,x);
Pop(S,x);push(S,’s’);
While(!
StackEmty(S)){pop(S,y);printf(y);}
Printf(x);
}
2>简述以下算法的功能(栈的元素类型SElemType为int)
Statusalgo2(StackS,inte)
{StackT;intd;
InitStack(T);
While(!
StackEmpty(S))
{pop(S,d);
If(d!
=e)push(T,d);
}
While(!
StackEmpty(S))
{pop(T,d);
Push(S,d);
}
}
3>写出以下程序段的输出结果(队列中元素类型QElemType为char)
Voidmain()
{QueueQ;InitQueue(Q);
Charx=’e’,y=’c’;
EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);
DeQueue(Q,x);EnQueue(Q,x);
DeQueue(Q,x);EnQueue(Q,’a’);
While(!
QueueEmpty(Q)){DeQueue(Q,y);
Printf(y);
}
Printf(x);
}
4>函数MultibaseOutput(longn,intB)的功能是:
将一个无符号十进制数n转换成B(2<=B<=16)进制整数并输出。
该函数先将转换过程中得到的各位数字入栈,转换结束后把B进制从栈中输出。
有关操作的各函数功能见相应函数中的注释。
C代码中的符号常量及栈的类型定义如下:
文档收集自网络,仅用于个人学习
#defineMAXSIZE32
Typedefstruct{
Int*elem;/*栈的存储区*/
Intmax;/*栈的容量,即栈中最多能存放的元素个数*/
Inttop;/*栈的指针*/
}Stack;
C代码
IntInitSack(Stack*s,intn)
{S->elem=(int*)malloc(n*sizeof(int));
If(S->elem==NULL)return-1;
S->max=n;
_____________=0;
Return0;
}`
Intpush(Stack*S,intitem)/*将整数item压入栈中*/
{if(S->top==S->max){printf(*Stackisfull!
\n);
Return-1;
}
_____________=irem;
Return0;
}
IntStackEmpty(StackS)
{
Return(!
S.top)?
1:
0;/*判断栈是否为空*/
}
Intpop(Stack*S)栈顶元素出栈*/
{
If(S->top){printf(“popanemptystack!
\n”);
Return-1;
}
Return__________;
}
VoidMultibaseOutput(longn,intB)
{
Intm;StackS;
If(InitStack(&S,MAXSIZE)){printf(“Failure!
\n”);
Return;
}
Do{if(push(&S,________)){printf(“Failure!
\n”);
Return;}
N=________;
}while(n!
=0);
While(!
StackEmpty(S))/*输出B进制数*/
{m=pop(&S);
If(m<10)printf(“%d”,m);/*小于10,输出数字*/
Elseprintf(“%c”,m+55);/*大于或等于10,输出相应的字符*/
}
Printf(“\n”);}
8.编写一个实现串的置换操作Replace(char*S,T,V)的算法
intReplace(StringType&s,StringTypeT,StringTypeV)//将串中S中所有子串T替换V并返回置换次数文档收集自网络,仅用于个人学习
{
}//Replace
9.编写算法,从串s中删除所有和串t相同的子串.
intDelete_SubString(StringType*s,StringTypet)/从串s中删除所有与t相同的子串,并返回删除次数文档收集自网络,仅用于个人学习
{
}//Delete_SubString
11.编写算法,实现串的基本操作StrAssign(char*T,chars)
voidStrAssign(StringType&T,charchars)//用字符数组chars给串T附值文档收集自网络,仅用于个人学习
{
}//StrAssign
12.编写算法,实现串的基本操作StrCompare(S,T).
charStrCompare(StringTypes,StringTypet)//串的比较,s>t时返回正数,s=t时返回0,s{
}//StrCompare
13.编写算法,实现串的基本操作Replace(char*S,T,V).
boolrepl(SString&News,SStringS,SStringT,SStringV)文档收集自网络,仅用于个人学习
{
}//repl
14.编写算法,求串s所含不同字符的总数和每种字符的个数。
15.假设以结点大小1(且附设头结点)的连表结构表示串,试编写实现下列六种串的基本操作:
StrAssign,StrCopy,StrCompare,StrLenght,ConCat和SubString的函数.文档收集自网络,仅用于个人学习
6.2典型例题解析
6.1一棵完全二叉树第6层有7个结点,则共有()个结点,其度为1的结点有()个,度为0的结点有()个,编号最大的非叶子结点是(),编号最小的叶子结点是()。
文档收集自网络,仅用于个人学习
6.2试回答下面的问题:
已知一棵满二叉树的结点个数为20~40的数,试问此二叉树的叶子结点有多少个?
有n个结点的二叉树,已知叶子结点的个数为n0,
写出求度为1的结点的个数n1计算公式;
若此数是高度为h的完全二叉数,写出n为最小的公式;
若二叉数中仅有度为0和度为2的结点,写出该二叉数结点个数n的公式。
(3)已知一棵度位m的树中有n1个度为1的结点,n2个度为2的结点,……,Nm个度为m的结点,问该树有多少个叶子结点?
文档收集自网络,仅用于个人学习
6.3.已知有一棵二叉树的中序遍历序列为DBEHAFCIG,后序遍历是DHEBFIGCA,试画出该二叉树,并给出该二叉树的的前序序列。
文档收集自网络,仅用于个人学习
6.5设二叉树用二叉链表表示,设计算法:
(1)求二叉树的高度;
(2)求二叉树的度为2的结点数;
6.6试编写算法判断二叉树T是否是完全二叉树;
(1)若给定的二叉树采用顺序表作为存储结构;
(2)若给定的二叉树采用二叉链表作为存储结构。
6.7.对以二叉链表存储的非空而叉树,从右向左依次释放所有的叶子结点,释放的同时,把结点存放到一个数组中。
要求:
文档收集自网络,仅用于个人学习
(1)用文字写出实现上述过程的基本思想。
(2)写出算法,
6.8.试以二叉树链表的存储结构,编写按层次顺序遍历二叉树的算法。
6.9假设二叉树以二叉链表为存储结构,编写求任一指定结点所在的层次。
6.11设计算法,统计一棵二叉树中所有结点的数目及非叶子结点的数目。
6.14已知以二叉链表表示的二叉树中有值为x,y,z的三个结点,试编写算法判断x是否为y和z的共同祖先。
文档收集自网络,仅用于个人学习
6.16假设二叉树的存储结构为二叉链表,试编写C语言的函数,其功能是交换二叉树中各结点的左子树和右子树。
文档收集自网络,仅用于个人学习
6.18已知一棵二叉树用二叉链表存储,root指向根结点,p指向树中任何一结点。
试编写算法输出从root~p路径上的结点。
文档收集自网络,仅用于个人学习
6.20编写一个算法,利用叶子结点中的空指针域,将所有叶子结点链接为一个带有头结点的单链表,算法返回头结点的地址。
文档收集自网络,仅用于个人学习
6.21假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度。
6.3习题及参考答案
1.已知一棵树边的集合为{,,,,,,,,,,,},文档收集自网络,仅用于个人学习
请画出这棵树,并回答下列问题:
(1)哪个是根结点?
(2)哪些是叶子结点?
(3)哪些是结点G的双亲?
(4)哪些是结点G的祖先?
(5)哪些是结点G的孩子?
(6)哪些是结点E的子孙?
(7)哪些是结点E的兄弟?
哪些是结点F的兄弟?
(8)结点B和N的层次号分别是什么?
(9)树的深度是多少?
(10)以结点C为根的子树的深度是多少?
2.一棵度为2的树与一棵二叉树有何区别?
3.试分别画出具有3个结点的树和3个结点的二叉树的所有不同的形态.
4.一棵深度为H的满K叉树有如下性质:
第H层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树,如果按层次顺序从1开始全部结点编号,问:
文档收集自网络,仅用于个人学习
(1)各层的结点数目是多少?
(2)编号为p的结点的父结点(若存在)的编号是多少?
(3)编号为p的第i的儿子结点(若存在)的编号是多少?
(4)编号为p的结点有右兄弟的条件是什么?
其右兄弟的编号是多少?
5.已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,...nk个度为k的结点,问该树中有多少个叶子结点?
文档收集自网络,仅用于个人学习
6.已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,试求该树含有叶子结点的数目.文档收集自网络,仅用于个人学习
7.一棵含有n个结点k叉树,可能达到的最大深度和最小深度各为多少?
9.对题3所得各种形态的二叉树,分别写出前序,中序和后序遍历的序列。
10.假设n和m为二叉树中两结点,有“1”,“0”或“¢“(分别表示肯定,恰恰相反或者不一定)填写下表。
文档收集自网络,仅用于个人学习
答问
已知
前序遍历时n在m前?
中序遍历n在m前?
后序遍历时n在m前?
n在m左方
n在m右方
n是m祖先
n是m子孙
11.找出所有满足下列条件的二叉树:
(1)他们在先序遍历和中序遍历时,得到的结点访问序列相同;
(2)他们在后序遍历和中序遍历时,得到的结点访问序列相同;
(3)他们在先序遍历和后序遍历时,得到的结点访问序列相同;
12.请对下图所示二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索。
19.画出和下列已知序列对应的树T:
树的先根次序访问序列为GFKDAIEBCHJ;
树的后根次序访问序列为DIAEKFCJHBG。
21.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK.
请画出该树.
22.假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA.
请画出该树.
29.编写递归算法,在二叉树中求位于先序序列中第K个位置的结点的值.
30.编写递归算法,计算二叉树中叶子结点的数目.
30.编写递归算法,将二叉树中所有结点的左,右子树相互交换.
32.编写递归算法:
求二叉树中以元素值为X的结点为根的子树的深度;
33.编写递归算法:
对于二叉树中每一个元素值为X的结点,删去以它为根的子树,并释放相应的空间.
34.编写复制一棵二叉树的非递归算法.
35.编写按层次顺序(同一层从左至右)遍历二叉树的算法.
36.在二叉树中,*root为根结点,*p和*q为二叉树中两个结点,试编写求距离它最近的共同祖先的算法.文档收集自网络,仅用于个人学习
41.试编写算法,求给定二叉树上从根到叶子结点的一条其路径长度等于树的深度减一的路径(即列出从根结点到该叶子结点的结点序列),若这样的路径存在多条,则输出路径终点文档收集自网络,仅用于个人学习
(叶子结点)在"最左"的一条.
42.已知一棵完全二叉树存于顺序表sa中,sa.elem[sa.last]中存放各结点的数据元素.
试编写算法由此顺序存储结构建立该二叉树的二叉链表.
43.为二叉链表的结点增加D