[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质
2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？
4、 哈希方法的基本思想
5、 给出一不稳定排序方法名称与实例
二、 构造结果：[24分]
（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do
for j:=1 to I do
for k:=1 to j do x:=x+1
（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。
（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．
（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．
（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。
（6） 构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、 写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分]
四、 编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分]
五、 编写程序，完成下列功能：[15分]
1． 读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。 2． 实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。
例：输入序列为：1，8，4，3，0
六、 给出有向图G的邻接表表示。找出其一棵最小生成树。[11分]
[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质
2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？
4、 哈希方法的基本思想
5、 给出一不稳定排序方法名称与实例
二、 构造结果：[24分]
（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do
for j:=1 to I do
for k:=1 to j do x:=x+1
（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。
（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．
（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．
（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突，并求出在等概率情况下查找成功的平均查找长度。
（6） 构造有7个元素组成的线性表一实例，是进行快速排序时比较次数最少的初始排序。 三、 写一算法，完成对这棵二叉树的左右子树的交换，设二叉树以二叉链表作存储结构。[15分]
四、 编写一非递归算法，对一棵二叉排序树实现中序遍历。[15分]
五、 编写程序，完成下列功能：[15分]
1． 读入整数序列，以整数0作为序列的结束标志（0不作为序列元素），建立一个单链表。 2． 实现单链表原地逆转，即单链表中结点指针方向反转，反转操作不使用额外的链表结点，可使用临时工作单元。
例：输入序列为：1，8，4，3，0
六、 给出有向图G的邻接表表示。找出其一棵最小生成树。[11分]
[注] 编写程序可选用PASCAL 或 C 语言
算法描述采用类语言，应加上必要的注释 所有答案均要求写在答题纸上
一、 回答问题 [15分]
1．结构化程序设计
2．面向对象开发方法与面向过程开发方法的不同之处 3．数据类型含义与作用 4．稳定排序与不稳定排序
二、简述方法与原因 [20分]
1．分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。
2．实现有向图的拓扑排序能否用图的深度搜索模式来查找？若能请简述方法，若不能，请简述原因。
3.有n个非零的数，仅要求将负数排列在正数的前面，但并不要求对其排序，简述处理方法。
4．说明在图的遍历中，设置访问标志数组的作用。
5.在一个连通无向图上，欲求从一点VI到另一点VJ（VI≠VJ）所经结点数目最少的路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径或图的其它算法中，你认为最好选择那种方法为基础，简述原因。
三、构造结果 [25分]
1. 二叉树按二叉链表方式存放，其中的data域为char类型，已
有按前序方式构造二叉树的算法，若输入序列为AB□CD□□ED□G□□□，请给出构造的相应二叉树。
2.已知Ackerman函数定义如下：
n+1 当m=0时
akm(m,n) = akm(m-1,1) 当m≠0,n=0时
akm(m-1, akm(m,n-1)) 当m≠0,n≠0时
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构精选考研试题在线全文阅读。
相关推荐：