模拟试卷二 模拟试卷二 一、选择题（每小题2分，共10分） 在下列备选
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
中选出一个正确的，将其号码填在“ ”上。 1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用 存储方式节省时间。 （1）单链表 （2）双链表 （3）单循环链表 （4）顺序表 2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用 次序的遍历实现编号。 （1）先序 （2）中序 （3）后序 （4）从根开始的层次遍历 3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。 （1）空或只有一个结点 （2）高度等于其结点数 （3）任一结点无左孩子 （4）任一结点无右孩子 4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（nlog2n）的是 。 （1）堆排序 （2）冒泡排序 （3）直接选择排序 （4）快速排序 5．下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 （1）堆排序 （2）冒泡排序 （3）快速排序 （4）SHELL排序 二、判断题（每小题1分，共10分） 判断下列各题是否正确，若正确，在（）内打“√”，否则打“×”。 1． （ ）在循环队列中，若尾指针Rear大于头指针Front，则其元素数为Rear-Front。 2．（ ）串是N个字母的有限序列（N=0）。 3．（ ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 4．（ ）二叉树只采用二叉多链表来存储。 5．（ ）有向图用邻接矩阵表示后，顶点I的出度等于第I行中非0且非的元素个数。 6．（ ）图Ｇ的最小生成树的代价一定小于其他生成树的代价。 7．（ ）给定结点数的平衡二叉树的高度是唯一的。 8．（ ）９阶Ｂ树中，除根以外的任一结点中的关键字个数不少于４。 9．（ ）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。 10．（ ）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。 三、填空（每小题２分，共２０分） 1．在单链表中，册除指针Ｐ所指的后继结点的语句是 。 2．取出广义表Ａ＝（（x,y,z ）），（a,b,c,d））中原子b的函数是 。 3．已知完全二叉树的第八层有８个结点，则其叶子结点是 。 4．将下三角矩阵Ａ［８，８］的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占４个单元，则Ａ[7,5]的地址为 。 5．有n个顶点的强连通有向图Ｇ至少有 条弧。 6．求最短路径牟DIJKSTRA算法的时间复杂度为 。 ７．高度为５的三阶Ｂ树至少有 个结点。 ８．在有序表Ａ[20]中，采用二分查找算法查找元素值等于Ａ［１２］的元素，所比较过的元素的下标依次为 。 ９．直接选择排序算法所执行的元素交换次数最多为 。 １０．下列排序算法中，稳定的排序算法是 （选择排序，堆排序，快速排序，直接插入排序。） 四、解答下列各题（３０） １．一棵二叉树的先序序列和中序序分别如下，画出该二叉树。（５分） 先序序列ABCDEFGHIJ 中序序列CBEDAGHFJI ２．对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。（６分） ４，５，６，７，１０，１２，１５，１８。２３ ３．图Ｇ的邻接表如下面，完成下列各题：（７分） （１）画出从顶点５出发进行广度遍历所生成的生成树。 （２）判断其中否存在有向回路，若不存在，求出其拓扑序列。 ４．对下列数据表，写出采用快速排序算法排序的每一趟的结果。（６分） （60,20,31,1,5,44,55,61,200,30,80,150,4,29） 1 2 3 4 5 6 7 8 9 10 11 12 ５．已知哈希表地址空间为０．．８，哈希函数为Ｈ(k)＝k mod ７，采用线性探查法处理冲突。 将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。 （６分） １００，２０，２１，３５，３，７８，９９，４５ 0 1 2 3 4 5 6 7 8 A：
浙公网安备 33021202002483