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

模拟试卷八 一、选择题（每小题2分，共10分） 1．一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是 。 （l）12345 （2）54321 （3）23451 （4）41235 2．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为 。 （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分，共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]中，按二分查找方法进行查找时，查找长度为5 的元素个数是。 8. 已知数组A[1..10，0..9]中每个元素占 4个单元，在按行优先方式将其存储到 起始地址为1000的连续的存储区域时，A［5，9］的地址是 。 9．有n个球队参加的足球联赛按主客场制进行比赛，共需进行 场比赛。 10. 下列排序算法中，占用辅助空间最多的是 （堆排序，希尔排序，快速 排序，归并排序）。 四、解答下列各题（20分） 1．一棵二叉树的先序、中序和后序序列如下，其中一部分本标出，请构造出该二 叉树。 先序序列： CDE GHI K 中序序列：CB FA JKIG 后序序列：