【计算机类职业资格】数据结构与算法练习试卷2-2及答案解析.doc

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:_ （正确答案：正确答案：逻辑独立性）解析：