当前位置：文档之家› 山东科技大学823数据结构与操作系统2004—2018考研专业课真题试卷

山东科技大学823数据结构与操作系统2004—2018考研专业课真题试卷

山东科技大学

2018年硕士研究生入学考试试题

考试科目：数据结构与操作系统科目代码：823

《数据结构》部分

一、简答题（30分，每题5分）

1、串、数组、广义表从元素间关系上可以看成线性结构，它们与

一般意义上的线性表相比有何特殊性？

2、借助栈可以实现更复杂的操作，请简述如何利用栈实现对表达

式中括号是否匹配的检验。

3、基于关键字比较的查找算法所能达到最优时间复杂度是？能否

设计一种与问题规模无关的查找算法？请给出基本思路。

4、图的广度优先遍历与树的何种遍历策略相似？请给出简单解释。

5、《数据结构》中经常采用“树形化组织”的方式来整理数据，

比如折半查找表、二叉排序树、大顶堆/小顶堆等，请简述这样

做的优点。

6、何为稳定的排序方法？何为不稳定的排序方法？哪些排序算法

是不稳定的？

二、综合应用题（40分，每题10分）

1、假设用于通信的电文共有8个字母A,B,C,D,E,F,G,H组成，字

母在电文中出现的频率分别是{0.2，0.04，0.06，0.02，0.12，

0.24，0.25，0.07}。

①试为这8个字符设计哈夫曼编码；

②试设计另一种由二进制表示的等长编码方案；

计算机数据结构考研真题及其答案

第1章绪论一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构

考研数据结构必须掌握的知识点与算法-打印版

《数据结构》必须掌握的知识点与算法第一章绪论 1、算法的五个重要特性（有穷性、确定性、可行性、输入、输出） 2、算法设计的要求（正确性、可读性、健壮性、效率与低存储量需求） 3、算法与程序的关系：（1）一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。（3）一个算法若用程序设计语言来描述，则它就是一个程序。 4、算法的时间复杂度的表示与计算（这个比较复杂，具体看算法本身，一般关心其循环的次数与N的关系、函数递归的计算）第二章线性表 1、线性表的特点：（1）存在唯一的第一个元素；（这一点决定了图不是线性表）（2）存在唯一的最后一个元素；（3）除第一个元素外，其它均只有一个前驱（这一点决定了树不是线性表）（4）除最后一个元素外，其它均只有一个后继。 2、线性表有两种表示：顺序表示（数组）、链式表示（链表），栈、队列都是线性表，他们都可以用数组、链表来实现。 3、顺序表示的线性表（数组）地址计算方法：（1）一维数组，设DataType a[N]的首地址为A0，每一个数据（DataType类型）占m个字节，则a[k]的地址为：A a[k]＝A0+m*k（其直接意义就是求在数据a[k]的前面有多少个元素，每个元素占m个字节）（2）多维数组，以三维数组为例，设DataType a[M][N][P]的首地址为A000，每一个数据（DataType 类型）占m个字节，则在元素a[i][j][k]的前面共有元素个数为：M*N*i+N*j+k，其其地址为： A a[i][j][k]＝A000+m*(M*N*i+N*j+k)； 4、线性表的归并排序：设两个线性表均已经按非递减顺序排好序，现要将两者合并为一个线性表，并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码，各元素的含义； 6、顺序线性表的初始化过程，可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法，注意其对于当原来的存储空间满了后，追加存储空间（就是每次增加若干个空间，一般为10个）的处理过程，可见算法2.4 9、顺序线性表的删除元素过程，可见算法2.5 10、顺序线性表的归并算法，可见算法2.7 11、链表的定义代码，各元素的含义，并能用图形象地表示出来，以利分析； 12、链表中元素的查找 13、链表的元素插入，算法与图解，可见算法2.9 14、链表的元素的删除，算法与图解，可见算法2.10 15、链表的创建过程，算法与图解，注意，链表有两种（向表头生长、向表尾生长，分别用在栈、队列中），但他们的区别就是在创建时就产生了，可见算法2.11 16、链表的归并算法，可见算法2.12 17、建议了解所谓的静态单链表（即用数组的形式来实现链表的操作），可见算法2.13 18、循环链表的定义，意义 19、循环链表的构造算法（其与单链表的区别是在创建时确定的）、图解

操作系统试卷(B卷)

山东科技大学2009—2010学年第二学期《操作系统》考试试卷（B卷）班级姓名学号一、判断题（回答“正确”或“错误”，并对错误命题简要说明理由）（每小题2分，共10分） 1、Wait、Signal操作中信号量的值永远代表着某类可用资源的数量。 2、死锁的形成只与资源分配策略有关，而与并发进程的执行速度无关。 3、进程A、B共享变量X，需要互斥执行；进程B、C共享变量Y，B、C也需要互斥执行。因此，进程A、C必须互斥执行。 4、请求分页系统中一条指令执行期间产生的缺页次数可能会超过4次。 5、最佳适应算法比首次适应算法具有更好的内存利用率。二、填空题（每空1分，共10分） 1、在多道批处理系统中，通常采用以下两种作业调度算法：（1）和（2）。 2、一个作业从进入系统到运行结束，一般要经历的阶段是提交，（3），（4），（5）。 3、分时系统的特点是：（6）、（7）、及时性和交互性。 4、系统中各进程对互斥资源操作的程序段必须互斥执行。我们把这种互斥执行的程序段称为（8）。 5、缓冲的实现方法有（9）和（10）两种。三、单项选择题（每小题2分，共30分） 1、响应比高者优先作业调度算法是以计算时间和______来考虑的。 A．输入时间B．完成时间C．周转时间D．等待时间

2、操作系统中______采用了以空间换时间的技术。 A．SPOOLing技术B．覆盖技术C．通道技术D．虚拟存储技术 3、虚存是______。 A．容量扩大了的内存B．提高运算速度的设备 C．实际不存在的存储器D．进程的地址空间及其内存扩大方法 4、在多道批处理系统中，用户的作业是由______组成的。 A．程序、数据、作业说明书B．程序、数据 C．程序、作业说明书D．程序 5、在可变式分配方案中，首先适应算法是将空白区在空白区表中按______次序排列。 A．地址递增8．地址递减C．容量递增D．容量递减 6、作业调度中的先来先服务算法是以______为出发点考虑的。 A．作业执行时间B．作业的周转时间 C．作业等待时间D．等待时间加运行时同 7、设m为同类资源数，n为系统中的并发进程数。当n个进程共享m个互斥资源时，每个进程的最大需求是w。下列情况下，系统会死锁的是______。 A．m=2, n=l, w=2 B．m=2, n=2, w=1 C．m=4, n=3, W=2 D．m=4, n=2, w=3 8、存储管理方案中，______可采用覆盖技术。 A．单一连续区B．可变分区C．段式D．段页式 9、分页式虚拟存储系统中，页面的大小与可能产生的缺页中断次数______。 A．成正比B．成反比C．无关D．成固定比值 10、从资源分配角度看，外设可分为若干种，其中不包括______。 A ．虚拟设备B．物理设备C．独占设备D．共享设备 11、采用树形目录结构可以______。 A．缩短查找文件的时间B．节省存储空间 C．减少文件的传送时间D．存储更多的文件 12、在进程基本调度状态转换时，会出现的情况是______。

山东科技大学毕业实习报告

毕业实习报告书系（部）机电工程系专业班级机制xxx班学生姓名xxx 完成日期200x年4月25日山东科技大学x x校区

一、毕业实习目的毕业实习是大学中最后一次理论与实践相结合的综合性实践锻炼，能让自己充分的将所学习的专业知识学以致用，从各方面锻炼提高自己的综合素质，毕业是我们机械设计制造及其自动化专业知识结构中不可缺少的组成部分。本次毕业实习的目的是为促进毕业设计的完成，根据学校安排组织进行实习参观，在实习过程中，使我们获得基本生产的感性认识，理论联系实际，扩大知识面，将所学的专业理论知识与生产实际相结合，从而进一步提高自己的理论基础和实践操作技能。通过本次实习进一步了解机械制造业的状况,以及一般零部件的生产加工，从而为毕业设计收集相关的实践技术资料及原始素材，并与现场技术人员进行技术咨询，为毕业设计做好充分的准备。二、实习任务这次毕业参观实习在指导老师的带领下我们分别参观了山东山工机械有限公司、山东省尤洛卡自动化装备股份有限公司。实习中学到了很多在课堂没学到的知识,让我们受益匪浅。根据本次毕业实习目的，我们将要完成： 1、掌握机械加工工艺方面的知识及方法； 2、了解切削刀具方面的知识，熟悉常用刀具的结构、选择、用途等； 3、熟悉机械加工生产工艺和方法及加工机床； 4、了解企业生产管理模式，学习先进的管理方式方法； 5、了解液压系统及控制方法，为毕业设计做好准备。三、实习内容在指导老师的带领下我们依次参观了山东山工机械有限公司、山东省尤洛卡自动化装备股份有限公司。下面自己对这次毕业实习内容总述如下：参观实习地点一：山东山工机械有限公司公司简介：山东山工机械有限公司坐落在古九州之一的山东省青州市，公司于2005年3月22日与世界500强之一的卡特比勒公司合资成立中美合资山东山工机械有限公司。属于国家大型一档企业，国家经贸委定点生产轮式装载机的重点

山东科技大学怎么样

山东科技大学怎么样山东科技大学，顶着种种压力和阻拦，毅然从泰安济南两校区分批搬迁至青岛，这可以称得上青岛发展史上重要的一笔，无论科技大学选择青岛，还是青岛选择科技大学，对两者都是重要的。山东科技大学决定在黄岛建新校区，从开始到现在依然是默默进行，可谓享受了难得的孤独，而当地政府却也很少表态，对其支持和关心的力度也不够，青岛市民对其也不甚了解，只认为是一般的职业技术教育学院而漠视它的存在，甚至很少有人知道这个学校还搬迁到了黄岛，这些都让科技大学的师生无比尴尬。在青岛市媒体宣传中也从不提山东科技大学的名字，只是反复强调青岛的四所本科院校，中国海洋大学,青岛大学,青岛科技大学,青岛理工大学.学校的师生的尴尬境地从他们的话中可见一斑：“也许青岛不稀罕我们这样的学校吧，人家需要的是北大，山大这样的高校引进，还是在济南和泰安好些。”“与一些青岛市民提起山东科技大学，会很诧异的看着你，说…你们是民办高校还是职业技术学院啊，没听过，只听过青岛科技大学。?我们直接和青岛科大合并算了，组建新的青岛科技大学。那样好多专家人才也不会走失了。?人才走失的原因，很多是因为搬迁到黄岛后位置过于偏僻，生活极其不方便导致。他们说与青岛科技大学合并的戏谑正是看中了青岛科技大学新校区的位置。目前因为山东科技大学搬迁而辞职的专家学者已经不少，他们有的是省部级重点实验室的相关带头人。不知道这是青岛市引进的尴尬，还是山东科技大学选择青岛的尴尬。现在诸如学校园区建设问题，教师宿舍楼问题等等，都存在着许多障碍，至于如何解决，那就看青岛市的政府了。这些大问题暂且不考虑，只一简单的解决科技大学到薛家岛直达公交车的问题，就很让科大师生困惑。科技大学师生若到开发区够物游玩，需要先乘10路区间车到港头陈，再转乘1，2路车。期间浪费的时间和金钱不用多说。为此学校每到周末，只能开几趟前往长江路立群的班车，解决他们够物难的问题。我与当地一个公交车司机说到这件事，人家还振振有辞说，你们反映到区政府也没用，区里能为了你们一个科大增改公交线路？说的让我无言以对。这可是一个综合大学啊，目前师生已经过万，暑假后全部搬迁来此，将是2万---三万人。满足这么多师生生活问题是小事吗？市区政府不能给他们解决吗？山东科技大学本身在夹缝中生存已经很为难了，当地政府的不重视更让他们寒心。当初，刚决定搬迁时，是动员泰安校区的，学生已经把行李都运到了黄岛，但是遇到了当地政府和上级政府的阻拦，只好作罢，临时动员济南校区学生搬迁。雄赳赳气昂昂的大队人马在无人喝彩声中孤独的搬迁到了荒凉的地方。学生失望，老师失望，本想融入青岛这个城市，但是却遭遇到许多意想不到的困难，最重要的是当地政府的认同与支持。学校师生期望能与驻青各高校互增交往，共同发展。[原文为山东科技大学学生在贴吧内所发] [评:在地理位置上,山东科技大学位于青岛下辖的黄岛区,但不在市区,与青岛市区隔着胶州弯,实属各种交通不便;即便现在开通了海底隧道,从山东科技大学坐车到通过隧道到市区,也需要两个小时,更不用说这条公交线路有多机,每年因为交通不便原因,很多大公司都不来山科进行校园招聘,就业机会比在市区的四所大学少了不少,而且假期各种大学生兼职活动比市区的大学就更少了,山科的招生办的老师也说过,向别人介绍说,山东科技大学在青岛时,心里感觉是在骗人,因为在这你看不到半点青岛的影子….]

2018考研计算机：数据结构重难点及复习建议

2018考研计算机：数据结构重难点及复习建议新东方在线推荐：一、重难点解析和复习建议数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。下面我们来解析一下知识点：线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二

山东科技大学青岛校区景观文化建设综述

山东科技大学青岛校区景观文化建设综述在山东省委、省政府的正确领导下，在省委高校工委和省教育厅的直接领导下，在社会各界人士与朋友的热切帮助下，山东科技大学自2001年6月启动青岛校区建设，至2006年10月校庆55周年之际基本建设完成，历时五年多的时间。当前，这所占地面积3000亩、建筑面积达140万平方米的现代化校园已成为学校办学的主体，成为在校35000名师生的学习、工作与生活之家；因其环境幽雅，景色秀丽、功能完善、人文荟萃且深蕴科大历史发展内涵，也成为广大师生的健康之家、欢乐之家、精神之家。兹趁省委高校工委组织评选高校校园文化建设优秀成果、以系统推进高校校园文化建设的契机，将我校在校园景观文化上的设计理念、工作思路和景观概况，向各位领导与专家作一简略的介绍。早在青岛校区建设之初，学校就提出了“总体规划，分期实施；高标准建设，可持续发展；五年初具规模，十年配套完善”的总体思路，制定了新校区建设的三个“三原则”，即：“高标准、高质量、高水平”；“大空间、大绿地、大水面”；“超前性、国际性、特色性”。本着这一总的建设思路与原则，联系科大历史发展的实际，我们在校园景观文化设计与建设上，具体做了如下的工作。一、“山、海、泉”交融的校园景观文化特质在整个青岛校区校园景观文化环境的培育上，我们根据校园南（教学办公区）与北（学生生活区）功能分区、以及教工住宅区相对独立的建筑布局特点，坚持对建筑群采用区域划分与系统命名的方

式，并结合科大近六十年来发展的历史实际以及在泰山、泉城、青岛三地办学的格局及现状，使学校校园景观在整体上呈现出“山、海、泉”交汇贯通的文化特质。具体而言：将南部教学办公三个区自西向东命名为“历山园”、“泰山园”、“珠山园”，各个园区的主要景观——广场，分别命名为历山广场、泰山广场、珠山广场。其中，泰山广场对应学校主大门——南大门，处于整个校园东西的中轴线上。取义“历山”以成其“勤”，取义珠山以成其“勇”，取义泰山以成其“高”。将北部学生生活三个区自西向东将其命名为“智泉园”、“悟泉园”、“慧泉园”，自古以来，中国人便以泉水作为智慧的象征，《周易·蒙卦》即以“山下出泉”为卦象，寄寓开启蒙昧之意。灵韵生动的济南七十二名泉，更是启迪我校师生智慧的永不枯竭的源泉。取义于此，希望广大莘莘学子在科大这片土地上体悟、探寻、开掘智慧之泉。将教工住宅区命名为“山海花园”，住宅区四个小区自东向西命名为“怡山园”、“乐水园”、“天和园”、“地祥园”。科大教工住宅区依傍笔架山北腰而建设，不少住在顶楼的教工用户，拉开东侧书房窗帘，即可远眺祖国黄海之蔚蓝海岸，以及北方最大的港湾码头——青岛港前湾港码头。依山傍海，仁者乐山，智者乐水，天人一体，万物祥和。这样的景观文化设计与命名，充分体现了当今社会以人为本、科学发展的精神。科大整个校园景观所体现出来的“山、海、泉”和谐一体的文化特质，是当今学校三地办学、协同发展、争创一流的一个缩影、一个

山东科技大学中外合作办学招生简章

山东科技大学年中外合作办学招生简章一、学校简介山东科技大学建校于年，现已发展成为一所工科优势突出，行业特色鲜明，工学、理学、管理学、文学、法学、经济学、艺术学等多学科相互渗透、协调发展的省属重点大学，是山东省重点建设的应用基础型人才培养特色名校，现有在校生余人，学校在青岛、泰安、济南三地办学，合作办学各专业设在济南校区。二、中外合作办学本科项目专业情况：序号专业名称层次合作学校教育部批号信息管理与信息系统本科美国克拉克大学2A 国际经济与贸易本科美国克拉克大学2A 澳大利亚塔斯马尼2A 电气工程及其自动化本科亚大学澳大利亚塔斯马尼 2A 通信工程本科亚大学金融学本科英国伍斯特大学2A 合作学校简介：美国克拉克大学建于年，是一所研究教案型大学，与哈佛大学、耶鲁大学同为著名的美国大学协会创始成员，据《美国新闻与世界报道》，其最新排名为全美第位。塔斯马尼亚大学始建于年，是英国高等教育评选出的全球强大学之一，是澳洲高等教育委员会评选的最有研究成就的澳洲前十所大学之一。伍斯特大学始建于年，是一所公立大学，为现任英国教育部部长的母校。伍斯特大学商学院是英国最受欢迎的商学院之一，在欧洲拥有良好的声誉，商学院课程都经过了英国管理准则协会（）、英国国家职业标准（）、英国管理标准中心（）的评估并获得了认证。培养模式：与美国克拉克大学合作办学：培养方案和培养计划由中美双方学校共同制定，学生在山东科技大学学习四年，美国克拉克大学派教师与山东科技大学教师共同承担课程的教案，学生完成培养计划规定的全部课程，成绩合格，获得山东科技大学普通高等教育本科毕业 1 / 3

考研数据结构图的必背算法及知识点

1.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置n(n-1)/ 2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢? 1.2 分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。图 G5无向连通图的生成树为(a)、(b)和(c)图所示： G5 G5的三棵生成树：

可以证明，对于有n 个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1 条边。 1.3最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。最小生成树的性质：假设N=(V,{ E}) 是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。 1.4 解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。他们都利用了最小生成树的性质 1.普里姆（Prim）算法：有线到点，适合边稠密。时间复杂度O(N^2)

大数据结构考研真题及其问题详解

一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（C ）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（C），它必须具备（B）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性【理工大学 1999 一、1（2分）【交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（ D ）【理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低4 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】 A．循环队列 B. 链表 C. 哈希表 D.栈

2017年山东科技大学研究生入学考试211翻译硕士英语考研真题

Part I Reading Comprehension(2*2.5=50 points) Derections: There are five passages in this section.Each passage is followed by some questions or unfinished statemens. For each of them, there are four choices marked A, B, C and D. Decide on the best choice. Passage 1 What might driving on an automated highway be like? The answer depends on what kind of system is ultimately adopted. Two distinct types are on the drawing board. The first is a special-purpose lane system, in which certain lanes are reserved for automated vehicles. The second is a mixed traffic system: fully automated vehicles would share the road with partially automated or manually driven cars. A special-purpose land system would require more extensive physical modifications to existing highways, but it promises the greatest gains in freeway capacity. Under either scheme, the driver would specify the desired destination, furnishing this information to a computer in the car at the beginning of the trip or perhaps just before reaching the automated highway. If a mixed traffic system was in place, automated driving could begin whenever the driver was on suitably equipped roads. If special-purpose lanes were available, the car could enter them and join existing traffic in two different ways. One method would use a special onramp. As the driver approached the point of entry for the highway, devices installed on the roadside would electronically check the vehicle to determine its destination and to ascertain that it had the proper automation equipment in good working order. Assuming it passed such tests, the driver would then be guided through a gate and toward an automated lane. In this case, the transition from manual to automated control would take place on the entrance ramp. An alternative technique could employ conventional lanes, which would be shared by automated and regular vehicles. The driver would steer onto the highway and move in normal fashion to a “transition” lane. The vehicle would then shift under computer control onto a lane reserved for automated traffic. (The limitation of these lanes to automated traffic would presumably be well respected, because all trespassers could be swiftly identified by authorities.) Either approach to joining a lane of automated traffic would

哈尔滨工程大学-考研数据结构真题-12_

哈尔滨工程大学-考研数据结构真题-12_ 哈尔滨工程大学试卷考试科目: 数据结构A 卷题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1、以下数据结构中，从逻辑结构看，（）和其他数据结构不同。 A．树B．字符串C．队列D．栈2、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 3、有六个元素A，B，C，D，E，F的顺序进栈，（）不是合法的出栈序列。 A．DEFCBA B．EDCBFA C．EFDBCA D．EDCFBA 4、字符串“ABCDEF”的子串有（）个。 A．19 B．20 C．21 D．22 5、顺序表中插入一个元素，需要平均移动的元素个数为（）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n-1 6、非空的单循环链表head 的尾结点（由P所指向）满足（）。 A．p-next ==NULL B．p==NULL C．p-next==head D．p==head 7、若A是中序线索二叉树中的一个结点，且A不为根，则A的前驱为( )。 A．A的右子树中最右的结点B．A的左子树中最左的结点C．A 的右子树中最左的结点D．A的左子树中最右的结点8、如某二叉树有30个叶子结点，有20个结点仅有一个孩子，则该二叉树中有两个孩子的结点数为（）。 A．29 B．30 C．31 D．19 9、二维数组A的每个元素是由8个字符组成的串，其行下标i=0,1,…,9,列下标j=1,2,…,10。若A按行序为主序存储，元素A的起始地址与当A按列序为主序存储时的元素（）的起始地址相同（设每个字符占一个字节）。 A．A B．A C．A D．A 10、图的深度优先遍历算法类似于二叉树的（）。

青岛青岛西海岸规划简介

对于青岛西海岸来说，2008年是一个特殊的年份，是一个发展史上的“分水岭”。之所以这样说，是因为经过这一年的发展、组合、沉淀和梳理，西海岸在发展变化过程中一些尚处在萌芽状态和动态变化中的不确定因素，正在走出朦胧而稳定成型，其代表青岛未来的禀赋，正在清楚地显现出来。青岛国资委在监管企业中开展了高层次人才岗位及项目需求征集工作。征集工作主要适应青岛市加快西海岸经济新区和蓝色硅谷建设，推进高端产业和战略性新兴产业快速发展和调整优化产业结构等重点工作的实际需求。重点引进能够促进企业自主创新、具有重大科研成果的高层次研究开发人才以及工作业绩突出、在业界有一定影响、熟悉相关产业领域和国际规则的高级经营管理人才、高级金融人才和高技能人才等。 2008年的西海岸，更精彩的不是速度的表现，而是结构和布局的明朗。一、港口城市的地位得到真正的确立据了解，到目前为止，青岛前湾新港区集装箱吞吐量，已经超过470万标准箱，全年超过500万标准箱已无疑义，由此跨过国际集装箱干线枢纽港的“临界点”，加上煤、油、矿，四大骨干货种已全部在西海岸港区吞吐，全港八成以上的吞吐量已由西海岸的新港区承担。正是由于前湾新港区的兴起，青岛港集装箱国际航线的密度以前所未有的速度增加，欧美干线比重不断加大，世界最新一代的集装箱船舶相继靠泊，由此，前湾新港区的发展前景，从今年起开始明朗化，2010 年和2020年集装箱吞吐量分别达到1200万和2100万标箱的发展预测，已跃然纸上，显示了一种发展的底气和自信。与其同步，航运服务业、物流业的规模迅速扩大，发展前景也因此而进一步明朗，全市航运业和物流业等港口产业集群的发展规划则因此而明确，提出了规模和档次要位居全国前列的目标。正是有了西海岸港航产业“垫底”，我们才敢于、才有条件提出这些目标。从这个意义上来说，西海岸正在逐渐地取代老城区的地位，这是2008年西海岸发展中一个最为显著的特点，它的意义，不仅是西海岸的航运业本身。一个吞吐能力只有两三千万吨的老港区，曾经支撑了青岛、山东乃至沿黄腹地几十年的经济腾飞，一个全新结构和全新功能的巨型新港区，在带动、辐射范围由过去的内陆腹地向东北亚更大范围拓展的同时，对西海岸新城区发展的“催化”作用，将是不言而喻的。青岛城市的国际化将因此真正成为现实，青岛三点布局、一线展开、组团发展的大都市战略目标，将因此而取得关键的突破。二、产业集群的优势基本确立在我市重点发展的家电电子、石油化工、汽车机车造船、新材料四大工业基地战略布局中，西海岸的优势在今年得到基本确立，几大制造业集群的框架，基本明朗。除了过去已在国内外形成明显竞争优势和品牌影响的家电电子产业集群以外，“中国石化青岛炼油化工公司”在2008年年末正式揭牌的动向，标志西海岸石化产业的框架由此确立，这一进程，为未来几年内青岛石化产业集群的规模和水平进入全国前列奠定了核心基础。就在海西湾造修船基地方兴未艾之际，又有总投资 17亿元的中海油海洋石油工程建设基地项目签约，这一海洋石油工程世界级项目的迅速跟进，并与世界级的造修船基地联手，形成有益的互

数据结构考研必背算法5星

数据结构考研必背算法5星文档说明：本文档是针对考研专业课《数据结构》所编写的，是对考研数据结构的核心算法进行总结，我们知道，不管是统考还是非统考，都会涉及至少10分的算法题（非统考至少25分），而这些题的答案都是在一些经典算法的思想上进行改进的，本文总结出必须要熟练掌握的算法，这些算法不管是考研初期还是冲刺，都应该高度重视，只要对这些代码进行熟练掌握，才能随机应变，希望对大家有所帮助；

线性表 1.逆转顺序表中的所有元素 void Reverse(int A[ ],int n){ int i,t; for(i=0;inext; while (P!=NULL){ if(p->data == X){ q->next = p->next; free(p); p=q->next; }else{ q = p; p = p->next; } } if(L->data == X){ q = L; L = L->next; free(q); } } 自我总结： 3.删除不带头结点单链表L中所有值为X的结点（递归） void Del_X(Linklist &L,Elemtype X){ LNode *p; if(L==NULL) return ; if(L->data == X){ P = L; L = L->next; free(p); Del_X(L,X); }else{ Del_X(L->next,X); } } 自我总结： 4.删除带头结点单链表L中所有值为X 的结点 void Del_X(Linklist &L,Elemtype X){ LNode *p = L->next,*pre = L, *q; while(P!=NULL){ if(P->data == X){ q = p; p=p->next; pre->next = p; free(q); }else{ pre = p; p=p->next; } } } 注：本算法是在无序单链表中删除满足某种条件的所有结点；如：若是要删除介于max 和min之间的所有结点，只需将if语句改为if(p->data>min&&p->data

你是我的眼山科大爱

你是我的眼科大教授叶蔚和她先生的感人爱情故事你的眼睛可以看不见道路，但不能停止前进的脚步；你可以摔倒一百次，但一定要在第一百零一次站起来…… ——主人公语 2009年7月3日，汤建泉出席了在人民大会堂举行的第四次全国“自强模范”表彰大会，当胡锦涛主席和温家宝总理先后握着他的手表示祝贺时，他忍不住流下了激动的泪水…… 十五年前，汤建泉在中国矿业大学读研究生，当他正准备赴日本读博士时，突患视神经萎缩，半年里双目几近失明。巨大的心理落差，让他痛不欲生，连身为中科院院士的父亲也无能为力。是她——叶蔚，用她执着坚定的爱，引领他一步步走向人生的巅峰，成为一个盲人企业家…… 失明破灭留学梦，爱情成了黑暗中最大亮光 1970年12月31日，汤建泉出生于泉城济南。父亲宋振骐和母亲祝侃都是山东科技大学的教授，因为宋振骐是宋家养子，所以到了汤建泉这一代，他将儿子改回了汤姓。高大、阳光、帅气的汤建泉于1988年以优异的成绩考入山东科技大学，并由人们向往的电气自动化专业主动要求转到艰苦危险的采矿专业。一入大学他就担任体育部长和足球队长，惹得众多女生对他倾心。但是，他对她们无动于衷，他心里只装着一个女孩，那就是高中同学叶蔚。叶蔚，与汤建泉一同考入山科大，只不过汤建泉在泰安的本校区，而她则在济南的分校区。因为她的美丽聪慧和汤建泉的潇洒睿智，一直是同学们心中的“金童玉女”。但因叶母严厉的家教，叶蔚不轻言感情，汤建泉也一直不敢向她表白。直到大二的一天，汤建泉约叶蔚去看电影，正走着，一辆摩托车从他们身后疾驰而来。眼看路边一个水坑的水就要溅到叶蔚的白裙子上，汤建泉急忙把叶蔚一拉，挡在了她的前面。结果，雨水裹着泥巴溅了汤建泉一身。叶蔚平日里本来也很欣赏汤建泉在足球场上的表现，不想生活中也这么细心，当即就向他投去感激的一瞥。汤建泉见状，猛地握紧了

考研《数据结构》复习知识点归纳

《数据结构》复习重点知识点归纳一．数据结构的章节结构及重点构成数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为： ·概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 ·线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题，如果有，也是与其它章节内容相结合。 ·栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 ·串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 ·多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 ·树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 ·图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 ·查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 ·排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。

文档之家