mooc数据结构_14章节答案(mooc完整答案)

mooc数据结构_14章节答案(mooc完整答案)

点击查看答案

第一讲 基本概念（1:15:26）[陈越]

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