Question

高分急求！！！！数据结构与算法试题！！！

1、树的后序遍历相当于该树转换成的二叉树的( )遍历？
A．前序遍历
B．中序遍历
C．后序遍历
D．层序遍历
2、已知某无向图具有n个顶点和e条边，采用邻接矩阵表示法，该邻接矩阵为( )行( )列？
A．n n
B．e e
C．e n
D．n e
3、已知记录 (46,74,53,14,26,38,86,65,27,34)，分别给以下排序方法的第一趟排序结果。
（1）冒泡排序
（2）快速排序（以第一个元素作基准）
（3）直接插入排序
（4）直接选择排序
（5）基数排序第一趟分配收集
（6）归并排序
4、假定一组数据对象为 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每个对象生成一棵高度平衡的二叉排序树（左右子树的高度差不超过1），请回答以下问题:
(1) 在插入16时需要进行____________________操作, 使树保持平衡。
(2) 在插入50时需要进行___________________操作, 使树保持平衡。
(3) 在插入32时需要进行____________________操作, 使树保持平衡。
5、线性表按链接方式存储时, 每个结点的存储包括________和________两部分。
6、已知一棵二叉树的前序和中序序列如下，求该二叉树的高度（假定空树的高度为0）,列出所有度为2的结点、叶结点，并写出后序遍历序列。
前序序列： A, B, C, D, E, F, G, H, I, J
中序序列： C,B, A, E, F, D, I, H, J, G
（1）二叉树的高度为：________
（2）度为2的结点有：________
（3）度为1的结点有：________
（4）叶子结点有：_________
（5）后序遍历序列为：______
（6）层序遍历序列为：______
7、______结点一定没有兄弟结点
8、n个结点组成的所有不同形态的二叉树中，高度最高为______，高度最矮为______。

给出答案就行，详细过程不用写，谢谢。

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.总之“抽象数据类型”是“物理”概念，“数据结构”是“逻辑”概念。“抽象数据类型”来实现“数据结构”。