东大数据结构Ⅱ期末考试复习资料与参考答案

3亿多的题库，支持文图片，语音搜题，包含国家开放大广东开放大云南开放大北京开放大上海开放大江苏开放大超青奥鹏等等多个平台题库，考试作业必备神器。

正确 答案：微信搜索【渝粤搜题】公众号

广东开放大学 2023年春季招生简章

数据结构II复习题

单选题

1．表达式a*(b+c)-d的后缀表达式是

A．*+- B．*+d-

C．+*d- D．-+*

2．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是

A. 空或只有一个结点 B.高度等于其结点数

C. 任一结点无左孩子 D.任一结点无右孩子

3．下面的说法中正确的是

(1)任何一棵二叉树的叶子结点在三种遍历中的相对次序不变。

(2)按二叉树定义，具有三个结点的二叉树共有6种。

A．(1)，(2) B．(1)

C．(2) D．(1)，(2)都错

4．树有先序遍历和后序遍历，树可以转化为对应的二叉树。下面的说法正确的是

A．树的后序遍历与其对应的二叉树的先序遍历相同

B．树的后序遍历与其对应的二叉树的中序遍历相同

C．树的先序序遍历与其对应的二叉树的中序遍历相同

D．以上都不对

5．下列说法正确的是

(1)二又树按某种方式线索化后，任一结点均有指向前趋和后继的线索

(2)二叉树的先序遍历序列中，任意一个结点均处于在子孙结点前

(3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值

A．(1)(2)(3) B．(1)(2)

C．(1)(3) D．都不对

6. 二叉树的第k层的结点数最多为

A．2k-1 B.2K+1

C.2K-1 D. 2k-1

7．以下说法不正确的是

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D．有向图的遍历不可采用广度优先搜索

8．有向图G用邻接矩阵A存储，则顶点i的入度等于A中

A. 第i行1的元素之和 B. 第i列1的元素之和

C. 第i行0的元素个数 D. 第i列非0的元素个数

9. 设有6个结点的无向图，该图至少应有多少条边才能确保是一个连通图？

A.5 B.6

C.7 D.8

10．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是

A. V1V2V3V4V5 B. V1V2V3V5V4

C. V1V4V3V5V2 D.V1V3V4V5V2

11．抽象数据类型的三个组成部分分别为

A．数据对数据关系和基本操作

B．数据元逻辑结构和存储结构

C．数据数据元素和数据类型

D．数据元数据结构和数据类型

12．要求相同逻辑结构的数据元素具有相同的特性，其含义为

A. 数据元素具有同一的特点

B. 不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致

C. 每个数据元素都一样

D. 仅需要数据元素包含的数据项的个数相同

13．下列各式中，按增长率由小至大的顺序正确排列的是

A．，n！，2n ，n3/2

B．n3/2，2n，nlogn，2100

C．2n，log n，nlogn，n3/2

D．2100，logn, 2n, nn

14. 在下列哪种情况下，线性表应当采用链表表示为宜

A.经常需要随机地存取元素

B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间

D.表中元素的个数不变

15．设指针p指向双链表的某一结点，则双链表结构的对称性可表示为

A. p->prior->nex=p->nex->nex;

B. p->prior->prior=p->nex->prior;

C. p->prior->nex=p-> nex->prior;

D. p->nex->nex= p->prior->prior;

16. 已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为

A. s->nex=q；p->nex=s->nex；

B. s->nex=p；q->nex=s->nex；

C. p->nex=s->nex；s->nex=q；

D. q->nex=s->nex；s->nex=p；

17. 栈和队列的共同特点是

A.只允许在端点处插入和删除元素

B.都是先进后出

C.都是先进先出

D.没有共同点

18. 对于链队列，在进行插入运算时.

A. 仅修改头指针

B. 尾指针都要修改

C. 仅修改尾指针

D.尾指针可能都要修改

19．设有一个顺序栈的入栈序列是3，则3个元素都出栈的不同排列个数为

A．4 B．5

C. 6 D. 7

20．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是

A．A，B，C，( ) B．D，C，B，A

C. A，C，D，B D. D，A，B，C

：

填空题

1.下面程序段中带下划线的语句的执行次数的数量级是( )。

i=1；

WHILE(i<n)

i=i*2;

2．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个结点之前插入指针s所指结点的语句依次是( )。

3．无表头结点的链队列Q为空的条件是( )。

4．设Q[0..N-1]为循环队列，其尾指针分别为P和R，则队Q中当前所含元素个数为( )。

5．一棵含999个结点的完全二叉树的深度为( )。

6．在 AOV网 中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它表明存在( )。

7. 有向图G可拓扑排序的判别条件是( )。

8．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是( )。

9．应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为( )。

10. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。

：

1. log2n 2．s->nes=L->nex->nex；L->nex->nex =S 3． Q->real==Q->ron=NULL 4．( )% N 5．10 6．死循环7. 不存在环8．4 9.限界函数 10. 4231

应用题

1．比较线性表和栈的基本操作的不同点。

2．有一个二叉树按层次顺序存放在一维数组中，如下图所示：

试求：( )该树的后序遍历序列。

( )画出该树的后序线索树。

1 2 3 4 5 6 7 8 9 10 11

3．分析顺序查找算法的“监视哨”设置作用

4．对n个整数的序列进行直接选择排序。

( )算法描述。

( )并给出实例( )的排序过程。

：

1．主要区别是对插入和删除操作的限制。

如线性表允许在表内任一位置进行插入和删除；而队列只允许在表尾一端进行插入，在表头一端进行删除；所以也称队列为受限的线性表。表头为队列头；表尾为队列尾。

插 入 　　　　　删 除

线性表 Inser(L,i,x)　　Delee(L,i)

　　　 　 (1≤i≤n+1)　 　(1≤i≤n)

队列 　　Inser(L,n+1,x) 　Delee(L,1)

2．( )后序遍历序列 C E ( )B A

( )后序线索树

3．为了考虑查找不成功的情况,在每次进行关键字的比较前，首先要判断循环变量i是否数组越界，这对算法来说是必要的。如果每步省略数组下标是否越界的判断，则可以大大提高算法运行的效率。为此，可以利用预留的0号单元，作为所设的“监视哨”控制循环变量i的出界。

假设数据从后向前比较，监视哨设在数组低端 L.elem [0] = k

将算法中的判断语句

while (i <= L.lengh &&L.elem [i] != k) ++i;

改为 while (L.elem [i] != k) --i;

这样，当在查找表中不存在其关键字等于给定值的数据元素时，i必等于0,并且这样的处理并不影响查找成功的情况。

4．( )直接选择算法描述：

[1] 第1趟，从n个记录中，经过比较选出关键字值为最小的记录，并与第1个记录交换位置。

[2] 第2趟，从余下的n-1个记录中选择出当前关键字最小的排序，并与第 2个记录交换位置。

[3] 第i趟，在无序的第i个到第n个的n-i+1 个记录中选出关键字最小的记录，与第i个记录进行互换。

[4] 以此类推，直至第n-1趟排序结束。

( )初始状态 52 49 80 36 14 58 61 23

i=1 [14] 49 80 36 52 58 61 23

i=2 [14 23] 80 36 52 58 61 49

i=3 [14 23 36] 80 52 58 61 49

i=4 [14 23 36 49] 52 58 61 80

i=5 [14 23 36 49 52] 58 61 80

i=6 [14 23 36 49 52 58] 61 80

i=7 [14 23 36 49 52 58 61] 80

排序结果 [14 23 36 49 52 58 61 80 ]

算法阅读题

设计算法实现以链表作存储结构，将线性表中前m个元素和后n个元素进行整体互换，即(a1,…,am,b1,…,bn) 改变成(b1,…,bn,a1,…,am)。阅读算法，在横线处填入语句或注释。

void exchange_L( Linklis &L，in m ) {
// 本算法实现单链表中前m个结点和后n个结点的整体互换
i ( m && L->nex ) { // 链表不空且

p = L->nex;

( )

while( k< m && p ) { //( )
p = p->nex; ++k;
} // while

i (p && ( )) { // n!=0 时才需要修改指针
ha = L->nex; // 以指针 ha 记a1结点的位置

( )= p->nex; // 将 b1 结点链接在头结点之后
p->nex = NULL; // 设am的后继为空
q = L->nex; // 令q 指向 b1结点

while (q->nex)

q = q->nex; // 查找 bn 结点

q->nex = ha; // ( )
} // i(p)
} // i(m)

} // exchange_L

( )k = 1;

( )查找第am 个结点
( )p->nex

( )L->nex

( )将第 a1 结点链接到 bn 结点之后

算法设计题

设计算法purge_Sq实现删除顺序表SqLis中重复元素，指出其算法的时间复杂度。

：

void purge_Sq( SqLis &L ) {// 删除顺序表L中的重复元素

k = -1;// k 指示新表的表尾
or (i=0; i<L.lengh; ++i) { // 顺序考察表中每个元素

j=0;

while(j<=k && L.elem[j]!=L.elem[i])
++j; // 在新表中查询是否存在和L.elem[i]相同的元素
i ( k==-1 || j>k )// k=-1 表明当前考察的是第一个元素
L.elem[++k] = L.elem[i];

} // or
L.lengh = k+1;// 修改表长

} // purge_Sq

此算法的时间复杂度为O (L.lengh2 )。

算法设计题( )

设计算法从图的邻接表结构转换成邻接矩阵结构的算法。

：

void AdjLisoAdjMarix(AdjLis gl, AdjMarix gm){

//将图的邻接表表示转换为邻接矩阵表示。

or (i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。

or (j=1;j<=n;j++) gm[i][j]=0;

or (i=1;i<=n;i++){

p=gl[i].irsarc; //取第一个邻接点。

while (p) {// 下一个邻接点

gm[i][p->adjvex]=1;

p=p->nex;

}// while

}//or

}// AdjLisoAdjMarix

综合题

阅读算法，在横线处填入语句或注释。

void exchange_L( Linklis &L，in m ) {
// 本算法实现带头结点的单链表中前m个结点和后n个结点的整体互换
i ( m && L->nex ) { // 链表非空

p = L->nex;

( )

while( k< m && p ) { //( )
p = p->nex; ++k;
} // while

i (p && ( )) {

ha = L->nex; // 记a1结点的位置

L->nex= p->nex; // 将 b1 结点链接在头结点之后
p->nex =( );
q = L->nex; // 令q 指向 b1结点

while (q->nex)

q = q->nex; // 查找 bn 结点

q->nex =( )
} // i(p)
} // i(m)

} // exchange_L

( )k = 1;

( )查找第am 个结点
( )p->nex

( )NULL

( )ha;

2．一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树中，设计算法1实现求值，并指出遍历的方式。

：

( )算法实现。

k = 1;

in 1(Birec ){

i(!) reurn 0;

i(!→lchild &&!→rchild)//判断是否为叶子结点

reurn (→daa);

Lv= 1(→lchild);Rv= 1(→rchild);

swich(→daa){// 求值运算

case ’+’ : V=Lv+Rv; break;

case’-’ : V=Lv-Rv; break;

case’*’: V=Lv*Rv; break;

case’/’: V=lv/Rv; break;

} //swich

reurn V;//返回值

}//1

( )后序遍历二叉树求值。

3．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：

顶点结构 表结点结构

：

算法实现

in oposor (ALGraph G,in pv[]){ //以逆邻接表为存储结构的有向图的拓扑排序

op=0;

or(i=0;i<G.vexnum;i++) or(p=G.jlis[i].irsedge;p;p→nex)

indoudegree(G,oudegree); // 对各顶点求出度

oudegree[p→adjvex]++; IniSack(&S); //初始化栈

or(i=0;i<G.Vexnum;i++)

i(oudegree[i]==0) Push(&S,i); //出度为零的顶点入栈

while(!Sack(S)){

Pop(&S,i);prin(G.jlis[i].vexex);

pv[op++]=i;

or(p=G.jlis[i].irsedge;p;p→nex){

j=p→adjvex; oudegree[j]--;

i(!oudegree[j]) Push(&S,j);

//出度为零的顶点入栈

}//or

}//while

i(op<G.vexnum) reurn 0; //无环

else {//输出顶点拓扑排序序列

or(i=0;j=op-1;i< G.vexnum/2;i++,j--){//置逆输出

emp=pv[i];pv[i]=pv[j];pv[j]=emp;

}//or

reurn 1;

}//else

}//oposor