中国大学数据结构_73课后答案(mooc完整答案)
67 min read中国大学数据结构_73课后答案(mooc完整答案)
1.2 什么是中国算法（3节共22:41）随堂测验
1、下列函数中，大学答案答案哪个函数具有最快的数据增长速度：
A、
B、结构
C、课后
D、完整
2、中国下面一段代码的大学答案答案时间复杂度是？if ( A > B ) { for ( i=0; i<N; i++ ) for ( j=N*N; j>i; j-- ) A += B; } else { for ( i=0; i<N*2; i++ ) for ( j=N*2; j>i; j-- ) A += B; }
A、
B、数据
C、结构
D、课后
第二讲 线性结构（2:19:00）[何钦铭]
2.1 线性表及其实现(6小节共45:04)随堂测验
1、完整对于线性表，中国在顺序存储结构和链式存储结构中查找第k个元素，大学答案答案其时间复杂性分别是数据多少？
A、都是O(1)
B、都是O(k)
C、O(1)和O(k)
D、O(k)和O(1)
2、在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是： for (___________ ) PtrL->Data[j-1]=PtrL->Data[j]; 其中空缺部分的内容应该是
A、j = i; j< = PtrL->Last; j++
B、j =PtrL->Last; j>= i; j--
C、j = i-1; j< = PtrL->Last; j++
D、j =PtrL->Last; j>= i-1; j--
3、下列函数试图求链式存储的线性表的表长，是否正确？ int Length ( List *PtrL ) { List *p = PtrL; int j = 0; while ( p ) { p++; j++; } return j; }
2.2 堆栈(4小节共39:51)随堂测验
1、借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：
A、2
B、3
C、4
D、5
2、设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：
A、3
B、n-2
C、n-3
D、任何元素均可能
3、若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？ （1）4->2->3 (2) 1->2->4
A、只能是（1）
B、只能是（2）
C、（1）和（2）都有可能
D、（1）和（2）都不可能
4、如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。
A、PPPOOPOPOO
B、POOPPPOPOO
C、POPPOPPOOO
D、PPOPPOOOPO
2.3 队列(2小节共15:45)随堂测验
1、在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：
A、f->next=s; f=s;
B、r->next=s; r=s;
C、s->next=r; r=s;
D、s->next=f; f=s;
2、现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？
A、4
B、5
C、6
D、7
第三讲 树(上) （1:50:08）[何钦铭]
3.1 树与树的表示(5小节共38:54)随堂测验
1、在分量1~11的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？
A、1
B、2
C、3
D、6
2、在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？
A、1
B、5
C、6
D、11
3、一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的总空间是n*(m+1) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（First Child/Next Sibling）表示法时，所需的总空间是：
A、3n
B、2n
C、n*m
D、n*(m-1)
3.2 二叉树及存储结构(2小节共16:43)随堂测验
1、如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？
A、31
B、39
C、63
D、71
2、若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？
A、25
B、50
C、不确定
D、这样的树不存在
3、设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1
3.3 二叉树的遍历(4小节共37:02)随堂测验
1、假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？
A、ABCD
B、ACDB
C、DCBA
D、DABC
2、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树________
A、是完全二叉树
B、所有结点都没有左儿子
C、所有结点都没有右儿子
D、这样的树不存在
3、已知一二叉树的后序和中序遍历的结果分别是FDEBGCA 和FDBEACG,那么该二叉树的前序遍历结果是什么？
A、ABDFECG
B、ABDEFCG
C、ABDFEGC
D、ABCDEFG
第四讲 树（中）（1:06:31）[何钦铭]
4.1 二叉搜索树(3小节共20:57)随堂测验
1、已知一棵由1、2、3、4、5、6、7共7个结点组成的二叉搜索树（查找树），其结构如图所示，问：根结点是什么？
A、1
B、4
C、5
D、不能确定
2、在上题的搜索树中删除结点1，那么删除后该搜索树的后序遍历结果是：
A、243765
B、432765
C、234567
D、765432
3、若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上
4、若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小值一定在叶结点上
4.2 平衡二叉树(2小节共22:53)随堂测验
1、将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树共有多少层？
A、2
B、3
C、4
D、5
2、若一AVL树的结点数是21，则该树的高度至多是多少？注：只有一个根节点的树高度为0
A、4
B、5
C、6
D、7
第五讲 树（下）（1:53:28）[何钦铭]
5.1 堆（4小节共30:05）随堂测验
1、下列序列中哪个是最小堆？
A、2, 55, 52, 72, 28, 98, 71
B、2, 28, 71, 72, 55, 98, 52
C、2, 28, 52, 72, 55, 98, 71
D、28, 2, 71, 72, 55, 98, 52
2、在最大堆 { 97,76,65,50,49,13,27}中插入83后，该最大堆为：
A、{ 97,76,65,83,49,13,27,50}
B、{ 97,83,65,76,49,13,27,50}
C、{ 97,83,65,76,50,13,27,49}
D、{ 97,83,65,76,49,50,13,27}
3、对由同样的n个整数构成的二叉搜索树（查找树）和最小堆，下面哪个说法是不正确的:
A、二叉搜索树（查找树）高度大于等于最小堆高度
B、对该二叉搜索树（查找树）进行中序遍历可得到从小到大的序列
C、从最小堆根节点到其任何叶结点的路径上的结点值构成从小到大的序列
D、对该最小堆进行按层序（level order）遍历可得到从小到大的序列
5.2 哈夫曼树与哈夫曼编码（3小节共19:52）随堂测验
1、如果哈夫曼树有67个结点，则可知叶结点总数为：
A、22
B、33
C、34
D、不确定
2、为五个使用频率不同的字符设计哈夫曼编码，下列方案中哪个不可能是哈夫曼编码？
A、00，100，101，110，111
B、000，001，01，10，11
C、0000，0001，001，01，1
D、000，001，010，011，1
3、一段文本中包含对象{ a,b,c,d,e}，其出现次数相应为{ 3,2,4,2,1}，则经过哈夫曼编码后，该文本所占总位数为：
A、12
B、27
C、36
D、其它都不是
5.3 集合及运算（2小节共12:57）随堂测验
1、已知a、b两个元素均是所在集合的根结点，且分别位于数组分量3和2位置上，其parent值分别为-3,-2。问：将这两个集合按集合大小合并后，a和b的parent值分别是多少？
A、-5，2
B、-5，3
C、-3，3
D、2，-2
第六讲 图（上）（1:29:32）[陈越]
6.1 什么是图（3小节共24:02）随堂测验
1、有个顶点的无向完全图有多少条边？
A、
B、
C、
D、
2、给定有向图的邻接矩阵如下： 顶点2（编号从0开始）的出度和入度分别是：
A、3, 1
B、1, 3
C、0, 2
D、2, 0
3、有向图的邻接矩阵一定是不对称的
4、用一维数组G[ ]存储有4个顶点的无向图如下： G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 } 则顶点2和顶点0之间是有边的。
6.1 什么是图（3小节共24:02）随堂测验
1、用邻接表表示有个顶点、条边的图，则遍历图中所有边的时间复杂度为：
A、
B、
C、
D、
6.2 图的遍历（4小节共22:22）随堂测验
1、已知一个图如下图所示，从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为
A、a,e,b,c,f,d
B、a,b,e,c,d,f
C、a,c,f,e,b,d
D、a,e,d,f,c,b
6.2 图的遍历（4小节共22:22）随堂测验
1、已知一个图如下图所示，从顶点a出发按广度优先搜索法进行遍历，则可能得到的一种顶点序列为
A、a,b,c,e,d,f
B、a,b,c,e,f,d
C、a,e,b,c,f,d
D、a,c,f,d,e,b
6.2 图的遍历（4小节共22:22）随堂测验
1、具有个顶点的无向图至多有多少个连通分量
A、0
B、1
C、
D、
2、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是
A、有回路的图
B、完全图
C、连通图
D、一棵树
3、具有个顶点的无向图至少有多少个连通分量
A、0
B、1
C、
D、
第八讲 图（下）（57:02）[陈越]
8.1 最小生成树问题（2小节共20:16）随堂测验
1、给定下图，其最小生成树的总权重是
A、21
B、30
C、34
D、35
2、连通图的最小生成树一定是唯一的
8.2 拓扑排序（2小节共27:57）随堂测验
1、拓扑序一定是唯一的。
8.2 拓扑排序（2小节共27:57）随堂测验
1、下图给定了一个项目的AOE。整个项目最早完工需要的时间是
A、17
B、19
C、20
D、23
2、在上图中，如果<0,2>组能加快进度，整个项目就能提前完工。
模拟
选择和填空
1、以下属于逻辑结构的是（ ）。
A、顺序表
B、哈希表
C、有序表
D、单链表
2、1. 一个栈的入栈序列是： a， b， c， d， e，则栈的不可能输出的序列是（） 。
A、a， b， c， d， e
B、e， d， c， b，a
C、d， c， e， a， b
D、d， e， c， b， a
3、从顶点 1 出发图的深度优先搜索序列。
4、有序表为 (11,22,33,44,55,66,77, 88,99), 则折半查找元素 35的比较序列
问答题
1、已知一组记录的关键字序列为 { 36， 55， 31， 28， 79， 66， 12， 07， 89}， 请写出进行冒泡排序的每一趟过程。
数据结构结课考试
选择、填空
1、下列数据结构中， 是非线性数据结构。
A、栈
B、队列
C、堆
D、完全二叉树
E、图
F、串
2、若一个算法中的语句频度之和为T(n)=3720n+4n2，则算法的时间复杂度为________
A、O(n)
B、O(n2)
C、O(nlogn)
D、O(logn)
3、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。
A、i
B、i+1
C、n-i
D、n-i+1
4、已知substr(s,i,len)函数的功能是返回串s中第i（i ≥ 1）个字符开始长度为len的子串，如substr("hello", 1, 2)结果是"he"。strlen(s)函数的功能是返回串s的长度。若s="ABCDEFGHIJK″, t="ABCD″,执行运算substr(s, strlen(t), strlen(t))后的返回值为____________。
A、"DEFG"
B、"ABCD"
C、"EFGH"
D、"HIJK"
5、一棵四层的完全二叉树具有的结点个数至少为 。
A、7
B、8
C、15
D、不确定
6、以下特点中链表不具有的是____________。
A、存储空间不必连续
B、删除操作不需要移动元素
C、不必事先估计存储空间
D、可随机访问任一元素
7、_______是限定仅在表尾进行插入和删除操作的线性表。
A、队列
B、栈
C、串
D、线性链表
8、引入二叉线索树的目的是 。
A、为了在二叉树中进行插入与删除
B、使二叉树的遍历结果唯一
C、为了能方便的找到双亲
D、加快查找结点的前驱或后继的速度
9、一个n个顶点的连通无向图，其边的个数至少为 。
A、n-1
B、n
C、n+1
D、nlogn
10、适用于折半查找的表的存储方式及元素排列要求为 。
A、链接方式存储，元素无序
B、顺序方式存储，元素无序
C、顺序方式存储，元素有序
D、链接方式存储，元素有序
11、利用二叉链表存储树，则结点的右指针是____________。
A、指向结点的第一个孩子
B、指向结点的第二个孩子
C、指向结点的兄弟
D、指向结点的双亲
12、下列排序算法中， 是稳定的。
A、堆排序
B、选择排序
C、快速排序
D、希尔排序
13、下列 的邻接矩阵是对称矩阵。
A、有向图
B、无向图
C、带权图
D、AOV网
14、分别以下列序列构造二叉排序树，与用其他3个序列所构造的结果不同的是 。
A、{ 100, 80, 90, 60, 120, 110, 130}
B、{ 100, 80, 60, 90, 120, 130, 110}
C、{ 100, 60, 80, 90, 120, 110, 130}
D、{ 100, 120, 110,130, 80, 60, 90}
15、对有18个元素的有序表R[1..18]进行二分查找，则查找A[3]的比较序列下标是 。
A、9, 4, 2, 3
B、9, 5, 2, 3
C、1, 2, 3
D、9, 5, 3
16、如果入栈序列是：a，b，c，d，e，则栈的不可能输出的序列是 。
A、a，b，c，d，e
B、e，d，c，b，a
C、d，e，c，b，a
D、d，c，e，a，b
17、空串与空格串 。
A、相同
B、不相同
C、可能相同
D、无法确定
18、对稀疏矩阵进行压缩存储，常用的两种方法是 。
A、二元组和散列表
B、三元组表和十字链表
C、三角矩阵和对角矩阵
D、对角矩阵和十字链表
19、以下排序方法中 不需要进行关键字的比较。
A、基数排序
B、希尔排序
C、快速排序
D、选择排序
20、将一棵树 T 转换为一棵二叉树 T2，则 T 的先序遍历是 T2 的 。
A、先序
B、中序
C、后序
D、无法确定
21、写出下图单链表中删除结点q并释放空间的有关语句。结点结构为：(data, next) 。
22、假设有循环队列Q，存放数据元素的队列长度为M，设Q.front指向队列中队头元素, Q.rear指向队尾元素的下一个位置，则 表示队为空，而 表示队满。
23、写出下图中二叉树的中序遍历序列。
24、写出下图的深度优先遍历序列。
综合题
1、题目要求见附件
数据结构是计算机科学中的一个重要学科，是研究数据组织，存储方式和操作方法的。中国大学中的数据结构课程，是计算机专业学生必修的一门课程，也是考研和就业中的重要考察内容之一。
课程目标
中国大学数据结构课程的目标，主要是让学生掌握以下几方面的知识：
- 基本的数据结构，如栈、队列、链表、树等
- 算法设计的基本思想和方法，如贪心、分治、动态规划等
- 各种常见算法的时间、空间复杂度等性质
- 实际问题中如何运用数据结构和算法进行解决
课程内容
中国大学数据结构课程的内容，一般包括以下几个方面：
- 线性结构:包括数组、链表、队列、栈等
- 树形结构: 包括二叉树、B树、AVL树、哈夫曼树等
- 图形结构: 包括基本概念、遍历算法、最短路径算法、最小生成树算法等
- 排序算法: 包括冒泡排序、插入排序、选择排序、快速排序、归并排序、基数排序等
- 查找算法: 包括顺序查找、二分查找、哈希查找等
教学方法
中国大学数据结构课程的教学方法，一般包括以下几种：
- 讲授和示范。教师会在课堂上进行讲解，同时通过示例程序来演示数据结构和算法的使用方法。
- 实验教学。学生需要通过上机实践的方式，掌握数据结构和算法的设计和实现。
- 课外阅读。学生需要通过阅读相关书籍和论文，加深对数据结构和算法的理解。
教材推荐
中国大学数据结构课程中，常用的教材有以下几种：
- 《数据结构(C语言版)》 严蔚敏/吴伟民
- 《算法与数据结构》 郑纬民
- 《数据结构习题解析》 郑纬民
- 《数据结构与算法分析》 Mark Allen Weiss
考试形式
中国大学数据结构课程的考试形式，一般包括以下几种：
- 笔试 / 机试。学生需要在规定的时间内完成一定数量的数据结构和算法的题目。
- 实验报告。学生需要完成一定的实验题目，并撰写实验报告。
- 学期论文。学生需要完成一篇数据结构和算法相关的论文，并进行答辩。
总结
中国大学数据结构课程是计算机专业学生必修的一门课程，也是考研和就业中的重要考察内容之一。通过学习本课程，学生可以掌握基本的数据结构和算法设计思想，为日后的学习和工作打下坚实的基础。
