中国大学MOOC-陈越、何钦铭-数据结构-2019春期中考试

谁践踏了优雅 2022-02-17 15:57 198阅读 0赞

1-1  
在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 (3分)  
答案：F

1-2  
若一棵平衡二叉树的所有非叶结点的平衡因子都是0，则其必为完美二叉树。(3分)  
答案：T

1-3  
在用数组表示的循环队列中，front值一定小于等于rear值。 (2分)  
答案：F

1-4  
一棵有124个结点的完全二叉树，其叶结点个数是确定的。 (3分)  
答案：T

1-5  
如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。 (3分)  
答案：T

1-6  
在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。 (3分)  
答案：F

1-7  
用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 (3分)  
答案：T

1-8  
若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。 (3分)  
答案：F

1-9  
算法可以没有输入，但是必须有输出。 (2分)  
答案：T

1-10  
若一个栈的输入序列为\{1, 2, 3, 4, 5\}，则不可能得到\{3, 4, 1, 2, 5\}这样的出栈序列。 (3分)  
答案：T

2-1  
将\{5, 2, 7, 3, 4, 1, 6\}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：(4分)  
![在这里插入图片描述][20190419204721135.png]  
2-2  
在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是\{ 1, -4, 1, 1, -3, 4, 4, 8, -2 \}（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？ (4分)  
![在这里插入图片描述][2019041920475530.png]  
2-7  
下列函数

int func ( int n )
    {   int i = 0, sum = 0;
        while ( sum < n )  sum += ++i;
        return i;
    }

的时间复杂度是：(4分)  
O(n1/2 )

2-10  
循环顺序队列中是否可以插入下一个元素（）。  
![在这里插入图片描述][20190419220032824.png]  
2-11  
带头结点的单链表h为空的判定条件是：  
![在这里插入图片描述][20190419220056466.png]  
2-12  
若某图的深度优先搜索序列是\{V2, V0, V4, V3, V1\}，则下列哪个图不可能对应该序列？  
![在这里插入图片描述][20190419220124440.png]

[20190419204721135.png]: /images/20220217/87fe0a79d6054ef289b5227a5dc8219b.png
[2019041920475530.png]: /images/20220217/c4fa5055be194c558802bd1d48d7b43c.png
[20190419220032824.png]: /images/20220217/ac13e735a8f54df8b72b416505679af8.png
[20190419220056466.png]: /images/20220217/1efb228789bb421aade9a1876af5d72e.png
[20190419220124440.png]: /images/20220217/b8f49e96613d4a2488267c52092a6ad0.png