哈工大数据结构与算法模拟题.doc

学号： 姓名：数据结构与算法模拟题一、填空题：（共15分）（每空一分）1. 按照排序时，存放数据的设备，排序可分为 排序和 排序。2. 图的常用的两种存储结构是 和 。3. 数据结构中的三种基本的结构形式是 和 、 。4. 一个高度为6的二元树，最多有 个结点。5. 线性查找的时间复杂度为： ，折半查找的时间复杂度为： 、堆分类的时间复杂度为： 。6. 在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是 法、最简单的构造方法是 。7. 线性表的三种存储结构是：数组、 、 。二、回答下列问题：（共30分）1. 现有如右图的树，回答如下问题：A） 根结点有：B） 叶结点有：C） 具有作大度的结点：D） 结点o的祖先是：E） 结点o的后代是：2. 栈存放在数组Am中，栈底位置是m-1。试问：A） 栈空的条件是什么？B） 栈满的条件是什么？ 3. 数据结构和抽象数据型的区别与联系： 4. 已知一株非空二元树，其先根与中根遍历的结果为：先根：ABCDEFGHI 中跟：CBEDAGFHI 将此二元树构造出来。5. 分析下列程序的运行时间：A) void mystery(int n)int i, j, k; for(i=1; in; 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，求该表达式的波兰表示法的前缀和后缀表示（要求给出过程）。三、实现下列算法：（共0分）1. 在指针实现的线性表L中，实现在线性表L 中删除关键字为x的结点。(共7分)2. 设有如下图的双向环形链表L=(a, b, c, d) 。请写出将该表转换为L=(b, a, c, d)的简单操作。（共7分）abcdLL D RLL 3. 在线索二元树中，由结点P求其先根顺序的后继。（共8分）4. 在二元查找树F中，实现插入记录R。（共8分）四、对下面的带权连通无向图，用Prim（普里姆）算法，构造一株最小生成树。画出构造过程的每一步。（12分）jklmop1028161222251418n24五、设要分类的数据存放在数组A3141592653中。要进行堆分类，首先得为其建立一个初始堆，试画出初始建堆过程中，二元树的变化和数组A的变化。（共13分）个人工作业务总结本人于2009年7月进入新疆中正鑫磊地矿技术服务有限公司(前身为“西安中正矿业信息咨询有限公司”)，主要从事测量技术工作，至今已有三年。在这宝贵的三年时间里，我边工作、边学习测绘相专业书籍，遇到不懂得问题积极的请教工程师们，在他们耐心的教授和指导下，我的专业知识水平得到了很到的提高，并在实地测量工作中加以运用、总结，不断的提高自己的专业技术水平。同时积极的参与技术培训学习，加速自身知识的不断更新和自身素质的提高。努力使自己成为一名合格的测绘技术人员。在这三年中，在公司各领导及同事的帮助带领下，按照岗位职责要求和行为规范，努力做好本职工作，认真完成了领导所交给的各项工作，在思想觉悟及工作能力方面有了很大的提高。 在思想上积极向上，能够认真贯彻党的基本方针政策，积极学习政治理论，坚持四项基本原则，遵纪守法，爱岗敬业，具有强烈的责任感和事业心。积极主动学习专业知识，工作态度端正，认真负责，具有良好的思想政治素质、思想品质和职业道德。 在工作态度方面，勤奋敬业，热爱本职工作，能够正确认真的对待每一项工作，能够主动寻找自己的不足并及时学习补充，始终保持严谨认真的工作态度和一丝不苟的工作作风。 在公司领导的关怀以及同事们的支持和帮助下，我迅速的完成了职业角色的转变。一、回顾这四年来的职业生涯，我主要做了以下工作：1、参与了新疆库车县新疆库车县胡同布拉克石灰岩矿的野外测绘和放线工作、点之记的编写工作、1:2000地形地质图修测、1:1000勘探剖面测量、测绘内业资料的编写工作，提交成果新疆库车县胡同布拉克石灰岩矿普查报告已通过评审。2、参与了库车县城北水厂建设项目用地压覆矿产资源评估项目的室内地质资料编写工作，提交成果为库车县城北水厂建设项目用地压覆矿产资源评估报告，现已通过评审。3、参与了新疆库车县巴西克其克盐矿普查项目的野外地质勘查工作，参与项目包括：1:2000地质测图、1:1000勘查线剖面测量、测绘内业资料的编写工作；最终提交的新疆库车县康村盐矿普查报告已通过评审。4、参与了新疆哈密市南坡子泉金矿2009年度矿山储量监测工作，项目包括：野外地质测量与室内地质资料的编写，提交成果为新疆哈密市南坡子泉金矿2009年度矿山储量年报，现已通过评审。6、参与了新疆博乐市五台石灰岩矿9号矿区勘探项目的野外地质勘查工作，项目包括：1:2000地质测图、1:1000勘探剖面测量、测绘内业资料的编写工作，并绘制相应图件。7、参与了新疆博乐市托特克斜花岗岩矿详查报告项目的野外地质勘查工作，项目包括：1:2000地质测图、1:1000勘探剖面测量、测绘内业资料的编写工作，并绘制相应图件。通过以上的这些工作，我学习并具备了以下工作能力： 1、通过实习，对测绘这门学科的研究内容及实际意义有了系统的认识。加深对测量学基本理论的理解，能够用有关理论指导作业实践，做到理论与实践相统一，提高分析问题、解决问题的能力，从而对测量学的基本内容得到一次实际应用，使所学知识进一步巩固、深化。2、熟悉了三、四等控制测量的作业程序及施测方法，并掌握了全站仪、静态GPS、RTK等测量仪器的工作原理和操作方法。3、掌握了GPS控制测量内业解算软件（南方测绘 Gps数据处理）以及内业成图软件（南方cass）的操作应用。能够将外业测量的数据导入软件进行地形图成图和处理。4、在项目技术负责的指导下熟悉了测量技术总结的编写要求和方法，并参与了部分项目测量技术总结章节的编写工作。5、在项目负责的领导下参与整个测量项目的组织运作，对项目的实施过程有了深刻理解。通过在项目组的实习锻炼了自己的组织协调能力，为以后的工作打下了坚实基础。二、工作中尚存在的问题 从事测绘工作以来，深深感受到工作的繁忙、责任的重大，也因此没能全方位地进行系统地学习实践，主要表现为没有足够的经验，对于地形复杂的地段理解不够深刻；理论知识掌握不够系统，实践能力尚为有限。以上问题，在今后工作中自己将努力做到更好。三、今后的工作打算 通过总结四年来的工作，我无论从工作技术上，还是从世界观、人生观、价值观等各个方面，都有了很大的提高。今后，我会在此基础上，刻苦钻研，再接再厉，使自己在业务知识水平更上一层楼，为测绘事业的发展，贡献自己的力量。第7页（共7页）