《数据结构》期末考试测试题【上】

数据结构测试题

• • 1.数据结构是指什么？
  • 2.某语句时间复杂为？
  • 3.关于数据结构的说法那个正确？
  • 4.一个算法的评价标准包括哪些方面?
  • 5.时间复杂度指的是什么？
  • 6.算法的重要特征有那些？
  • 7.某语句时间复杂为？
  • 8.存储数据时要存储什么？
  • 9.某语句时间复杂为？
  • 10.某语句时间复杂为？
  • 11.某二叉树的遍历序列为？
  • 12.某线索二叉树的线索数为？
  • 13.有向图顶点的入度与出度的关系为？
  • 14. 由邻接矩阵进行深度优先遍历的结果为？
  • 15.关于图的深度优先搜索描述正确的为？
  • 16.构造无向连通图的最小生成树的算法？
  • 17.拓扑排序适用于哪类图？
  • 18.关于图的遍历算法描述正确的为？
  • 19.邻接矩阵与邻接表的适用情况为？
  • 20.关于哈夫曼树的描述不正确的为？

1.数据结构是指什么？

数据结构 ：相互之间存在一种或多种特定关系的数据元素的集合。

• 换句话说，数据结构是带“结构”的数据元素的集合，
  • “结构”就是指数据元素之间存在的关系。
• 因此，数据结构是指数据元素的组织形式。

2.某语句时间复杂为？

算法的时间复杂度 ：衡量算法执行时间随输入规模增长的增长率。

• 它用大O符号(O)来表示，表示最差情况下的运行时间。

对于给定的语句执行频度 ( 3 n + n l o g 2 n + n 2 + 8 ) (3n+nlog_2{n}+n^2+8) (3n+nlog2​n+n2+8)我们可以根据增长趋势判断其时间复杂度。

• 当n趋向无穷大时，其中的线性项 3 n 3n 3n和对数项 n l o g 2 n nlog_2{n} nlog2​n都会被抛弃。
• 而平方项 n 2 n^2 n2会主导增长。

因此，该算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

答案【C】

3.关于数据结构的说法那个正确？

数据结构 ：指数据的存储、组织和管理的方式，是为了满足特定的操作需求而设计和实现的。

逻辑结构 ：指数据元素之间的关系，主要分为线性结构和非线性结构两种。

• 线性结构包括：线性表、栈、队列等。
• 非线性结构包括：树、图等。

存储结构 ：指数据元素在内存中的存储表示方式，主要分为顺序存储和链式存储两种。

• 顺序存储是将数据元素连续地存储在一块连续的存储空间中，
• 链式存储是通过指针来连接数据元素。

线性结构 ：一种由有限个数据元素组成的结构。

线性结构具有四个基本特征：

1. 必须存在唯一的一个开始元素。
2. 必须存在唯一的一个终端元素。
3. 除开始元素外，其他数据元素均有唯一的前驱元素。
4. 除终端元素外，其他数据元素均有唯一的后继元素。

非线性结构 ：不符合线性结构特征的数据结构。

顺序存储 ：

• 在计算机存储器中用一片地址连续的存储单元依次存放数据元素。

链式存储 ：

• 在计算机存储器中用任意地址的存储单元存放数据元素。

• 数据元素之间的逻辑关系以指针连接的方式实现。

A选项： 数据结构的逻辑结构独立于其存储结构。

解析： 逻辑结构是描述数据元素之间的关系，

而存储结构是描述数据元素在内存中的存储方式，

二者是相对独立的。

B选项： 数据结构的存储结构独立于该数据结构的逻辑结构。

C选项： 数据结构的逻辑结构唯一地决定了该数据结构的存储结构。

解析： 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构，B、C 错误。

D选项： 逻辑结构和存储结构均相同的数据结构一定为同一数据结构。

数据结构包括逻辑结构、存储结构和运算三个要素。

当逻辑结构和存储结构相同而运算不同时，可能不是同一数据结构。

• 比如：栈和队列逻辑结构和存储结构可以相同，由于运算的不同，而属于两种不同的数据结构。

答案【A】

4.一个算法的评价标准包括哪些方面?

正确性 ：指算法是否能够按照设计的要求正确地解决问题。

可读性 ：指算法的代码是否易于理解和维护。

健壮性 ：算法是否能够处理异常情况或非法输入。

可扩展性 ：指算法是否能够处理更大规模的数据或更复杂的问题。

时间复杂度 ：指算法执行所需的时间与输入规模之间的关系。

空间复杂度 ：指算法执行所需的内存空间与输入规模之间的关系。

5.时间复杂度指的是什么？

算法中基本语句重复执行的次数是问题规模 n n n的某个函数 f ( n ) f(n) f(n)

算法的时间量度记作 T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))

表示随问题规模n的增大，算法执行时间的增长率和 f ( n ) f(n) f(n)的增长率相同称作算法的时间复杂度
这里所谓的”基本语句“指的是算法中重复执行次数和算法的执行时间成正比的语句，它对算法运行时间的贡献最大。

---

本题中算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

表明该算法中基本语句重复执行的次数即算法的执行时间与 n 2 n^2 n2成正比。

答案【C】

6.算法的重要特征有那些？

算法的五个重要特性：

有穷性 ：指一个算法必须在执行有限个操作步骤后终止。

确定性 ：算法中的每一步骤都必须有确切的定义，不能有二义性。

可行性 ：算法中的每一步操作都必须是可以通过已经实现的基本运算执行有限次来实现的。

输入 ：指一个算法可以有零个或多个输入。

输出 ：指一个算法必须有一个或多个输出。

B选项： 可读性是指算法的代码或描述易于理解和阅读。虽然可读性对于编写和维护代码很重要，但它并不是算法的基本特性之一。

C选项： 正确性是指算法能够正确地解决问题，输出预期的结果。虽然正确性是算法的一个重要目标，但它并不是算法的基本特性之一。

D选项： 稳定性通常用于描述算法在处理相同输入时是否产生相同或相似的输出。虽然稳定性在某些算法（如排序算法）中很重要，但它并不是算法的基本特性之一。

答案【A】

7.某语句时间复杂为？

在计算算法时间复杂度时，可以忽略所有 低次幂项 和 最高次幂的系数，这体现出了增长率的含义。

依据该原则，可以看出上述：

• 前两个算法的时间复杂度均为 O ( n 3 ) O(n^3) O(n3)
• 最后一个算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

答案【D】

8.存储数据时要存储什么？

A选项： 数据元素的类型在很多情况下在程序设计阶段就已经明确，不是存储时重点考虑的额外内容。

B选项：数据的基本运算通常是在程序运行时根据算法和逻辑来执行，而不是在存储阶段进行处理。

C选项： 数据元素之间的关系对于数据的组织、查询、修改等操作非常重要。

• 比如在链表、树、图等数据结构中，明确元素之间的关系才能有效地进行各种数据处理。

D选项： 数据的存取方式更多是在设计存储结构和算法时考虑，而不是直接作为存储的部分。

综上所述 ：

存储数据时通常不仅需要存储数据元素的值，还要存储数据元素之间的关系。

答案【C】

9.某语句时间复杂为？

函数中的基本语句为：sum+=++i;

该语句等价于以下两条基本语句：

• ++i;
• sum=sumt+i;

该 w h i l e while while循环的含义为求前 i i i项自然数的和，直到该和不再小于数值 n n n

由于 s u m = 1 + 2 + 3 + . . + i = ( 1 + i ) ∗ i / 2 ， sum=1+2+3+..+i=(1+i)*i/2， sum=1+2+3+..+i=(1+i)∗i/2，若 s u m < n ， sum<n， sum<n，即 ( 1 + i ) ∗ i / 2 < n ， i (1+i)*i/2<n，i (1+i)∗i/2<n，i为循环次数，因此时间复杂度为 O ( n 1 / 2 ) O(n^{1/2}) O(n1/2)

答案【B】

10.某语句时间复杂为？

首先，外层的 f o r for for循环，从 i = 1 i=1 i=1到 i < = n ， i<=n， i<=n，一共执行了 n n n次
对于每次外层循环的值，内层的 f o r for for循环从 j = 1 j=1 j=1到 j < = 2 ∗ i j<=2*i j<=2∗i执行的次数是 2 i 2i 2i次

• 当i=1时，内层循环执行2 次。
• 当i=2时，内层循环执行4次。
• 当i=3时，内层循环执行6次。
• 以此类推，当i=n时，内层循环执行2n次。

答案【A】

11.某二叉树的遍历序列为？

中序遍历：左->中->右 B D C E A F H G

后序遍历：左->右->中 D E C B H G F A

答案【AC】

12.某线索二叉树的线索数为？

线索二叉树的概念：

• 在有n个结点的二叉链表中，有n + 1个空指针域。
  • 因为n个结点的二叉树有2n个指针域（每个结点有两个指针域，分别指向左孩子和右孩子）
  • 而n个结点的二叉树中，除了根结点外，每个结点都有一个指针指向它
  • 所以有n - 1个指针是用来连接结点的，那么空指针域的个数为2n-(n - 1)=n + 1个。
• 线索二叉树就是利用这些空指针域来存放指向结点在某种遍历次序下的前驱和后继的指针（这些指针称为线索）。

结论：n个结点的线索二叉树上含有的线索数为n + 1

答案【B】

13.有向图顶点的入度与出度的关系为？

在有向图中，所有顶点的入度之和是所有顶点出度之和的1倍

• 由于每条弧必然连接两个顶点，也就对应一个入度和一个出度，所以所有顶点的入度之和等于所有顶点的出度之和。

• 事实上，各顶点入度之和等于弧数，各顶点出度之和也等于弧数，所以两者相等。

答案【B】

14. 由邻接矩阵进行深度优先遍历的结果为？

答案【C】

15.关于图的深度优先搜索描述正确的为？

C选项：

深度优先搜索（DFS）可以使用栈或者递归实现。(递归实现时，函数调用栈就起到了栈的作用)

• 当进行深度优先搜索每次深入一个节点，就相当于将该节点压入栈中。
• 当回溯时，就相当于将栈顶元素弹出。

D选项：

深度优先搜索（DFS）不适合寻找图中的最短路径，广度优先搜索（BFS）才适合寻找图中的最短路径。

• 因为BFS是按照层进行搜索的，最先找到的路径往往是最短路径（在无权图中）
• 而DFS是深入搜索，可能会陷入很深的路径，很难保证找到的是最短路径。

答案【C】

16.构造无向连通图的最小生成树的算法？

Dijkstra算法：

Dijkstra算法主要用于计算一个顶点到其他所有顶点的最短路径。

• 它从一个起始顶点开始，逐步扩展到图中的其他顶点，记录每个顶点到起始顶点的最短距离。
• 但是它不是用于构造无向连通图的最小生成树的算法，其重点在于求最短路径而非构建最小生成树。

Prim算法：

Prim算法是专门用于构造无向连通图的最小生成树的算法。

• 它从图中的任意一个顶点开始，每次选择一个与当前生成树相连且权值最小的边，将对应的顶点加入到生成树中。
• 不断重复这个过程，直到所有顶点都被加入到生成树中，这样就得到了图的最小生成树。

Floyd算法：

Floyd算法用于求解图中任意两点之间的最短路径。

• 它通过动态规划的思想，逐步更新任意两点之间的最短路径长度。
• 其目的是求最短路径矩阵，不是构建最小生成树。

拓扑排序：

拓扑排序是针对有向无环图（DAG）的一种操作。

• 它将图中的顶点按照一定的顺序排列，使得对于图中的每条有向边(u, v)，顶点u在排序结果中都排在顶点v之前。
• 拓扑排序不适用于无向连通图，更不能用于构造无向连通图的最小生成树。

答案【B】

17.拓扑排序适用于哪类图？

拓扑排序 ：拓扑排序的目的是为图中的顶点提供一种线性排序，使得对于图中的每条有向边(u, v)，顶点u在排序中都位于顶点v之前。

• 如果图中存在环，就无法满足这样的线性排序要求。

A选项： 无向图没有方向的概念，而拓扑排序是基于有向边的概念来定义顶点的先后顺序的，所以拓扑排序不适用于无向图。

B选项： 有向无环图（DAG）符合拓扑排序的适用条件，因为它不存在环，能够进行拓扑排序。

C选项： 连通图只是强调图中任意两个顶点之间存在路径，但没有涉及到有向无环的特性，连通图可能是无向的，也可能是有向且有环的，所以拓扑排序不一定适用于连通图。

D选项： 强连通图是有向图且图中任意两个顶点都互相可达，这意味着存在环，而拓扑排序不适用于有环的图，所以拓扑排序不适用于强连通图。

答案【B】

18.关于图的遍历算法描述正确的为？

A选项：

深度优先搜索（DFS）可以用于检测图中的环路

• 在深度优先搜索过程中，如果在搜索到某个顶点v时，发现它的某个邻接顶点u已经被标记为“正在访问”（而不是“已访问”），那么就说明存在环路。
• 因为这意味着从v可以通过其他路径再次到达u，从而形成了一个环。

B选项：

广度优先搜索（BFS）在无权图中总是能找到从起点到终点的最短路径

• 在有权图中，BFS不能保证找到从起点到终点的最短路径。
• 因为BFS是按照层次进行搜索的，它没有考虑边的权重。

C选项：

• BFS从起始顶点开始，按照距离起始顶点的距离逐层搜索。
• 在无权图中，每经过一条边就相当于距离增加1。
• 所以先被搜索到的目标顶点一定是距离起始顶点最短的路径到达的。

D选项：

DFS和BFS都可以用来检测图是否连通

如果从某个顶点开始进行DFS或者BFS：

• 若能够访问到图中的所有顶点，则图是连通的。
• 若不能访问到所有顶点，则图是非连通的。

答案【ACD】

19.邻接矩阵与邻接表的适用情况为？

答案【ABCD】

20.关于哈夫曼树的描述不正确的为？

A选项：

• 在构造哈夫曼树的过程中，每次都是选取权值最小的两个结点合并为一个新的结点。
• 所以树中两个权值最小的结点一定是兄弟结点。

B选项：

• 哈夫曼树的构造是基于权值的，每次合并都是选择权值较小的结点。
• 非叶子结点是由下层的结点合并而来，其权值是下层两个结点权值之和。
• 所以树中任一非叶子结点的权值一定不小于下一层任一结点的权值。

C选项：

• 哈夫曼树是一棵严格的二叉树，每个非叶子节点都有两个子节点，因此不存在度为1的节点。

A选项：

完全二叉树 ：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

• 哈夫曼树的结构取决于叶子节点的权值和合并顺序，不一定是完全二叉树。

答案【D】