小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Computer & DL
  4. Data Structure
  5. 正文

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

2018年5月24日 6523点热度 0人点赞 1条评论

一、判断题

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.jpg 

图1

14

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

最短路径

2-4 给定二叉树如下图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4,则其遍历方式是:(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对于序列{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.jpg

图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.jpg 

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

4和-5

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

4

 

二、程序填空题

 1527149270110276.jpg

图6

三、编程题

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

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

输入格式:

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

输出格式:

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

输入样例:

9

ABDFGHIEC

FDHGIBEAC

输出样例:

5

代码:

暂时不公布代码

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2018年5月24日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

  • 小奥

    答案解析待更新,敬请期待~

    2018年5月24日
    回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    搜索
    欢迎关注我的个人公众号
    最新 热点 随机
    最新 热点 随机
    DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
    奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
    Waterx 1.0 For WordPress发布! Python chapter 6 learning notes C++面向对象程序设计课程笔记(第九周)(上) TIOBE Index for March 2015[TOP 20] 计算机组成原理笔记第七章(7.3) 志愿高校团体掠影
    标签聚合
    Java 生活 Python linux 高中 鸟哥的linux私房菜 学习 python学习 算法 leetcode
    最近评论
    davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
    tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
    cuicui 发布于 9 个月前(10月20日) :wink:
    niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
    davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
    Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
    davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
    aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
    匿名 发布于 5 年前(12月30日) 烫
    小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

    COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang

    陕ICP备19003234号-1

    鲁公网安备37120202000100号