1、数据结构与算法练习试卷 2-2 及答案解析(总分:52.00,做题时间:90 分钟)一、填空题(总题数:26,分数:52.00)1.填空题(每空)请将每一个空的正确答案写在答题卡上。注意:以命令关键字填空的必须拼写完整。(分数:2.00)_2.数据元素之间 1 的整体称为逻辑结构。(分数:2.00)填空项 1:_3.一个算法的时间复杂性是 1 的函数。(分数:2.00)填空项 1:_4.在单链表中,NULL 称为 1,它不指向任何结点,只起 2 作用。(分数:2.00)填空项 1:_5.对长度为 n 的顺序表的删除算法,它的最坏情况时间复杂度及其量级分别是和 1,平均时间复杂性及其量级分别为
2、2 和 3。(分数:2.00)填空项 1:_6.存储结点中数据域占用的存储量与整个结点占用存储量之比称为 1。(分数:2.00)填空项 1:_7.一般地,二叉树可以有 1 种基本形态。(分数:2.00)填空项 1:_8.按照排序过程涉及的存储设备的不同,排序可分为 1 和 2。(分数:2.00)填空项 1:_9.评价排序算法优劣的主要标准是 1 和 2。(分数:2.00)填空项 1:_10.稳定的排序算法有 1、 2 和 3。(分数:2.00)填空项 1:_11.第一趟排序后序列中关键字最大的记录交换到最后的排序方法是 1。(分数:2.00)填空项 1:_12.数据结构分为逻辑结构与存储结构,
3、线性链表属于 1。(分数:2.00)填空项 1:_13.在树型结构中,树根结点没有 1。(分数:2.00)填空项 1:_14.数据的逻辑结构有线性结构和 1 两大类。(分数:2.00)填空项 1:_15.顺序存储方法是把逻辑上相邻的结点存储在物理位置 1 的存储单元中。(分数:2.00)填空项 1:_16.当线性表采用顺序存储结构实现存储时,其主要特点是 1。(分数:2.00)填空项 1:_17.用链表表示线性表的突出优点是 1。(分数:2.00)填空项 1:_18.栈和队列通常采用的存储结构是 1。(分数:2.00)填空项 1:_19.当循环队列非空且队尾指针等于队头指针时,说明循环队列已满
4、,不能进行入队运算。这种情况称为 1。(分数:2.00)填空项 1:_20.数据结构包括数据的逻辑结构、数据的 1 以及对数据的操作运算。(分数:2.00)填空项 1:_21.算法的基本特征是可行性、确定性、 1 和拥有足够的情报。(分数:2.00)填空项 1:_22.在长度为 n 的有序线性表中进行二分查找,最坏的情况下,需要的比较次数为 1。(分数:2.00)填空项 1:_23.长度为 n 的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为 1。(分数:2.00)填空项 1:_24.排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序
5、、 1 和选择排序等。(分数:2.00)填空项 1:_25.设一棵二叉树的中序遍历结果为 DBEAFC,前序遍历结果为 ABDECF,则后序遍历结果为 1。(分数:2.00)填空项 1:_26.数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时,其逻辑结构可以不变,因此,基于逻辑结构的应用程序不必修改,称为 1。(分数:2.00)填空项 1:_数据结构与算法练习试卷 2-2 答案解析(总分:52.00,做题时间:90 分钟)一、填空题(总题数:26,分数:52.00)1.填空题(每空)请将每一个空的正确答案写在答题卡上。注意:以命令关键字填空的必须拼写完整。(分数:2.00)_解析:
6、2.数据元素之间 1 的整体称为逻辑结构。(分数:2.00)填空项 1:_ (正确答案:正确答案:逻辑关系)解析:3.一个算法的时间复杂性是 1 的函数。(分数:2.00)填空项 1:_ (正确答案:正确答案:算法输入规模)解析:4.在单链表中,NULL 称为 1,它不指向任何结点,只起 2 作用。(分数:2.00)填空项 1:_ (正确答案:正确答案:空指针、标志)解析:5.对长度为 n 的顺序表的删除算法,它的最坏情况时间复杂度及其量级分别是和 1,平均时间复杂性及其量级分别为 2 和 3。(分数:2.00)填空项 1:_ (正确答案:正确答案:n-1、O(n)、(n-1)/2、O(n))
7、解析:6.存储结点中数据域占用的存储量与整个结点占用存储量之比称为 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:存储密度)解析:7.一般地,二叉树可以有 1 种基本形态。(分数:2.00)填空项 1:_ (正确答案:正确答案:5)解析:8.按照排序过程涉及的存储设备的不同,排序可分为 1 和 2。(分数:2.00)填空项 1:_ (正确答案:正确答案:内部排序、外部排序)解析:9.评价排序算法优劣的主要标准是 1 和 2。(分数:2.00)填空项 1:_ (正确答案:正确答案:时间复杂度、算法需要的附加空间)解析:10.稳定的排序算法有 1、 2 和 3。(分数:2.00)填空
8、项 1:_ (正确答案:正确答案:直接插入排序、冒泡排序、归并排序)解析:11.第一趟排序后序列中关键字最大的记录交换到最后的排序方法是 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:冒泡排序)解析:12.数据结构分为逻辑结构与存储结构,线性链表属于 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:存储结构)解析:13.在树型结构中,树根结点没有 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:前件)解析:14.数据的逻辑结构有线性结构和 1 两大类。(分数:2.00)填空项 1:_ (正确答案:正确答案:非线性结构)解析:15.顺序存储方法是把逻辑上相邻
9、的结点存储在物理位置 1 的存储单元中。(分数:2.00)填空项 1:_ (正确答案:正确答案:相邻)解析:16.当线性表采用顺序存储结构实现存储时,其主要特点是 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:逻辑结构中相邻的结点在存储结构中仍相邻)解析:17.用链表表示线性表的突出优点是 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:便于插入和删除操作)解析:18.栈和队列通常采用的存储结构是 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:链式存储和顺序存储)解析:19.当循环队列非空且队尾指针等于队头指针时,说明循环队列已满,不能进行入队运算。这种
10、情况称为 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:上溢)解析:20.数据结构包括数据的逻辑结构、数据的 1 以及对数据的操作运算。(分数:2.00)填空项 1:_ (正确答案:正确答案:存储结构)解析:21.算法的基本特征是可行性、确定性、 1 和拥有足够的情报。(分数:2.00)填空项 1:_ (正确答案:正确答案:有穷性)解析:22.在长度为 n 的有序线性表中进行二分查找,最坏的情况下,需要的比较次数为 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:log 2 n)解析:23.长度为 n 的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一
11、个元素所需移动元素的平均个数为 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:n/2)解析:24.排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序、 1 和选择排序等。(分数:2.00)填空项 1:_ (正确答案:正确答案:交换掉序)解析:25.设一棵二叉树的中序遍历结果为 DBEAFC,前序遍历结果为 ABDECF,则后序遍历结果为 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:DEBFCA)解析:26.数据独立性分为逻辑独立性与物理独立性。当数据的存储结构改变时,其逻辑结构可以不变,因此,基于逻辑结构的应用程序不必修改,称为 1。(分数:2.00)填空项 1:_ (正确答案:正确答案:逻辑独立性)解析: