《数据结构》模拟试卷.docVIP

模拟试卷二 一、选择题（每小题2分，共10分） 1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用 存储方 式节省时间。 a．单链表 b. 双链表 c．单循环链表 d．顺序表 2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号， 同一个结点的左右孩子中， 其左孩子的编号小于其有孩子的编号， 则可采用 次序的遍历实现编号。 a．无序 b．中序 c．后序 d．从根开始的层次遍历 3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二又树。 a．空或只有一个结点 b. 高度等于其结点数 C．任一结点无左孩子 d．任一结点无右孩子 4．下列排序算法中，时间复杂度不受数据初始状态影响， 恒为 O（nlog2n）的是 。 a．堆排序 b. 冒泡排序 c．直接选择排序 d. 快速排序 5. 下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费 的时间反而最多。 a．堆排序 b．冒泡排序 c．快速排序 d. SHELL排序 二、判断题（每小题1分，共10分） 1．（ ）在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为 Rear - Front。 2．（ ）串是n个字母的有限序列（n = 0）。 3. ( ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 4．（ ）二叉树只能采用二又链表来存储。 5.（ ）有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非加 的元素个数。 6．（ ）图G的某一最小生成树的代价一定小于其他生成树的代价。 7.（ ）给定结点数的平衡二叉树的高度是唯一的。 8.（ ）9阶B树中，除报以外的任一结点中的关键字个数不少于4。 9．（ ）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。 10.（ ）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将 被调到“叶子结点”上。 三、项空（每小题2分，共20分） l. 在单链表中，删除指针P所指结点的后继结点的语句是 。 2．取出广义表A = ((x，y，z），（a，b，c，d）)中原子b的函数是 。 3．已知完全二叉树的第八层有8个结点，则其叶子结点数是 。 4. 将下三角矩阵A[1..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存 单元中，已知每个元素占4个单元，则A［7，5］的地址为 。 5. 有n个顶点的强连通有向图G至少有 条弧。 6．求最短路径的Dijkstra算法的时间复杂度为 。 7．高度为5的三阶B树至少有 个结点。 8．在有序表A[1..20]中，采用二分查找算法查找元素值等于A「12」的元素，所比 较过的元素的下标依次为 。 9．直接选择排序算法所执行的元素交换次数最多为 。 10. 下列排序算法中，稳定的排序算法是 。（选择排序，难排序，快速排 序，直接插入排序）。 四、解答下列各题（30分） 1. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。（5分） 先序序列 ABCDEFGHIJ 中序序列CBEDAGHFJI 2. 对下面给出的数据序列