数据结构第二次作业答案
学号：学号一单项选择题20分选择题20选择题1一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为_________。ba、0b、1c、2d、不确定2下列排序算法中时间复杂度不受数据初始状态影响，恒为O
2的是__________。ca、堆排序b、起泡排序c、直接选择排序d、快速排序3设图的顶点数
边数e，若用邻接表表示图，那么求最短路径的Dijkstra算法的时间复杂度为_________。baO
ebO
2cO
edO
34下面程序段的时间复杂度是_________。di1whilei
ii2aO
bO
2cO2
dOlog2
5在有
0个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为___________。baO
bOlog2
cO
log2
dO
26采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为________个结点最佳。ba10b25c6d6257已知数据表中的每个元素距其最终位置不远，则采用_______排序算法最省时间。ba堆排序b插入排序c快速排序d直接选择排序8某二叉树的先序序列和后序序列正好相反，则该二叉树一定是________的二叉树。ba空或只有一个结点b高度等于其结点数（空树高度为0）c任一结点无左孩子d任一结点无右孩子9一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为_________。aa2b1c0d不确定10假设图的顶点数
边数e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为_________。baO
2bO
ecO
edO
3填空作图简答题（二填空作图简答题（共64分）：1依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树，画出该平衡二叉树形成过程及其中序线索二叉树。
3030303021432143919219215143154315433030
姓名：姓名
评分：评分

f有一组关键码序列40，20，60，15，50，45，95，10，75，采用Shell排序方法从小到大进行排序，假设其间隔序列为5，3，1，请写出每趟的结果。第1趟：40，20，10，15，50，45，95，60，75第2趟：15，20，10，40，50，45，95，60，75第3趟：10，15，20，40，45，50，60，75，952
3
对下面的3阶B树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。
2010281216304050
1062814401216305060
4
用Prim算法求下图的最小生成树若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。
3167445386515775822r