数据结构与算法-大连理工大学中国大学mooc课后章节答案期末考试题库2023年

数据结构与算法_大连理工大学中国大学mooc课后章节答案期末考试题库2023年一棵二叉树的前序遍历序列为1234567,它的中序遍历序列可能是

参考答案:

1234567

在任何一棵二叉树中，如果结点a有左孩子b,右孩子c,则在结点的先序序列、中序序列、后序序列中，

参考答案:

结点b一定在结点c的前面

一棵完全二叉树上有1001个结点，其中叶子结点的个数是。

参考答案:

501

二叉树的先序遍历的递归实现如下：templatevoidBinaryTree::PreOrder(BinaryTreeNode*root){if(root!=NULL){;}}则中间部分应为：

参考答案:

Visit(root->value());PreOrder(root->leftchild());PreOrder(root->rightchild());

关键路径是事件结点网络中。

参考答案:

从源点到汇点的最长路径

一个有n个顶点和n条边的无向图一定是（）。

参考答案:

有环的

下列说法不正确的是。(1).求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。

参考答案:

(1),(2),(3)

在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个辅助结构。

参考答案:

并查集

长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找失败时的平均查找长度是

参考答案:

49/13

长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是

参考答案:

37/12

对于数据结构的描述，下列说法中不正确的是。

参考答案:

相同的逻辑结构对应的存储结构也必须相同

在链接存储结构中，要求。

参考答案:

每个结点占用一片连续的存储区域

当n足够大时，在有序顺序表中进行折半查找，假设顺序表中每个元素的查找概率相同，则查找成功的平均查找长度为。

参考答案:

lg(n+1)-1

用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）。

参考答案:

21,32,46,40,80,69,90,94

对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}，则该次采用的增量是()

参考答案:

4

快速排序方法在（）情况下最不利于发挥其长处。

参考答案:

要排序的数据已基本有序

归并排序中，归并的趟数是()。

参考答案:

O(logn)

有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（）

参考答案:

-1，4，7，8，20，15，7，9

下列排序算法中，若将顺序存储更换为链式存储，则算法的时间效率会降低的是()

参考答案:

堆排序

对给定的关键字序列110，119，007，911，114，120，122进行基数排序，第二趟分配收集后得到的关键字序列是()

参考答案:

007，110，911，114，119，120，122

若对27个元素只进行3趟多路归并排序，则选取的归并路数最少是()

参考答案:

3

对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）

参考答案:

元素之间的比较次数

在下面的排序方法中，辅助空间为O（n）的是。

参考答案:

归并排序

在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<

参考答案:

直接插入排序

下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是。

参考答案:

快速排序

数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的的两趟排序后的结果。

参考答案:

插入排序

一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。

参考答案:

(40,38,46,56,79,84)

按{10，20，30，100，40，25}的顺序构成平衡二叉树，其根结点是。

参考答案:

30

设结点X和Y是二叉树中任意的两个结点．在该二叉树的先序遍历序列中X在Y之前，而在其后序遍历序列中X在Y之后，则X和Y的关系是

参考答案:

X是Y的祖先

已知一个栈的进栈序列是ABC，出栈序列是CBA，经过的栈操作是。

参考答案:

push,push,push,pop,pop,pop

某内排序方法的稳定性是指。

参考答案:

以上都不对

高度为K（只有根结点时的高度为1）的二叉树最大的结点数为。

参考答案:

2^k-1

平均查找长度与查找集合中记录个数n无关的查找方法是。

参考答案:

散列查找

对表长为n的有序表进行折半查找，其判定树的高度为。

参考答案:

lg(n+1)

一棵树高为K（只有根结点时的高度为1）的完全二叉树至少有个结点

参考答案:

2^(k-1)

二叉树是非线性数据结构，所以。

参考答案:

顺序存储结构和链式存储结构都能存储

下面关于Huffman树的说法，不正确的是。

参考答案:

Huffman树中除了度为1的结点外，还有度为2的结点和叶结点

算法的时间复杂度属于一种。

参考答案:

事前分析估算的方法

有n个叶子的哈夫曼树的结点总数为。

参考答案:

2n-1

判断一个有向图是否存在回路除了可以使用拓扑排序方法外，还可以使用方法。

参考答案:

深度优先遍历

无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是。

参考答案:

a,e,d,f,c,b

在二叉搜索树的存储结构中，关键字值最大的结点（）

参考答案:

右指针一定为空

设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是。

参考答案:

O(nlgn)

下列说法不正确的是。

参考答案:

图的深度遍历不适用于有向图

设无向图的顶点个数为n，则该图最多有条边。

参考答案:

n(n-1)/2

线性表的顺序存储结构是一种的存储结构。

参考答案:

随机存取

在含有n个节点的二叉排序树中查找一个关键码，最多进行次比较。

参考答案:

n

对于链队，在进行删除操作时，。

参考答案:

头、尾指针可能都要修改

在二叉树的前序序列、中序序列和后序序列中，所有叶子结点的先后顺序

参考答案:

完全相同

设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是

参考答案:

n在m左方

下列序列中，不能唯一地确定一棵二叉树的是

参考答案:

先序序列和后序序列

对线性表进行顺序查找，要求线性表的存储结构为。

参考答案:

顺序存储或链接存储

设环形队列中数组的下标是0～N-1，其头、尾指针分别为f和r，则其元素个数为。

参考答案:

(r-f+N)%N

链栈与顺序栈相比有一个明显的优点，即。

参考答案:

通常不会出现栈满的情况

设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（    ）。

参考答案:

M2+M3

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

参考答案:

2m

对于下列关键字序列，不可能构成某二叉搜索树中的一条查找路径的序列是（）

参考答案:

95，22，91，24，94，71

二叉树的第I（只有根结点时的层数为1）层上最多含有结点数为。

参考答案:

2^(l-1)

设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是。

参考答案:

s=rear->next->next;rear->next->next=s->next;

若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是。

参考答案:

11

用顺序查找方法在长度为n的线性表中进行查找，在等概率情况下，查找成功的平均查找长度为。

参考答案:

(n+1)/2

经过以下栈运算后，x的值是。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);

参考答案:

a

一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是。

参考答案:

dceab

散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。

参考答案:

同等概率

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()

参考答案:

k（k+1）/2次

设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()

参考答案:

9

对线性表进行二分查找时，要求线性表必须（）

参考答案:

以顺序方式存储,且数据元素有序

当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度

参考答案:

在大部分情况下要快

下面关于二分查找的叙述正确的是()

参考答案:

表必须有序，且表只能以顺序方式存储

下面不是算法所必须具备的特性。

参考答案:

高效性

在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。

参考答案:

G中有一条从Vj到Vi的路径

求解最短路径的Floyd算法的时间复杂度为()。

参考答案:

O（n*n*n）

在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。

参考答案:

O(n+e)

用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。

参考答案:

Am

用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（）。

参考答案:

逆拓扑有序

若邻接表中有奇数个边表结点，则一定是（）

参考答案:

图为有向图

对于含有n个字符的链串s，查找元素值为x的算法时间复杂度为。

参考答案:

O(n)

已知t=”abcaabbcabcaabdab”，该模式串的特征数组值为。

参考答案:

-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1

设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是。

参考答案:

n(k+1)-2m

在长度为n的线性表中查找值为x的数据元素的时间复杂度为。

参考答案:

O(n)

在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行操作。

参考答案:

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

带头结点的单链表L为空的判定条件是。

参考答案:

L->next==NULL

与单链表相比，双链表的优点之一是。

参考答案:

访问前后相邻结点更灵活

设线性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高。

参考答案:

删除指定的元素

将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是。

参考答案:

n

某算法的时间复杂度是O(n^2)，表明该算法。

参考答案:

执行时间与n^2成正比

可以用、数据关系和基本操作定义一个完整的抽象数据类型。

参考答案:

数据元素

以下关于链接存储结构的叙述中，是不正确的。

参考答案:

可以通过计算得到第i个节点的存储地址

设森林F对应的二叉树为B，它有m个结点，B的根为P，P的右子树结点个数为n，森林F中的第一棵树的结点个数是__。

参考答案:

m-n-1

已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G的拓扑序列是（）。

参考答案:

V1,V3,V4,V6,V2,V5,V7

如果最常用的操作是取第i个节点及其前驱，则采用存储方式最节省时间。

参考答案:

顺序表

要连通具有n个顶点的有向图，至少需要（）条边。

参考答案:

n

设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（    ）个。

参考答案:

n+1

对n个记录的文件进行堆排序，最坏情况下的执行时间是多少？

参考答案:

O（nlog2n）

若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是。

参考答案:

归并排序

下列排序算法中，算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

参考答案:

插入排序

排序趟数与序列的原始状态有关的排序方法是排序法。

参考答案:

冒泡

下列关于排序的叙述中正确的是（）

参考答案:

对同一线性表使用不同的排序方法进行排序得到的排序结果可能不同

算法指得是。

参考答案:

对特定问题求解步骤的一种描述，是指令的有限序列

对于二叉搜索树，下面说法正确的是（）

参考答案:

用逐点插入法构造二叉搜索树，若先后插入的关键字有序，二叉搜索树的深度最大

对于任意非空二叉树，要设计出其后序遍历的非递归算法而不是用堆栈结构，最适合的方法是对该二叉树采用存储结构。

参考答案:

三叉链表

一棵二叉树高度为h（只有根结点时的高度为1）,所有结点的度或为0，或为2，则这棵二叉树最少有结点

参考答案:

2h-1

一个具有1025个结点的二叉树的高h（只有根结点时的高度为1）为

参考答案:

11至1025之间

任何一个无向连通图的最小生成树（）。

参考答案:

有一棵或多棵

度为4、高度为h的树，__。

参考答案:

至少有h+3个结点

判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为。

参考答案:

st.top==-1

下面关于求关键路径的说法不正确的是。

参考答案:

一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={,,,}。若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）

参考答案:

5

用邻接表存储的图的深度优