2020年10月自考02331数据结构试题及答案含解析

数据结构年月真题

02331202010

1、【单选题】数据结构研究的基本内容是

数据的逻辑结构、存储结构和对数据元素施加的操作

数据的类型、数据的定义、算法描述和各种操作实现

A:

数据的线性结构、树型结构、图型结构及相关的算法

B:

数据元素之间的逻辑关系、物理存储和相关程序实现

C:

答D:案：A

解析：数据结构研究的基本内容包括数据的逻辑结构、存储结构和对数据元素施加的操

作。1.数据的逻辑结构：数据的逻辑结构描述了数据元素之间的关系，包括线性结构、

树形结构、图形结构等。线性结构中的数据元素之间存在一对一的关系，如数组、链表

等；树形结构中的数据元素之间存在一对多的关系，如二叉树、堆等；图形结构中的数据

元素之间存在多对多的关系，如图、网络等。2.数据的存储结构：数据的存储结构描述了

数据在计算机内存中的存储方式，包括顺序存储和链式存储等。顺序存储将数据元素连续

地存储在一块连续的内存空间中，如数组；链式存储通过指针将数据元素存储在不连续的

内存空间中，如链表。3.对数据元素施加的操作：对数据元素施加的操作包括插入、删

除、查找、修改等。这些操作可以通过不同的数据结构来实现，不同的数据结构对这些操

作的效率有所差异。通过研究数据的逻辑结构、存储结构和对数据元素施加的操作，可以

选择合适的数据结构来解决实际问题，提高数据的存储和操作效率。

2、【单选题】数据结构中,评价算法好坏的重要指标之一是

程序的执行时间

源程序的代码长度

A:

程序采用的语言

B:

算法的时间复杂度

C:

答D:案：D

解析：算法的时间复杂度是评价算法好坏的重要指标之一。时间复杂度描述了算法执行所

需的时间与输入规模之间的关系。它衡量了算法的执行效率，即算法在处理不同规模的输

入时所需的时间量级。通常情况下，我们希望算法的时间复杂度尽可能低，即算法的执行

时间随着输入规模的增加而增长得较慢。常见的时间复杂度有常数时间O(1)、对数时间

O(logn)、线性时间O(n)、线性对数时间O(nlogn)、平方时间O(n^2)等。其中，常数

时间和对数时间的算法效率较高，而平方时间的算法效率较低。通过分析算法的时间复杂

度，我们可以对算法的执行效率有一个大致的估计，从而选择合适的算法来解决问题。然

而，时间复杂度并不是唯一的评价指标，还需要考虑算法的空间复杂度、可读性、可维护

性等因素来综合评价算法的好坏。

3、【单选题】等概率情况下,在长度为n的顺序表中插入1个元素需要移动元素的平均次数

是

1

n/2

A:

n

B:

n+1

C:

答D:案：B

4、【单选题】已知head为指向带头结点的单链表的头指针,指针变量p指向一个新结

点,next是结点的指针域,若要将p所指结点插入到单链表的表头,则正确的语句序列是

head->next=p;p->next=head;

p->next=head->next;head=p;

A:

head=p;p->next=head->head;

B:

p->next=head->next;head->next=p;

C:

答D:案：D

5、【单选题】后缀表达式求值的过程中要用到的数据结构是

一个保存各种操作符的栈

一个保存操作数及运算结果的栈

A:

两个分别保存操作符和操作数的栈

B:

两个分别保存操作数和运算结果的栈

C:

答D:案：B

6、【单选题】广义表LS=(((a),(b)),((c,(d)),(e,(f))),(g,h))的表尾是

(g,h)

((c,(d)),(e,(f))),(g,h)

A:

((g,h))

B:

(((c,(d)),(e,(f))),(g,h))

C:

答D:案：D

7、【单选题】

A

B

A:

C

B:

D

C:

答D:案：A

8、【单选题】用n(n≥2)个带权值的结点作为叶结点构造一棵哈夫曼树,下列选项中正确的

是

哈夫曼树是叶结点权值之和最小的二叉树

哈夫曼树是带权路径长度WPL最小的二叉树

A:

n个带有权值的结点可以构造出唯一一棵哈夫曼树

B:

哈夫曼树是有n个叶结点的二叉树中高度最低的二叉树

C:

答D:案：B

9、【单选题】将一棵树T转换为等价的二叉树T1,与T的后序遍历序列相同的是T1的

前序遍历序列

中序遍历序列

A:

后序遍历序列

B:

按层遍历序列

C:

答D:案：B

解析：将一棵树T转换为等价的二叉树T1，且T1的后序遍历序列与T的后序遍历序列相

同的话，T1的中序遍历序列也与T的中序遍历序列相同。后序遍历的顺序是先遍历左子

树，再遍历右子树，最后访问根节点。如果T1的后序遍历序列与T的后序遍历序列相

同，说明T1的根节点与T的根节点相同，且T1的左子树和右子树的后序遍历序列也与T

的左子树和右子树的后序遍历序列相同。中序遍历的顺序是先遍历左子树，再访问根节

点，最后遍历右子树。由于T1的后序遍历序列与T的后序遍历序列相同，说明T1的根节

点与T的根节点相同，且T1的左子树和右子树的后序遍历序列也与T的左子树和右子树

的后序遍历序列相同。因此，T1的中序遍历序列与T的中序遍历序列相同。

10、【单选题】要在带权图(权值>0)中求从某一顶点到其余各顶点的最短路径,应采用的算

法是

哈夫曼算法

普里姆算法

A:

克鲁斯卡尔算法

B:

迪杰斯特拉算法

C:

答D:案：D

解析：迪杰斯特拉算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为

止。

11、【单选题】设图G存在拓扑序列,则下列结论中正确的是

图G是一个有向图

图G的拓扑序列唯一

A:

图G是一个无向图

B:

图G是一个有向无环图

C:

答D:案：D

12、【单选题】内排序过程中,待排序数据保存在

CPU中

内存储器中

A:

外存储器中

B:

计算机中

C:

答D:案：B

解析：内部排序:待排序记录存放在计算机随机存储器中(说简单点,就是内存)进行的排序

过程。

13、【单选题】下列排序方法中,关键字总的比较次数与记录的初始排列次序无关的是

冒泡排序

希尔排序

A:

直接插入排序

B:

直接选择排序

C:

答D:案：D

14、【单选题】散列查找方法可以达到的最好时间复杂度是

O(1)

A:

O(n)

O(logn)

B:

O(n1/2)

C:

答D:案：A

解析：散列查找方法可以达到的最好时间复杂度是O(1)。散列查找，也称为哈希查找，是

一种通过散列函数将关键字映射到存储位置的查找方法。在理想情况下，如果散列函数能

够将每个关键字均匀地映射到不同的存储位置，那么查找一个元素的时间复杂度就是常数

级别的，即O(1)。

15、【单选题】下列关于二分查找判定树T的叙述中,正确的是

T是一棵二叉树

T是一棵满二叉树

A:

T是一棵完全二叉树

B:

T的叶结点在同一层

C:

答D:案：A

16、【问答题】将中缀表达式“a*(b+c)”转换为后缀表达式,请回答下列问题。(1)画出

转换过程中栈的变化过程。(2)写出转换后得到的后缀表达式。

答案：

17、【问答题】已知二叉树T的前序遍历序列为:adbce,中序遍历序列为:daceb请回答下列

问题。(1)画出对应的二叉树T。(2)建立并画出二叉树T的后序线索。

答案：

18、【问答题】

答案：

19、【问答题】已知数据序列(19,14,23,01,68,79,84,27,55,11,10),请画出建立大根堆的

过程。

答案：

20、【问答题】

答案：

21、【问答题】

答案：(1)-1(2)L.length(3)pmax-pmin

22、【问答题】

答案：(1)null(2)head->next(3)head->next

23、【问答题】

答案：(1)2,10.12.24,3343,50,66,88(2)增量序列(3)函数f33()的功能是对数组a进

行希尔排序。

24、【问答题】

答案：

25、【填空题】算法必须满足的五个准则是:输入、输出、有穷性、确定性和____

答案：可行性

26、【填空题】将100个数据元素保存在顺序表中,若第一个元素的存储地址是1000,第二个

元素的存储地址是1004,则该顺序表最后一个元素的存储地址是____

答案：1396

27、【填空题】循环队列保存在长度为M的数组中,队头为front,队尾为rear,若要求队满

时条件为真,则条件表达式应是____

答案：(rear+1)%M==front

28、【填空题】广义表(())的长度是____

答案：1

29、【填空题】具有n个结点的完全二叉树的深度为____

答案：[logn]+1(或]log(n+1)]

30、【填空题】图G的邻接矩阵不是一个对称矩阵,则图G一定是____图。

答案：有向

31、【填空题】顶点表示活动、边表示活动间先