数据结构模拟试卷8

1． 一个栈的输入序列为1 2 3 4 5 ，则下列序列中不可能是栈的输出序列的是___________。 A.1 2 3 4 5 B.5 4 3 2 1 C.2 3 4 5 1 D.4 1 2 3 5

2． 一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为___________。 A.0 B.1 C.2 D.不确定

3． 在用邻接表表示图的情况下，拓扑排序算法的时间复杂度为___________。 A.o(n+e) B.o(n2) C.o(n*e) D.o(n3)

4． 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影

响的是___________。

A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序

5． 下列排序算法中，依次将待排序序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是

___________。

A.直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序 二、 判断题

1． 设指针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)。 三、 填空题

1． 在单链表中，在指针P所指结点的后面插入一个结点S^的语句序列是___________。

2． 已知一个栈的输入序列为123…n，则其输出序列的第二个元素为n的输出序列的个数是___________。 3． 取出广义表A=((a,x,y,z)，（b,c）)中的原子c的复合函数是___________。

4． 若以｛4,5,6,7,8｝作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。 5． 在顺序存储的二叉树中，编号为I和j的两个结点处在同一层的条件是___________。 6． 已知二叉树有50个叶子结点，则该二叉树的总结点数至少是___________。

7． 在按关键字递增的数组A〔1..20〕中，按二分查找方法进行查找时，查找长度为5的元素个数是

___________。

8． 已知数据A[1..10,0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续的

存储区域时，A[5,9]的地址是___________。

9． 有n个球队参加的足球联赛按主客场制进行比赛，共需进行___________场比赛。

10．下列排序算法中，占用辅助空间最多的是___________（堆排序，希尔排序，快速排序，并归排序）。 四、 解答题

1． 一棵二叉树的先序、中序和后序序列如下，其中一部分未标出，请构造该二叉树。 先序序列：_CDE_GHI_K 中序序列：CB_ FAJKIG 后序序列：_EFDB_JIH_A 2． 将下面数据表建成一个堆。

(70 ,12 ,20 ,32 ,1 ,5 ,44 ,66 ,61 ,200 ,30 ,80 ,150 ,4 ,28) 3． 求出下图中顶点1到其余各顶点的最短路径。

4． 已知下面二叉排序树的各结点的值依次为1-9，请标出各结点的值。