《数据结构》复习题及参考答案Word格式.docx
- 文档编号:7717818
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:34
- 大小:209.87KB
《数据结构》复习题及参考答案Word格式.docx
《《数据结构》复习题及参考答案Word格式.docx》由会员分享,可在线阅读,更多相关《《数据结构》复习题及参考答案Word格式.docx(34页珍藏版)》请在冰点文库上搜索。
O(log3n)
在顺序表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数与有关。
~0025
表中一半表长和该元素在表中的位置
`002603C1
判定一个栈ST(最多元素为m0)为空的条件是B
A、ST->
top<
>
0B、ST->
top=0C、ST->
m0D、ST->
top=m0
`002702B2
向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动n-i+1个元素。
`002802B2
向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动n-i个元素。
`002902B1
在顺序表中访问任意一结点的时间复杂度均为,因此,顺序表也称为的数据结构。
~0029
O
(1)随机存取
`003102B1
在单链表中,除了首元结点外,任一结点的存储位置由指示。
~0031
其直接前驱结点的链域的值
`003202B2
在n个结点的单链表中要删除已知结点*p,需找到它的,其时间复杂度为o(n)。
~0032
前驱结点的地址O(n)
线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
(x)
`003702D1
顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
(X)
`004502C1
在n个结点的顺序表中,算法的时间复杂度是O
(1)的操作是(A)
A、访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
B、在第i个结点后插入一个新结点(1≤i≤n)
C、删除第i个结点(1≤i≤n)
D、将n个结点从小到大排序
`010609F2
从循环单链表中查找出最大值.
~0106
intsearchmax(linklistl)
{intmax;
int*p;
p=l;
max=p->
data;
p=p->
next;
while(p->
next<
>
nil)
{
if(max<
p->
data)max=p->
}
returnmax;
`010709F2
从循环单链表中查找出最小值.
~0107
intsearchmin(linklistl)
{
intmin;
int*p;
p=l;
min=p->
p=p->
if(min>
data)min=p->
returnmin;
`011203D1
栈和队列都是线性表.()
~0112
正确
`011603B1
栈的两个重要应用是___________和_________.
~0116
在编译系统运行计算机语言程序的过程中,利用栈进行语法检查,实现递归调用.
`011703A2
栈和队列都是运算受到限制的特殊的线性表,栈和队列有何不同?
`011903C1
用数组A存放循环队列的元素值,若其头指针为front,尾指针为rear,则循环队列中当前元素个数为(A).
A、(rear-front+m)modmB、(rear-front+1)modm
C、(rear-front-1+m)modmD、(rear-front)modm
~0119
A
`012003A2
设循环队列Q头指针为front,尾指针为rear,队列的最大容量为M,写出循环队列队满和队空的判定条件.
~0120
队满条件:
(q.front+1)modm=q.rear
队空条件:
q.front=q.rear
`012203F2
给出循环队列的入队和出队算法.
~0122
intENQUEUE(sequeue*sq;
datatypex)
if(sq->
front==(sq->
rear+1)%maxsize)
printf("
queueisfull"
);
returnNULL;
}
else
sq->
rear=(sq->
rear+1)%maxsize;
data[sq->
rear]=x;
return(TRUE);
}
datatypeDEQUEUE(sequeue*sq)
if(EMPTY(sq))
queueisempty"
front=(sq->
front+1)%maxsize;
return(sq->
front];
`012503F2
设计算法判断一个算术表达式的圆括号是否正确配对,(提示:
对表达式进行扫描,凡遇'
('
就进栈,遇'
)'
就退掉栈顶的'
表达式被扫描完毕,栈就为空.)
~0125
booleanpair(b)
stacks;
s.top=0;
i=1;
ch=b[i];
while(ch!
="
@"
)
if((ch='
)||(ch='
))
switch
'
:
push(s,ch);
break;
ifempty(s){pair=false;
return;
}elsepop(s)
i=i+1;
ch=b[i];
ifempty(s)pair=true;
elsepair=false;
`012703B2
程序段的输出结果是_________(队列中的元素类型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);
EnQueue(Q,’a’);
while(!
QueueEmpty(Q)){DeQueue(Q,y);
printf(y);
};
Printf(x);
~0127
stack
`012909E2
什么是二叉排序树,按如下关键字的插入次序生成一棵二叉排序树,试画出此二叉排序树25,48,36,16,45,20,18,72
~0129
二叉排序树或者是一棵空树,或者是具有如下性质的二叉树:
(1)若它的左子树不空,则左子树上所有结点的值均小于根结点的值;
(2)若它的右子树不空,则右子树上所有结点的值均大于根结点的值;
(3)左右子树又各是一棵二义排序树.
25
1648
203672
1845
`013503E1
设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有
①front=11,rear=19;
②front=19,rear=11;
问在这两种情况下,循环队列中各有元素多少个?
~0135
用队列长度计算公式:
(N+r-f)%N
①L=(40+19-11)%40=8②L=(40+11-19)%40=32
`013803F2
设两个栈共享向量空间V(1:
m),它们的栈底分别设在向量的两端,且进栈的每个元素只占一个分量,试写出这两个栈公用的栈操作算法pushi(i,x),popi(i),其中i为0或1,用以指示栈号
~0138
pushi(i,x)
ifs.top0=s.top1-1printf("
orerflow"
ifi=0{s.top=s.top1+1;
s.elem[s.ti\op]=x;
else{s.top1=s.top0-1;
s.elem[s.top]=x;
popi(i)
ifi=0{
ifs.top0=0printf("
underflow"
pop=s.elem[s.top0]
s.top1=s.top1-1;
elseif
s.top=m+1printf("
pop=s.elem[s.top1];
s.top1=s.top1+1;
`014003F1
设HS为一个链栈的栈顶指针,试写出退栈的算法,(回收被删除的结点)
~0140
linkstack*POPSTACK(top,datap)
linkstack*top;
datatype*datap;
linkstack*p
if(top==NULL){printf("
underflow"
returnNULL)}
*data=top->
p=top;
top=top->
free(p);
returntop;
`014303E3
设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序.
~0143
至少有14种。
①全进之后再出情况,只有1种:
4,3,2,1
②进3个之后再出的情况,有3种,3,4,2,13,2,4,13,2,1,4
③进2个之后再出的情况,有5种,2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4
④进1个之后再出的情况,有5种,1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,3
`014703E2
写出栈的顺序存储结构(即顺序栈)的类型定义.
~0147
顺序栈的结构:
typedefintdatatype;
#definemaxsize64
typedefstruct
datatypedata[maxsize];
inttop
}seqstack;
seqstack*s;
`014803A1
写出队列的顺序存储结构(顺序队列)的类型定义.
~0148
顺序队列的结构:
datatypedata[maxsize]
intfrontrear;
}sequeue;
sequeue*sq;
`015003B2
带有头结点的链队列q,队头指针front,队尾指针rear,则置空队的算法描述为:
q->
front=malloc(sizeof(linklist));
________________;
~0150
q->
front->
next=NULL
rear=q->
front;
`015306C2
已知完全二叉树有28个结点,则整个二叉树有()个度为1的结点。
A、0;
B、1;
C、2;
D、不确定
~0153
B
`016506E3
已知一棵二叉树中序和后序序列为分别为:
BDCEAFHG和DECBHGFA画出这棵二叉树
`016806D1
哈夫曼树的带权路径长度WPL等于叶子结点的权值之和。
()
~0168
对
`016906E3
已知二叉树的先序、中序、后序序列分别如下,但其中有一些已模糊不清,构造出该二叉树.
先序:
_23_5_78
中序:
3_41_789
后序:
_42__651
~0169
`017206B3
在有N(N>
0)个结点的二叉链表中,空链域的个数是:
_____。
~0172
N+1
以二叉链表作存贮结构,试写出中序遍历二叉树的算法。
~0178
INORDER()
bitree*t;
{if(t)
{INORDER(t->
lchild);
|t%c|n"
t->
data);
INORDER(t->
rchild);
`018106B2
具有N个结点的完全二叉树的深度为_________。
~0181
└log2n+1┘+1或┌log2(n+1)┐
`018406A2
何谓哈夫曼树?
何谓完全二叉树,它具有哪些特点?
~0184
哈夫曼树:
带权路径WPL最小的二叉树称最优二叉树或哈夫曼树。
完全二叉树:
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上,则此二叉树为完全二叉树。
特点:
1只有最下面两层有叶子。
2如果一个结点无左子树,那它一定是叶子。
3完全二叉树中任一个结点的左子树深度为T,其右子树深度为T或T-1。
`019006E3
已知二叉树的中序和先序序列分别为:
中序序列:
DEBAFCHG
先序序列:
ABDECFGH
试构造该二叉树
~0190
`019106A3
度为2的树与二叉树的区别。
~0191
度为2的树每个结点如度为1子树无左右之分;
而二叉树则有。
`019206F2
试编写算法判断两棵二叉树是否等价,称二叉树T1和T2的根结点的值相同,并且T1的左子树与T2的左子树是等价的,T1的右子树和T2的右子树是等价的.
~0192
EQUBINTREE(t1,t2)
bintree*t1,*t2;
{if(t1=NULL&
&
t1=NULL)returnTRUE
else
{if(t1->
data=t2->
data&
ERUBINTREE(t1->
lchild,t2->
lchild)&
rchild,t2->
rchild))
returnTRUE;
returnFALSE;
`019806E2
已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,问该树中有多少片叶子.
~0198
N0=1+(i-1)Ni(i=1tom)
`020006E3
一个深度为L的满K叉树有如下性质:
第L层上的结点是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点编号,问:
(1)各层的结点的数目是多少?
(2)编号为n的结点的双亲结点(若存在)编号是多少?
(3)编号为n的结点的第i个孩子(若存在)编号是多少?
(4)编号为n的结点有右兄弟的条件是什么?
其右兄弟的编号是多少?
~0200
1.
K^(I-1)(1<
=I<
=k)
2.(n+k-2)/k
3.kn+I-k+1
4.nki+1(I=0,1,……);
n+1
`020807B1
一个具有n个顶点的连通有向图至多有_________条弧.
~0208
n(n-1)
`020907B1
一个具有n个顶点的连通有向图至少有________条弧.
~0209
n+1
`028106E2
把如图所示的树转化成二叉树。
~0281
注意全部兄弟之间都要连线(包括度为2的兄弟),并注意原有连线结点一律归入左子树,新添连线结点一律归入右子树。
B
EC
KFHD
LGI
MJ
`028206E2
画出和下列二叉树相应的森林。
~0282
注意根右边的子树肯定是森林,而孩子结点的右子树均为兄弟。
`029103C1
判定一个队列QU(最多元素为m0)为满队列的条件是()
A、QU->
rear-QU->
front==m0B、QU->
front-1==m0
C、QU->
front==QU->
rearD、QU->
rear+1
~0291
A
`032108E2
用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么?
如果要求时间复杂度更小,你采用什么方法?
此方法的时间复杂度是多少?
~0321
查找某个元素的时间复杂度下限,如果理解为最短查找时间,则当关键字值与表头元素相同时,比较1次即可。
要想降低时间复杂度,可以改用Hash查找法。
此方法对表内每个元素的比较次数都是O
(1)。
`035607C1
用邻接表表示图进行广度优先遍历时,通常是采用(B)来实现算法的。
A、栈B、队列C、树D、图
`035707C1
用邻接表表示图进行深度优先遍历时,通常是采用(A)来实现算法的。
A、栈B、队列C、树D、图
`035807C2
A.0243156
B.0136542
C.0423165
D.0361542
建议:
0134256
已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是(C)
`035907C2
已知图的邻接矩阵,根据算法,则从顶点0出发,按深度优先遍历的结点序列是(C)
A、0243156B、0135642C、0423165D、0134256
`036007C2
已知图的邻接矩阵,根据算法,则从顶点0出发,按广度优先遍历的结点序列是()
A、0243651B、0136425C、0423156D、0134256
(建议:
0123456)
~0360
B
`036107C2
A、0243165B、0135642C、0123465D、0123456
~0361
C
`036207C2
已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是()
A.0132B.0231C.0321D.0123
~0362
D
`036307C2
已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是()
A、0321B、0123C、0132D、0312
~0363
`036407C1
深度优先遍历类似于二叉树的(A)
A、先序遍历B、中序遍历C、后序遍历D、层次遍历
`036507C1
广度优先遍历类似于二叉树的(D)
A、先序遍历B、中序遍历C、后序遍历D、层次遍历
`037007B1
n个顶点e条边的图,若采用邻接矩阵存储,则空间复杂度为O(n2)。
n个顶点e条边的图,若采用邻接表存储,则空间复杂度为O(n+e)。
`037207B1
设有一稀疏图G,则G采用邻接表存储较省空间。
设有一稠密图G,则G采用邻接矩阵存储较省空间。
图的逆邻接表存储结构只适用于有向图。
已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。
图的深度优先遍历序列不是惟一的。
n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为O(n2);
若采用邻接表存储时,该算法的时间复杂度为O(n+e)。
n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为O(n2);
若采用邻接表存储,该算法的时间复杂度为O(n+e)。
图的BFS生成树的树高比DFS生成树的树高小或相等。
用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2);
用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。
若要求一个稀疏图G的最小生成树,最好用克鲁斯卡尔(Kruskal)算法来求解。
若要求一个稠密图G的最小生成树,最好用普里姆(Prim)算法来求解。
拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。
`038507E3
已知如图所示的有向图,请给出该图的:
(1)每个顶点的入/出度;
(2)
邻接矩阵;
(3)邻接表;
(4)逆邻接表。
顶点
1
2
3
4
5
6
入度
出度
~0385
`038607E3
请对下图的无向带权图:
(1)写出它的邻接矩阵;
(2)写出它的邻接表。
~0386
(1)
a
→
b
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题 参考答案