数据结构精选考研试题

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

数据结构精选考研试题

[注]:编写程序可选用任一种高语言,算法描述可采用类语言,必要时加上注释 一、 回答下列问题:[20分] 1、 算法的定义和性质 2、 为什么说数组与广义表是线性表的推广? 3、 什么是结构化程序设计? 4、 哈希方法的基本思想 5、 给出一不稳定排序方法名称与实例 二、 构造结果:[24分] 确定x:=x+1语句在下面程序段中的频率,要求写出分析过程。 for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 画出对长度为8的有序表进行折半查找的判定树,并求其在等概率时查找成功的平均查找长度。 已知一棵二叉树如右图,给出对这棵二叉树进行前序、中序、后序遍历的结果序列. 假设用于通讯的电文仅8个字母组成,字母在电文中出现的频率

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 1 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

分别为{2,3,5,7,11,4,13,15},试为这8个字母设计哈夫曼编码. 在地址空间为0~15的散列区中,对以下关键字序列构G造哈希表,关键字序列为,H(x)=[i/2] ,其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突,并求出在等概率情况下查找成功的平均查找长度。 构造有7个元素组成的线性表一实例,是进行快速排序时比较次数最少的初始排序。 三、 写一算法,完成对这棵二叉树的左右子树的交换,设二叉树以二叉链表作存储结构。[15分] 四、 编写一非递归算法,对一棵二叉排序树实现中序遍历。[15分] 五、 编

写程序,完成下列功能:[15分] 1. 读入整数序列,以整数0作为序列的结束标志,建立一个单链表。 2. 实现单链表原地逆转,即单链表中结点指针方向反转,反转操作不使用额外的链表结点,可使用临时工作单元。 例:输入序列为:1,8,4,3,0 六、

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 2 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

给出有向图G的邻接表表示。找出其一棵最小生成树。[11分] [注]:编写程序可选用任一种高语言,算法描述可采用类语言,必要时加上注释 一、 回答下列问题:[20分] 1、 算法的定义和性质 2、 为什么说数组与广义表是线性表的推广? 3、 什么是结构化程

序设计? 4、 哈希方法的基本思想 5、 给出一不稳定排序方法名称与实例 二、 构造结果:[24分] 确定x:=x+1语句在下面程序段中的频率,要求写出分析过程。 for i:=1 to n do for j:=1 to I do for k:=1 to j do x:=x+1 画出对长度为8的有序表进行折半查找的判定树,并求其在等概率时查找成功的平均查找长度。 已知一棵二叉树如右图,给出对这棵二叉树进行前序、中序、后序遍历的结果序列. 假设用于通讯的电文仅8个字母组成,字母在电文中出现的频率分别为{2,3,5,7,11,4,13,15},试为这8个字母设计哈夫曼编

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 3 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

码. 在地址空间为0~15的散列区中,对以下关键字序列构G造哈希表,关键字序列为,H(x)=[i/2] ,其中i为关键字中第一字母在字母表中的序号。要求用线性探测开放定址法处理冲突,并求出在等概率情况下查找成功的平均查找长度。 构造有7个元素组成的线性表一实例,是进行快速排序时比较次数最少的初始排序。 三、 写一算法,完成对这棵二叉树的左右子树的交换,设二叉树以二叉链表作存储结构。[15分] 四、 编写一非递归算法,对一棵二叉排序树实现中序遍历。[15分] 五、 编

写程序,完成下列功能:[15分] 1. 读入整数序列,以整数0作为序列的结束标志,建立一个单链表。 2. 实现单链表原地逆转,即单链表中结点指针方向反转,反转操作不使用额外的链表结点,可使用临时工作单元。 例:输入序列为:1,8,4,3,0 六、 给出有向图G的邻接表表示。找出其一棵最小生成树。[11分] [注] 编

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 4 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

写程序可选用PASCAL 或 C 语言 算法描述采用类语言,应加上必要的注释 所有答案均要求写在答题纸上 一、 回答问题 [15分] 1.结构化程序设计 2.面向对象开发方法与面向过程开发方法的不同之处 3.数据类型含义与作用 4.稳定排序与不稳定排序 二、简述方法与原因 [20分] 1.分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序,给出最省时间与最费时间的算法名称,简述原因。 2.实现有向图的拓扑排序能否用图的深度搜索模式来查找?若能请简述方法,若不能,请简述原因。 3.有n个非零的数,仅要求将负数排列在正数的前面,但并不要求对其排序,简述处理方法。 4.说明在图的遍历中,设置访问标志数组的作用。 5.在一个连通无向图上,欲求从一点VI到另一点VJ所经结点数目最少的路径,在深度优先搜索、广度优先搜索、从一

~ 5 ~

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4