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

一、判断题

1-1若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。(2分)

1-2对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。(2分)

1-3_n_!是_O_(_n^n_)的。(2分)

1-4对一棵平衡二叉树，所有非叶结点的平衡因子都是0，当且仅当该树是完全二叉树。(2分)

1-5无向连通图至少有一个顶点的度为1。(2分)

二、选择题

2-1 对一组数据{2，12，16，88，5，10}进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88第二趟排序结果：2，12，5，10，16，88第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是：(2分)

冒泡排序

2-2 给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：(4分)

图1

2-3 数据结构中Dijkstra算法用来解决哪个问题？(2分)

最短路径

2-4 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是：(2分)

图2

RNL

2-5 设栈S和队列Q的初始状态均为空，元素{1,2,3,4,5,6,7}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是{2,5,6,4,7,3,1}，则栈S的容量至少是：(2分)

2-6对于序列{49，38，65，97，76，13，27，50}，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？(4分)

49,13,27,50,76,38,65,97

2-7在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？(4分)

c与a的最短路径长度就是13
c与a的最短路径长度就是7
c与a的最短路径长度不超过13
c与a的最短路径不小于7

2句

2-8 在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？(2分)

有可能会不同

2-9 设最小堆（小根堆）的层序遍历结果为{5,18,15,28,22,42,40}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：(4分)

A. 18,28,22,42,15,40,5

2-10 在图中自a点开始进行广度优先遍历算法可能得到的结果为：(2分)

图3

a,b,e,c,d,f

2-11 在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（）。(2分)

rear->next=s;rear=s;

2-12 设散列表的地址区间为[0,16]，散列函数为_H_(_Key_)=_Key_%17。采用线性探测法处理冲突，并将关键字序列{26，25，72，38，8，18，59}依次存储到散列表中。元素59存放在散列表中的地址是：(4分)

2-13 令P代表入栈，O代表出栈。则将一个字符串3a+b/c变为3abc/+的堆栈操作序列是哪个？（例如将ABC变成BCA的操作序列是PPOPOO。）(4分)

POPPOOPPOPPOOO

2-14要判断一个整数_N_（>10）是否素数，我们需要检查3到√_N_之间是否存在奇数可以整除_N_。则这个算法的时间复杂度是：(2分)

O(根号N)

2-15 将1~6这6个键值插到一棵初始为空的二叉搜索树中。如果插入完成后，搜索树结构如图所示，问：可能的插入序列是什么？(2分)

图4

413256

2-16 将9,8,7,2,3,5,6,4顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？(4分)

5是根结点

2-17 对给定序列{110，119，7，911，114，120，122}采用次位优先（LSD）的基数排序，则两趟收集后的结果为：(2分)

7,110,911,114,119,120,122

2-18 给定输入序列{4371,1323,6173,4199,4344,9679,1989}以及散列函数_h_(_X_)=_X_%10。如果用大小为10的散列表，并且用分离链接法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）(4分)

1,3,3,9,4,9,9

2-19

在图中自d点开始进行深度优先遍历算法可能得到的结果为：(2分)

图5

d,e,a,c,f,b

2-20 哈夫曼树是n个带权叶子结点构成的所有二叉树中（带权路径长度）最小的二叉树。(2分)

2-21 在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{1,-4,1,1,-3,4,4,8,-2}（注：−_n_表示树根且对应集合大小为_n_），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？(4分)

4和-5

2-22 将10,12,1,14,6,5,8,15,3,9,7逐个按顺序插入到初始为空的最小堆中，然后连续执行两次删除最小元素操作（DeleteMin），再插入4，16，此后堆顶的元素是什么？(4分)

二、程序填空题

图6

三、编程题

7-1 还原二叉树（8 分）

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

输入格式：

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

输出格式：

输出为一个整数，即该二叉树的高度。

输入样例：

ABDFGHIEC

FDHGIBEAC

输出样例：

代码：

暂时不公布代码