2019上海科技大学991数据结构与算法

文章目录

• 基础知识与结论

• • • ①：
    • ②：
    • ③：渐进号

• 试题集

• 一、判断题型（共10题）

  • 每小题均为2分

• 二、单项选择题（共10个小项）

  • 每小项均为2分

• 三、多项选择题目（共5个小类）

  • 每个小类均为2分

• 四、 Lists 部分（满分25分）

• 五、二叉树部分（满分25分）

  • 六. Graph (25 points) 图（25 分）
  • 七.快速排序（25 分）

    算法导论：
    链接：https://pan.baidu.com
    /s/1nXzwVML3V_FFnQHGFfBcYg 
    提取码：50pq

基础知识与结论

①：

在满二叉树中的情况下

②：

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

③：渐进号

O：算法运行时间的上界
\Omega：算法运行时间的下界
\Theta：描述了算法运行时间的渐近行为
o：在数学分析中通常用于描述函数间的增长速率比较

真题

一.判断题（10 题，每题 2 分）

1. 在循环链表结构中存在某些节点的链接域指向null或未初始化的状态。
2. 都是环状结构哦！
3. 为了保证数据完整性，请确保每个节点的数据信息完全一致。
4. 如果一个节点的链接域为空，则整个链表将无法正常遍历。

对于任何函数f和g来说，在f=Q(g)的情况下f=o(g)是不可能同时成立的。

3. 一个好的哈希函数需满足简单均匀（对）

4.下列树是二叉搜索树。 （对）

满足左子<根<右子
5.一棵树的节点数目未必多于叶子数目两倍。（对）
非二叉树情况下是否为二叉树？（ ╱　　_　　╲ ）
只要选取一条足够长的单链结构即可举例。

6.图的邻接矩阵表示空间复杂度与边数无关。 （ 对）

7.在图的广度遍历算法中，每个节点恰好仅入队一次。 （ 对）

给定一个带权有向图G(V,E)，其中V={v₁,v₂,…,vₙ}表示顶点集合。我们需要找出从v₁到vₙ的最短路径是否存在以及其实现的具体方法。

在图论问题中，确定该图是否包含正好100个节点的clique属于NP完全问题。假设P≠NP时

对于任意给定的一个图G=(V,E)，判定是否存在这样一个子集V'⊆V且|V'|=|V|/2（当|V|为偶数时），使得剩余的节点组成的子图G[V']具有三染色性质）。假设P≠NP，则这一判定过程是否可以在多项式时间内完成？

二.单选题（10 题，每题 2 分）

哪一种字符串的数据结构能够方便地进行添加、移除以及连接操作，并且能够容易地重新排列子串？（ B）
A. 固定长度的存储结构
B. 链表存储结构
C. 具有固定最大长度的变存储结构
D. 数组存储结构
E. 以上都不是

在下面哪一个选项中给出的函数序列是按照渐进增长顺序排列？（C ）

3. 存储这些元素到一个哈希表中（共有十个元素），这些元素的键为{5、28、19、15、20、12、33、17、10和18}。该哈希表共包含九个槽位，并使用了h(k) = k mod9这一函数来计算键的位置，并采用链表来处理发生冲突的情况。在计算出mod结果后得到如下余数值序列：5、1、…直至最后的结果为0；那么在这些条件下，请问此哈希表中最长链表的最大长度是多少？选项如下：
   A. 最大长度为一
   B. 最大长度为二
   C. 最大长度为三
   D. 最大长度为四

4．每个中间顶点都具有两个子顶点的完全二又树称为完美二又树。在一个完美二又树中如果有5o o片叶子层中的叶子数目是多少？（ B） A．2so B．499 C．soo D．sO1 E．1oOO

5. 在下面选项中哪个关于树的说法是错误的？（ A）
   A. 可能存在非叶子节点没有子节点
   B. 添加一条边会导致出现环路
   C. 并非所有树中的每个节点都会有父节点
   D. 包含单个节点的树其高度为 0

对于A选项而言，若其非叶子节点，则其下必然连接着子节点。对于C选项而言，仅存的一个根节点自然没有父节点。

6.下面二叉树的中序遍历是什么？（ A）

A. DFBEAC
B. ABDFEC
C. FDEBCA
D. FDEBAC

7. Prim 算法用于计算图的最小生成树吗？Floyd-Warshall 算法可用来计算有向图中的各节点间最短路径吗？以下哪些表述肯定正确？（B）

i: The Prim algorithm is a well-known greedy algorithm used in various applications.
ii: The Prim algorithm is often employed as a dynamic programming approach in network optimization.
iii: The Floyd-Warshall algorithm is known for its greedy nature in solving all-pairs shortest path problems.
iv: The Floyd-Warshall algorithm utilizes dynamic programming principles to compute the shortest paths efficiently.

8. 在以下选项中，哪个图的问题可以在线性时间内解决？（ B）
   A. 确定无向图中的最大简单环
   B. 找出有向图中的强连通分量
   C. 求解带权有向图中的单源最短路径
   D. 确定无向图的最大团
   汪同学认为答案是B项。

9.下列关于归并排序和快速排序的陈述哪一项是对的？（ A）
A. 都是用分治法
B. 给定一个长度为 n 的输入数组，都是需要O(n)的时间进行每一次切分
C. 都有相同的最坏时间复杂度
D. 以上都对
我是感觉AB都对，但是汪同学说，归并并不划分，只是在并的时候才花时间，大概这个意思
10.任何一个基于比较的算法在一个长度为 n 的数组中同时找出最大和最小值，至少需要数组元素之间的比较的次数与下列哪个最接近？（B ）
A. n
B. 1.5n
C. 2n
D. n²

汪同学指出，在阅读算法导论第九章第一页的内容时提到了一个结论选B。
实际上就是将元素两两放入并进行一次比较。
拿进去的这两个会被先进行一次比较。
然后较小的那个会被用来确定最小值较大的那个会被用来确定最大值
每一轮总共会进行三次这样的操作但整个过程总共只会运行\frac{n}{2}轮因此总的计算次数是\frac{3n}{2}次
经过测试发现优化后的结果似乎并没有预期中的提升试想一下如果是生成了一个非常有序的随机序列那么标答的方法就会变得明显起来
于是尝试更换策略仅采用条件判断和赋值操作完成了这一过程
第三种方法是由其他同学提出的这个方案让我印象深刻因为它提供了一种简洁而有效的方式

    #include"bits/stdc++.h"
    #define Rand(L,R) (L+sui()%(R-L+1))
    using namespace std;
    const int maxn=1e8+5;
    int a[maxn],N=maxn-5;
    clock_t t1,t2;
    int solve1()
    {
    	int Max=a[1],Min=a[1];
    	t1=clock();
    	for(int i=2;i<=N;i++)
    	{
    		if(a[i]>Max)Max=a[i];
    		if(a[i]<Min)Min=a[i];
    	}
    	t2=clock();
    	cout<<"Max="<<Max<<" Min="<<Min<<endl;
    	return t2-t1;
    }
    int solve2()
    {
    	int Max=-1e9,Min=1e9;
    	t1=clock();
    	for(int i=1;i<=N;i+=2)
    	{
    		if(a[i]<a[i+1])
    		{
    			if(a[i]<Min)Min=a[i];
    			if(a[i+1]>Max)Max=a[i+1];
    		}
    		else
    		{
    			if(a[i+1]<Min)Min=a[i+1];
    			if(a[i]>Max)Max=a[i];
    		}
    	}
    	t2=clock();
    	cout<<"Max="<<Max<<" Min="<<Min<<endl;
    	return t2-t1;
    }
    int solve3()//最好情况递减O(n),最坏情况递增O(2n) 
    {
    	int Max=a[1],Min=a[1];
    	t1=clock();
    	for(int i=2;i<=N;i++)
    	{
    		if(a[i]>Max)Max=a[i];
    		else if(a[i]<Min)Min=a[i];
    	}
    	t2=clock();
    	cout<<"Max="<<Max<<" Min="<<Min<<endl;
    	return t2-t1;
    }
    int main()
    {
    	mt19937 sui(time(0));
    	for(int i=1;i<=N;i++)a[i]=Rand(1,100000000);
    	cout<<"优化前="<<solve1()<<endl;
    	cout<<"优化后="<<solve2()<<endl;
    	cout<<"第三种="<<solve3()<<endl;
     }

三.多选题（5 题，每题 2 分）

假设用链表表示一个稀疏矩阵，则每个节点应包含哪些信息？（ABCD ）
A. 行号
B. 列号
C. 矩阵元素的具体值
D. 非零元素的数量
E. 零元素的数量
争议点在于是否选择D选项？

在一个字符编码问题中,如果一个文件只由 a, b, c 组成,它们出现的频率分别是 45, 13, 12, 以下哪些编码是最优的?(D ) A. a:000, b:010, c:101 B. a:000, b:010, c:100 C. a:00, b:01, c:10 D. a:1, b:01, c:00 大概是他选择最短的编码方案吧

请判断以下哪项描述是正确的？（AC）

4.考虑以下带权无向图，以下哪一个或哪些表述是正确的？（ BCE）

A. 该图表展示了四个不同的最小生成树实例
B. 至少存在一个包含边（6,8）的最小支撑树
C. 至少存在一个包含边（5,6）的最小支撑树
D. 每棵最小支撑树必定包括边（2,9）
E. 每个最小支撑树必然包括边（4,7）

使用符号 X \leq_p Y 来表示问题 X 可能在多项式时间内归约至问题 Y。假设 X 属于 P类别，并且 Y 同时属于 NP类别的前提下满足 X \leq_p Y 关系。以下哪一选项必然正确？（A）

据霍同学说是625页的这个(ಥ_ಥ)

四. Lists (25 points) 列表（25 分）

给定如下不含重复关键字的数组（数组的索引从 0 开始）：

（1）在如上所述的情况下，请计算在已存在的数组中插入一个新数据元素所需的时间平均值，并将其用 O(...)的形式表示出来。假设该数组当前已有 N 个数据元素，并且尚未满员。（5 分）

我觉得是O(\frac{N}{2})

（2）以两个数组的形式将给定的原始数据序列转换为单链表结构（要求必须严格遵循原始数据序列顺序），并在两组数组中相应地填写各节点的关键信息。（提示：其中一组数组用于存储各个节点的关键字信息，请使用"／"符号表示空指针位置；另一组则用于存储各节点所指的下一个节点的关键字位置）。

汪同学的答案，注意索引是从0开始滴：

请在以下两个链表中删除关键字K3，并展示删除后这两个链表的状态（不考虑被链表占用的空间）。 （5分）

同样是汪同学的答案：

（4）根据 (3)的结果，只给定了 K4 在关键字数组里的索引，要求把 K4 用O(1)时间复杂度从链表中删除，画出删除后的两个数组状态。（5 分）

这道题确实应该是这样的，因为题目说了要O(1)的复杂度，感谢群里的童鞋~

然后我才知道O(1)删除邻接表的边竟然是这么回事！以前一直没有想到过O(1)删除邻接表的边
（5）假设有五个关键字K1到K5呈降序排列：K1 > K2 > K3 > K4 > K5。我们需要构造一棵完全二叉树作为二叉搜索树的结构，并将该结构转换为数组形式，并画出该数组结构（总共有5个元素）。备注：这里的完全二叉树是指每一层（除最后一层外）都完全填充，并且最后一层从左到右填满某一部分。（5 分）
没听懂的同学大意是先构建这棵二叉搜索树再一层一层地填入数组中

五.Binary Trees (25 points) 二叉树（25 分）

请完成这棵二叉树的前序、中序、后序和广度优先遍历，并以节点序列的形式呈现出来。（9 分）

前序：3241675；中序：4261357；后序：4612573；广度优先：3274156。（2）已知一棵二叉树的先根遍历序列是1-3-2-7-6-5-4，中根遍历序列是1-2-3-4-5-6-7，请绘制该二叉树。（8分）

（3）一棵二叉树的后序遍历是 1,3,2,7,6,5,4，中序遍历是 1,2,3,4,5,6,7。请画出这棵树。（8 分）

六. Graph (25 points) 图（25 分）

给定如下带权有向图

（1）画出该图的邻接表表示

（2）画出该图的邻接矩阵表示

（3）画出该图的以 A 为出发节点的一棵广度优先树

（4）画出该图的以 A 为出发节点的最短路径树。

七.快速排序（25 分）

当我们采用快速排序算法对包含n个整数的数组E进行排序时，在其完成排序后使其按升序排列，并以比较次数作为评估其时间复杂度的标准依据。其中每次比较所需的时间均为常数时间内完成一次比较操作。（1）考虑一个基于划分策略的选择型快速排序算法，在每次递归调用中选择子数组左端点处的元素作为基准元进行划分操作。对于这种选择基准策略的情况，请找出其在所有可能输入中最差情况下的一种输入实例——即由集合{1,2,…,n}中的所有整数构成的一个特定排列序列E_0={e₁,e₂,…,e_n}——使得该版本快速排序算法在此特定输入下运行效率达到最低水平并求解该版本快速排序算法在这种最坏情况下的渐近时间复杂度并用符号O表示其渐近行为特征。（8分）

解：
在每一步中选择当前可排序元素中的最大值
定义：T(n)代表剩余待排序元素的数量
递归关系：当前步骤所需时间为前一次步骤的时间加上(n-1)个单位时间
展开计算：
依次类推可得 T(n)=T(1)+1+2+\cdots+(n-1)
计算结果：进一步化简得到 T(n)=\frac{n(n-1)}{2}=O(n^2)
因此，在最坏情况下时间复杂度为 O(n^2)

对于时间复杂度为O(nlogn)的算法分析而言，在网络上流传着这样的一个推导过程：
递归关系式为 T(n) = 2T\left(\frac{n}{2}\right) + n, 其中 T(n) 表示解决问题所需的时间与问题规模n之间的关系。
通过不断展开该递归关系式可以得到以下结果：

\begin{align*} T(n) &= 2\left(2 T\left(\frac{n}{4}\right) + \frac{n}{2}\right) + n \\ &= 4 T\left(\frac{n}{4}\right) + 2n \\ &= 4\left(2 T\left(\frac{n}{8}\right) + \frac{n}{4}\right) + 2n \\ &= 8 T\left(\frac{n}{8}\right) + 3n \\ & \vdots \end{align*}

同时规定当n=1时有 T(1)=0, 因此最终可得出时间复杂度为 O(nlogn) 的结论。

（2）基于递归的快速排序算法通常会对大量较小的子数组执行反复调用操作，在此过程中进一步降低了其时间效率。相比之下，在处理小型数据集时插值排序算法能够实现较高的执行速度。阐述一种改进方法以利用插值排序算法来解决上述问题：即当对每一个子数组进行处理时其长度不超过k个元素。经过推导可得改进后的快速排序算法平均时间复杂度为O(nk + n lg(n / k))。（9分）

解：
当数组长度缩减至k时，快速排序仅需进行\log(\frac{n}{k})次递归调用；每一次这样的递归操作所需时间为线性阶即为 O(n) 的时间复杂度。因此整个快速排序过程的时间复杂度为 n \cdot \log \left( \dfrac{n}{k} \right ) 。接着对每一个大小为 k 的数据块执行插入排序其时间复杂度为每个块 O(k^2) 所会有 \dfrac{ n }{ k } 块这样的数据块；总的时间复杂度则会达到 $ O( n k ) 。综上所述整个算法的时间复杂度即为：

O( n k + n \cdot \log \left( \dfrac{ n }{ k } \right ) )

（3）在本题的假设下,快速排序算法选择输入数组的第一个、最后一个以及中间位置三个元素中的中位数作为基准元素.我们需要证明在此假设下,使用快速排序算法对数组进行最坏情况下的排序时所需进行的元素间比较次数至多为\frac{n^2}{4}+O(n^2)次.