《数据结构》模拟试卷八

试一、选择题（每题分，共10分一个的输入序列为12345则列序列不可能是栈的输出序列的是。（）12345（54321（）23451（41235．一棵左子树为空的二叉树在序线索化后，其中的空链域的个为。（）（）（）（）确定．在用邻接表表示图的情况下拓扑排序算法的时间复杂度为。（）（n＋）（2）On）（）（n×）（4）On）．下列排序算法中，在每一趟能选出一个元素放到其最终位置，并且其时间性能受数据初始特影响的是。（）直接插入排序（2）快速排序（）直接选择排序（4）堆排序．下列排序算法中，依次将待序序列中的元素和前面有序序列并为一个新的有序序列的排序法是。（）直接插入排序（2）冒泡排序（）快速排序（4）直接择排序二、判断题（每题分，共10分l）设指针P向单链表中一个点句序列U:=U^.next将删除一个结点2）和队列都是运算限的线性表。3）义表的长度是指义表中的原子个数。4）某二叉树的叶子点数为1，则其先序列和后序序列一定相反。5.（）二叉树在按任一种序线索化后，都可以很容易地求出相应次序下的前趋和后继。6.（）在采用线性探测法理冲突的散列表中，所有同义词在表中相邻。7.（）对B树中任一非叶结点中的某关键字K比小最大关键字和比K大的最小关键字定都在叶子结点中。8）若一个无向图的以点为起点的深度遍历序列唯，则可唯一确定该图。9）对一有向无环图行拓扑排序算法之后，入度数组中的所有元素的值为0。10.）数据表基本有序时，冒泡排序算的时间复杂度一定接近On1/3

三、填空题（每题分，共20分．在单链表中，在指针P所指点的后面插入一个结点到的语序列是。．已知一个栈的输入序列为123...n，则其输出序列第二个元素为的输出序列的个数是。．取出广义表A=((ax，，z）)中的原子c的合函数是。4．若以4，，，7，｝作为叶子结点的权值构造哈夫曼树，则其带权路径长是。5.在序存储的二叉树中，编为和j的个结点处在同一的条件是。．已知二叉树有5O个子结点，则该二叉树的总结点数至少是。7.在关键字递增的数组A[1..20]中按二分查找方法进行查找时，找长度为5的元素个数是。8.知数组，0..9]中个元素4单元，在按行优先方式将其存到起始地址为1000的续的存储区域时A［，］的址是。．有n球队参加的足球联赛主客场制进行比赛，共需进行场赛。10.下列排序算中，占用辅助空间最多的是（排序，希尔排序，快速排序，归并排序四、解答下列各20分）．一棵二叉树的先序、中序和序序列如下，其中一部分本标出请构造出该二叉树。先序序列：CDEGHIK中序序列：CBFAJKIG后序序列：EFDBJIH．将下面数据表建成一个堆。（70，，20，311，544，66，，2O0，30，，15O，28．求出下图中顶点1到其各点的最短路径。4．已知下面二叉排序树的各结点的值依次为1～，请标出各结点的值五、算法设计（分，每题分）2/3

．已知递增有序的单链表AB分存储了一个合。设计算法以求出两个集合A，B的集AB即仅由在A出现而不在B中出的元素所构成的集合以同样的形式存储同时返回该集合的元素个数。．设计算法以返回二叉树的后序序列的第一个结点的指针。求采用非递归形式，且不用栈。．已知二叉树T以二链表形作为其存储结构。设计算法按先序次序输出各结点的值及相应的层数，并以二元组的形式给出。下面的二叉树及对应的输出如下页图所示。（，1，，，4，，，，，4）4．已知数组的素类型为integer。计算法将其调整