数据结构与算法练习试卷2(题后含答案及解析)_1

数据结构与算法练习试卷2 (题后含答案及解析)

全部题型 2. 填空题

填空题（每空2分，共30分）请将每一个空的正确答案写在答题卡上。注意：以命令关键字填空的必须拼写完整。

1． 数据元素之间______的整体称为逻辑结构。

正确答案：逻辑关系 涉及知识点：数据结构与算法

2． 一个算法的时间复杂性是______的函数。

正确答案：算法输入规模 涉及知识点：数据结构与算法

3． 在单链表中，NULL称为______，它不指向任何结点，只起______作用。

正确答案：空指针、标志 涉及知识点：数据结构与算法

4． 对长度为n的顺序表的删除算法，它的最坏情况时间复杂度及其量级分别是和______，平均时间复杂性及其量级分别为______和______。

正确答案：n-1、O(n)、(n-1)/2、O(n) 涉及知识点：数据结构与算法

5． 存储结点中数据域占用的存储量与整个结点占用存储量之比称为______。

正确答案：存储密度 涉及知识点：数据结构与算法

6． 一般地，二叉树可以有______种基本形态。

正确答案：5 涉及知识点：数据结构与算法

7． 按照排序过程涉及的存储设备的不同，排序可分为______和______。

正确答案：内部排序、外部排序 涉及知识点：数据结构与算法

8． 评价排序算法优劣的主要标准是______和______。

正确答案：时间复杂度、算法需要的附加空间 涉及知识点：数据结构与算法

9． 稳定的排序算法有______、______和______。

正确答案：直接插入排序、冒泡排序、归并排序 涉及知识点：数据结构与算法

10． 第一趟排序后序列中关键字最大的记录交换到最后的排序方法是______。

正确答案：冒泡排序 涉及知识点：数据结构与算法

11． 数据结构分为逻辑结构与存储结构，线性链表属于______。

正确答案：存储结构 涉及知识点：数据结构与算法

12． 在树型结构中，树根结点没有______。

正确答案：前件 涉及知识点：数据结构与算法

13． 数据的逻辑结构有线性结构和______两大类。

正确答案：非线性结构 涉及知识点：数据结构与算法

14． 顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。

正确答案：相邻 涉及知识点：数据结构与算法

15． 当线性表采用顺序存储结构实现存储时，其主要特点是______。

正确答案：逻辑结构中相邻的结点在存储结构中仍相邻 涉及知识点：数据结构与算法

16． 用链表表示线性表的突出优点是______。

正确答案：便于插入和删除操作 涉及知识点：数据结构与算法

17． 栈和队列通常采用的存储结构是______。

正确答案：链式存储和顺序存储 涉及知识点：数据结构与算法

18． 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为______。

正确答案：上溢 涉及知识点：数据结构与算法

19． 数据结构包括数据的逻辑结构、数据的______以及对数据的操作运算。

正确答案：存储结构 涉及知识点：数据结构与算法

20． 算法的基本特征是可行性、确定性、______和拥有足够的情报。

正确答案：有穷性 涉及知识点：数据结构与算法

21． 在长度为n的有序线性表中进行二分查找，最坏的情况下，需要的比较次数为______。

正确答案：log2n 涉及知识点：数据结构与算法

22． 长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为______。

正确答案：n/2 涉及知识点：数据结构与算法

23． 排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、______和选择排序等。

正确答案：交换掉序 涉及知识点：数据结构与算法 24． 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为______。

正确答案：DEBFCA 涉及知识点：数据结构与算法

25． 数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为______。

正确答案：逻辑独立性 涉及知识点：数据结构与算法