1 / 3 模拟试卷八一、选择题（每小题2 分，共 10 分） 1．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是。（l ）12345 （2）54321 （3）23451 （4）41235 2．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为。（1）0 （2）1 （3）2 （4）不确定 3．在用邻接表表示图的情况下，拓扑排序算法的时间复杂度为。（l ） O（n＋e）（2） O（n2）（3） O（n×e）（4） O（n3） 4．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是。（1）直接插入排序（2）快速排序（3）直接选择排序（4）堆排序 5．下列排序算法中，依次将待排序序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是。（1）直接插入排序（2）冒泡排序（3）快速排序（4）直接选择排序二、判断题（每小题1 分，共 10 分）l ．（）设指针 P 指向单链表中一个结点，则语句序列U:=P^.next ； U :=U^.next 将删除一个结点。 2．（）栈和队列都是运算受限的线性表。 3．（）广义表的长度是指广义表中的原子个数。 4．（）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。 5.（）二叉树在按任一种次序线索化后，都可以很容易地求出相应次序下的前趋和后继。 6.（）在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 7.（）对 B 树中任一非叶子结点中的某关键字K，比 K 小的最大关键字和比K 大的最小关键字一定都在叶子结点中。8．（）若一个无向图的以顶点1 为起点的深度遍历序列唯一，则可唯一确定该图。 9．（）在对一有向无环图执行拓扑排序算法之后，入度数组中的所有元素的值为 0。 10.（）在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O（n）。2 / 3 三、填空题（每小题2 分，共 20 分） 1．在单链表中，在指针P 所指结点的后面插入一个结点到的语句序列是。 2．已知一个栈的输入序列为123...n，则其输出序列的第二个元素为n 的输出序列的个数是。 3．取出广义表A=((a ，x，y，z），（b，c）) 中的原子 c 的复合函数是。4．若以｛ 4，5， 6，7，8｝作为叶子结点的权值构造哈夫曼树，则其带权路径长度是。 5. 在顺序存储的二叉树中，编号为i 和 j 的两个结点处在同一层的条件是。 6．已知二叉树有5O个叶子结点，则该二叉树的总结点数至少是。 7. 在按关键字递增的数组A[1..20]中，按...
