Question

高分求此套数据结构与算法模拟题 完整正确答案

1. 按照排序时，存放数据的设备，排序可分为<1> 排序和<2> 排序。
2. 图的常用的两种存储结构是<3> 和<4> 。
3. 数据结构中的三种基本的结构形式是<5> 和<6> 、<7> 。
4. 一个高度为6的二元树，最多有<8> 个结点。
5. 线性查找的时间复杂度为：<9> ，折半查找的时间复杂度为：<10> 、堆分类的时间复杂度为：<11> 。
6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12> 法、最简单的构造方法是<13> 。
7. 线性表的三种存储结构是：数组、<14> 、<15> 。
二——

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

A） 根结点有：

B） 叶结点有：

C） 具有作大度的结点：

D） 结点o的祖先是：

E）结点o的后代是：

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

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

4. 已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI 中跟：CBEDAGFHI
将此二元树构造出来。
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;
}
}

6. 已知数学表达式是(3+b)sin(x+5)—a/x2，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。
三、实现下列算法：（共30分）
1. 在指针实现的线性表L中，实现在线性表L 中删除关键字为x的结点。(共7分)
2. 设有如下图的双向环形链表L=(a, b, c, d) 。请写出将该表转换为L=(b, a, c, d)的简单操作。（共7分）

a
b
c
d
LL D RL
L

3. 在线索二元树中，由结点P求其先根顺序的后继。（共8分）
4. 在二元查找树F中，实现插入记录R。（共8分）





Answer 1

1.内部排序和外部排序
2.邻接表和十字链表
3.线性表，树，图
4.63
5.θ（n），θ（lg n），θ（n lg n）
6.直接定址法，随机法
7.链表
8.根节点0，叶节点4,9,10,7,8，最大度的是0，节点0的后代是1,2,3
9.空的条件栈顶位置是m-1.满的条件是栈顶位置是-1
10，数据结构和抽象数据类型关系：a.“数据结构”定义为一个二元组（D，S），即两个集合，D是数据元素的集合，S是数据元素之间一个或多个关系的集合。
b.“抽象数据类型”本质是“数据类型”，与计算机相关，涉及数据的存储及如何用存储来反应数据元素之间的关系。它定义为一个三元组（D，S，P），加上的P是定义的一组针对存储的数据操作（如插入，删除，排序等）。
c.总之“抽象数据类型”是“物理”概念，“数据结构”是“逻辑”概念。“抽象数据类型”来实现“数据结构”。

追问

其他的那些大题能解决不，我加分求