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

一、判断题

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

F

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

F

1-3n!是O(n^n)的。(2分)

T

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

F

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

F

二、选择题

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

14

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分)

4

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分)

1. c与a的最短路径长度就是13

2. c与a的最短路径长度就是7

3. c与a的最短路径长度不超过13

4. 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分)

11

2-13 令P代表入栈，O代表出栈。则将一个字符串3*a+b/c变为3a*bc/+的堆栈操作序列是哪个？（例如将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分)

4

 

二、程序填空题

 

图6

三、编程题

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

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

输入格式：

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

输出格式：

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

输入样例：

9

ABDFGHIEC

FDHGIBEAC

输出样例：

5

代码：

暂时不公布代码