全国2020年10月自考数据结构02331真题

自考真题是考生复习备考的一大法宝，需要好好利用，而且年份离的越近，参考价值越高。以下是希赛网自考频道整理的全国2020年10月自考数据结构02331真题，考生可参考试卷题型、分值、重点考试内容及答题规范，参考答案现在暂未公布，希赛网将持续更新。

全国2020年10月自考数据结构02331真题

一、单项选择题:本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1.数据结构研究的基本内容是

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

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

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

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

2.数据结构中，评价算法好坏的重要指标之一是

A.程序的执行时间

B.源程序的代码长度

C.程序采用的语言

D.算法的时间复杂度

3.等概率情况下，在长度为n的顺序表中插入1个元素需要移动元素的平均次数是

A.1

B. n/2

C. n

D. n+1

4.已知head 为指向带头结点的单链表的头指针，指针变量p指向一个新结点，next是结点的指针域，若要将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;

5.后缀表达式求值的过程中要用到的数据结构是

A.一个保存各种操作符的栈

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

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

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

8.用n (n≥2)个带权值的结点作为叶结点构造一 棵哈夫曼树， 下列选项中正确的是

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

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

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

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

9.将一棵树T转换为等价的二叉树T1，与T的后序遍历序列相同的是T1的

A.前序遍历序列

B. 中序遍历序列

C. 后序遍历序列

D. 按层遍历序列.

10. 要在带权图(权值>0)中求从某一顶点到其余各顶点的最短路径，应采用的算法是

A.哈夫曼算法

B.普里姆算法

C.克鲁斯卡尔算法

D.迪杰斯特拉算法

11.设图G存在拓扑序列，则下列结论中正确的是

A.图G是一个有向图

B.图G的拓扑序列唯一

C.图G是一个无向图

D.图G是一个有向无环图.

12.内排序过程中，待排序数据保存在

A. CPU中

B.内存储器中

C.外存储器中

D.计算机中

13.下列排序方法中，关键字总的比较次数与记录的初始排列次序无关的是

A.冒泡排序

B.希尔排序

C.直接插入排序

D.直接选择排序

14.散列查找方法可以达到的最好时间复杂度是

A.0(1)

B. O(n)

C. O(log n)

D.0(n'2)

15.下列关于二分查找判定树T的叙述中，正确的是

A. T是一棵二叉树

B. T是一棵满二叉树

C. T是一棵完全二叉树

D. T的叶结点在同一层

二、填空题:本大题共10小题，每小题2分，共20分。

16.算法必须满足的五个准则是:输入、输出、有穷性、确定性和           

17.将100个数据元素保存在顺序表中，若第一个元素的存储地址是1000,第二个元素的存储地址是1004，则该顺序表最后一个元素的存储地址是           

18.循环队列保存在长度为M的数组中，队头为front, 队尾为rear,若要求队满时条件为真，则条件表达式应是           

19.广义表(())的长度是           

20.具有n个结点的完全二叉树的深度为           

21.图G的邻接矩阵不是一个对称矩阵，则图G一定是           图。

22.顶点表示活动、边表示活动间先后关系的有向无环图称为           网。

23.在排序过程中，如果具有相同关键字的记录之间的相对次序保持不变，则称该排序方法是           的。

24.对二叉排序树BT进行           遍历可以得到BT中所有结点的有序序列。

25.在一棵25阶的B树中，非根结点内所包含的关键字个数至少是           个。

三、解答题:本大题共4小题，每小题5分，共20分。

26.将中缀表达式“a*(b+c)”转换为后缀表达式，请回答下列问题。

(1)画出转换过程中栈的变化过程。

(2)写出转换后得到的后缀表达式。

27.已知二叉树T的前序遍历序列为: adbce, 中序遍历序列为: daceb.请回答下列问题。

(1)画出对应的二叉树T。

(2)建立并画出二叉树T的后序线索。

28.求题28图的最小生成树。要求:按照克鲁斯卡尔算法的思想，依次写出进入最小生成树的边。

29.已知数据序列(19, 14, 23, 01, 68, 79, 84, 27,55, 11, 10)，请画出建立大根堆的过程。