第一章 绪论（总时长：56分26秒，共6讲）

第1讲 数据结构的基础概念（总时长12分钟）随堂测验

2、抽象数据类型具有 、信息隐蔽的特点。

第2讲 数据结构的内容（总时长5分29秒）随堂测验

1、线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ）

2、1、数据结构的逻辑结构分为集合、线性、层次和 四种。

3、2、数据结构的存储结构分为 和非顺序 两种。

4、3、在线性结构、树形结构和图结构中，数据元素之间分别存在着一对一、一对多和 联系。

第3讲 数据结构与c语言表示（总时长7分32秒）随堂测验

第4讲 算法性能评价（总时长8分06秒）随堂测验

第5讲 算法与算法的描述（总时长14分59秒）随堂测验

MOOC第一章单元测试题

20、具有线性结构的数据元素只能顺序存储，非线性结构的元素只能非顺序存储。

22、算法的优劣与算法描述的语言无关。

23、算法的可行性是指每一条指令具有明确含义。

24、健壮的算法不会因为非法输入而出现莫名的执行结果。

25、高效率和低存储是衡量一个算法的唯一标准。

26、数据类型就是一组性质相同的值的集合和在该集合上的一组操作的总称。

27、数据元素的存储结构分为顺序存储和非顺序存储。

28、数据元素的顺序存储优于非顺序存储。

29、一个数据结构在存储时，只需要存储数据元素即可。

第二章 线性表（一）（总时长：72分22秒，共6讲）

第1讲 线性表的概念（总时长9分20秒）随堂测验

3、线性表的特点是每个元素都有一个前驱和一个后继。（）

第2讲 线性表的顺序存储（总时长13分）随堂测验

第3讲 线性表顺序结构应用示例及小结（总时长7分57秒）随堂测验

2、线性表的顺序存储是指将表中元素按照从大到小或从小到大存储。

第4讲 线性表的链式存储（总时长10分20秒）随堂测验

2、单链表中必须设有头结点。（）

第5讲 单链表的基本运算（总时长20分58秒）随堂测验

第6讲 单链表运算的应用示例及小结（总时长10分47秒）随堂测验

2、对链表进行插入和删除操作时不必移动链表中结点。( )

3、在单链表中，可以从头结点出发，查找到表中所有结点。（ ）

第二章 第一次单元测验

11、单链表中增加头结点的目的是存储链表的长度。

12、静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

13、线性表在链式存储时，查找第i个元素的时间同i的值无关。

14、线性表在顺序存储时，查找第i个元素的时间同i 的值成正比。

15、线性表的特点是每个元素都有一个前驱和一个后继。

16、线性表的链式存储结构优于顺序存储。

17、顺序存储方式的优点是存储密度大，插入、删除效率高。

18、顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。

19、插入和删除操作是线性表的基本操作。这两种操作在数组中也经常使用。

20、在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。

21、在线性表的链式存储结构中，逻辑上相邻的两个元素在物理存储上并不一定相邻。

22、线性表采用顺序存储，必须占用一段地址连续的存储单元。

23、顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。

24、若某线性表经常做插入、删除操作，易采用 结构存储。【请填 顺序 或 链式】

第二章 线性表（二）（总时长：59分37秒）

第7讲 循环链表（总时长7分05秒）随堂测验

2、在单向循环链表中，从表中任意结点出发都可以顺着next域访问到表中所有元素（）

第8讲 双向链表（总时长7分47秒）随堂测验

2、在双向链表L中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）

第9讲 静态链表（总时长6分24秒）随堂测验

1、静态链表中与动态链表的插入和删除运算类似，不需要做元素的移动。（）

2、静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中第ｉ个元素的时间与位置序号ｉ无关，可以实现随机存取。（）

第10讲 链式结构小结（总时长7分32）随堂测验

4、在双向循环链表中，可以从任一结点p出发沿同一方向的指针域查找到表中所有元素。（）

第12讲 顺序表与链表的综合比较（总时长6分08秒）随堂测验

3、下面关于线性表的叙述错误的是（ ）。

总结与提高（总时长15分15秒）随堂测验

3、线性表的顺序存储优于链式存储结构。（）

4、在带头结点的非空单链表中，头结点的存储位置由 指示

第二章 第二次单元测试

6、静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

7、循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。

8、静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

9、静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

10、线性表在顺序存储时，查找第i个元素的时间同i的值无关。

11、线性表在顺序存储时，删除第i个元素的时间同i的值无关。

12、静态链表因为采用的是一段连续的空间来存储元素，因此查找第i个元素的时间和i无关。

13、在带头指针的长度为n的双向循环链表的末尾插入一个元素，其时间复杂度为O( )。（填写阿拉伯数字或字母）

15、在某双向链表中删除一个结点，需要改动 个指针域（填写阿拉伯数字）

第三章 栈与队列（一）（总时长53分23秒）

第1讲 栈的定义与实现（总时长6分59秒）随堂测验

3、栈是线性结构，是操作受限制的线性表。（）

第2讲 栈的顺序结构（总时长10分54秒）随堂测验

第3讲 顺序栈的两栈共享（总时长13分19秒）随堂测验

3、已知一个双端栈的地址为dS，则该双端栈不空时，1号栈（高端栈）出栈操作的语句是*x= dS->stack[dS->top[1]--]（）

第4讲 栈的链式实现（总时长8分01秒）随堂测验

第5讲 栈的应用（总时长8分34秒）随堂测验

3、在括号匹配算法中，当正扫描的符号是左括号时，则该做左括号（ ）。

第6讲 栈与递归（上）（总时长10分43秒）随堂测验

2、从被调用函数返回调用函数之前，递归退层（i←i +1层）系统也应完成三件工作是（ ）
    D、依照被调函数保存的返回地址，将控制转移回调用函数。

3、递归是指在定义自身的同时又出现了对自身的引用。（ ）

4、系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个（ ）。

14、消除递归肯定要用到栈，否则无法完成。

15、若输入序列为1234,则通过一个栈可以得到输出序列3124。

16、若输入序列为1234,则通过栈只能得到4321的输出序列。

17、有些问题，比如汉诺塔问题等，只能用递归来解，无法转换成非递归算法。

18、顺序栈因为是顺序存储，所以可以随机存取栈中任意元素。

19、两顺序栈共享空间，也存在空间溢出问题。

20、栈与队列是一种特殊操作的线性表。

21、栈和队列都是限制插入和删除位置的线性结构。

22、函数或过程调用需要用到栈。

23、栈中将允许操作的一端称作 。

24、栈中将不允许操作的一端称作 。

25、凡是对元素的保存次序与使用顺序相反的，都可以使用 。

26、若栈采用单链表结构实现，则链表的头指针的位置，表示的是栈的 。（请填栈顶或栈底）

28、123按顺序进栈，如果进栈出栈操作可以交替，则不可能得到的出栈序列是 。(数字中间不要加空格)

第三章 栈与队列（二）（总时长：52分54秒）

第7讲 栈与递归（下）（总时长：8分40秒）随堂测验

第8讲 队列的定义与实现（总时长：13分32秒）随堂测验

3、队列操作的特性是LIFO。（）

4、队列允许做插入的一端称为队头，允许删除的一端称为队尾（ ）

第9讲 序列的顺序存储（循环队列）（总时长：11分08秒）随堂测验

第10讲 队列的应用（总时长：7分08秒）随堂测验

1、在打印杨辉三角形前N行的算法中，需要申请一个N*N的二维数组存放杨辉三角形N行数据。（）

第五章 数组与广义表（上）（总时长：38分01秒）

第1讲 数组的定义与顺序存储（总时长：19分57秒）随堂测验

1、数组的维数和维度一旦确定，数组中元素的个数就确定了，不能增加不能减少。（ ）

2、数组的维数n决定了数组中的元素受n个线性关系的约束。（ ）

3、数组如同一般的线性表，可以做的基本运算包括存取指定位置的元素，插入，删除等。( )

4、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000，数组A共占用 字节;

5、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1000 ,计算数组A的最后一个元素的地址是 。

6、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1 000 ,计算按行存储时元素A36的地址是 ;

7、假设有6行8列的二维数组A(下标从1开始),每个元素占用6个字节,存储器按字节编址。已知A的基地址为1 000 ,计算按列存储时元素A36的地址是 。

第2讲 规律分布特殊矩阵的压缩存储（总时长：18分04秒）随堂测验

3、所谓的n阶下三角矩阵A是指当i<j时（i为元素的行标，j 为元素的列标）元素aij为0或常数C .( )

4、所谓的n阶（n>3）三对角矩阵（带状矩阵）是指非零元素只出现在矩阵的两条对角线上。（ ）

第五章 数组与广义表（下）（总时长：57分05秒）

第3讲 稀疏矩阵的压缩存储（上）（总时长：17分54秒）随堂测验

第4讲 稀疏矩阵的压缩存储（下）（总时长：19分16秒）随堂测验

1、对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（ ）个头指针。

2、对于一个m行n列的稀疏矩阵中有len个非零元素，则用十字链表存储时，需要（ ）个三元组结点。

第5讲 广义表及本章小结（总时长：19分55秒）随堂测验

1、任意一个广义表都可以表示为由表头和表尾构成（ ）。

2、非空的广义表的表尾可能是单个元素也可能是表元素（ ）。

第六章 树和二叉树（上）（总时长：48分02秒）

第1讲 树的基本概念（总时长：17分07秒）随堂测验

2、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 则该树的度为（ ）；

3、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 该树的深度为（ ）；

4、若一棵树的广义表法表示为：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 该树中叶子结点的个数为：（ ）

第2讲 二叉树（总时长：18分04秒）随堂测验

4、二叉树就是结点度不大于2的树。（）

5、不存在这样的二叉树：它有n个度为0的结点，n-1个度为1的结点，n-2个度为2的结点。（ ）

6、具有n个结点的二叉树采用二叉链表存储结构，共有（ ）非空的指针域。

7、拥有100个结点的完全二叉树的最大层数是（ ）

第3讲 二叉树的遍历（总时长：12分51秒）随堂测验

3、已知二叉树的先序和后序遍历序列可以唯一确定该二叉树。（ ）

6、完全二叉树一定存在度为1的结点。

7、完全二叉树中，若一个结点没有左孩子，则它必是叶子。

8、二叉树只能用二叉链表表示。

9、树形结构中，每个元素都有一个前驱，0个或多个后继。

10、由3 个结点可以构造出 种形态不同的无序树。

11、由3 个结点可以构造出 种形态不同的二叉树。

12、对任意一棵有n个结点的树，这n个结点的度之和为 。

13、高度为7的完全二叉树，最少有 个结点。

第六章 树和二叉树（下）（总时长：112分28秒）

第4讲 遍历算法应用（总时长：19分50秒）随堂测验

第5讲 基于栈的递归消除（总时长：14分27秒）随堂测验

第6讲 线索二叉树（总时长：17分35秒）随堂测验

第7讲 由遍历序列确定的二叉树（总时长：7分48秒）随堂测验

第8讲 树、森林和二叉树的关系（总时长：17分33秒）随堂测验

2、与树等价的二叉树，根没有（ ）子树。

第9讲 哈夫曼树及其应用——哈夫曼树（总时长：12分46秒）随堂测验

2、在哈夫曼树中，权值相同的叶子点一定在同一层上。（ ）

3、在哈夫曼树中，权值较大的叶子点一般离根比较近。（ ）

4、若以{4,5,6,7,8}作为叶子点构造哈夫曼树，则其带全路径长度为（ ）

第10讲 哈夫曼树及其应用——哈夫曼编码（总时长：14分35秒）随堂测验

1、在哈夫曼编码中，当两个字符出现的频率相等时，则两个字符的哈夫曼编码也相同。（ ）

8、哈夫曼树的带权路径长度等于其中所有结点的带权路径之和。

9、给定二叉树的先序、中序和后序遍历序列中的两个，就可以唯一确定一棵二叉树。

10、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是哈夫曼树。

11、将一棵树转成二叉树，根结点一定没有右子树。

12、一棵哈夫曼树中不存在度为1的结点。

13、在叶子数目和权值相同的所有二叉树中，带权路径长度最小的树一定是完全二叉树。

14、先序线索二叉树中，某结点的后继一定在左子树上。

15、有10个叶子结点的哈夫曼树，总结点个数是 。

16、将一棵树转换为二叉树时，遵循的规则是左孩子、 。

17、用权值{1,2,3,4,5}构造一棵哈夫曼树，则该树的带权路径长度为 。

18、假设T是一棵高度为5的二叉树,T中只有度为0和度为2的结点，那么T树最少应该有 个结点。

19、树的后根遍历，相当于对应二叉树的 遍历。

20、含有100个结点的树有 条边。

第七章 图（总时长：102分26秒）

第1讲 图的基本概念（总时长：12分20秒）随堂测验

3、在一个无向图中，所有顶点的度之和等于边条数的 倍。

4、具有6个顶点的无向图至少应有 条边才能确保是一个连通图。

5、一个有向图G中所有顶点的入度之和是所有顶点出度之和的 倍。

第2讲 图的存储结构（总时长：12分28秒）随堂测验

2、有向图的邻接矩阵一定是对称矩阵。（）

3、用邻接矩阵存储无向图G时，其第i行中1的个数与第i列中1的个数相等。（）

4、对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则表头结点数组的大小为 。

5、对于一个有n个顶点，e条边的无向图，若采用邻接表表示，则边结点有 个。

6、用邻接矩阵存储有向图G时，其第i列的所有元素之和等于该顶点的 。

第3讲 图的遍历（总时长：17分05秒）随堂测验

第4讲 图的连通性（总时长：11分36秒）随堂测验

3、对于n个顶点的连通图G来说，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。（ ）

4、对于n个顶点的连通图而言，它的生成树一定有 条边。

第5讲 有向无环图应用——拓扑排序（总时长：12分37秒）随堂测验

2、任何有向无环图的顶点都可以排成拓扑排序序列，且拓扑排序序列唯一（ ）

3、在ＡＯＶ网中，顶点表示 。

第6讲 有向无环图应用——关键路径（总时长：15分21秒）随堂测验

2、关键活动若不能按期完成就会影响整个工程的完成时间，若某些关键活动能提前完成，将可能使整个工程提前完成。（）

3、在ＡＯE网中，关键路径上的活动称为 。

第7讲 最短路径（总时长：16分28秒）随堂测验

2、求最短路径的Dijkstra算法不适用于有回路的有向网（ ）

7、以下说法错误的是( )。
    A、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
    B、邻接表只能用于有向图的存储，而邻接矩阵对于有向图和无向图的存储都适用。
    C、存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（或上）三角部分就可以了
    D、用邻接矩阵M表示图，判定任意两个结点Vi和Vj之间是否有长度为n的路径相连，则只要检查M的n次方后，第 i行第j列的元素是否为0即可。

11、关键路径上的活动都是关键活动，它们是否按时完成会影响工期。

12、求稀疏图的最小生成树，用克鲁斯卡尔算法来求解较好。

13、求稠密图的最小生成树，用普里姆算法来求解较好。

14、迪杰斯特拉算法求最短路径时，是按照路径长度递增的顺序求解的。

15、一个有向图的拓扑排序只有一个。

16、每一个有向图肯定至少有一个拓扑排序。

17、具有6个顶点的无向图至少应有6条边才能确保是一个连通图。

18、非关键活动，可以无限期延迟。

19、图的存储结构主要有邻接矩阵和________两种。

20、对具有n个顶点的图其生成树有且仅有________条边。

21、在有向图的邻接矩阵上，第i行中的非零且非无穷元素个数是第i个结点的 。

22、如果n个顶点的图是一个环，则它有 棵生成树。

23、关键路径是从源点到汇点的 路径。

24、稠密图采用 存储较省空间

25、稀疏图采用 存储较省空间。

第八章 查找（总时长：73分53秒）

第1讲 查找的基本概念（总时长：10分31秒）随堂测验

3、顺序查找方法只能在顺序存储结构上进行。（ ）

4、顺序查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次。

5、顺序查找含n个元素的顺序表，若查找不成功，则比较关键字的次数为 次。

第2讲 基于线性表的查找法（总时长：10分44秒）随堂测验

2、当采用分块查找时，数据的组织方式要求 。
    B、数据分成若干块，每块内元素不必有序，但块间必须有序，且每块内最大（或最小）的数据组成索引块；
    D、数据分成若干块，每块（除最后一块外）中元素个数相等。

4、折半查找可以在有序的双向链表上进行。（ ）

第3讲 树表式查找方法——二叉排序树（总时长：12分08秒）随堂测验

3、查找效率最高的二叉排序树是平衡二叉排序树。（ ）

4、在二叉排序树中新插入的结点总是作为叶子结点来插入的。（ ）

5、在二叉排序树中新插入的结点总是处于最底层。（ ）

6、每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。（ ）

第4讲 计算式查找法——哈希表的构造（总时长：16分27秒）随堂测验

第5讲 哈希法的性能分析（总时长：9分02秒）随堂测验

第九章 内部排序（总时长：97分05秒）

第2讲 插入类排序（总时长：14分05秒）随堂测验

第3讲 交换类排序（总时长：12分01秒）随堂测验

4、在直接插入排序、希尔排序、简单选择排序、快速排序、堆排序和归并排序中，平均比较次数最少的排序方法是

第4讲 选择类排序（1）（总时长：9分16秒）随堂测验

3、10个元素进行简单选择排序，需要做 趟排序才能得到有序序列。

第5讲 选择类排序（2）——堆排序（总时长：19分01秒）随堂测验

4、对于待排序的数据元素集{12,13,23,18,60,15,7,20,52,100}，用筛选法建初堆时，必须从值为 的关键字开始。

第6讲 归并排序（总时长：7分20秒）随堂测验

第7讲 分配类排序（总时长：12分56秒）随堂测验

16、内部排序要求数据元素全部在内存完成排序，且顺序存储。

17、所有的排序算法的比较次数与初始序列无关。

18、所有排序算法中，快速排序的时间复杂度和空间复杂度都最小。

19、快速排序的最坏情况，可以通过适当选择中轴元素避免。

20、排序的稳定性是指，关键字相同的记录，排序前后其领先关系不发生改变。

21、冒泡排序在最好情况下的时间复杂度是O(n)。

22、简单选择排序和堆排序性能不受初始序列顺序的影响。

23、直接插入排序、简单选择排序、冒泡排序和快速排序中，其时间复杂度为O（n*n），关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是 。

24、希尔排序法、快速排序法、堆排序法和二路归并排序法四种排序法中，要求辅助空间最多的是 。

25、快速排序、归并排序、堆排序、基数排序中，适合记录个数很大，但待排序关键字位数很少的排序算法是 。

26、对关键字集合{46，79，56，33，40，90}按冒泡排序，则一趟排序后的结果为 。（请只用一个空格隔开各关键字，不必加大括号）

2.一个含有x,y的五次单项式,x的指数是3,且当x=2,y=-1时,这个单项式的值是40,求这个单项式.

共回答了13个问题采纳率：92.3%