友情提示:本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案,部分学校更新至2012年,2013年;均提供收费下载。 下载流程: 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
科目代码:405 请在答题纸(本)上做题,在此试卷或草稿纸上做题无效! 山东科技大学 2006 年招收硕士学位研究生入学考试 数据结构与离散数学试卷 数据结构部分 (共 3 页) 注意事项: 1、算法应说明基本思路,应对主要数据类型、变量给出说明,所写算法应给构清晰、简明 易懂,应加上必要的注释。 2、算法可用(类)PASCAL 语言、(类)C 语言等你所熟悉的高级语言编写,但要注明语种。 一、解答下列问题(共 30 分): 1、[5 分]度量一个程序的执行时间通常有哪几种方法?各有何优缺点? 2、[5 分]如果元素的进栈序列为 123456,问能否得到 435612 和 135426 的出栈序列?请说 明为什么不能得到或者如何得到。 3、[5 分]串是一种特殊类型的线性表,请你从串的存储及操作两方面分析它特殊在什么地 方? 4、[5 分]给出树的层次遍历序列与后序遍历序列能否唯一确定一棵树?(如能请说明原因, 如不能请举例说明。) 5、[5 分]设有三对角矩阵(aij)n*n,将其三条对角线上的元素逐行地存于数组 B[3n-2],使得 B[k]= aij,求用 i, j 表示 k 的下标变换公式。 6、[5 分]基于比较的查找算法所能达到的最优时间复杂度是?基于比较的排序算法所能达到 的最优时间复杂度是? 二、[10 分]森林的中序遍历结果为 DECBAFIKLG,先序遍历结果为 ADCEBIFGKL,要求: 1、画出此森林。 2、将其转换为二叉树。 3、将得到的二叉树后序线索化。 三、[15 分]定义链栈数据类型,并编写函数实现链栈入栈操作。 四、[15 分]2 路归并排序的一种策略是,先对待排序序列扫描一遍,找出并划分为若干个最 大有序子列,将这些子列作为初始归并段。试在链表结构上实现这一排序算法。 五、[15 分]试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存 储结构。且树中结点的关键字均不同。 六、[15 分]试写一算法,在图 G 中求一条从顶点 Vi 到顶点 Vj 的简单路径。 科目代码:405 请在答题纸(本)上做题,在此试卷或草稿纸上做题无效! 山东科技大学 2006 年招收硕士学位研究生入学考试 数据结构与离散数学试卷 离散数学部分 (共 1 页) 一.(12 分)求 )( RPQP 主析取范式和主合取范式。 二.(12 分)设集合 A={a, b, c},A 的幂集为 (A),画出偏序集< (A),>的哈斯图;若 B={{ a, b},{ b, c},{b}},求 B 的极大元和极小元、最大元和最小元、上界和下界、上确 界和下确界。 三.(16 分)设和都是群的子群,HK= KkHhkh , ,证明: 是的子群的充要条件是 HK=KH。
免责声明:本文系转载自网络,如有侵犯,请联系我们立即删除,另:本文仅代表作者个人观点,与本网站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
|