中国大学MOOC-陈越、何钦铭-数据结构-2018春期末考试 – 小奥の部落格

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

一、判断题

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

F

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

F

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

T

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

F

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

F

二、选择题

2-1 对一组数据{2121688510}进行排序,若前三趟排序结果如下:第一趟排序结果:2121651088第二趟排序结果:2125101688第三趟排序结果:2510121688则采用的排序方法可能是:(2)

冒泡排序

 

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

1.jpg 

1

14

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

最短路径

2-4 给定二叉树如下图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3175624,则其遍历方式是:(2)

2.jpg 

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对于序列{4938659776132750},按由小到大进行排序,下面哪一个是初始步长为4的希尔排序法第一趟的结果?(4)

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

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

  1. ca的最短路径长度就是13

  2. ca的最短路径长度就是7

  3. ca的最短路径长度不超过13

  4. ca的最短路径不小于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.jpg

3

a,b,e,c,d,f

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

rear->next=s;rear=s;

2-12 设散列表的地址区间为[0,16],散列函数为H(Key)=Key%17。采用线性探测法处理冲突,并将关键字序列{2625723881859}依次存储到散列表中。元素59存放在散列表中的地址是:(4)

11

2-13 P代表入栈,O代表出栈。则将一个字符串3*a+b/c变为3a*bc/+的堆栈操作序列是哪个?(例如将ABC变成BCA的操作序列是PPOPOO。)(4)

POPPOOPPOPPOOO

2-14要判断一个整数N>10)是否素数,我们需要检查3N之间是否存在奇数可以整除N。则这个算法的时间复杂度是:(2)

O(根号N)

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

4.jpg 

4

413256

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

5是根结点

2-17 对给定序列{1101197911114120122}采用次位优先(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.jpg 

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),那么将元素68所在的集合合并(要求必须将小集合并到大集合)后,该集合对应的树根和父结点编号值分别是多少?(4)

4-5

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

4

 

二、程序填空题

 1527149270110276.jpg

图6

三、编程题

7-1 还原二叉树(8 分)

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

输入格式:

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

输出格式:

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

输入样例:

9

ABDFGHIEC

FDHGIBEAC

输出样例:

5

代码:

暂时不公布代码

You May Also Like

About the Author: 小奥

不忘初心,奋力前行!

1 Comment

发表评论

电子邮件地址不会被公开。

This site uses Akismet to reduce spam. Learn how your comment data is processed.