[计算机类试卷]数据结构与算法练习试卷7及答案与解析.doc

1、数据结构与算法练习试卷 7及答案与解析 1 在具有 n个单元的循环队列中，队满时共有 _个元素。 2 队列和栈分别是 _、 _的线性表结构。 3 数据结构包括 3个方面的内容是数据的 _、数据的逻辑结构、数据的运算。 4 数据的基本单位是 _。 5 一个深度为 n的满二叉树上的结点总数为 _；一棵深度为 n的完全二叉树上的结点总数最小值为 _，最大值为 _。 6 线性表、栈和队列都是线性结构，可以在线性表的 _位置插入和删 除元素；而对栈只能在 _插入和删除元素；对于队列只能在 _插入和在 _删除元素。 7 广义表 (a， (a， B)， d， e， (i， j， k)的长度是 _，深度是 _

2、。 8 长度为 255的表，采用分块查找法，每块的最佳长度是 _。 9 已知一个待散列存储的线性表 18， 34， 58， 26， 75， 67， 48， 81，散列函数为H(k)=k mod 11，若采用线性探测法解决冲突，则平均查找长度为 _。若采用链接法解决冲突，则平均查找长度为 _。 10 在一棵二叉排序树中，按 _遍历得到的结点序列是有序序列。 11 在堆排序、快速排序、希尔排序、插入排序、归并排序、基数排序和选择排序中， _平均比较次数最少， _需要内存容量最多。 12 对 n个元素的序列采用冒泡排序的方法，最少的比较次数为 _。 13 二分查找法的存储结构要求是 _，对元素要求

3、_。 14 在算法正确的前提下，评价一个算法的两个标准是 _、 _。 15 在分块查找方法中，首先查找 _，然后 再查找相应的 _。 16 链表中数据元素的入栈顺序为 abcde，则其出栈顺序为 _。 17 设有关键字序列 23， 4， 67， 2， 65， 2， 59， 13， 42，按堆排序思想选出当前序列最大元素 67和 65后，剩余元素构成的堆是 _。 18 一棵有 n个结点的树，该树中所有结点的入度之和为 _。 19 对二叉树结点的先序遍历、中序遍历、后序遍历序列中，所有叶子结点的先后顺序 _。 20 算法的时间复杂性是指该算法包含 _的多少，它是一个算法运行时间的相对度量；一个算法

4、的空间复杂性是指该算法在运行过程中临时占用 _的大小。 数据结构与算法练习试卷 7答案与解析 1 【正确答案】 n-1 【知识模块】 数据结构与算法 2 【正确答案】 先进先出，后进先出 【知识模块】 数据结构与算法 3 【正确答案】 存储结构 【知识模块】 数据结构与算法 4 【正确答案】 数据元素 【知识模块】 数据结构与算法 5 【正确答案】 2n-1， 2n-1， 2n-1 【知识模块】 数据结构与算法 6 【正确答案】 任何，栈顶，队尾，队首 【知识模块】 数据结构与算法 7 【正确答案】 5， 3 【知识模块】 数据结构与算法 8 【正确答案】 15 【知识模块】 数据结构与算法

5、9 【正确答案】 14/9， 13/9 【知识模块】 数据结构与算法 10 【正确答案】 中序 【知识模块】 数据结构与算法 11 【正确答案】 快速排序，基数排序 【知识模块】 数据结构与算法 12 【正确答案】 n-1 【知识模块】 数据结构与算法 13 【正确答案】 顺序存储结构，有序 【知识模块】 数据结构与算法 14 【正确答案】 时间复杂度，空间复杂度 【知识模块】 数据结构与算法 15 【正确答案】 索引，块 【知识模块】 数据结构与算法 16 【正确答案】 edcba 【知识模块】 数据结构与算法 17 【正确答案】 59， 42， 23， 13， 5， 2， 2) 【知识模块】 数据结构与算法 18 【正确答案】 n-1 【知识模块】 数据结构 与算法 19 【正确答案】 相同 【知识模块】 数据结构与算法 20 【正确答案】 简单操作次数，存储空间 【知识模块】 数据结构与算法