数据结构本科期末综合练习四算法分析题Word文档格式.docx
- 文档编号:5824285
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:41
- 大小:33.61KB
数据结构本科期末综合练习四算法分析题Word文档格式.docx
《数据结构本科期末综合练习四算法分析题Word文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构本科期末综合练习四算法分析题Word文档格式.docx(41页珍藏版)》请在冰点文库上搜索。
4.设顺序表SeqList具有下列操作:
intLength()const;
//计算表长度并返回,若表为空则返回0
TRemove();
//删除当前表项并返回其值,置下一表项为当前表项
TFirst();
//取表中第一个表项的值并返回,并置为当前表项
TNext();
//取当前表项后继表项的值并返回,
//并把此后继表项置为当前表项
若顺序表中存放的数据为{29,38,47,16,95,64,73,83,51,10,0,26},表的长度为12,参数值s=10,t=30,说明算法执行后顺序表的状态和长度的变化。
#include<
iostream.h>
#include“SeqList.h”
template<
voidunknown(SeqList<
T>
&
L,Ts,Tt)
{
if(!
L.Length()||s>
=t)
{cerr<
<
“表为空或参数值有误!
”<
endl;
exit
(1);
inti=0;
Ttemp=L.First();
while(i<
L.Length())
if(temp>
=s&
temp<
=t)L.Remove();
else{temp=L.Next();
i++;
算法执行后顺序表中的数据:
算法执行后顺序表的长度:
5.设字符串String具有下列操作:
intLength()const;
//计算字符串的长度
chargetData(k);
//提取字符串第k个字符的值
若字符串Tar的值为“ababcabcacbab”,Pat的值为“abcac”时,给出算法执行后函数返回的结果。
#include“String.h”
intunknown(String&
Tar,String&
Pat)const{
for(inti=0;
=Tar.Length()–Pat.Length();
i++){
intj=0;
while(j<
Pat.Length())
if(Tar.getData(i+j)==Pat.getData(j))j++;
elsebreak;
if(j==Pat.Length())returni;
return-1;
算法执行的结果是:
6.阅读下列算法,并补充所缺内容。
voidpurge_linkst(ListNode*&
la){
//从头指针为la的有序链表中删除所有值相同的多余元素,并释放被删结点空间
ListNode*p,*q;
if(la==NULL)return;
q=la;
p=la->
link;
while(p){
if(p&
___
(1)___){q=p;
p=p->
else{
q->
link=___
(2)___;
delete(p);
p=___(3)___;
}//while
}//purge_linkst
(1)
(2)(3)
7.设单链表的存储结构为ListNode=(data,link),表头指针为LH,所存线性表
L=(‘a’,’b’,’c’,’d’,’e’,’f’,’g’),若执行unknown(LH)调用下面程序,则写出执行结束后的输出结果。
voidunknown(LinkNode*Ha)
{//Ha为指向单链表的头指针
if(Ha){
unknown(Ha->
link);
cout<
Ha->
data;
8.设单链表结点的结构为LNode=(data,link),阅读下面的函数,指出它所实现的功能。
intAA(LNode*Ha)
{//Ha为指向带表头附加结点的单链表的表头指针
intn=0;
LNode*p=Ha->
while(p){
n++;
p=p->
return(n);
算法功能:
9.设单链表结点的结构为ListNode=(data,link),下面程序段执行后将生成由L所指向的带头结点的单链表,给出该单链表所对应的线性表。
ListNode*L=newListNode;
ListNode*p=L;
for(inti=0;
4;
i++){
p->
link=newListNode;
p=p->
data=i*2-1;
}//for
p->
link=NULL;
10.这是一个统计单链表中结点的值等于给定值x的结点数的算法,其中有两行错误,请指出错误行的行号并改正。
intcount(ListNode*Ha,ElemTypex)
{//Ha为不带头结点的单链表的头指针
intn=0;
while(Ha!
=NULL){
Ha=Ha->
if(Ha->
data==x)n++;
}//while
returnn;
}//count
错误语句号:
修改如下:
11.写出下列程序段的输出结果:
voidmain(){
stackS;
charx,y;
S.InitStack();
x='
c'
;
y='
k'
S.Push(x);
S.Push('
a'
);
S.Push(y);
S.Pop(S,x);
t'
s'
while(!
S.IsEmpty()){S.Pop(y);
y;
cout<
y<
}//main
运行结果:
12.写出下列程序段的输出结果:
queueQ;
charx,y='
Q.InitQueue();
Q.EnQueue('
h'
Q.EnQueue('
r'
Q.EnQueue(y);
Q.DeQueue(x);
Q.EnQueue(x);
Q.DeQueue(x);
while(Q.IsEmpty()){Q.DeQueue(y);
x<
输出结果:
13.指出下面算法的功能。
Stackunknown(StackS){
StackT;
intd;
T.IniStack();
//初始化栈
While(!
S.IsEmpty()){
d=S.GetTop();
S.Pop();
T.Push(d);
returnT;
14.请写出下面算法的功能.
voidunknown(Queue&
Q){
StackS;
S.InitStack();
while(!
Q.IsEmpty()){
Q.DeQueue(d);
S.Push(d);
S.IsEmpty()){
S.Pop(d);
Q.EnQueue(d);
15.下面算法的功能为:
将两个有序单链表合并成一个有序单链表并返回其表头指针。
阅读下列算法,按标号填写空缺的内容,要求统一填写在算法后面的标记处。
ListNode*Merge1(ListNode*&
p1,ListNode*&
p2)
ListNodea;
//a结点作为结果有序单链表的表头附加结点
ListNode*p=&
a;
link=NULL;
while(p1!
=NULL&
p2!
=NULL)
if(p1->
data<
=p2->
data){
___
(1)___;
p1=p1->
}
else{
p->
link=p2;
p2=p2->
___
(2)___;
if(p1!
=NULL)p->
link=p1;
else___(3)___;
p1=p2=NULL;
returna.link;
(1)
(2)(3)
16.阅读下列算法,写出算法功能。
LinkNode*BB(LinkNode*first)
if(first==NULL||first->
link==NULL)returnfirst;
LinkNode*q=first,*p=q->
while(p!
=NULL){
ListNode*r=p->
link=q;
q=p;
p=r;
returnq;
17.下面是判断一个带表头结点的双向循环链表L其前后结点值是否对称相等的算法,若相等则返回1,否则返回0。
请按标号补充合适的内容。
intsymmetry(DoublelList*DL){
DoublelNode*p=DL->
rLink,*q=DL->
lLink;
while(p!
=q)
if(p->
data==q->
data){
rLink;
if(p->
lLink==q)___
(2)___;
}
else___(3)___;
return1;
18.阅读下面的算法,写出它的功能。
ListNode*unknown(){
ListNode*first,*p,*q;
intx;
p=first=newListNode;
cin>
>
x;
while(x!
=0){
q=newListNode;
data=x;
rlink=q;
llink=p;
p=q;
rlink=NULL;
returnfirst->
rlink;
19.rear是指向以循环链表表示的队列的队尾指针,EnLQueue函数实现插入x为新的队尾元素的操作。
DeLQueue函数实现删除队头元素并赋给x的操作。
voidEnLQueue(ListNode*&
rear,ElemTypex)
//rear是指向以循环链表表示的队列的队尾指针,插入x为新的队尾元素。
{
ListNode*p;
p=newListNode;
rear->
link=p;
rear=p;
};
boolDeLQueue(ListNode*&
rear,ElemType&
x)
//rear是指向以循环链表表示的队列的队尾指针,若队列不空,
//则删除队头元素并以x带回,并返回true,否则返回false,x无意义
if(rear==NULL)returnfalse;
if(rear->
link==rear){
x=rear->
deleterear;
rear=NULL;
returntrue;
ListNode*p=rear->
link=p->
___
(2)___;
deletep;
___(3)___;
(1)
(2)(3)
20.设有一个求解汉诺塔(Hanoi)的递归算法如下:
voidHANOI(intn,intpeg1,intpeg2,intpeg3){
if(n==1)cout<
peg1<
’->
’<
peg3<
else{
HANOI(n-1,peg1,peg3,peg2);
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<
int>
*f,int&
n){
if(f==NULL)return0;
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;
下面函数的功能是:
从二叉树BT中查找值为X的结点,返回指向其父结点的指针。
若该结点不存在或为树根结点则返回空。
算法中参数PT的初值为NULL。
请在划有横线的地方填写合适内容。
BinTreeNode*ParentPtr(BinTreeNode*BT,BinTreeNode*PT,ElemType&
X)
if(BT==NULL)returnNULL;
data==X)returnPT;
if(PT=ParentPtr(BT->
left,BT,X))__
(1)_____;
if_________________
(2)_______________returnPT;
else___(3)____;
25.已知二叉树中的结点类型BinTreeNode定义为:
根据下面函数的定义指出函数的功能。
算法中参数BT指向一棵二叉树。
BinTreeNode*BTreeSwopX(BinTreeNode*BT)
else{
BinTreeNode*pt=newBinTreeNode;
pt->
data=BT->
right=BTreeSwopX(BT->
left);
left=BTreeSwopX(BT->
right);
returnpt;
26.已知二叉树中的结点类型STreeNode定义为:
structSTreeNode{datatypedata;
STreeNode*lchild,*rchild,*parent;
其中data为结点值域,lchild和rchild分别为指向左、右子女结点的指针域,parent为指向父亲结点的指针域。
算法中参数ST指向一棵二叉树,X保存一个结点的值。
STreeNode*PN(STreeNode*ST,datatype&
if(ST==NULL)returnNULL;
StreeNode*mt;
if(ST->
data==X)returnST->
parent;
elseif(mt=PN(ST->
lchild,X))returnmt;
rchild,X))returnmt;
returnNULL;
算法功能:
27.已知二叉树中的结点类型BinTreeNode定义为:
voidBTC(BinTreeNode*BT)
if(BT!
if(BT->
left!
BT->
right!
=NULL)
if(BT->
left->
data>
BT->
right->
BinTreeNode*t=BT->
left;
BT->
left=BT->
right;
right=t;
BTC(BT->
BTC(BT->
28.已知二叉树中的结点类型BinTreeNode定义为:
structBinTreeNode{chardata;
假定指针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)
data==x)k++;
BTC1(BT->
left,x,k);
right,x,k);
(4)
29.已知二叉树中的结点类型BinTreeNode定义为:
下面函数的功能是从二叉树BT中查找值为X的结点,若查找成功则返回结点地址,否则返回空。
BinTreeNode*BTF(BinTreeNode*BT,ElemTypex)
if(BT==NULL)___
(1)____;
data==x)__
(2)____;
BinTreeNode*t;
if(t=B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 本科 期末 综合 练习 算法 分析