快速排序
B堆排序
C归并排序
D插入排序
10下列四种排序中（）的空间复杂度最大。
A插入排序
B冒泡排序
C堆排序
D归并排序
二、填空殖每空1分共20分1数据的物理结构主要包括_____________和______________两种情况。2设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉
树的存储结构，则共有___________个空指针域。3设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。4设有向图G用邻接矩阵A
作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的
________，第i列上所有元素之和等于顶点i的________。5设哈夫曼树中共有
个结点，则该哈夫曼树中有________个度数为1的结点。6设有向图G中有
个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。7__________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。
5
f8设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。
9不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。
10设有
个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。
11设一组初始记录关键字为72，73，71，23，94，16，5，则以记录关键字72为基准的一趟快速排序结果为___________________________。
12设有向图G中有向边的集合E1，2，2，3，1，4，4，2，4，3，则该图的一种拓扑序列为____________________。
13下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。structrecordi
tkeyi
tothersi
thashsqsearchstructrecordhashtablei
tki
tijjikpwhilehashtablejkeykhashtablejflag0j____mifijretur
1if_______________________retur
jelseretur
1
14下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedefstruct
odei
tkeystruct
odelchildstruct
oderchildbitreebitreebstsearchbitreeti
tkift0retur
0elsewhilet0iftkeyk_____________elseiftkeykttlchildelse_____________
三、计算题每题10分，共30分
1已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。
2．已知待散列r