1、02331 数据结构 2020 年 10 月真题1、【单选题】、【单选题】数据结构研究的基本内容是数据结构研究的基本内容是A:数据的逻辑结构、存储结构和对数据元素施加的操作B:数据的类型、数据的定义、算法描述和各种操作实现C:数据的线性结构、树型结构、图型结构及相关的算法D:数据元素之间的逻辑关系、物理存储和相关程序实现答案：A解析：数据结构研究的基本内容包括数据的逻辑结构、存储结构和对数据元素施加的操作。1.数据的逻辑结构：数据的逻辑结构描述了数据元素之间的关系，包括线性结构、树形结构、图形结构等。线性结构中的数据元素之间存在一对一的关系，如数组、链表等；树形结构中的数据元素之间存在一对多的
2、关系，如二叉树、堆等；图形结构中的数据元素之间存在多对多的关系，如图、网络等。2.数据的存储结构：数据的存储结构描述了数据在计算机内存中的存储方式，包括顺序存储和链式存储等。顺序存储将数据元素连续地存储在一块连续的内存空间中，如数组；链式存储通过指针将数据元素存储在不连续的内存空间中，如链表。3.对数据元素施加的操作：对数据元素施加的操作包括插入、删除、查找、修改等。这些操作可以通过不同的数据结构来实现，不同的数据结构对这些操作的效率有所差异。通过研究数据的逻辑结构、存储结构和对数据元素施加的操作，可以选择合适的数据结构来解决实际问题，提高数据的存储和操作效率。2、【单选题】、【单选题】数据结
3、构中数据结构中,评价算法好坏的重要指标之一是评价算法好坏的重要指标之一是A:程序的执行时间B:源程序的代码长度C:程序采用的语言D:算法的时间复杂度答案：D解析：算法的时间复杂度是评价算法好坏的重要指标之一。时间复杂度描述了算法执行所需的时间与输入规模之间的关系。它衡量了算法的执行效率，即算法在处理不同规模的输入时所需的时间量级。通常情况下，我们希望算法的时间复杂度尽可能低，即算法的执行时间随着输入规模的增加而增长得较慢。常见的时间复杂度有常数时间 O(1)、对数时间O(logn)、线性时间 O(n)、线性对数时间 O(n log n)、平方时间 O(n2)等。其中，常数时间和对数时间的算法效
4、率较高，而平方时间的算法效率较低。通过分析算法的时间复杂度，我们可以对算法的执行效率有一个大致的估计，从而选择合适的算法来解决问题。然而，时间复杂度并不是唯一的评价指标，还需要考虑算法的空间复杂度、可读性、可维护性等因素来综合评价算法的好坏。3、【单选题】、【单选题】等概率情况下等概率情况下,在长度为在长度为 n n 的顺序表中插入的顺序表中插入 1 1 个元素需要移动元素的平均次数个元素需要移动元素的平均次数是是A:1B:n/2C:nD:n+1答案：B4、【单选题】、【单选题】已知已知 headhead 为指向带头结点的单链表的头指针为指向带头结点的单链表的头指针,指针变量指针变量 p p
5、指向一个新结指向一个新结点点,next,next 是结点的指针域是结点的指针域,若要将若要将 p p 所指结点插入到单链表的表头所指结点插入到单链表的表头,则正确的语句序列是则正确的语句序列是A:head-next=p;p-next=head;B:p-next=head-next;head=p;C:head=p;p-next=head-head;D:p-next=head-next;head-next=p;答案：D5、【单选题】、【单选题】后缀表达式求值的过程中要用到的数据结构是后缀表达式求值的过程中要用到的数据结构是A:一个保存各种操作符的栈B:一个保存操作数及运算结果的栈C:两个分别保存操
6、作符和操作数的栈D:两个分别保存操作数和运算结果的栈答案：B6、【单选题】、【单选题】广义表广义表 LS=(a),(b),(c,(d),(e,(f),(g,h)LS=(a),(b),(c,(d),(e,(f),(g,h)的表尾是的表尾是A:(g,h)B:(c,(d),(e,(f),(g,h)C:(g,h)D:(c,(d),(e,(f),(g,h)答案：D7、【单选题】、【单选题】A:AB:BC:CD:D答案：A8、【单选题】、【单选题】用用 n(nn(n2)2)个带权值的结点作为叶结点构造一棵哈夫曼树个带权值的结点作为叶结点构造一棵哈夫曼树,下列选项中正确的下列选项中正确的是是A:哈夫曼树是叶
7、结点权值之和最小的二叉树B:哈夫曼树是带权路径长度 WPL 最小的二叉树C:n 个带有权值的结点可以构造出唯一一棵哈夫曼树D:哈夫曼树是有 n 个叶结点的二叉树中高度最低的二叉树答案：B9、【单选题】、【单选题】将一棵树将一棵树 T T 转换为等价的二叉树转换为等价的二叉树 T1,T1,与与 T T 的后序遍历序列相同的是的后序遍历序列相同的是 T1T1 的的A:前序遍历序列B:中序遍历序列C:后序遍历序列D:按层遍历序列答案：B解析：将一棵树 T 转换为等价的二叉树 T1，且 T1 的后序遍历序列与 T 的后序遍历序列相同的话，T1 的中序遍历序列也与 T 的中序遍历序列相同。后序遍历的顺序
8、是先遍历左子树，再遍历右子树，最后访问根节点。如果 T1 的后序遍历序列与 T 的后序遍历序列相同，说明 T1 的根节点与 T 的根节点相同，且 T1 的左子树和右子树的后序遍历序列也与 T的左子树和右子树的后序遍历序列相同。中序遍历的顺序是先遍历左子树，再访问根节点，最后遍历右子树。由于 T1 的后序遍历序列与 T 的后序遍历序列相同，说明 T1 的根节点与 T 的根节点相同，且 T1 的左子树和右子树的后序遍历序列也与 T 的左子树和右子树的后序遍历序列相同。因此，T1 的中序遍历序列与 T 的中序遍历序列相同。10、【单选题】、【单选题】要在带权图要在带权图(权值权值0)0)中求从某一顶
9、点到其余各顶点的最短路径中求从某一顶点到其余各顶点的最短路径,应采用的算应采用的算法是法是A:哈夫曼算法B:普里姆算法C:克鲁斯卡尔算法D:迪杰斯特拉算法答案：D解析：迪杰斯特拉算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。11、【单选题】、【单选题】设图设图 G G 存在拓扑序列存在拓扑序列,则下列结论中正确的是则下列结论中正确的是A:图 G 是一个有向图B:图 G 的拓扑序列唯一C:图 G 是一个无向图D:图 G 是一个有向无环图答案：D12、【单选题】、【单选题】内排序过程中内排序过程中,待
10、排序数据保存在待排序数据保存在A:CPU 中B:内存储器中C:外存储器中D:计算机中答案：B解析：内部排序:待排序记录存放在计算机随机存储器中(说简单点,就是内存)进行的排序过程。13、【单选题】、【单选题】下列排序方法中下列排序方法中,关键字总的比较次数与记录的初始排列次序无关的是关键字总的比较次数与记录的初始排列次序无关的是A:冒泡排序B:希尔排序C:直接插入排序D:直接选择排序答案：D14、【单选题】、【单选题】散列查找方法可以达到的最好时间复杂度是散列查找方法可以达到的最好时间复杂度是A:O(1)B:O(n)C:O(log n)D:O(n1/2)答案：A解析：散列查找方法可以达到的最好
11、时间复杂度是 O(1)。散列查找，也称为哈希查找，是一种通过散列函数将关键字映射到存储位置的查找方法。在理想情况下，如果散列函数能够将每个关键字均匀地映射到不同的存储位置，那么查找一个元素的时间复杂度就是常数级别的，即 O(1)。15、【单选题】、【单选题】下列关于二分查找判定树下列关于二分查找判定树 T T 的叙述中的叙述中,正确的是正确的是A:T 是一棵二叉树B:T 是一棵满二叉树C:T 是一棵完全二叉树D:T 的叶结点在同一层答案：A16、【问答题】、【问答题】将中缀表达式将中缀表达式“a*(b+c)a*(b+c)”转换为后缀表达式转换为后缀表达式,请回答下列问题。请回答下列问题。(1)
12、(1)画出画出转换过程中栈的变化过程。转换过程中栈的变化过程。(2)(2)写出转换后得到的后缀表达式。写出转换后得到的后缀表达式。答案：17、【问答题】、【问答题】已知二叉树已知二叉树 T T 的前序遍历序列为的前序遍历序列为:adbce,:adbce,中序遍历序列为中序遍历序列为:dacebdaceb 请回答下列请回答下列问题。问题。(1)(1)画出对应的二叉树画出对应的二叉树 T T。(2)(2)建立并画出二叉树建立并画出二叉树 T T 的后序线索。的后序线索。答案：18、【问答题】、【问答题】答案：19、【问答题】、【问答题】已知数据序列已知数据序列(19,14,23,01,68,79,
13、84,27,55,11,10),(19,14,23,01,68,79,84,27,55,11,10),请画出建立大根堆的请画出建立大根堆的过程。过程。答案：20、【问答题】、【问答题】答案：21、【问答题】、【问答题】答案：(1)-1(2)L.length(3)pmax-pmin22、【问答题】、【问答题】答案：(1)null(2)head-next(3)head-next23、【问答题】、【问答题】答案：(1)2,10.12.24,3343,50,66,88(2)增量序列(3)函数 f33()的功能是对数组 a 进行希尔排序。24、【问答题】、【问答题】答案：25、【填空题】、【填空题】算法
14、必须满足的五个准则是算法必须满足的五个准则是:输入、输出、有穷性、确定性和输入、输出、有穷性、确定性和_答案：可行性26、【填空题】、【填空题】将将 100100 个数据元素保存在顺序表中个数据元素保存在顺序表中,若第一个元素的存储地址是若第一个元素的存储地址是 1000,1000,第二个第二个元素的存储地址是元素的存储地址是 1004,1004,则该顺序表最后一个元素的存储地址是则该顺序表最后一个元素的存储地址是_答案：139627、【填空题】、【填空题】循环队列保存在长度为循环队列保存在长度为 M M 的数组中的数组中,队头为队头为 front,front,队尾为队尾为 rear,rear
15、,若要求队满若要求队满时条件为真时条件为真,则条件表达式应是则条件表达式应是_答案：(rear+1)%M=front28、【填空题】、【填空题】广义表广义表()()的长度是的长度是_答案：129、【填空题】、【填空题】具有具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为_答案：log n+1(或log(n+1)30、【填空题】、【填空题】图图 G G 的邻接矩阵不是一个对称矩阵的邻接矩阵不是一个对称矩阵,则图则图 G G 一定是一定是_图。图。答案：有向31、【填空题】、【填空题】顶点表示活动、边表示活动间先后关系的有向无环图称为顶点表示活动、边表示活动间先后关系的有向无环图称为_网。网。答案：顶点活动(或 AOV)32、【填空题】、【填空题】在排序过程中在排序过程中,如果具有相同关键字的记录之间的相对次序保持不变如果具有相同关键字的记录之间的相对次序保持不变,则称该则称该排序方法是排序方法是_的。的。答案：稳定33、【填空题】、【填空题】对二叉排序树对二叉排序树 BTBT 进行进行_遍历可以得到遍历可以得到 BTBT 中所有结点的有序序列。中所有结点的有序序列。答案：中序34、【填空题】、【填空题】在一棵在一棵 2525 阶的阶的 B B 树中树中,非根结点内所包含的关键字个数至少是非根结点内所包含的关键字个数至少是_个。个。答案：12
