东北师范大学20秋《数据结构》在线作业2答案参考

东北师范大学20秋《数据结构》在线作业2答案参考

递归过程的实现需用到()。

A.线性表

B.链表

C.栈

D.队列

在下列情况中，可称为二叉树的是0。

A.每个结点至多有两棵子树的树

B.哈夫曼树

C.每个结点至多有两棵子树的有序树

D.每个结点只有一棵右子树

经过下列栈的操作后，GetTop(ST)的值是()。InitStack(ST);push(ST,

，a');push(ST,'b');pop(ST,x);

A.a

B.b

C.1

D.2

若要求尽可能快地对序列进行稳定的排序，则应选()。

A.快速排序

B.归并排序

C.起泡排序

D.希尔排序

一个算法应该是()。

A.程序

B.问题求解步骤的描述

C.要满足五个基本特性

D.A和C

判断线索二叉树中某结点p有左子女的条件是()。

A.p!=NULL

B.p-lchild!=NULL

C.p-ltag==0

D.p-ltag==l

二叉树在中序线索化后，仍不能有效求解的问题是()。

A.求指定结点的前序后继

B.求指定结点的中序前驱

C.求指定结点的中序后继

D.求指定结点的后序后继

顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求

重新复制整个文件，代价很高，采用()的方法可降低所需的代价。

A.附加文件

B.按关键字大小排序

C.按记录输入先后排序

D.连续排序

广义表A=(a,b,(c,d),(e,(f,g))),则式子

head(tai(head(tai1(tai1(A)))))的值为()。

A.(g)

B.(d)

C.c

D.d

()的遍历仍需要栈的支持。

A.前序线索二叉树

B.中序线索二叉树

C.后序线索二叉树

D.前三种均需要

线索二叉树是一种()结构。

A.逻辑

B.物理

C.逻辑和存储

D.线性

有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用

三元组表示该矩阵时，所需的字节数是0。

A.60

B.66

C.18000

D.33

就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是()。

A.堆排序B.堆排序C.堆排序》归并排序》快速排序

D.堆排序》快速排序〉归并排序

下列说法不正确的是()。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次

B.遍历的基本方法有两种：深度优先遍历和广度优先遍历

C.图的深度优先遍历不适用于有向图

D.图的深度优先遍历是一个递归过程

在一个图中，所有顶点的度数之和等于图的边数的几倍()。

A.1/2

B.1

C.2

D.4

在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入

s所指结点，则执行()。

A.p->next=s;s->next=q;

B.s->next=p->next;p->next=s;

C.p->next=s->next;s->next=p;

D.q->next=s;s->next=p;

在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是()。

A.0(log2n)

B.0(1)

C.0(n)

D.0(nlog2n)

已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为

LOC(a0),则第i个结点的地址为()。

A.LOC(aO)+(i-l)*c

B.LOC(aO)+i*c

C.LOC(a0)-i*c

D.LOC(aO)+(i+l)*c

分块查找要求表中的结点0。

A.全部无序

B.块之间无序

C.全部有序

D.块之间有序

下面关于串的叙述中，哪一个是不正确的？。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。

0

A.错误

B.正确

在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移

动，则该算法是不稳定的。（）

A.错误

B.正确

非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。（）

A.错误

B.正确

数组是同类型值的集合。（）

A.错误

B.正确

用链表（Ichild-rchild表示法）存储的包含n个结点的二叉树，结点的2n个指

针域中有n+1个空指针。（）

A.错误

B.正确

链表中的表头指针与表头结点起到相同的作用。（）

A.错误

B.正确

栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）

A.错误

B.正确

一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）

A.错误

B.正确

对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，

对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均

查找长度是不同的。（）

A.错误

B.正确

任何无向图都存在生成树。（）

A.错误

B.正确

在完全二叉树中，若一个结点没有左子女，则它必是树叶。（）

A.错误

B.正确

链表中的表头结点仅起到标识的作用。（）

A.错误

B.正确

将一棵树转成二叉树，根结点没有右子树。（）

A.错误

B.正确

连通分量是无向图中的极大连通子图。（）

A.错误

B.正确

所谓取广义表的表尾就是返回广义表中最后一个元素。（）

A.错误

B.正确

需要借助于一个栈来实现DFS算法。（）

A.错误

B.正确

必须把一般的树转换成二叉树后才能进行存储。（）

A.错误

B.正确

对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。（）

A.错误

B.正确

后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。（）

A.错误

B.正确

二维以上的数组其实是一种特殊的广义表。（）

A.错误

B.正确

参考答案：C

参考答案：B

参考答案：A

参考答案：B

参考答案：B

参考答案：C

参考答案：D

参考答案：A

参考答案：D

参考答案：C

参考答案：B

参考答案：A

参考答案：A

参考答案：C

参考答案：C

参考答案：D

参考答案