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

1、数据结构与算法练习试卷 4及答案解析(总分：42.00，做题时间：90 分钟)一、填空题(总题数：21，分数：42.00)1.填空题（每空）请将每一个空的正确答案写在答题卡上。（分数：2.00）_2.在具有 n个单元的循环队列中，队满时共有 1 个元素。（分数：2.00）填空项 1:_3.队列和栈分别是 1、 2 的线性表结构。（分数：2.00）填空项 1:_填空项 1:_4.数据结构包括 3个方面的内容是数据的 1、数据的逻辑结构、数据的运算。（分数：2.00）填空项 1:_5.数据的基本单位是 1。（分数：2.00）填空项 1:_6.一个深度为 n的满二叉树上的结点总数为 1；一棵深度为

2、n的完全二叉树上的结点总数最小值为 2，最大值为 3。（分数：2.00）填空项 1:_7.线性表、栈和队列都是线性结构，可以在线性表的 1 位置插入和删除元素；而对栈只能在 2 插入和删除元素；对于队列只能在 3 插入和在 4 删除元素。（分数：2.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_8.广义表(a，(a，B)，d，e，(i，j，k)的长度是 1，深度是 2。（分数：2.00）填空项 1:_填空项 1:_9.长度为 255的表，采用分块查找法，每块的最佳长度是 1。（分数：2.00）填空项 1:_10.已知一个待散列存储的线性表 18，34，58，26，75，67，4

3、8，81，散列函数为 H(k)=k mod 11，若采用线性探测法解决冲突，则平均查找长度为 1。若采用链接法解决冲突，则平均查找长度为 2。（分数：2.00）填空项 1:_填空项 1:_11.在一棵二叉排序树中，按 1 遍历得到的结点序列是有序序列。（分数：2.00）填空项 1:_12.在堆排序、快速排序、希尔排序、插入排序、归并排序、基数排序和选择排序中， 1 平均比较次数最少， 2 需要内存容量最多。（分数：2.00）填空项 1:_填空项 1:_13.对 n个元素的序列采用冒泡排序的方法，最少的比较次数为 1。（分数：2.00）填空项 1:_14.二分查找法的存储结构要求是 1，对元素要

4、求 2。（分数：2.00）填空项 1:_填空项 1:_15.在算法正确的前提下，评价一个算法的两个标准是 1、 2。（分数：2.00）填空项 1:_填空项 1:_16.在分块查找方法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_填空项 1:_17.链表中数据元素的入栈顺序为 abcde，则其出栈顺序为 1。（分数：2.00）填空项 1:_18.设有关键字序列23，4，67，2，65，2，59，13，42，按堆排序思想选出当前序列最大元素 67 和 65后，剩余元素构成的堆是 1。（分数：2.00）填空项 1:_19.一棵有 n个结点的树，该树中所有结点的入度之和为 1

5、分数：2.00）填空项 1:_20.对二叉树结点的先序遍历、中序遍历、后序遍历序列中，所有叶子结点的先后顺序 1。（分数：2.00）填空项 1:_21.算法的时间复杂性是指该算法包含 1 的多少，它是一个算法运行时间的相对度量；一个算法的空间复杂性是指该算法在运行过程中临时占用 2 的大小。（分数：2.00）填空项 1:_填空项 1:_数据结构与算法练习试卷 4答案解析(总分：42.00，做题时间：90 分钟)一、填空题(总题数：21，分数：42.00)1.填空题（每空）请将每一个空的正确答案写在答题卡上。（分数：2.00）_解析：2.在具有 n个单元的循环队列中，队满时共有 1 个元素。

6、分数：2.00）填空项 1:_ （正确答案：正确答案：n-1）解析：3.队列和栈分别是 1、 2 的线性表结构。（分数：2.00）填空项 1:_ （正确答案：正确答案：先进先出）填空项 1:_ （正确答案：后进先出）解析：4.数据结构包括 3个方面的内容是数据的 1、数据的逻辑结构、数据的运算。（分数：2.00）填空项 1:_ （正确答案：正确答案：存储结构）解析：5.数据的基本单位是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：数据元素）解析：6.一个深度为 n的满二叉树上的结点总数为 1；一棵深度为 n的完全二叉树上的结点总数最小值为 2，最大值为 3。（分数：2.00）

7、填空项 1:_ （正确答案：正确答案：2 n -1，2 n-1 ，2 n -1）解析：7.线性表、栈和队列都是线性结构，可以在线性表的 1 位置插入和删除元素；而对栈只能在 2 插入和删除元素；对于队列只能在 3 插入和在 4 删除元素。（分数：2.00）填空项 1:_ （正确答案：正确答案：任何）填空项 1:_ （正确答案：栈顶）填空项 1:_ （正确答案：队尾）填空项 1:_ （正确答案：队首）解析：8.广义表(a，(a，B)，d，e，(i，j，k)的长度是 1，深度是 2。（分数：2.00）填空项 1:_ （正确答案：正确答案：5）填空项 1:_ （正确答案：3）解析：9.长度为 255

8、的表，采用分块查找法，每块的最佳长度是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：15）解析：10.已知一个待散列存储的线性表 18，34，58，26，75，67，48，81，散列函数为 H(k)=k mod 11，若采用线性探测法解决冲突，则平均查找长度为 1。若采用链接法解决冲突，则平均查找长度为 2。（分数：2.00）填空项 1:_ （正确答案：正确答案：14/9）填空项 1:_ （正确答案：13/9）解析：11.在一棵二叉排序树中，按 1 遍历得到的结点序列是有序序列。（分数：2.00）填空项 1:_ （正确答案：正确答案：中序）解析：12.在堆排序、快速排序、希尔排

9、序、插入排序、归并排序、基数排序和选择排序中， 1 平均比较次数最少， 2 需要内存容量最多。（分数：2.00）填空项 1:_ （正确答案：正确答案：快速排序）填空项 1:_ （正确答案：基数排序）解析：13.对 n个元素的序列采用冒泡排序的方法，最少的比较次数为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n-1）解析：14.二分查找法的存储结构要求是 1，对元素要求 2。（分数：2.00）填空项 1:_ （正确答案：正确答案：顺序存储结构）填空项 1:_ （正确答案：有序）解析：15.在算法正确的前提下，评价一个算法的两个标准是 1、 2。（分数：2.00）填空项 1:_

10、正确答案：正确答案：时间复杂度）填空项 1:_ （正确答案：空间复杂度）解析：16.在分块查找方法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_ （正确答案：正确答案：索引）填空项 1:_ （正确答案：块）解析：17.链表中数据元素的入栈顺序为 abcde，则其出栈顺序为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：edcba）解析：18.设有关键字序列23，4，67，2，65，2，59，13，42，按堆排序思想选出当前序列最大元素 67 和 65后，剩余元素构成的堆是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：59，42，23，13，5，2，2)）解析：19.一棵有 n个结点的树，该树中所有结点的入度之和为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：n-1）解析：20.对二叉树结点的先序遍历、中序遍历、后序遍历序列中，所有叶子结点的先后顺序 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：相同）解析：21.算法的时间复杂性是指该算法包含 1 的多少，它是一个算法运行时间的相对度量；一个算法的空间复杂性是指该算法在运行过程中临时占用 2 的大小。（分数：2.00）填空项 1:_ （正确答案：正确答案：简单操作次数）填空项 1:_ （正确答案：存储空间）解析：