Question

数据结构与算法题需要回答

《数据结构与算法》模拟题
一、填空题：（共15分）（每空一分）
按照排序时，存放数据的设备，排序可分为<1> 排序和<2> 排序。内部排序和外部排序
图的常用的两种存储结构是<3> 和<4> 。邻接矩阵和邻接表
数据结构中的三种基本的结构形式是<5> 和<6> 、<7> 。
一个高度为6的二元树，最多有<8> 个结点。
线性查找的时间复杂度为：<9> ，折半查找的时间复杂度为：<10> 、堆分类的时间复杂度为：<11> 。
在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12> 法、最简单的构造方法是<13> 。
线性表的三种存储结构是：数组、<14> 、<15> 。
二、回答下列问题：（共30分）
现有如右图的树，回答如下问题：
根结点有：

叶结点有：

具有作大度的结点：

结点的祖先是：

结点的后代是：

栈存放在数组A[m]中，栈底位置是m-1。试问：
栈空的条件是什么？
栈满的条件是什么？

数据结构和抽象数据型的区别与联系：

已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI 中跟：CBEDAGFHI
将此二元树构造出来。

分析下列程序的运行时间：
void mystery(int n)
{int i, j, k;
for(i=1; i<n; i++)
for(j=i+1; j<=n; j++)
for(k=1; k<=j; k++)
{some statement requiring O(1) time;}
}

B）void podd(int n)
{int I, j, x, y;
for(I=1; I<=n; I++)
if( odd(I ) )
{for(j=I; j<=n; j++)
x=x+1;
for(j=1; j<=I; j++)
y=y+1;
}
}

已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。

三、实现下列算法：（共30分）
在指针实现的线性表L中，实现在线性表L 中删除关键字为x的结点。(共7分)

设有如下图的双向环形链表L=(a, b, c, d) 。请写出将该表转换为L=(b, a, c, d)的简单操作。（共7分）

在线索二元树中，由结点P求其先根顺序的后继。（共8分）

在二元查找树F中，实现插入记录R。（共8分）

四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）
五、设要分类的数据存放在数组A
3 1 4 1 5 9 2 6 5 3
中。要进行堆分类，首先得为其建立一个初始堆，试画出初始建堆过程中，二元树的变化和数组A的变化。（共13分）

Answer 1

《数据结构与算法》模拟题
一、填空题：（共15分）（每空一分）
按照排序时，存放数据的设备，排序可分为<1> 排序和<2> 排序。内部排序和外部排序
图的常用的两种存储结构是<3> 和<4> 。邻接矩阵和邻接表
数据结构中的三种基本的结构形式是<5> 线性结构 和<6> 树型结构 、图型结构<7> 。
一个高度为6的二元树，最多有<8> 63 个结点。
线性查找的时间复杂度为：<9> O(n^2) ，折半查找的时间复杂度为：<10> O(nlogn) 、堆分类的时间复杂度为：<11> O(nlogn) 。
在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12> 随机数 法、最简单的构造方法是除留余数法<13> 。
线性表的三种存储结构是：数组、<14> 链表 、<15> 静态链表 。
二、回答下列问题：（共30分）
现有如右图的树，回答如下问题：看不见图
根结点有：
叶结点有：
具有最大度的结点：
结点的祖先是：
结点的后代是：
栈存放在数组A[m]中，栈底位置是m-1。试问：
栈空的条件是什么？top=m-1
栈满的条件是什么？top=-1
数据结构和抽象数据型的区别与联系：
数据结构（data structure)—是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。
抽象数据类型（ADT）：是指一个数学模型（数据结构）以及定义在该模型（数据结构）上的一组操作。

Answer 2

第二大题的第四小题
A
B F
C D G H
E I
E是和D相连的，C、D和B相连，I和H相连，G、H和F相连，B、F和A相连