内容发布更新时间 : 2024/11/9 14:40:33星期一 下面是文章的全部内容请认真阅读。

精品文档

《数据结构与算法》模拟题

一、填空题：（共15分）（每空一分）

1. 按照排序时，存放数据的设备，排序可分为<1> 排

序和<2> 排序。

2. 图的常用的两种存储结构是<3> 和<4> 。

3. 数据结构中的三种基本的结构形式是<5> 和

<6> 、<7> 。 4. 一个高度为6的二元树，最多有<8> 个结点。 5. 线性查找的时间复杂度为：<9> ，折半查找的时间复杂度为：<10> 、堆分类的时间复杂度为：<11> 。

6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数

必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12> 法、最简单的构造方法是<13> 。

7. 线性表的三种存储结构是：数组、<14> 、

<15> 。

二、回答下列问题：（共30分）

1. 现有如右图的树，回答如下问题：

A） 根结点有：

B） 叶结点有：

精品文档

精品文档

C） 具有作大度的结点：

D） 结点?的祖先是：

E） 结点?的后代是：

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

B） 栈满的条件是什么？

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

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

分析下列程序的运行时间： A) void mystery(int n)

{int i, j, k;

for(i=1; i

{some statement requiring O(1) time;}

2.

3.

4.

5.

精品文档

精品文档

}

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; } }

6. 已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表

示法的前缀和后缀表示（要求给出过程）。

精品文档

精品文档

三、实现下列算法：（共３0分）

1. 在指针实现的线性表L中，实现在线性表L 中删除关键字为

x的结点。(共7分)

2. 设有如下图的双向环形链表L=(a, b, c, d) 。请写出将该表转

换为L=(b, a, c, d)的简单操作。（共7分） L a b LL D RL c d

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

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

精品文档

精品文档

四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）

? 14

28 16

25 ?18 ?

? 精品文档