HANOI(n-1,peg2,peg1,peg3);
}
}
当使用HANOI(3,1,2,3)进行调用时,执行过程中else子句的cout语句得到的结果为:
21.针对如下算法,回答问题:
(1)若整型数组A[8]={12,24,33,38,95,83,64,57},n=8,则给出算法返回的结果。
(2)说明算法的功能是什么。
intunknown(intA[],intn){
if(n==1)returnA[0];
inttemp=unknown(A,n-1);
returnA[n-1]>temp?
A[n-1]:
temp;
}
返回结果:
算法功能:
22.针对如下算法,设整数链表L中各结点的数据为12,24,30,90,84,36,n的初值为0,则
(1)给出执行unknown(L.first,n)调用后的返回结果;
(2)指出算法功能。
在算法中getLink()函数返回结点指针域的值,getData()函数返回结点的数据域的值。
floatunknown(ListNode*f,int&n){
if(f==NULL)return0;
else{
n++;
returnunknown(f->getLink(),n)+f->getData()/n;
}
}
返回结果:
算法功能:
23.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};
其中data为结点值域,left和right分别为指向左、右子女结点的指针域。
下面函数的功能是返回二叉树BT中值为X的结点所在的层号,请在划有横线的地方填写合适内容。
intNodeLevel(BinTreeNode*BT,ElemTypeX)
{
if(BT==NULL)return–1;//空树的层号为-1
elseif(BT->data==X)return0;//根结点的层号为0
//向子树中查找X结点
else{
intc1=NodeLevel(BT->left,X);
if(c1>=0)_____
(1)___________;
intc2=_______
(2)______________;
if_________(3)__________________;
//若树中不存在X结点则返回-1
elsereturn-1;
}
}
(1)
(2)
(3)
24.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};
其中data为结点值域,left和right分别为指向左、右子女结点的指针域。
下面函数的功能是:
从二叉树BT中查找值为X的结点,返回指向其父结点的指针。
若该结点不存在或为树根结点则返回空。
算法中参数PT的初值为NULL。
请在划有横线的地方填写合适内容。
BinTreeNode*ParentPtr(BinTreeNode*BT,BinTreeNode*PT,ElemType&X)
{
if(BT==NULL)returnNULL;
elseif(BT->data==X)returnPT;
else{
if(PT=ParentPtr(BT->left,BT,X))__
(1)_____;
if_________________
(2)_______________returnPT;
else___(3)____;
}
}
(1)
(2)
(3)
25.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};
其中data为结点值域,left和right分别为指向左、右子女结点的指针域。
根据下面函数的定义指出函数的功能。
算法中参数BT指向一棵二叉树。
BinTreeNode*BTreeSwopX(BinTreeNode*BT)
{
if(BT==NULL)returnNULL;
else{
BinTreeNode*pt=newBinTreeNode;
pt->data=BT->data;
pt->right=BTreeSwopX(BT->left);
pt->left=BTreeSwopX(BT->right);
returnpt;
}
}
算法功能:
26.已知二叉树中的结点类型STreeNode定义为:
structSTreeNode{datatypedata;STreeNode*lchild,*rchild,*parent;};
其中data为结点值域,lchild和rchild分别为指向左、右子女结点的指针域,parent为指向父亲结点的指针域。
根据下面函数的定义指出函数的功能。
算法中参数ST指向一棵二叉树,X保存一个结点的值。
STreeNode*PN(STreeNode*ST,datatype&X)
{
if(ST==NULL)returnNULL;
else{
StreeNode*mt;
if(ST->data==X)returnST->parent;
elseif(mt=PN(ST->lchild,X))returnmt;
elseif(mt=PN(ST->rchild,X))returnmt;
returnNULL;
}
}
算法功能:
27.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};
其中data为结点值域,left和right分别为指向左、右子女结点的指针域。
根据下面函数的定义指出函数的功能。
算法中参数BT指向一棵二叉树。
voidBTC(BinTreeNode*BT)
{
if(BT!
=NULL){
if(BT->left!
=NULL&&BT->right!
=NULL)
if(BT->left->data>BT->right->data){
BinTreeNode*t=BT->left;
BT->left=BT->right;
BT->right=t;
}
BTC(BT->left);
BTC(BT->right);
}
}
算法功能:
28.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{chardata;BinTreeNode*left,*right;};
其中data为结点值域,left和right分别为指向左、右子女结点的指针域。
假定指针bt指向一棵二叉树,该二叉树的广义表表示为a(b(a,d(f)),c(e(,a(k)),b)),每次调用时整数变量C的值均为0,若:
执行BTC1(bt,’a’,C)调用后,C的值为___
(1)_____;
执行BTC1(bt,’b’,C)调用后,C的值为___
(2)_____;
执行BTC1(bt,’c’,C)调用后,C的值为___(3)_____;
执行BTC1(bt,’g’,C)调用后,C的值为__(4)______;
voidBTC1(BinTreeNode*BT,charx,int&k)
{
if(BT!
=NULL){
if(BT->data==x)k++;
BTC1(BT->left,x,k);
BTC1(BT->right,x,k);
}
}
(1)
(2)
(3)
(4)
29.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};
其中data为结点值域,left和right分别为指向左、右子女结点的指针域。
下面函数的功能是从二叉树BT中查找值为X的结点,若查找成功则返回结点地址,否则返回空。
请在划有横线的地方填写合适内容。
BinTreeNode*BTF(BinTreeNode*BT,ElemTypex)
{
if(BT==NULL)___
(1)____;
else{
if(BT->data==x)__
(2)____;
else{
BinTreeNode*t;
if(t=B