文档介绍：《数据结构与算法》模拟题
一、填空题：（共 15 分）（每空一分）
1. 按照排序时，存放数据的设备，排序可分为 <1> 内部排
序和<2> 外部排序。
2. 图的常用的两种存储结构是 <3> 邻接矩阵存储和<4>
邻接表面存储。
3. 数据结构中的三种基本的结构形式是 <5> x 线性结构
和<6> 树形结构、<7> 图形结构。
4. 一个高度为 6 的二元树，最多有 <8> 63 个结点。
5. 线性查找的时间复杂度为： <9> ，折半查找的时
间复杂度为： <10> 、堆分类的时间复杂度
为：<11> 。
6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数
必须具有较好的随机性，在我们介绍的几种散列函数构造法
中，随机性最好的是 <12>随机数法、最简单的构造方法
是<13> 除留余数法。
7. 线性表的三种存储结构是：数组、 <14> 链表、<15>
静态链表。
二、回答下列问题：（共 30 分）
1. 现有如右图的树，回答如下问题：
A）根结点有：
6
B）叶结点有：
5
学号：姓名：
C）具有作大度的结点： 9 和 10
D）结点的祖先是： 0 和 2
E）结点的后代是： 10
2. 栈存放在数组 A[m]中，栈底位置是 m-1。试问：
A）栈空的条件是什么？
B）栈满的条件是什么？
3. 数据结构和抽象数据型的区别与联系：
4. 已知一株非空二元树，其先根与中根遍历的结果为：
先根： ABCDEFGHI
中跟： CBEDAGFHI
将此二元树构造出来。
第 2 页（共 12 页）
学号：姓名：
5.
分析下列程序的运行时间：
A) 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 页（共 12 页）
学号：姓名：
2
6. 已知数学表达式是 (3+b)sin(x+5) — a/x ，求该表达式的波兰
表示法的前缀和后缀表示（要求给出过程）。